Mathematical Recreations and Essays · W. W. Rouse Ball
I propose to discuss in this chapter the mathematical theory of certain of the more common mathematical amusements and games. Some of these might have been treated in the first two chapters, but, since most of them involve mixed geometry and algebra, it is rather more convenient to deal with them apart from the problems and puzzles which have been described already. This division, however, is by no means well defined, and the arrangement is based on convenience rather than on any logical distinction.
The majority of the questions here enumerated have no connection one with another, and I jot them down almost at random.
I shall discuss in succession the Fifteen Puzzle, the Tower of Hanoï, Chinese Rings, the Eight Queens Problem, the Fifteen School-Girls Problem, and some miscellaneous Problems connected with a pack of cards.
[The Fifteen Puzzle]The Fifteen Puzzle (There are two articles on the subject in the American Journal of Mathematics 1879, vol. ii, by Professors Woolsey Johnson and Story; but the whole theory is deducible immediately from the proposition I give above in the text.) Some years ago the so-called fifteen puzzle was on sale in all toy-shops. It consists of a shallow wooden box--one side being marked as the top--in the form of a square, and contains fifteen square blocks or counters
numbered 1 , 2 , 3... up to 15. The box will hold just sixteen such counters, and, as it contains only fifteen, they can be moved about in the box relatively to one another. Initially they are put in the box in any order, but leaving the sixteenth cell or small square empty; the puzzle is to move them so that finally they occupy the position shown in the first of the annexed figures.
We may represent the various stages in the game by supposing that the blank space, occupying the sixteenth cell, is moved over the board, ending finally where it started.
The route pursued by the blank space may consist partly of tracks followed and again retraced, which have no effect on the arrangement, and partly of closed paths travelled round, which necessarily are cyclical permutations of an odd number of counters. No other motion is possible.
Now a cyclical permutation of n letters is equivalent to n-1 simple interchanges; accordingly an odd cyclical permutation is equivalent to an even number of simple interchanges. Hence, if we move the counters so as to bring the blank space back into the sixteenth cell, the new order must differ from the initial order by an even number of simple interchanges. If
therefore the order we want to get can be obtained from this initial order only by an odd number of interchanges, the problem is incapable of solution; if it can be obtained by an even number, the problem is possible.
Thus the order in the second of the diagrams given illus:121
is deducible from that in the first diagram by six interchanges; namely, by interchanging the counters 1 and 2 , 3 and 4 , 5 and 6 , 7 and 8 , 9 and 10 , 11 and 12. Hence the one can be deduced from the other by moving the counters about in the box.
If however in the second diagram the order of the last three counters had been 13 , 15 , 14 , then it would have required seven interchanges of counters to bring them into the order given in the first diagram. Hence in this case the problem would be insoluble.
4pt The easiest way of finding the number of simple interchanges necessary in order to obtain one given arrangement from another is to make the transformation by a series of cycles. For example, suppose that we take the counters in the box in any definite order, such as taking the successive rows from left to right, and suppose the original order and the final order to be respectively
We can deduce the second order from the first by 12 simple interchanges. The simplest way of seeing this is to arrange the process in three separate cycles as follows:--
Thus, if in the first row of figures 11 is substituted for 1 , then 8 for 11 , then 1 for 8 , we have made a cyclical interchange of 3 numbers, which is equivalent to 2 simple interchanges (namely, interchanging 1 and 11 , and then 1 and 8 ). Thus the whole process is equivalent to one cyclical interchange of 3 numbers, another of 11 numbers, and another of 1 number. Hence it is
equivalent to (2 + 10 + 0) simple interchanges. This is an even number, and thus one of these orders can be deduced from the other by moving the counters about in the box.
It is obvious that, if the initial order is the same as the required order except that the last three counters are in the order 15 , 14 , 13 , it would require one interchange to put them in the order 13 , 14 , 15 ; hence the problem is insoluble.
If however the box is turned through a right angle, so as to make AD the top, this rotation will be equivalent to 13 simple interchanges. For, if we keep the sixteenth square always blank, then such a rotation would change any order such as
which is equivalent to 13 simple interchanges. Hence it will change the arrangement from one in which a solution is impossible to one where it is possible, and vice versa.
Again, even if the initial order is one which makes a solution impossible, yet if the first cell and not the last is left blank it will be possible to arrange the fifteen counters in their natural order. For, if we represent the blank cell by b , this will be equivalent to changing the order
this is a cyclical interchange of 16 things and therefore is equivalent to 15 simple interchanges. Hence it will change the arrangement from one in which a solution is impossible to one where it is possible, and vice versa.
It is evident that the above principles are applicable equally to a rectangular box containing mn cells or spaces and mn-1 counters which are numbered. Of course m may be equal to n. If such a box is turned through a right angle, and m and n are both even, it will be equivalent to mn-3 simple interchanges--and thus will change an impossible position to a possible one, and vice versa--but unless both m and n are
even the rotation is equivalent to only an even number of interchanges. Similarly, if either m or n is even, and it is impossible to solve the problem when the last cell is left blank, then it will be possible to solve it by leaving the first cell blank.
The problem may be made more difficult by limiting the possible movements by fixing bars inside the box which will prevent the movement of a counter transverse to their directions. We can conceive also of a similar cubical puzzle, but we could not work it practically except by sections.
I may mention next the ingenious
puzzle known as the Tower of Hanoï. It was brought out in 1883 by M. Claus (Lucas).
It consists of three pegs fastened to a stand, and of eight circular discs of wood or cardboard each of which has a hole in the middle so that a peg can be put through it. These discs are of different radii, and initially they are placed all on one peg, so that the biggest is at the bottom, and the radii of the successive discs decrease as we ascend: thus the smallest disc is at the top. This arrangement is called the Tower. The problem is to shift the discs from one peg to another in such a way that a disc shall never rest on one smaller than itself, and finally to transfer the tower ( all the discs in their proper order) from the peg on which they initially rested to one of the other pegs.
The method of effecting this is as follows. (i) If initially there are n discs on the peg A , the first operation is to transfer gradually the top n-1 discs from the peg A to the peg B , leaving the peg C vacant: suppose that this requires x separate transfers. (ii) Next, move the bottom disc to the peg C. (iii) Then, reversing the first process, transfer gradually the n-1 discs from B to C , which will necessitate x transfers. Hence, if it requires x transfers of simple discs to move a tower of n-1 discs, then it will require 2x +1 separate transfers of single discs to move a tower of n discs. Now
with 2 discs it requires 3 transfers, 2^2-1 transfers; hence with 3 discs the number of transfers required will be 2 (2^2-1) + 1 , that is, 2^3-1. Proceeding in this way we see that with a tower of n discs it will require 2^n-1 transfers of single discs to effect the complete transfer. Thus the eight discs of the puzzle will require 255 single transfers. The result can be also obtained by the theory of finite differences. It will be noticed that every alternate move consists of a transfer of the smallest disc from one peg to another, the pegs being taken in cyclical order.
M. De Parville gives an account of the origin of the toy which is a sufficiently pretty conceit to deserve repetition (La Nature, Paris, 1884, part i, pp. 285--286.). In the great temple at Benares, says he, beneath the dome which marks the centre of the world, rests a brass-plate in which are fixed three diamond needles, each a cubit high and as thick as the body of a bee. On one of these needles, at the creation, God placed sixty-four discs of pure gold, the largest disc resting on the brass plate, and the others getting smaller and smaller up to the top one. This is the Tower of Bramah. Day and night unceasingly the priests transfer the discs from one diamond needle to another according to the fixed and immutable laws of Bramah, which require that the priest must not move more than one disc at a time and that he must place this disc on a needle so that there is no smaller disc below it. When the sixty-four discs shall have been thus transferred from the needle on which at the creation God placed them to one of the other needles, tower, temple, and Brahmins alike will crumble into dust, and with a thunder-clap the world will vanish. Would that English writers were in the habit of inventing equally interesting origins for the puzzles they produce!
The number of separate transfers of single discs which the Brahmins must make to effect the transfer of the tower is 2^64-1 , that is, is 18,446744,073709,551615 : a number which,
even if the priests never made a mistake, would require many thousands of millions of years to carry out
.
A somewhat more elaborate toy, known as Chinese Rings, which is on sale in most English toy-shops, is represented in the accompanying figure. It consists of a
number of rings hung upon a bar in such a manner that the ring at one end (say A ) can be taken off or put on the bar at pleasure; but any other ring can be taken off or put on only when the one next to it towards A is on, and all the rest towards A are off the bar. The order of the rings cannot be changed.
Only one ring can be taken off or put on at a time. [In the toy, as usually sold, the first two rings form an exception to the rule. Both these can be taken off or put on together. To simplify the discussion I shall assume at first that only one ring is taken off or put on at a time.] I proceed to show that, if there are n rings, then in order to disconnect them
from the bar, it will be necessary to take a ring off or to put a ring on either 1/3(2^(n+1)-1) times or 1/3(2^(n+1)-2) times according as n is odd or even.
Let the taking a ring off the bar or putting a ring on the bar be called a step. It is usual to number the rings from the free end A. Let us suppose that we commence with the first m rings off the bar and all the rest on the bar; and suppose that then it requires x-1 steps to take off the next ring, that is, it requires x-1 additional steps to arrange the rings so that the first m + 1 of them are off the bar and all the rest are on it. Before taking these steps we can take off the (m + 2) th ring and thus it will require x steps from our initial position to remove the (m + 1) th and (m + 2) th rings.
Suppose that these x steps have been made and that thus the first m + 2 rings are off the bar and the rest on it, and let us find how many additional steps are now necessary to take off the (m + 3) th and (m + 4) th rings. To take these off we begin by taking off the (m + 4) th ring: this requires 1 step. Before we can take off the (m + 3) th we must arrange the rings so that the (m + 2) th is on and the first m + 1 rings are off: to effect this, (i) we must get the (m + 1) th ring on and the first m rings off, which requires x-1 steps, (ii) then we must put on the (m + 2) th ring, which requires 1 step, (iii) and lastly we must take the (m + 1) th ring off, which requires x-1 steps: thus this series of movements requires in all {2 (x-1) + 1} steps. Next we can take the (m + 3) th ring off, which requires 1 step; this leaves us with the first m + 1 rings off, the (m + 2) th on, the (m + 3) th off and all the rest on. Finally to take off the (m + 2) th ring, (i) we get the (m + 1) th ring on and the first m rings off, which requires x-1 steps, (ii) we take off the (m + 2) th ring, which requires 1 step, (iii) we take (m+1) th ring off, which requires x-1 steps: thus this series of movements requires {2 (x-1) + 1} steps.
Therefore, if when the first m rings are off it requires x steps to take off the (m + 1) th and (m + 2) th rings, then the number of additional steps required to take off the (m + 3) th
and (m + 4) th rings is 1 + {2(x-1) + 1} + 1 + {2(x-1) + 1} , that is, is 4x.
To find the whole number of steps necessary to take off an odd number of rings we proceed as follows.
To take off the first ring requires 1 step; 4pt In this way we see that the number of steps required to take off the first 2n+ 1 rings is 1 + 4 + 4^2 +... + 4^n , which is equal to 1/3(2^(2n+2) - 1).
To find the number of steps necessary to take off an even number of rings we proceed in a similar manner.
In this way we see that the number of steps required to take off the first 2n rings is 2 + (2 × 4) + (2 × 4^2) +... + (2 × 4^(n-1)) , which is equal to 1/3(2^(2n+1)-2).
If we take off or put on the first two rings in one step instead of two separate steps, these results become respectively 2^2n and 2^(2n-1)-1.
I give the above analysis because it is the direct solution of a problem attacked by Cardan in 1550 and by Wallis in 1693--in both cases unsuccessfully--and which at one time attracted some attention. I proceed next to give another solution, more elegant though rather artificial.
This solution, which is due to M. Gros (Théorie du Baguenodier, by L. Gros, Lyons, 1872. I take the account of this from Lucas, vol. i, part 7.), depends on a convention by which any position of the rings is denoted by a certain number expressed in the binary scale of notation in such a way that a step is indicated by the addition or subtraction of unity.
Let the rings be indicated by circles: if a ring is on the bar, it is represented by a circle drawn above the bar; if the ring is off the bar, it is represented by a circle below the bar.
Thus figure i below represents a set of seven rings of which the first two are off the bar, the next three are on it, the sixth is off it, and the seventh is on it.
Denote the rings which are on the bar by the digits 1 or 0 alternately, reckoning from left to right, and denote a ring which is off the bar by the digit assigned to that ring on the bar which is nearest to it on the left of it, or by a 0 if there is no ring to the left of it.
Thus the three positions indicated below are denoted respectively by the numbers written below them. The position represented in figure ii is obtained from that in figure i by putting the first ring on to the bar, while the position represented
in figure iii is obtained from that in figure i by taking the fourth ring off the bar.
It follows that every position of the rings is denoted by a number expressed in the binary scale: moreover, since in going from left to right every ring on the bar gives a variation (that is, 1 to 0 or 0 to 1 ) and every ring off the bar gives a continuation, the effect of a step by which a ring is taken off or put on the bar is either to subtract unity from this number or to add unity to it. For example, the number denoting the position of the rings in figure ii is obtained from the number denoting that in figure i by adding unity to it. Similarly the number denoting the position of the rings in figure iii is obtained from the number denoting that in figure i by subtracting unity from it.
The position when all the seven rings are off the bar is denoted by the number 0000000 : when all of them are on the bar by the number 1010101. Hence to change from one
position to the other requires a number of steps equal to the difference between these two numbers in the binary scale. The first of these numbers is 0 : the second is equal to 2^6 + 2^4 + 2^2 + 1 , that is, to 85. Therefore 85 steps are required. In a similar way we may show that to put on a set of 2n + 1 rings requires (1+2^1 + 2^2 +... + 2^2n) steps, that is, 1/3 (2^(2n+2)-1) steps; and to put on a set of 2n rings requires (2 + 2^3 +... + 2^(2n-1)) steps, that is, 1/3(2^(n+1)-2) steps.
I append a table indicating the steps necessary to take off the first four rings from a set of five rings. The diagrams in the middle column show the successive position of the rings after each step. The number following each diagram indicates
that position, each number being obtained from the one above it by the addition of unity. The steps which are bracketed together can be made in one movement, and, if thus effected, the whole process is completed in 7 movements instead of 10 steps: this is in accordance with the formula given above.
M. Gros asserted that it is possible to take from 64 to 80 steps a minute, which in my experience is a rather high estimate. If we accept the lower of these numbers, it would be possible to take off 10 rings in less than 8 minutes; to take off 25 rings would require more than 582 days, each of ten hours work; and to take off 60 rings would necessitate no less than 768614,336404,564650 steps, and would require nearly 55000,000000 years work--assuming of course that no mistakes were made.
The determination of the number of ways in which eight queens
can be placed on a chess-board--or more generally, in which n queens can be placed on a board of n^2 cells--so that no queen can take any other was proposed originally by Nauck in 1850.
In 1874 Dr S. Günther (Grunert's Archiv der Mathematik und Physik, 1874, vol. lvi pp. 281--292.) suggested a method of solution by means of determinants. For, if each symbol represents the corresponding cell of the board, the possible solutions for a board of n^2 cells are given by those terms, if any, of the determinant |; 0 ; | in which no letter and no suffix appears more than once.
The reason is obvious. Every term in a determinant contains one and only one element out of every row and out
of every column: hence any term will indicate a position on the board in which the queens cannot take one another by moves rook-wise. Again in the above determinant the letters and suffixes are so arranged that all the same letters and all the same suffixes lie along bishop's paths: hence, if we retain only those terms in each of which all the letters and all the suffixes are different, they will denote positions in which the queens cannot take one another by moves bishop-wise. It is clear that the signs of the terms are immaterial.
In the case of an ordinary chess-board the determinant is of the 8 th order, and therefore contains 8! , that is, 40320 terms, so that it would be out of the question to use this method for the usual chess-board of 64 cells or for a board of larger size unless some way of picking out the required terms could be discovered.
A way of effecting this was suggested by Dr J.W.L. Glaisher (Philosophical Magazine, London, December, 1874, series 4, vol. xlviii, pp. 457--467.) in 1874, and as far as I am aware the theory remains as he left it. He showed that if all the solutions of n queens on a board of n^2 cells were known, then all the solutions of a certain type for n+1 queens on a board of (n+1)^2 cells could be deduced, and that all the other solutions of n+1 queens on a board of (n+1)^2 cells could be obtained without difficulty. The method will be sufficiently illustrated by one instance of its application.
It is easily seen that there are no solutions when n=2 and n=3. If n=4 there are two terms in the determinant which give solutions, namely, b_2c_5γ_3β_6 and c_3β_2b_6γ_5. To find the solutions when n=5 , Glaisher proceeded thus. In this case Günther's determinant is 1
To obtain those solutions (if any) which involve a_9 it is sufficient to append a_9 to such of the solutions for a board of 16 cells as do not involve a. As neither of those given above involves an a we thus get two solutions, namely, b_2 c_5 γ_3 β_6 a_9 and c_3 β_2 b_6 γ_5 a_9. The solutions which involve a_1 , e_5 and ε_5 can be written down by symmetry. The eight solutions thus obtained are all distinct; we may call them of the first type.
The above are the only solutions which can involve elements in the corner squares of the determinant. Hence the remaining solutions are obtainable from the determinant 2 If, in this, we take the minor of b_2 and in it replace by zero every term involving the letter b or the suffix 2 we shall get all solutions involving b_2. But in this case the minor at once reduces to d_6 a_5 δ_4 β_8. We thus get one solution, namely, b_2 d_6 a5 δ_4 β_8. The solutions which involve β_2 , δ_4 , δ_6 , β_8 , b_8 , d_6 , and d_4 can be obtained by symmetry. Of these eight solutions it is easily seen that only two are distinct: these may be called solutions of the second type.
Similarly the remaining solutions must be obtained from the determinant 3
If, in this, we take the minor of c_3 , and in it replace by zero every term involving the letter c or the suffix 3 , we shall get all the solutions which involve c_3. But in this case the
minor vanishes. Hence there is no solution involving c_3 , and therefore by symmetry no solutions which involve γ_3 , γ_7 , or c_3. Had there been any solutions involving the third element in the first or last row or column of the determinant we should have described them as of the third type.
Thus in all there are ten and only ten solutions, namely, eight of the first type, two of the second type, and none of the third type.
Similarly, if n = 6 , we obtain no solutions of the first type, four solutions of the second type, and no solutions of the third type; that is, four solutions in all. If n = 7 , we obtain sixteen solutions of the first type, twenty-four solutions of the second type, no solutions of the third type, and no solutions of the fourth type; that is, forty solutions in all. If n = 8 , we obtain sixteen solutions of the first type, fifty-six solutions of the second type, and twenty solutions of the third type, that is, ninety-two solutions in all.
It will be noticed that all the solutions of one type are not always distinct. In general, from any solution seven others can be obtained at once. Of these eight solutions, four consist of the initial or fundamental solution and the three similar ones obtained by turning the board through one, two, or three right angles; the other four are the reflexions of these in a mirror: but in any particular case it may happen that the reflexions reproduce the originals, or that a rotation through one or two right angles makes no difference. Thus on boards of 4^2 , 5^2 , 6^2 , 7^2 , 8^2 , 9^2 , 10^2 cells there are respectively 1 , 2 , 1 , 6 , 12 , 46 , 92 fundamental solutions; while altogether there are respectively 2 , 10 , 4 , 40 , 92 , 352 , 724 solutions.
The following collection of fundamental solutions may interest the reader. The positions on the board of the queens are indicated by digits: the first digit represents the number of the cell occupied by the queen in the first column reckoned from one end of the column, the second digit the number in the second column, and so on. Thus on a board of 4^2 cells the solution 3142 means that one queen is on the 3 rd square of
the first column, one on the 1 st square of the second column, one on the 4 th square of the third column, and one on the 2 nd square of the fourth column. If a fundamental solution gives rise to only four solutions the number which indicates it is placed in curved brackets, ( ; ); if it gives rise to only two solutions the number which indicates it is placed in square brackets, [ ; ]; the other fundamental solutions give rise to eight solutions each.
On a board of 4^2 cells there is 1 fundamental solution: namely, [ 3142 ].
On a board of 5^2 cells there are 2 fundamental solutions: namely, 14253 , [ 25314 ].
On a board of 6^2 cells there is 1 fundamental solution: namely, ( 246135 ).
On a board of 7^2 cells there are 6 fundamental solutions: namely, 1357246 , 3572461 , ( 5724613 ), 4613572 , 3162574 , ( 2574136 ).
On a board of 8^2 cells there are 12 fundamental solutions: namely, 25713864 , 57138642 , 71386425 , 82417536 , 68241753 , 36824175 , 64713528 , 36814752 , 36815724 , 72418536 , 26831475 , ( 64718253 ). The arrangement in this order is due to Mr Oram. It will be noticed that the 10 th, 11 th, and 12 th solutions somewhat resemble the 4 th, 6 th, and 7 th respectively. The 6 th solution is the only one in which no three queens are in a straight line.
On a board of 9^2 cells there are 46 fundamental solutions; one of them is 248396157. On a board of 10^2 cells there are 92 fundamental solutions; these were given by Dr A. Pein (Aufstellung von n Königinnen auf einem Schachbrett von n^2 Feldern, Leipzig, 1889.); one of them is 2468t13579 , where t stands for ten. On a board of 11^2 cells there are 341 fundamental solutions; these have been given by Dr T.B. Sprague (Proceedings of the Edinburgh Mathematical Society, vol. xvii, 1898--9, pp. 43--68.): one of them is 15926t37e48. I may add that for a board of n^2 cells there is always a
symmetrical solution of the form 246... n135... (n-1) , when n= 6m or n = 6m + 4 , Also Mr Oram has shown that for a board of n^2 cells, when n is a prime, cyclical arrangements of the n natural numbers, other than in their natural order, will give solutions; see, for instance, the solution quoted above.
The puzzle in the form of a board of 36 squares is sold in the streets of London for a penny, a small wooden board being ruled in the manner shown in the diagram and having holes drilled in it at the points marked by dots. The object is to put six pins into the holes so that no two are connected by a straight line. [width=5cm]./images/illus136illus:136
Other Problems with Queens Other Problems with Queens and Chess-pieces Problems with Queens. Captain Turton called my attention to two other problems of a somewhat analogous character, neither of which, as far as I know, has been published elsewhere, or solved otherwise than empirically.
The first of these is to place eight queens on a chess-board so as to command the fewest possible squares. Thus, if queens are placed on cells 1 and 2 of the second column, on cell 2 of the sixth column, on cells 1 , 3 , and 7 of the seventh column, and on cells 2 and 7 of the eighth column, eleven cells on the board will not be in check; the same number can be obtained by other arrangements. Is it possible to place the eight queens so as to leave more than eleven cells out of check? I have never succeeded in doing so, nor in showing that it is impossible to do it.
The other problem is to place m queens ( m being less than 5 ) on a chess-board so as to command as many cells as possible. For instance, four queens can be placed in several ways on the board so as to command 58 cells besides those on which the queens stand, thus leaving only 2 cells which are not commanded: this is effected if the queens are placed on cell 5 of the third column, cell 1 of the fourth column, cell 6 of the seventh column, and cell 2 of the eighth column; or on cell 1 of the first column, cell 7 of the third column, cell 3 of the fifth column, and cell 5 of the seventh column. A similar problem is to determine the minimum number and the position of queens which can be placed on a board of n^2 cells so as to occupy or command every cell. It would seem that, even with the additional restriction that no queen shall be able to take any other queen, there are no less than ninety-one typical solutions in which five queens can be placed on a chess-board so as to command every cell (L'Intermédiaire des mathématiciens, Paris, 1901, vol. viii, p. 88.)
.
Extension to other Chess Pieces Analogous problems may
be proposed with other chess-pieces. For instance, questions as to the maximum number of knights which can be placed on a board of n^2 cells so that no knight can take any other, and the minimum number of knights which can be placed on it so as to occupy or command every cell have been propounded (ibid:1L'Intermédiaire des mathématiciens, Paris, March, 1896, vol. iii, p. 58; 1897, vol. iv, p. 15, 254; and 1898, vol. v, p. 87.).
Similar problems have also been proposed for k kings placed on a chess-board of n^2 cells (ibid:1L'Intermédiaire des mathématiciens, Paris, June, 1901, p. 140.). It has been asserted that, if k = 2 , the number of ways in which two kings can be placed on a board so that they may not occupy adjacent squares is 1/2(n-1)(n-2) (n^2 + 3n-2). Similarly, if k=3 , the number of ways in which three kings can be placed on a board so that no two of them occupy adjacent squares is said to be 1/6(n-1) (n-2) (n^4+ 3n^3-20n^2-30n + 132).
This problem
--which was first enunciated by Mr T.P. Kirkman, and is sometimes known as Kirkman's problem (It was published first in the Lady's and Gentleman's Diary for 1850, p. 48, and has been the subject of numerous memoirs. Among these I may single out the papers by A. Cayley in the Philosophical Magazine, July, 1850, series 3, vol. xxxvii, pp. 50--53; by T.P. Kirkman in the Cambridge and Dublin Mathematical Journal, 1850, vol. v, p. 260; by R.R. Anstice, , 1852, vol. vii, pp. 279--292; by B. Pierce, Gould's Journal, Cambridge, U.S., 1860, vol. vi, pp. 169--174; by T.P. Kirkman, Philosophical Magazine, March, 1862, series 4, vol. xxiii, pp. 198--204; by W.S.B. Woolhouse in the Lady's Diary for 1862, pp. 84--88, and for 1863, pp. 79--90, and in the Educational Times Reprints, 1867, vol. viii, pp. 76--83; by J. Power in the Quarterly Journal of Mathematics, 1867, vol. viii, pp. 236--251; by A.H. Frost, , 1871, vol. xi, pp. 26--37; by E. Carpmael in the Proceedings of the London Mathematical Society, 1881, vol. xii, pp. 148--156; by Lucas in his Récréations, vol. ii, part vi; by A.C. Dixon in the Messenger of Mathematics, Cambridge, October, 1893, vol. xxiii, pp. 88--89; and by W. Burnside, , 1894, vol. xxiii, pp. 137--143. It has also, since the issue of my third edition, been discussed by W. Ahrens in his Mathematische Unterhaltungen und Spiele, Leipzig, 1901, chapter xiv.)--consists in arranging fifteen things in different sets of triplets. It is usually presented in the form that a school-mistress was in the habit of taking her girls for a daily walk. The girls were fifteen in number, and were arranged in five rows of three each so that each girl might have two companions. The problem is to dispose them so that for seven consecutive days no girl will walk with any of her school-fellows more than once. More generally we may require to arrange 3m girls in triplets to walk out for 1/2(3m-1) days, so that no girl will walk with any of her school-fellows more than once.
The theory of the formation of all such possible triplets in the case of fifteen girls is not difficult, but the extension to 3m girls is, as yet, unsolvedIn 1971 Ray-Chaudhuri and Wilson proved that Kirkman triple systems of order ν exist if and only if ν3 6. I proceed to describe three methods of solution: these methods are analytical, but I may add that the problem can be also attacked by geometrical methods.
Frost's Method The first of these solutions is due to Mr Frost. A full exposition of it would occupy a good deal of space, but I hope that the following sketch will make the process intelligible.
Denote one of the girls by k. Her companions on each day are different: suppose that on Sunday they are a_1 and a_2 , on Monday b_1 and b_2 , and so on, and finally on Saturday g_1 and g_2. Hence for each day we have one triplet, and we have to find four others, but in each of the latter no two like letters can occur together, that is, the three letters in any of them must be all different.
Let a stand for a_1 , or a_2 , b for b_1 or b_2 , and so on. The suffixes 1 and 2 are called complementary. Then, since the three letters in each of the triplets we are trying to find must be different, we must make some arrangement such as putting a with bc , de , and fg ; and, if so, b may be associated with df and eg ; and c with dg and ef. Thus there are seven possible triads, such as abc , ade , afg , bdf , beg , cdg , and cef. Moreover each of these may stand for any one of four triplets: for instance, the triad bdf may stand for any of the triplets b_1 d_1 f_1 , b_1 d_2 f_2 , b_2 d_1 f_2 , b_2 d_2 f_1.
The four triads which do not involve a must be placed in the Sunday column, the four which do not involve b in the Monday column, and so on. Thus each triad will occur four times.
It only remains to insert the proper suffixes. This is done as follows. Take one triad, such as bdf , and insert a different set of suffixes each time that it occurs; for instance, the four sets given above. Next, the other like letters ( b , d , or f as the case may be) in these four columns must have the complementary suffixes attached.
After this is done, the next triplet in the Sunday column will be b_2 eg. The triad beg occurs in four columns and includes four possible triplets, such as b_2 e_1 g_1 , b_2 e_2 g_2 , b_1 e_1 g_2 , b_1 e_2 g_1. Insert these, and then give the complementary suffixes to the other like letters in these four columns.
In this way the arrangement is constructed gradually, by
taking one triad at a time, inserting the proper suffixes to the four triplets included in it, and then the complementary suffixes in the other like letter in the same columns.
One final arrangement, thus obtained, is as follows: 0 We might obtain other solutions by selecting other seven triads or by choosing other arrangements of the suffixes in each triad (or by merely interchanging letters and suffixes in the above order). By these means Mr Power showed that there are no less than 15567,552000 different solutions; but, since the total number of ways in which the school can walk out for a week in triplets is (455)^7 , the probability that any chance way satisfies Kirkman's condition is very small.
Frost's method is applicable to the case of 2^2n-1 girls walking out for 2^(2n-1)-1 days in triplets. The detailed solution for 63 girls walking out for 31 days, which corresponds to n = 3 , have been given.
Anstice's Method Another method of attacking the problem is due to Mr Anstice; it is illustrated by the following elegant solution, by which from the order on Sunday we can obtain the order on the following six days by a cyclical permutation. Let the girls be denoted respectively by the letters k , a_1 , a_2 , a_3 , a_4 , a_5 , a_6 , a_7 , b_1 , b_2 , b_3 , b_4 , b_5 , b_6 , b_7 ; and suppose the order on Sunday to be k a_1 b_1,; a_2 a_3 a_5,; a_4 b_3 b_6,; a_6 b_2 b_7,; a_7 b_4 b_5. Then, if the suffixes are permuted cyclically, we obtain six other arrangements which satisfy the conditions of the problem: the reason being that in the above arrangement the difference
of the suffixes of every pair of like letters--such as either the " a "s or the " b "s--in a triplet is different for each triplet, as also is the difference of the suffixes of every pair of unlike letters which are in a triplet.
Two other arrangements for Sunday, from which those for the remaining days are obtainable by cyclical permutations can be formed. These are ka_1b_1 , a_2a_3a_5 , a_4b_5b_7 , a_6b_3b_4 , a_7b_2b_6 ; and ka_1b_1 , a_2a_3a_5 , a_4b_2b_6 , a_6b_5b_7 , a_7b_3b_4.
Anstice's method is applicable to the case of 2p+1 girls walking out for p days in triplets so that no pair may walk together more than once, provided p is a prime of the form 12m+7. In such a case he showed how to construct a fundamental arrangement for one day from which the arrangements for the remaining p-1 days can be obtained by cyclical permutations of suffixes. The number of such fundamental arrangements is 3 (2m+1)(3m+1).
The problem of 15 girls corresponds to m = 0 , and the three fundamental Anstician arrangements are given above. If m=1 we have the problem of 39 girls. One Anstician arrangement in this case is as follows: ka_1b_1 , a_2a_8a_12 , a_5a_7a_10 , a_6a_17a_18 , a_3b_10b_15 , a_4b_3b_5 , a_9b_18b_19 , a_11b_8b_14 , a_13b_9b_17 , a_14b_12b_16 , a_15b_4b_7 , a_16b_2b_11 , a_19b_6b_13. If m=2 we have the problem of 63 girls, of which Frost has given one solution; and so on.
Gill's Method Another method of attacking the problem has been suggested to me by Mr T.H. Gill. Representing the girls by a_1, a_2, a_3..., a_3m he (i) forms one triplet of the type a_1a_(m+1)a_(2m+1) , from which, by cyclical permutation of the suffixes 1, 2..., 3m he obtains m triplets which constitute an arrangement for one day, and (ii) forms 1/2(m-1) other triplets such that the three differences of the suffixes are different, from which, by cyclical permutations of the suffixes, the arrangements for the remaining 3/2(m-1) other days can be obtained. Thus in the case of 15 girls, the triplet a_1a_6a_11 gives, by cyclical permutations of the suffixes, an arrangement for the first day and two triplets such as a_1a_2a_5 , a_1a_3a_9 enable us to form 30 triplets from which an arrangement for the
other six days can be found. Here is a solution thus determined. -2 But, although this method gives triplets with which the problem can be solved, the final arrangement is empirical.
A solution of the problem of 21 girls for 10 days can be got by the same method: a_1a_8a_15 giving 7 triplets which constitute an arrangement for one day; and a_1a_2a_6 , a_1a_3a_11 , a_1a_4a_10 giving 63 triplets from which an arrangement for the other nine days can be formed. Here is the solution thus determined. 4pt -2
I should be interested if any of my readers could give me a similar solution of the analogous arrangement of 33 girls for 16 days formed from typical triplet suffixes like 1 , 12 , 23 ; 1 , 2 , 10 ; 1 , 3 , 16 ; 1 , 4 , 18 ; 1 , 5 , 11 ; 1 , 6 , 13 ; or from other sets of triplets formed in a similar way so that (except in the first triplet) the differences of the suffixes are all different.
Walecki's Theorem Lastly, Walecki--quoted by Lucas--has shown that, if a solution for the case of n girls walking
out in triplets for 1/2(n-1) days is known, then a solution for 3n girls walking out for 1/2(3n-1) days can be deduced.
For if an arrangement of the n girls, a_1, a_2..., a_n for 1/2(n-1) days is known; and also one of the n girls, b_1, b_2..., b_n ; and also one of the n girls c_1, c_2..., c_n ; then an arrangement of these 3n girls for 1/2(n-1) days is known. A set of n triplets for another day will be given by a_mb_(m+k)c_(m + 2k) where m is put equal to 1, 2..., n successively. Here k may have any of the n values, 0, 1, 2..., (n-1) ; but, wherever a suffix is greater than n , it is to be divided by n and only the remainder retained. Hence altogether we have an arrangement for n + 1/2 (n-1) days, for 1/2(3n-1) days.
The arrangement of 3 girls for one day is obvious. Hence, by Walecki's theorem, we can deduce at once an arrangement of 3^m girls for 1/2(3^m-1) days. And, generally, as I have given solutions of the problem in the case of 3n girls when n= 1 , 3 , 5 , 7 , 9 , 13 , 15 , it follows that for the same values of n , we can solve the analogous arrangements of 3^m × n girls.
To the original theorem J.J. Sylvester (Philosophical Magazine, July, 1850, series 3, vol. xxxvii, p. 52; a solution by Sylvester is given in the Philosophical Magazine, May, 1861, series 4, vol. xxi, p. 371.) added the corollary that the school of 15 girls could walk out in triplets on 13× 7 days until every possible triplet had walked abreast once.
The generalized problem of finding the greatest number of ways in which x girls walking in rows of a abreast can be arranged so that every possible combination of b of them may walk abreast once and only once has been solved for various cases. Suppose that this greatest number of ways is y. It is obvious that, if all the x girls are to walk out each day in rows of a abreast, then x must be an exact multiple of a and the number of rows formed each day is x/a. If such an arrangement can be made for z days, then we have a solution of the problem to arrange x girls to walk out in rows of a abreast for z days so that they all go out each day and so that
every possible combination of b girls may walk together once, and only once. In the corresponding generalization of Kirkman's problem no companionship of girls which has occurred once may occur again, but it does not follow necessarily that every possible companionship must occur once.
An example where the solution is obvious is if x=2n , a=2 , b=2 , in which case y=n(2n-1) , z=2n-1.
If we take the case x=15 , a=3 , b=2 , we find y=35 ; and it happens that these 35 rows can be divided into 7 sets, each of which contains all the symbols; hence z=7. More generally, if x=5 × 3^m , a=3 , b=2 , we find y=3/2(x-1)/x , z=1/2(x-1). It will be noticed that in the solutions of the original fifteen school-girls problem and of Walecki's extension of it given above every possible pair of girls walk together once; hence we might infer that in these cases we could determine z as well as y.
The results of the last paragraph were given by Kirkman (Cambridge and Dublin Mathematical Journal, 1850, vol. v, pp. 255--262.) in 1850. In the same memoir he also proved that, if p is a prime, and if x=p^m , a=p , b=2 , then y=(p^m-1)/(p-1) ; if x=(p^2+p+1)(p+1) where p^2+p+1 has no divisor less than p+1 , a=p+1 , b=2 , then y=x(x-1)/p(p+1) ; if x=p^3+p+1 , a=p+1 , b=2 , then y=x ; and Sylvester's result that if x=15 , a=3 , b=3 , y=455 , z=91. Three years later Kirkman (ibid:2Cambridge and Dublin Mathematical Journal, 1853, vol. viii, pp. 38--42.) solved the problem when x=2^n , a=4 , b=3. Lastly, in 1893, Sylvester (Messenger of Mathematics, February, 1893, vol. xxii, pp. 159--160.) published the solution when x=9 , a=3 , b=3 , in which case y=84 , z=28 ; and stated that a similar method was applicable when x=3^m , a=3 , b=3 : thus 9 girls can be arranged to walk out 28 times (say 4 times a day for a week) so that in any day the same pair never are together more than once and so that at the end of the week each girl has been associated with every possible pair of her schoolfellows.
In 1867 Mr S. Bills (Educational Times Reprints, London, 1867, vol. viii, pp. 32--33.) showed that if x=7 , a=3 , b=2 , then y=7 : if x=15 , a=3 , b=2 , then y=35 : if x=31 , a=3 , b=2 , then y=155 : and the method by which these results are proved will give the value of y , if x=2^n-1 , a=3 , b=2. Shortly afterwards Mr W. Lea (ibid:3Educational Times Reprints, London, 1868, vol. ix, pp. 35--36; and 1874, vol. xxii, pp. 74--76; see also the volume for 1869, vol. xi, p. 97.) showed that if x=11 , a=5 , b=4 , then y=66 ; also that if x=16 , a=4 , b=3 , then y=140 ; the latter result is a particular case of Kirkman's theorems. It will be noticed that these writers did not confine their discussion to cases where x is an exact multiple of a
.
[Problems connected with a pack of cards] Problems connected with a Pack of Cards I mentioned in chapter i that an ordinary pack of playing cards could be used to illustrate many tricks depending on simple properties of numbers. Most of these involve the relative position of the cards. The principle of solution generally consists in re-arranging the pack in a particular manner so as to bring the card into some definite position. Any such rearrangement is a species of shuffling.
I shall treat in succession of problems connected with shuffling a pack, arrangements by rows and columns, the determination of a pair out of 1/2n(n+1) pairs, Gergonne's pile problem, and the game known as the mouse trap.
tocsubsectionMonge on shuffling a pack of cards Any system of shuffling a pack of cards, if carried out consistently, leads to an arrangement which can be calculated; but tricks that depend on it generally require considerable technical skill.
Suppose for instance that a pack of n cards is shuffled, as is not unusual, by placing the second card on the first, the third below these, the fourth above them, and so on. The theory of this system of shuffling is due to Monge (Monge's investigations are printed in the Mémoires de l'Académie des Sciences, Paris, 1773, pp. 390--412. Among those who have studied the subject afresh I may in particular mention V. Bouniakowski, Bulletin physico-mathématique de St Pétersbourg, 1857, vol. xv, pp. 202--205, summarised in the Nouvelles annales de mathématiques, 1858, pp. 66--67; T. de St Laurent, Mémoires de l'Académie de Gard, 1865; L. Tanner, Educational Times Reprints, 1880, vol. xxxiii, pp. 73--75; and M.J. Bourget, Liouville's Journal, 1882, pp. 413--434. The solutions given by Prof. Tanner are simple and concise.). The
following are some of the results and are not difficult to prove directly.
If the pack contains 6p+4 cards, the (2p + 2) th card will occupy the same position in the shuffled pack. For instance, if a complete pack of 52 cards is shuffled as described above, the 18 th card will remain the 18 th card.
Again, if a pack of 10p + 2 cards is shuffled in this way, the (2p + 1) th and the (6p × 2) th cards will interchange places. For instance, if an écarté pack of 32 cards is shuffled as described above, the 7 th and the 20 th cards will change places.
More generally, one shuffle of a pack of 2p cards will move the card which was in the x_0 th place to the x_1 th place, where x_1=1/2(2p+x_0+1) if x_0 is odd, and x_1=1/2(2p-x_0 + 2) if x_0 is even, from which the above results can be deduced. By repeated applications of the above formulae we can show that the effect of m such shuffles is to move the card which was initially in the x_0 th place to the x_m th place where 2^(m+1)x_m=(4p+1)(2^(m-1) ± 2^(m-2) ±... ± 2 ± 1) ± 2x_0 + 2^m ± 1 , the sign ± representing an ambiguity of sign.
Again, in any pack of n cards after a certain number of shufflings, not greater than n , the cards will return to their primitive order. This will always be the case as soon as the original top card occupies that position again. To determine the number of shuffles required for a pack of 2p cards, it is sufficient to put x_m=x_0 and find the smallest value of m which satisfies the resulting equation for all values of x_0 from 1 to 2p. It follows that, if m is the least number which makes 4^m-1 divisible by 4p+1 , then m shuffles will be required if either 2^m+1 or 2^m-1 is divisible by 4p+1 , otherwise 2m shuffles will be required. The number for a pack of
2p+1 cards is the same as that for a pack of 2p cards. With an écarté pack of 32 cards, six shuffles are sufficient; with a pack of 2^n cards, n+1 shuffles are sufficient; with a full pack of 52 cards, twelve shuffles are sufficient; with a pack of 13 cards ten shuffles are sufficient; while with a pack of 50 cards fifty shuffles are required; and so on.
Mr W.H.H. Hudson (Educational Times Reprints, London, 1865, vol. ii, p. 105.) has also shown that, whatever is the law of shuffling, yet if it is repeated again and again on a pack of n cards, the cards will ultimately fall into their initial positions after a number of shufflings not greater than the greatest possible l.c.m. of all numbers whose sum is n.
For suppose that any particular position is occupied after the 1 st, 2 nd, ... , p th shuffles by the cards A_1, A_2..., A_p respectively, and that initially the position is occupied by the card A_0. Suppose further that after the p th shuffle A_0 returns to its initial position, therefore A_0=A_p. Then at the second shuffling A_2 succeeds A_1 by the same law by which A_1 succeeded A_0 at the first; hence it follows that previous to the second shuffling A_2 must have been in the place occupied by A_1 previous to the first. Thus the cards which after the successive shuffles take the place initially occupied by A_1 are A_2, A_3..., A_p, A_1 ; that is, after the p th shuffle A_1 has returned to the place initially occupied by it: and so for all the other cards A_2, A_3..., A_(p-1).
Hence the cards A_1, A_2..., A_p form a cycle of p cards, one or other of which is always in one or other of p positions in the pack, and which go through all their changes in p shufflings. Let the number n of the pack be divided into p, q, r... such cycles, whose sum is n ; then the l.c.m. of p, q, r... is the utmost number of shufflings necessary before all the cards will be brought back to their original places.
In the case of a pack of 52 cards, the greatest l.c.m. of numbers whose sum is 52 will be found by trial to be 180180.
tocsubsectionArrangement by rows and columns A not uncommon trick, which rests on a species of shuffling, depends on the obvious fact that if n^2 cards are arranged in the form of a square of n rows, each containing n cards, then any card will be defined if the row and the column in which it lies are mentioned.
This information is generally elicited by first asking in which row the selected card lies, and noting the extreme left-hand card of that row. The cards in each column are then taken up, face upwards, one at a time beginning with the lowest card of each column and taking the columns in their order from right to left--each card taken up being placed on the top of those previously taken up. The cards are then dealt out again in rows, from left to right, beginning with the top left-hand corner, and a question is put as to which row contains the card. The selected card will be that card in the row mentioned which is in the same vertical column as the card which was originally noted.
The above is the form in which the trick is usually presented, but it is greatly improved by allowing the pack to be cut as often as is liked before the cards are re-dealt, and then giving one cut at the end so as to make the top card in the pack one of those originally in the top row.
The explanation is obvious. For, if 16 cards are taken,
the first and second arrangements may be represented by
figures i and ii. For example, if we are told that in figure i the card is in the third row, it must be either 9 , 10 , 11 , or 12 : hence, if we know in which row of figure ii it lies, it is determined. If we allow the pack to be cut between the deals, we must secure somehow that the top card is either 1 , 2 , 3 , or 4 , since that will leave the cards in each row of figure ii unaltered though the positions of the rows will be changed.
tocsubsectionDetermination of one out of n(n+1) given couples Another common trick is to throw twenty cards on to a table in ten couples, and ask someone to select one couple. The cards are then taken up, and dealt out in a certain manner into four rows each containing five cards. If the rows which contain the given cards are indicated, the cards selected are known at once.
This depends on the fact that the number of homogeneous products of two dimensions which can be formed out of four things is 10. Hence the homogeneous products of two dimensions formed out of four things can be used to define ten things.
Suppose that ten pairs of cards are placed on a table and someone selects one couple. Take up the cards in their
couples. Then the first two cards form the first couple, the next two the second couple, and so on. Deal them out in four rows each containing five cards according to the scheme shown in the diagram.
The first couple ( 1 and 2 ) are in the first row. Of the next couple ( 3 and 4 ), put one in the first row and one in the second. Of the next couple ( 5 and 6 ), put one in the first row and one in the third, and so on, as indicated in the diagram. After filling up the first row proceed similarly with the second row, and so on.
Enquire in which rows the two selected cards appear. If only one line, the m th, is mentioned as containing the cards then the required pair of cards are the m th and (m+1) th cards in that line. These occupy the clue squares of that line. Next, if two lines are mentioned, then proceed as follows. Let the two lines be the p th and the q th and suppose q>p. Then that one of the required cards which is in the q th line will be the (q-p) th card which is below the first of the clue squares in the p th line. The other of the required cards is in the p th line and is the (q-p) th card to the right of the second of the clue squares.
Bachet's rule, in the form in which I have given it, is applicable to a pack of n(n+1) cards divided into couples, and dealt in n rows each containing n+1 cards; for there are 1/2n(n+1) such couples, also there are 1/2n(n+1) homogeneous products of two dimensions which can be formed out of n things. Bachet gave the diagrams for the cases of 20 , 30 , and 42 cards: these the reader will have no difficulty in constructing for himself, and I have enunciated the rule for 20 cards in a form which covers all the cases.
I have seen the same trick performed by means of a sentence and not by numbers. If we take the case of ten couples, then after collecting the pairs the cards must be dealt in four rows each containing five cards, in the order indicated by the sentence Matas dedit nomen Cocis. This sentence must be imagined as written on the table, each word forming one line, The first card is dealt on the M. The next card (which is the pair of the first) is placed on the second m in the sentence, that is, third in the third row. The third card is placed on the a. The fourth card (which is the pair of the third) is
placed on the second a , that is, fourth in the first row. Each of the next two cards is placed on a t , and so on. Enquire in which rows the two selected cards appear. If two rows are mentioned, the two cards are on the letters common to the words that make these rows. If only one row is mentioned, the cards are on the two letters common to that row.
The reason is obvious: let us denote each of the first pair by an a , and similarly each of any of the other pairs by an e , i , o , c , d , m , n , s , or t respectively. Now the sentence Matas dedit nomen Cocis contains four words each of five letters; ten letters are used, and each letter is repeated only twice. Hence, if two of the words are mentioned, they will have one letter in common, or, if one word is mentioned, it will have two like letters.
To perform the same trick with any other number of cards we should require a different sentence.
The number of homogeneous products of three dimensions which can be formed out of four things is 20 , and of these the number consisting of products in which three things are alike and those in which three things are different is 8. This leads to a trick with 8 trios of things, which is similar to that last given--the cards being arranged in the order indicated by the sentence Lanata levete livini novoto.
I believe that these arrangements by sentences are known, but I am not aware who invented them.
tocsubsectionGergonne's Pile Problem Before discussing Gergonne's
theorem I will describe the familiar three pile problem, the theory of which is included in his results.
The Three Pile Problem (The trick is mentioned by Bachet, problem xviii, p. 143, but his analysis of it is insufficient.) This trick is usually performed as follows. Take 27 cards and deal them into three piles, face upwards. By "dealing" is to be understood that the top card is placed as the bottom card of the first pile, the second card in the pack as the bottom card of the second pile, the
third card as the bottom card of the third pile, the fourth card on the top of the first one, and so on: moreover I assume that throughout the problem the cards are held in the hand face upwards. The result can be modified to cover any other way of dealing.
Request a spectator to note a card, and remember in which pile it is. After finishing the deal, ask in which pile the card is. Take up the three piles, placing that pile between the other two. Deal again as before, and repeat the question as to which pile contains the given card. Take up the three packs again, placing the pile which now contains the selected card between the other two. Deal again as before, but in dealing note the middle card of each pile. Ask again for the third time in which pile the card lies, and you will know that the card was the one which you noted as being the middle card of that pile. The trick can be finished then in any way that you like. The usual method--but a very clumsy one--is to take up the three piles once more, placing the named pile between the other two as before, when the selected card will be the middle one in the pack, that is, if 27 cards are used it will be the fourteenth.
The trick is often performed with 15 cards or with 21 cards, in either of which cases the same rule holds.
Gergonne's Generalization The general theory for a pack of m^m cards was given by M. Gergonne (Gergonne's Annales de Mathématiques, Nismes, 1813--4, vol. iv, pp. 276--283.). Suppose the pack is arranged in m piles, each containing m^(m-1) cards, and that, after the first deal, the pile indicated as containing the selected card is taken up a th; after the second deal, is taken up b th; and so on, and finally after the m th deal, the pile containing the card is taken up k th. Then when the cards are collected after the m th deal the selected card will be n th from the top where 0
For example, if a pack of 256 cards ( m = 4 ) was given, and anyone selected a card out of it, the card could be determined by making four successive deals into four piles of 64 cards each, and after each deal asking in which pile the selected card lay. The reason is that after the first deal you know it is one of sixty-four cards. In the next deal these sixty-four cards are distributed equally over the four piles, and therefore, if you know in which pile it is, you will know that it is one of sixteen cards. After the third deal you know it is one of four cards. After the fourth deal you know which card it is.
Moreover, if the pack of 256 cards is used, it is immaterial in what order the pile containing the selected card is taken up after a deal. For, if after the first deal it is taken up a th, after the second b th, after the third c th, and after the fourth d th, the card will be the (64d-16c + 4b-a + 1) th from the top of the pack, and thus will be known. We need not take up the cards after the fourth deal, for the same argument will show that it is the (64-16c + 4b-a + 1) th in the pile then indicated as containing it. Thus if a = 3 , b = 4 , c = 1 , d = 2 , it will be the 62 nd card in the pile indicated after the fourth deal as containing it and will be the 126 th card in the pack as then collected.
In exactly the same way a pack of twenty-seven cards may be used, and three successive deals, each into three piles of nine cards, will suffice to determine the card. If after the deals the pile indicated as containing the given card is taken up a th, b th, and c th respectively, then the card will be the (9c-3b + a) th in the pack or will be the (9-3b + a) th card in the pile indicated after the third deal as containing it.
The method of proof will be illustrated sufficiently by considering the usual case of a pack of twenty-seven cards, for which m = 3 , which are dealt into three piles each of nine cards.
Suppose that, after the first deal, the pile containing the selected card is taken up a th: then (i) at the top of the pack there are a-1 piles each containing nine cards; (ii) next
there are 9 cards, of which one is the selected card; and (iii) lastly there are the remaining cards of the pack. The cards are dealt out now for the second time: in each pile the bottom 3(a-1) cards will be taken from (i), the next 3 cards from (ii), and the remaining 9-3a cards from (iii).
Suppose that the pile now indicated as containing the selected card is taken up b th: then (i) at the top of the pack are 9(b-1) cards; (ii) next are 9-3a cards; (iii) next are 3 cards, of which one is the selected card; and (iv) lastly are the remaining cards of the pack. The cards are dealt out now for the third time: in each pile the bottom 3 (b-1) cards will be taken from (i), the next 3-a cards will be taken from (ii), the next card will be one of the three cards in (iii), and the remaining 8-3b+a cards are from (iv).
Hence, after this deal, as soon as the pile is indicated, it is known that the card is the (9-3b + a) th from the top of that pile. If the process is continued by taking up this pile as c th, then the selected card will come out in the place 9(c-1) + (8-3b + a) + 1 from the top, that is, will come out as the (9c-3b + a) th card.
Since, after the third deal, the position of the card in the pile then indicated is known, it is easy to notice the card, in which case the trick can be finished in some way more effective than dealing again.
If we put the pile indicated always in the middle of the pack we have a=2 , b = 2 , c = 2 , hence n = 9c-3b + a= 14 , which is the form in which the trick is usually presented, as was explained above on page.
I have shown that if a , b , c are known, then n is determined. We may modify the rule so as to make the selected card come out in any assigned position, say the n th. In this case we have to find values of a , b , c which will satisfy the equation n = 9c-3b + a , where a , b , c can have only the values 1 , 2 , or 3.
Hence, if we divide n by 3 and the remainder is 1 or 2 , this remainder will be a ; but, if the remainder is 0 , we must decrease
the quotient by unity so that the remainder is 3 , and this remainder will be a. In other words a is the smallest positive number (exclusive of zero) which must be subtracted from n to make the difference a multiple of 3.
Next let p be this multiple, p is the next lowest integer to n/3 : then 3p = 9c-3b , therefore p = 3c-b. Hence b is the smallest positive number (exclusive of zero) which must be added to p to make the sum a multiple of 3 , and c is that multiple.
A couple of illustrations will make this clear. Suppose we wish the card to come out 22 nd from the top, therefore 22 = 9c-3b + a. The smallest number which must be subtracted from 22 to leave a multiple of 3 is 1 , therefore a = 1. Hence 22 = 9c-3b + 1 , therefore 7 = 3c-b. The smallest number which must be added to 7 to make a multiple of 3 is 2 , therefore b = 2. Hence 7 = 3c-2 , therefore c = 3. Thus a = 1 , b=2 , c = 3.
Again, suppose the card is to come out 21 st. Hence 21 = 9c-3b+a. Therefore a is the smallest number which subtracted from 21 makes a multiple of 3 , therefore a= 3. Hence 6 = 3c-b. Therefore b is the smallest number which added to 6 makes a multiple of 3 , therefore b = 3. Hence 9 = 3c , therefore c = 3. Thus a = 3 , b = 3 , c = 3.
If any difficulty is experienced in this work, we can proceed thus. Let a = x+1 , b=3-y , c=z+1 ; then x , y , z may have only the values 0 , 1 , or 2. In this case Gergonne's equation takes the form 9z + 3y + x = n-1. Hence, if n-1 is expressed in the ternary scale of notation, x , y , z will be determined, and therefore a , b , c will be known.
The rule in the case of a pack of m^m cards is exactly similar. We want to make the card come out in a given place. Hence, in Gergonne's formula, we are given n and we have to find a, b..., k. We can effect this by dividing n continually by m , with the convention that the remainder are to be alternately positive and negative and that their numerical values are to be not greater than m or less than unity.
An analogous theorem with a pack of lm cards can be constructed. C.T. Hudson and L.E. Dickson (Educational Times Reprints, 1868, vol. ix, pp. 89--91; and Bulletin of the American Mathematical Society, New York, April, 1895, vol. i, pp. 184--186.) have discussed the general case where such a pack is dealt n times, each time into l piles of m cards; and they have shown how the piles must be taken up in order that after the n th deal the selected card may be r th from the top.
The principle will be sufficiently illustrated by one example treated in a manner analogous to the cases already discussed. For instance, suppose that an écarté pack of 32 cards is dealt into 4 piles each of 8 cards, and that the pile which contains some selected card is picked up a th. Suppose that on dealing again into four piles, one pile is indicated as containing the selected card, the selected card cannot be one of the bottom 2 (a-1) cards, or of the top 8-2a cards, but must be one of the intermediate 2 cards, and the trick can be finished in any way, as for instance by the common conjuring ambiguity of asking someone to choose one of them, leaving it doubtful whether the one he takes is to be rejected or retained
.
tocsubsectionThe Mouse Trap. Treize I will conclude this chapter with the bare mention of another game of cards, known as the mouse trap, the discussion of which involves some rather difficult algebraic analysis.
It is played as follows. A set of cards, marked with the numbers 1, 2, 3..., n , is dealt in any order, face upwards, in the form of a circle. The player begins at any card and counts round the circle always in the same direction. If the k th card has the number k on it--which event is called a hit--the player takes up the card and begins counting afresh. According to Cayley, the player wins if he thus takes up all the cards, and the cards win if at any time the player counts up to n without being able to take up a card.
For example, if a pack of only four cards is used and these cards come in the order, 3214 , then the player would obtain the second card 2 as a hit, next he would obtain 1 as a hit, but if he went on for ever he would not obtain another hit. On the other hand, if the cards in the pack were initially in the order 1423 , the player would obtain successively all four cards in the order 1 , 2 , 3 , 4.
The problem may be stated as the determination of what hits and how many hits can be made with a given number of cards; and what permutations will give a certain number of hits in a certain order.
Cayley (Quarterly Journal of Mathematics, 1878, vol. xv, pp. 8--10.) showed that there are 9 arrangements of a pack of four cards in which no hit will be made, 7 arrangements in which only one hit will be made, 3 arrangements in which only two hits will be made, and 5 arrangements in which four hits will be made.
Prof. Steen (ibid:4Quarterly Journal of Mathematics, vol. xv, pp. 230--241.) has investigated the general theory for a pack of n cards. He has shown how to determine the number of arrangements in which x is the first hit [Arts. 3--5]; the number of arrangements in which 1 is the first hit and x is the second hit [Art. 6]; and the number of arrangements in which 2 is the first hit and x the second hit [Arts. 7--8]; but beyond this point the theory has not been carried. It is obvious that, if there are n-1 hits, the n th hit will necessarily follow.
Treize The French game of treize is very similar. It is played with a full pack of fifty-two cards (knave, queen, and king counting as 11 , 12 , and 13 respectively). The dealer calls out 1, 2, 3..., 13 , as he deals the 1 st, 2 nd, 3 rd, ... , 13 th cards respectively. At the beginning of a deal the dealer offers to lay or take certain odds that he will make a hit in the thirteen cards next dealt.
One of the innumerable forms of patience is played in a similar way.
· · ·
End of part 6 of 16
Continue readingChapter V: Magic Squares
Starvard