### Flipping and Proving

Years ago I came across a problem of flipping several items simultaneously:

There are 7 glasses on a table--all standing upside down. It is allowed to turn over any 4 of them in one move. Is it possible to reach a situation where all the glasses stand right side up.

The solution is rather obviously in the negative: at all times the number of the upright glasses is even and hence can't be 7.

At the time of my first encounter with the problem, I wrote a Java simulation that worked for numbers other than 7 and 4 and left a remark to the effect that the problem is solvable if and only if the number of glasses to be inverted on a single move is odd. I did not include a proof and do not remember now if I even had one.

More recently, while perusing a popular problem collection by C. W. Trigg, I chanced on a related problem (#22):

It is desired to invert the entire set of N upright cups by a series of moves in each of which N-1 cups are turned over. Show that this can always be down if N is even, but never if N is odd.

The proof is simple. Every cup is assigned a number - either +1 or -1. For N-1 even, the product of all the the numbers associated with all the cups is invariant under any move. Since, for N odd, the product of the all-upright configuration is 1 whilst the product of the inverted configuration is -1; if so, the problem is unsolvable in this case.

For the case where N is even, observe that there are N combinations of N-1 terms out of N and each term appears exactly in N-1 such combinations. Importantly, N-1 is an odd number. It follows that applying all N moves associated with with N such combinations, we shall turn each of the cups exactly N-1 times, thus ending up with all the cups inverted the wrong side up.

This problem fits nicely into the generalization but the solution does not appear to be easily adaptable to a more general case. The upside of the situation is that I recovered a simply looking, nice problem with unknown solution. The downside was that my old writeup seemed to intimate otherwise. I decided it was the right time to patch up my old claim.

Thus the problem is this. There are N items that may be in one of two positions, say, *up* and *down*. A move consists in flipping M items simultaneously, M < N. Originally, all the items are in the up position. Is it possible with a series of moves and, if so when and how, bring all the items to the down position? Let's call this a

A couple of rather obvious observation are in order. If

Second, we may assume that M < N < 2M. The first inequality is a natural requirement: one can't flip more than a present number of items. The second inequality is a tidy-up condition. If N is too large, it is always possible to keep flipping groups of M distinct items until the number of the up items goes below 2M, forgetting from then on about the items that have just been turned over.

### Proposition

The

### References

- D. Fomin, S. Genkin, I. Itenberg,
*Mathematical Circles (Russian Experience)*, AMS, 1996 - C. W. Trigg,
*Mathematical Quickies*, Dover, 1985, #22.

### Proposition

The

### Proof

If N is odd and M is even then the number of down items is always even and could not equal an odd N.

Let {U, D}, U + D = N, denote a position with U up and D down items. Let _{a, b},_{a, b}

_{a, b}{U, D} = {U - a + b, D + a - b}.

In what follows we shall asume that

Suppose first that N = 2n + 1 and M = 2m + 1. Then the following sequence of moves solves the problem:

_{2m + 1, 0}, T

_{n - m, 3m - n + 1}, T

_{2m + 1, 0}.

Starting with the configuration {N, 0} these moves produce successively the following configurations:

For the second move to be applicable we need the inequality

Next assume N = 2n and M = 2m. Apply two moves T_{M, 0} and then T_{1, M-1} that would result successively in the positions

Disregarding the two down items, we have a problem with smaller (but still even) number of up items. If

The remaining case where N = 2n and M = 2m + 1 is more complex. Before we proceed, let's record a couple of obvious properties of the T operators.

### Lemma 1

- T
_{a, b}T_{b, a}= 1, the identity transform. - If T
_{a, b}{U_{1}, D_{1}} = {U_{2}, D_{2}} then T_{a, b}{D_{2}, U_{2}} = {D_{1}, U_{1}}.

Also, for convenience, let R = T_{m, m+1} and S = T_{m+1, m}.

R{U, D} = {U + 1, D - 1} and S{U, D} = {U - 1, D + 1}.

In Cartesian coordinates, for a fixed N, all possible configurations lie on the diagonal U + D = N (shown for N = 14):

Under our assumptions, M < N < 2M, the first move _{M, 0}{N, 0} = {N - M, M}

If it is, one application of R will move the configuration along the diagonal one step closer to the midpoint. This happens, for example, with

If it is not, as in case N = 14 and M = 11, the operator T_{U, M-U} will shorten the distance to the midpoint.

For M = 11, T_{3, 8}{3, 11} = {8, 6}. Let's see how it works in general. Assume

T_{U, M-U}{U, D} = {M - U, D - M + 2U}.

What can be said about this move? First of all, it moves

We could similarly handle the case where U > n and

Of course it is not necessary to use the one-step operators R and S; the sequence of moves may be shortened if several such moves are combined into one. I have only introduced them to make is clear that it is always possible to land on the midpoint: there is no way to pass it with 1 step moves. Let's have a couple of examples.

#### N = 20, M = 13

We only need 4 moves: T_{13, 0}, T_{5, 8}, T_{5, 8}, T_{13, 0}. Here are the consecutive configurations:

#### N = 20, M = 17

Now we need 8 eight moves: T_{17, 0}, T_{3, 14}, T_{11, 6}, T_{8, 9}, T_{8, 9}, T_{11, 6}, _{3, 14},_{17, 0}.

Lovely!

April 1st, 2011 at 6:29 amI think I have an alternative proof for the N even, M odd case.

With M < N < 2M, look at {N, N-M}. This is again an N even, M odd case. All N even, M odd solutions will have an even number of steps. If we have a solution for {N, N-M}, we also have a solution for {N, M} by flipping those elements in {N, M} we didn't flip in the {N, N-M} solution because that's equivalent to performing the {N, N-M} solution plus flipping everything on every move, which results in the same position on all even moves.

{N, N-M} can of course be reduced to a smaller position by subtracting N-M a number of times from N, leaving either a strictly smaller (even, odd) problem or an (odd, odd) problem.

Proof by induction without an initial case because every (odd, even) position will at some point be reduced to an (odd, odd) problem.