CTK Insights

Tweet

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 P(N, M) problem.

A couple of rather obvious observation are in order. If P(N, M) is solvable then so is P(qN, qM), for any positive integer q. For a long time I thought that two problems P(N, M) and P(N/G, M/G) are equivalent where G = gcd(N, M), but they are not. I was disabused by the Zbarsky family who pointed out that P(6, 4) is solvable (and in only three steps at that) while P(3, 2) is not.

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.

Proof →

References

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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 T_{a, b}, a + b = M, designate a move which inverts a up and b down items. For T_{a, b} to be applicable to {U, D} one needs a ≤ U and b ≤ D. Assuming that,

In what follows we shall asume that M < N < 2M. The first inequality is necessary to make the problem meaningful. The second inequality is attained by repeatedly subtracting M from N, if necessary.

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

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

For the second move to be applicable we need the inequality 2m + 1 > 3m - n + 1 to hold. This inequality is equivalent to n > m, which is a consequence of N > M.

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 M = N - 2, the problem is solved immediately. Otherwise, the number of up items may be again reduced by 2, and so on.

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

1. T_{a, b}T_{b, a} = 1, the identity transform.
2. If T_{a, b}{U₁, D₁} = {U₂, D₂} then T_{a, b}{D₂, U₂} = {D₁, U₁}.

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 T_{M, 0}{N, 0} = {N - M, M} always overshoots the midpoint {n, n} because M > n. There are now two possibilities: operator R may or may not be applicable to the new position {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 N = 14 and M = 9. The step can be repeated until the midpoint is reached.

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 U < n < D and U < m. Then

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

What can be said about this move? First of all, it moves {U, D} in the direction of {n, n} because U < M - U, or, equivalently, U ≤ m. But we assumed that U < m. It follows that, if M - U < n, then {M - U, D - M + 2U} is indeed closer to {n, n} than {U, D}. On the other hand, if the move overshoots {n, n}, making M - U > n, then still
(M - U} - n < n - U for it is equivalent to M < 2n = N.

We could similarly handle the case where U > n and D < m. One way or another it is possible to move nearer to the midpoint {n, n}. We shall continue this process until it becomes possible to apply one of the operators R or S to move 1 step at a time to make sure that eventually we'll get to the midpoint {n, n}. Once there, we first record the sequence of moves from the initial point {N, 0} and then apply them in reverse order, thus forming a palindromic sequence of moves from {N, 0} to {0, N}. (The palindromic sequence will work due to the second property in Lemma.)

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: {20, 0}, {7, 13}, {10, 10}, {13, 7}, {0, 20}.

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}, T_{3, 14}, T_{17, 0}. These generate a sequence of configurations: {20, 0}, {3, 17}, {14, 6}, {9, 11}, {10, 10}, {11, 9}, {6, 14}, {17, 3}, {0, 20}.