6. Humpty buys a box of 15 eggs, with 3 rows and 5 columns. Each meal he removes one egg to cook and eat. If necessary, he moves one or more eggs in the box so that between meals there are always two lines of reflective symmetry. What is the smallest total number of extra egg moves he can make while he empties the box?
Note: You must carefully justify that your answer is minimal; that it is impossible to make fewer extra egg moves while emptying the box.
SolUTION
Label the 15 egg spaces as in the diagram on the right.
First, note that, if there is currently an odd number of eggs in the box, there must be one in space $\mathrm{H}$, since this is the only space which does not reflect onto (at least) one other space.
Also note that, every time Humpty removes an egg, the number of eggs in the box changes from even to odd (or vice versa).

So if the box has an even number of eggs in it, Humpty must, after removing an egg, move an egg into the central space to retain symmetry.

Humpty removes an egg from the box when it contains an even number of eggs seven times, so there must be at least seven egg moves.
Now consider eggs in the four corner spaces (A, E, $\mathrm{K}$ and $\mathrm{O}$ ). If one of these spaces contains an egg, all four must (since they reflect onto each other), and if one of them is empty, all four must be.

So when Humpty first removes an egg from one of these spaces and does not move an egg into the space he has just created (which must occur at some point because he is emptying the box), he must move the eggs out of the remaining three spaces, which requires three egg moves (of course, one of these moves may be moving an egg into space $\mathrm{H}$ ).

An identical argument can be applied to the four spaces B, D, L and N.
So we know that there must be at least 11 egg moves: three out of $\mathrm{A}, \mathrm{E}, \mathrm{K}$ and $\mathrm{O}$, three out of $\mathrm{B}, \mathrm{D}, \mathrm{L}$ and $\mathrm{N}$ and at least five more into $\mathrm{H}$ (assuming two of the seven moves required into $\mathrm{H}$ were done when moving the sets of three eggs).

It turns out that it is possible to empty the box while making only 11 egg moves (for example see below), so we know 11 moves must be the minimum.
\begin{tabular}{cccc} 
step & remove from & move(s) & total moves \\
\hline 1 & H & - & \\
2 & G & I to H & 1 \\
3 & H & - & 1 \\
4 & F & J to H & 2 \\
5 & H & - & 2 \\
6 & A & E to H, K to G, O to 1 & 5 \\
7 & H & - & 5 \\
step & remove from & move (s) & total moves \\
\hline 8 & G & I to H & 6 \\
9 & H & - & 6 \\
10 & B & D to H, L to G, N to I & 9 \\
11 & H & - & 9 \\
12 & G & - & 10 \\
13 & H & M to H & 10 \\
14 & C & - & 11 \\
15 & H & & 11
\end{tabular}

A graphical representation of this is shown below.
an egg
an empty space
O an egg which has just been moved elsewhere
$\otimes$ an egg which has just been removed from the box