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 G = gcd(N, M), then P(N, M) is solvable if and only if P(N/G, M/G) is solvable, meaning that it is sufficient to consider only the problem for N and M mutually prime.
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
Assume, N and M are mutually prime and M < N < 2M. Then the P(N, M) problem is solvable if and only if M is odd. Furthermore, if N is also odd, the problem is always solvable in three moves.
Proof →
References
- D. Fomin, S. Genkin, I. Itenberg, Mathematical Circles (Russian Experience), AMS, 1996
- C. W. Trigg, Mathematical Quickies, Dover, 1985, #22.
Proposition
Assume, N and M are mutually prime and M < N < 2M. Then the P(N, M) problem is solvable if and only if M is odd. Furthermore, if N is also odd, the problem is always solvable in three moves.
Proof
If M is even then, since gcd(N, M) = 1, N is odd. However the number of down items is always even.
Let {U, D}, U + D = N, denote a position with U up and D down items. Let Ta, b, a + b = M, designate a move which inverts a up and b down items. For Ta, b to be applicable to {U, D} one needs a ≤ U and b ≤ D. Assuming that,
Ta, b {U, D} = {U – a + b, D + a – b}.
Suppose first that N = 2n + 1 and M = 2m + 1. Then the following sequence of moves solves the problem:
T2m + 1, 0, Tn – m, 3m – n + 1, T2m + 1, 0.
Starting with the configuration {N, 0} these moves produce successively the following configurations:
{2n – 2m, 2m + 1}, {2m + 1, 2n – 2m}, {0, 2n + 1}.
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.
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
- Ta, bTb, a = 1, the identity transform.
- If Ta, b{U1, D1} = {U2, D2} then Ta, b{D2, U2} = {D1, U1}.
Also, for convenience, let R = Tm, m+1 and S = Tm+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 TM, 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 TU, M-U will shorten the distance to the midpoint.
For M = 11, T3, 8{3, 11} = {8, 6}. Let’s see how it works in general. Assume U < n < D and U < m. Then
TU, 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: T13, 0, T5, 8, T5, 8, T13, 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: T17, 0, T3, 14, T11, 6, T8, 9, T8, 9, T11, 6, T3, 14, T17, 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}.