automatically:
(1) Invert any diagonal pair.
(2) Invert any adjacent pair.
(3) Invert any diagonal pair.
(4) Invert any single glass.
(5) Invert any diagonal pair.
(6) Invert any adjacent pair.
(7) Invert any diagonal pair.
The Problem Generalized
In the end, a table with two pockets presents a trivial problem, one with three pockets an easy problem and one with four pockets a rather more subtle problem. What about a table with five pockets? The answer is that the situation changes radically since, with a five-sided (or greater) table, there is no algorithm which will guarantee that the bell will ring in a finite number of moves. (In chapter 6 we will meet a second situation in which matters change radically at the fifth level, a phenomenon which is far from uncommon in mathematics.)
The March 1979 Scientific American column provided the solution to the original problem. Evidently, mathematicians had been active between the February and March issues, since the March column also mentions two generalizations suggested by Ronald L. Graham and Persi Diaconis:
(1) Can the bell be made to ring if the player is replaced by an ‘octopus’ with k hands sitting at a table with n sides?
(2) Can the bell be made to ring if the glasses are replaced by objects which can occupy more than two positions?
They provided a partial solution to the first question, showing that with a table having a prime number of sides n the minimum number of hands needed to guarantee the bell ringing is n- 1 and that the minimum number is bounded above by n- 2 otherwise.Of course, their result decides the case for the five-sided table mentioned above; there, k = 2 and n = 5.
Subsequently, William T. Laaser and Lyle Ramshaw, both of Stanford, solved the first generalization completely. Their result is that the minimum number of hands, k , required to ensure that the bell will ring for an n -sided table is k = ( 1 −1 /p)n , where p is the largest prime factor of n (a formula conjectured by James Boyce). Of course, this reduces to the above result in the case where n is prime (and therefore n = p ).
The full exposition of the Laaser–Ramshaw result (Probing the rotating table, Mathematical Gardner , 1981, 288–307) is too long for inclusion here but we will consider the first part of it, which establishes that (1 − 1 /p)n is a lower bound on k ; that is, if k < ( 1 − 1 /p)n , it is impossible to guarantee that the bell will ring.
First we will establish a preliminary result.
Consider the set of integers { 0,1,2, …,p- 1} reduced modulo the prime p . If we start at any position r and move through the integers in steps of 1 (reducing modulo p ), it is evident that we will visit each integer before we reach our starting point again. Now suppose that we move in steps of size j (where 2 ≤ j ≤ p - 1). We will generate the set of integers {r + αj : 0 ≤ α ≤ p - 1}, modulo p , as we move through the integers and if two of these numbers are equal it must be that r + αj = r + ßj , modulo p , and this means that (ß - α)j is divisible by p . Since p is prime and cannot possibly divide j , it must be that p divides ß - α and this makes ß = α + Np . In short, any walk around the integers will visit each one of them once before returning to the starting point.
With that in place consider the Laaser–Ramshaw result in two parts:
(1) Suppose that n = p is prime. If the player has fewer than p - 1 hands, then he has no winning strategy.
If the player has fewer than p - 1 hands, any probe of the table will leave at least two pockets untested; call these pockets gaps and suppose that two of them are a distance j apart. Ourpreliminary argument shows that, if we start at any pocket and walk around the table in steps of length j , we will visit every pocket before returning to the starting point. Since the pockets must contain glasses of both orientations, it must be that our journey will at some stage cause us to step from a glass of one
(1) Invert any diagonal pair.
(2) Invert any adjacent pair.
(3) Invert any diagonal pair.
(4) Invert any single glass.
(5) Invert any diagonal pair.
(6) Invert any adjacent pair.
(7) Invert any diagonal pair.
The Problem Generalized
In the end, a table with two pockets presents a trivial problem, one with three pockets an easy problem and one with four pockets a rather more subtle problem. What about a table with five pockets? The answer is that the situation changes radically since, with a five-sided (or greater) table, there is no algorithm which will guarantee that the bell will ring in a finite number of moves. (In chapter 6 we will meet a second situation in which matters change radically at the fifth level, a phenomenon which is far from uncommon in mathematics.)
The March 1979 Scientific American column provided the solution to the original problem. Evidently, mathematicians had been active between the February and March issues, since the March column also mentions two generalizations suggested by Ronald L. Graham and Persi Diaconis:
(1) Can the bell be made to ring if the player is replaced by an ‘octopus’ with k hands sitting at a table with n sides?
(2) Can the bell be made to ring if the glasses are replaced by objects which can occupy more than two positions?
They provided a partial solution to the first question, showing that with a table having a prime number of sides n the minimum number of hands needed to guarantee the bell ringing is n- 1 and that the minimum number is bounded above by n- 2 otherwise.Of course, their result decides the case for the five-sided table mentioned above; there, k = 2 and n = 5.
Subsequently, William T. Laaser and Lyle Ramshaw, both of Stanford, solved the first generalization completely. Their result is that the minimum number of hands, k , required to ensure that the bell will ring for an n -sided table is k = ( 1 −1 /p)n , where p is the largest prime factor of n (a formula conjectured by James Boyce). Of course, this reduces to the above result in the case where n is prime (and therefore n = p ).
The full exposition of the Laaser–Ramshaw result (Probing the rotating table, Mathematical Gardner , 1981, 288–307) is too long for inclusion here but we will consider the first part of it, which establishes that (1 − 1 /p)n is a lower bound on k ; that is, if k < ( 1 − 1 /p)n , it is impossible to guarantee that the bell will ring.
First we will establish a preliminary result.
Consider the set of integers { 0,1,2, …,p- 1} reduced modulo the prime p . If we start at any position r and move through the integers in steps of 1 (reducing modulo p ), it is evident that we will visit each integer before we reach our starting point again. Now suppose that we move in steps of size j (where 2 ≤ j ≤ p - 1). We will generate the set of integers {r + αj : 0 ≤ α ≤ p - 1}, modulo p , as we move through the integers and if two of these numbers are equal it must be that r + αj = r + ßj , modulo p , and this means that (ß - α)j is divisible by p . Since p is prime and cannot possibly divide j , it must be that p divides ß - α and this makes ß = α + Np . In short, any walk around the integers will visit each one of them once before returning to the starting point.
With that in place consider the Laaser–Ramshaw result in two parts:
(1) Suppose that n = p is prime. If the player has fewer than p - 1 hands, then he has no winning strategy.
If the player has fewer than p - 1 hands, any probe of the table will leave at least two pockets untested; call these pockets gaps and suppose that two of them are a distance j apart. Ourpreliminary argument shows that, if we start at any pocket and walk around the table in steps of length j , we will visit every pocket before returning to the starting point. Since the pockets must contain glasses of both orientations, it must be that our journey will at some stage cause us to step from a glass of one
Similar Books
Free Lunch
David Cay Johnston
The Empire (The Lover's Opalus)
Grayson Reyes-Cole
Under His Command
Annabel Wolfe
The Mating Intent-mobi
Bonnie Vanak
Mourning Glory
Warren Adler
Wolf's Desire
Ambrielle Kirk
Abigail's Story
Ann Burton
Not Dead in the Heart of Dixie
R Kralik
Shoeshine Girl
Clyde Robert Bulla
Breaking Point
C. J. Box