orientation to one of another, precisely a distance j apart. If the table happens to align itself so that the gaps j apart in the probe pattern match the glasses of different orientation, the bell cannot ring. The procedure can be repeated indefinitely, which shows that no ringing of the bell can be guaranteed.
Figure 4.4. A table and its sub-tables
(2) Now suppose that n ≥ 2 is composite and let p be its largest prime factor. If the player has fewer than (1−1 /p)n hands, then he has no winning strategy.
Write n = pl . The argument essentially reduces this case to the previous one. Rather than consider the table cyclically, picture it as l copies of a sub-table of p sides. For example, if n = 6 = 2 × 3, we can think of the hexagonal table in figure 4.4 (a) as the superposition of the two triangular sub-tables in figure 4.4 (b).
Since the player has fewer than
hands at any probe, at least one of the sub-tables will have at least two gaps when the full table is probed, since if each had atmost one gap, there would have to be at least l×(p- 1 ) = (p- 1 )l hands. Suppose that on a sub-table the two gaps are a distance j apart.
Table 4.1. Minimum number of hands, N , needed for n -sided tables.
There must exist a sub-table whose pockets contain glasses of both orientations. Take a walk around it as before in steps of length j and, as before, every pocket will be visited before returning to the starting place and this means that there will be two pockets, a distance j apart, one of which contains an ‘up’ glass and the other a ‘down’ glass. If the table happens to align itself so that a probe’s sub-table with two gaps is aligned with the sub-table with the glasses of both orientations and with the gaps and the up and down glasses superimposed, the bell cannot ring. This can continue indefinitely, denying any possibility of an assured ringing of the bell.
We should note in passing that (for n > 2), since
Figure 4.5.
if p = 2, then n must be a power of 2, otherwise p > 2 and so p - 1 is even; either way (rather strangely), (1 − 1 /p)n is even.
We will finish with table 4.1 , which gives the values of N = ( 1−1 /p)n for the first few values of n , and figure 4.5 , which graphs the values for n up to 100. The trend is clear and reasonable, but regularly upset (most particularly) when n is a power of 2, in which case p = 2 and
In fact, it is evident that the following bounds exist for N
with the lower limit achieved when N is a power of 2 and the upper limit when N is prime. This is indicated by the linesand y = n - 1, which have been added to the plot.
Chapter 5
DERANGEMENTS
I think it is said that Gauss had ten different proofs for the law of quadratic reciprocity. Any good theorem should have several proofs, the more the better. For two reasons: usually, different proofs have different strengths and weaknesses, and they generalise in different directions: they are not just repetitions of each other.
Sir Michael Atiyah
We shall look at a famous old problem in three different, enlightening ways and then consider three surprising facts originating from it.
An Old Card Game
The French word for 13, trieze , was also the name of a commonly played card game of the eighteenth century. It could be considered as a simple patience (or solitaire) game but in its classic form it was played by several individuals, and commonly for money. We will leave it to the man who is credited with its first analysis to explain matters:
The players draw first for who will have the hand. We suppose that this is Pierre, & that the number of the playersis as such as one would wish. Pierre having an entire deck composed of fifty-two cards shuffled at discretion, draws them one after the other, naming & pronouncing one when he draws the first card, two when he draws the second, three when he draws the third, & thus in sequence up to the thirteenth which is a King. Now if in all this sequence of cards he has drawn none of
Figure 4.4. A table and its sub-tables
(2) Now suppose that n ≥ 2 is composite and let p be its largest prime factor. If the player has fewer than (1−1 /p)n hands, then he has no winning strategy.
Write n = pl . The argument essentially reduces this case to the previous one. Rather than consider the table cyclically, picture it as l copies of a sub-table of p sides. For example, if n = 6 = 2 × 3, we can think of the hexagonal table in figure 4.4 (a) as the superposition of the two triangular sub-tables in figure 4.4 (b).
Since the player has fewer than
hands at any probe, at least one of the sub-tables will have at least two gaps when the full table is probed, since if each had atmost one gap, there would have to be at least l×(p- 1 ) = (p- 1 )l hands. Suppose that on a sub-table the two gaps are a distance j apart.
Table 4.1. Minimum number of hands, N , needed for n -sided tables.
There must exist a sub-table whose pockets contain glasses of both orientations. Take a walk around it as before in steps of length j and, as before, every pocket will be visited before returning to the starting place and this means that there will be two pockets, a distance j apart, one of which contains an ‘up’ glass and the other a ‘down’ glass. If the table happens to align itself so that a probe’s sub-table with two gaps is aligned with the sub-table with the glasses of both orientations and with the gaps and the up and down glasses superimposed, the bell cannot ring. This can continue indefinitely, denying any possibility of an assured ringing of the bell.
We should note in passing that (for n > 2), since
Figure 4.5.
if p = 2, then n must be a power of 2, otherwise p > 2 and so p - 1 is even; either way (rather strangely), (1 − 1 /p)n is even.
We will finish with table 4.1 , which gives the values of N = ( 1−1 /p)n for the first few values of n , and figure 4.5 , which graphs the values for n up to 100. The trend is clear and reasonable, but regularly upset (most particularly) when n is a power of 2, in which case p = 2 and
In fact, it is evident that the following bounds exist for N
with the lower limit achieved when N is a power of 2 and the upper limit when N is prime. This is indicated by the linesand y = n - 1, which have been added to the plot.
Chapter 5
DERANGEMENTS
I think it is said that Gauss had ten different proofs for the law of quadratic reciprocity. Any good theorem should have several proofs, the more the better. For two reasons: usually, different proofs have different strengths and weaknesses, and they generalise in different directions: they are not just repetitions of each other.
Sir Michael Atiyah
We shall look at a famous old problem in three different, enlightening ways and then consider three surprising facts originating from it.
An Old Card Game
The French word for 13, trieze , was also the name of a commonly played card game of the eighteenth century. It could be considered as a simple patience (or solitaire) game but in its classic form it was played by several individuals, and commonly for money. We will leave it to the man who is credited with its first analysis to explain matters:
The players draw first for who will have the hand. We suppose that this is Pierre, & that the number of the playersis as such as one would wish. Pierre having an entire deck composed of fifty-two cards shuffled at discretion, draws them one after the other, naming & pronouncing one when he draws the first card, two when he draws the second, three when he draws the third, & thus in sequence up to the thirteenth which is a King. Now if in all this sequence of cards he has drawn none of
Similar Books
A Knight With Grace: Book 1 of the Assassin Knights Series
Laurel O'Donnell
The Empress' Rapture
Trinity Blacio
Lucky Charm
Valerie Douglas
Balancing Act
Joanna Trollope
Betrayals
Sharon Green
On the Divinity of Second Chances
Kaya McLaren
The Immaculate
Mark Morris
The Betrayers
David Bezmozgis
Evan Arden 01 Otherwise Alone
Shay Savage