CHAPTER X.

MISCELLANEOUS PROBLEMS.
I propose to discuss in this chapter the mathematical theory of a few common mathematical amusements and games. I might have dealt with them in the first four 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; the arrange- ment is, however, based on convenience rather than on any logical distinction.
The majority of the questions here enumerated have no connection one Avith another, and I jot them down almost at random.
I shall discuss in succession the Fifteen Puzzle, the Tower of Hanoi, Chinese Rings, and some miscellaneous Problems connected with a Pack of Cards.
The Fifteen Puzzle*. 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
* Thdi'e are two articles on the subject in the American Journal of Matheviatics, 1879, vol. ii, by Professors Woolsey Johnson and Storey ; but the whole theory is deducible immediately from the proposition I give in the tesct.
CH. X]
MISCELLANEOUS PROBLEMS
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.
D Top of Box C
n 4 1 ta
Bottom of Box
B
We may represent the various stages in the game by sup- posing 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 permu- tation 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 above is deducible from that in the first diagram by six interchanges ; namely, by interchanging the counters 1 and 2,
15
B. R.
226 MISCELLANEOUS PROBLEMS [CH. X
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.
The easiest way of finding the number of simple inter- changes 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
1, 13, 2, 3, 5, 7, 12, 8, 15, 6, 9, 4, 11, 10, 14, and 11, 2, 3, 4, 5, 6, 7, 1, 9, 10, 13, 12, 8, 14, 15.
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 : —
1, 11, 8; 11, 8, 1;
13, 2, 3, 4, 12, 7, 6, 10, 14, 15, 9; 5. 2, 3, 4, 12, 7, 6, 10, 14, 15, 9, 13; 5.
Thus, iLin 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
CH. X] MISCELLANEOUS PROBLEMS
227
to make AB 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
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, to 13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3, 12, 8, 4,
which is equivalent to 13 simple interchanges. Hence it will change the arrangement from one where 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 6, this will be equivalent to changing the order
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 6, to 6, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15:
this is a cyclical interchange of 16 things and therefore is equivalent to 15 simple interchanges. Hence it will change the arrangement from one where a solution is impossible to one where it is possible, and vice versa.
So, too, if it were permissible to turn the 6 and the 9 upside down, thus changing them to 9 and 6 respectively, this would be equivalent to one simple interchange, and therefore would change an arrang:ement where a solution is impossible to one where it is possible.
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 m/i - 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 w 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.
15-2
228 MISCELLANEOUS PROBLEMS [CH. X
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.
The Tower of Hanoi. I may mention next the ingenious puzzle known as the Tower of Hanoi. It was brought out in 1883 by M. Glaus (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 through which a peg can be passed. 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 {i.e. all the discs in their proper order) from the peg on which they initially rested to one of the other pegs.
The method of efiecting 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 G vacant : suppose that this requires x separate transfers, (ii) Next, move the bottom disc to the peg G. (iii) Then, reversing the first process, transfer gradually the n — l discs from B to 0, which will necessitate x transfers. Hence, if it requires oc transfers of simple discs to move a tower of n — 1 discs, then it will require 2^7+1 separate transfers of single discs to move a tower of n discs. Now with 2 discs it requires 3 transfers, i.e. 2^—1 transfers ; hence with 3 discs the number of transfers required will be 2 (2^ - 1) + 1, that is, 2^ - 1. Proceeding in this way we see that with a tower of n discs it will require 2" — 1 transfers of single discs to effect the complete transfer. Thus the eight discs of the puzzle will require 255 single transfers. It will be noticed that every alternate move
CH. X] MISCELLANEOUS PROBLEMS 229
consists of a transfer of the smallest disc from one peg to another, the pegs being taken in cyclical order : further if the discs be numbered consecutively 1, 2, 3, ... beginning with the smallest, all those with odd numbers rotate in one direction, and all those with even numbers in the other direction.
De Parville gave an account of the origin of the toy which is a sufficiently pretty conceit to deserve repetition*. 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 on duty 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 thunderclap the world will vanish. Would that other 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«^-l, 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.
Chinese RiNGSf. A somewhat more elaborate toy, known as Chinese Rings, which is on sale in most English toy-shops,
* La Nature, Paris, 1884, part i, pp. 285—286.
+ It waa described by Cardan in 1550 in his De Subtilitate, bk. xv, paragraph 2, ed. Sponius, vol. iii, p. 587 ; by Wallis in his Algebra, Latin edition, 1693, Opera, vol. ii, chap, cxi, pp. 472—478 ; and allusion is made to it also in Ozanam's Recreations, 1723 edition, vol. iv, p. 439.
230 MISCELLANEOUS PROBLEMS [CH. X
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 J (2**+^ — 1) times or J (2"+^ — 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
CH. X] MISCELLANEOUS PROBLEMS 231
*
the (m + 2)th ring and thus it will require x steps from our initial position to remove the (m+l)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 ring we must arrange the rings so that the (?7i+ 2)th ring is on and the first m 4- 1 rings are off: to effect this, (i) we must get the (m + l)th ring on and the first m rings off, which requires x — \ steps, (ii) then we must put on the (m + 2)th ring, which requires 1 step, (iii) and lastly we must take the (m + l)th ring off, which re- quires x — \ steps: these movements require in all j2 (a? — 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+l)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 the {in-\- l)th ring off, which requires x—\ steps: these movements require [2 (a; — 1) + 1} steps.
Therefore, if when the first in rings are off it requires x steps to take off the {in + l)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(a;- 1) + 1} + 1 + {2 (^- 1) + 1}, that is, is 4a7.
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 ; .'. to take off the first 3 rings requires 4 additional steps ;
^ 4,2
• • >> »» «-' )5 )> ^ 3> ii
In this way we see that the number of steps required to take off the first 2n-\-\ rings is 1 + 4 + 4- -f ... + 4", which is equal to J- ( 22'*+=^-!).
To find the number of steps necessary to take off an even number of rings we proceed in a similar manner.
232 MISCELLANEOUS PROBLEMS [CH. X
To take off the first 2 rings requires 2 steps ; /. to take off the first 4 rings requires 2x4 additional steps ;
• • « » >» " » )J ^ ^ -X 5, f,
In this way we see that the number of steps required to take off the first 2n rings is 2 + (2 x 4) + (2 x 4^) + . . . + (2 x 4^-i), which is equal to | (22"+i - 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^^ and 2''''-'- - 1.
I give the above analysis because it is the direct solution of a problem attacked unsuccessfully by Cardan in 1550 and by WalKs in 1693, and which at one time attracted some attention.
I proceed next to give another solution, more elegant though rather artificial. This, which is due to Monsieur Gros*, 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 re- spectively 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 repre- sented in figure iii is obtained from that in figure i by taking the fourth ring off the bar.
* Theorie du Baguenodier, by L. Gros, Lyons, 1872. I take the account of this from Lucas, vol. i, part 7.
CH. X] MISCELLANEOUS PROBLEMS 233
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 continu- ation, 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 m figure i by adding unity to it. Similarly the number de- noting the position of the rings in figure iii is obtained from the number denoting that in figure i by subtracting unity from it.
O OOP
o o o
o o o o o
OOP
o o o o
^ Q
1101000 1101001 1100111
Figure i. Figure ii. Figure iii.
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^ + 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 2?i 4- 1 rings requires (1 + 2- + . . . + 2-'') steps, that is, i (22^+2 _ j) g^eps ; and to put on a set of 2n rings requires (2 + 2^ + . . . + 2^"~^) steps, that is, J (2""+i - 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 to- gether 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.
234
MISCELLANEOUS PROBLEMS
[CH. X
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.
Initia
. position
After
1st step
>i
2nd „
»
3rd „
ji
4th „
?>
5th „
j>
6th „
jj
7th „
jj
8th „
>j
9th ,,
jy
10th „
o
o
o
o
o
P
o
o
o
1
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
o
L2L
o
o
o
o
o
r^
o
o
o
o
o
o
o
o
10101 10110 1 lOlllJ 11000 11001 1
iioio)
11011 11100 11101 11110
11111.
Problems connected with a Pack of Cards. An ordinary pack of playing cards can be used to illustrate many questions depending on simple properties of numbers, or involving the relative position of the cards. In problems of this kind, 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 re-arrangement is a species of shuffling.
I shall treat in succession of problems connected with Shuffling a Pack, Arrangements hy Rows and Columns, the Determination of a Pair out of ^n{n + l) Pairs, Gergonne's Pile Problem, and the game known as the Mouse Trap.
CH. X] MISCELLANEOUS PROBLEMS 235
Shuffling a Pack. 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 theo:^ of this system of shuffling is due to Monge*. The following are some of the results and are not difficult to prove directly.
If the pack contains Qp + 4 cards, the (2jo 4- 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 18th card will remain the 18th card.
Again, if a pack of 10/) + 2 cards is shuffled in this way, the {2p + l)th and the (6^ + 2)th cards will interchange places. For instance, if an 6carte pack of 32 cards is shuffled as described above, the 7 th and the 20th cards will change places.
More generally, one shuffle of a pack of 2p cards will move the card which was in the o^oth place to the x-fii place, where a^i = -^ (2p -\- Xq-\-V) if Xq is odd, and Xi = \ (2p — Xo + 2) if Xo 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 Xoth. place to the a^^th place, where
2»"+ia;;^ = (4j9 + l)(2"^-^±2"^-2± ... ±2 ± 1) ± 2^o + 2"» ± 1, the sign ± representing an ambiguity of sign.
Again, in any pack of n cards after a certain number of shufflings, not greater than ?i, 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
* Monge's investigations are printed in the Memoires de VAcadimie des Sciences, Paris, 1773, pp. 390 — 412, Among those who have studied the subject afresh I may in particular mention V. Bouniakowski, Bulletin physico-viatMma- tique de St Petersbourg, 1857, vol. xv, pp. 202 — 205, summarised iu the Nouvelles annales de mathematiques, 1858, pp. G6 — 67 ; T. de St Laurent, Memoires de V Academic de Gard, 1865 ; L. Tanner, Educational Times Re})rints, 1880, vol. xxxiii, pp. 73 — 75; M. J. Bourget, Lioxiville's Journal, 1882, pp. 413 — 434; and H. F. Baker, Transactions of the British Association for 1910, pp. 520 — 528.
236 MISCELLANEOUS PROBLEMS [CH. X
the number of shuffles required for a pack of 2p cards, it is sufficient to put oom = ^o ^'Hd find the smallest value of m which satisfies the resulting equation for all values of ccq from 1 to 2p. It follows that, if m is the least number which makes 4"* — 1 divisible by 4p+l, then m shuffles will be required if either 2"* + 1 or 2"* — 1 is divisible by 4p + 1, otherwise 2m shuffles will be required. The number for a pack of 2^ + 1 cards is the same as that for a pack of 2p cards. With an ^cart6 pack of 32 cards, six shuffles are sufficient; with a pack of 2" cards, n + 1 shuffles are sufficient; with a fall pack of 52 cards, twelve shuffles are sufficient; with a pack of 13 cards ten shuffles are sufflcient ; while with a pack of 50 cards fifty shuffles are required ; and so on.
W. H. H. Hudson* 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 posi- tions 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 1st, 2nd, ..., pth. shuffles by the cards Ai, Ao, ..., Ap re- spectively, and that initially the position is occupied by the card J-o- Suppose further that after the ^th shuffle Aq returns to its initial position, therefore Aq = Ap. Then at the second shuffling -ia succeeds ^1 by the same law by which Ai succeeded -4o at the first; hence it follows that previous to the second shuffling A2 must have been in the place occupied by Ai pre- vious to the first. Thus the cards which after the successive shuffles take the place initially occupied by A^ are A^, A3, ..., Ap, All that is, after the pth shuffle Ai has returned to the place initially occupied by it: and so for all the other cards
xi^} ■"■%} •••, -0._p.-i.
Hence the cards At,, A^, ..., Ap 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
• Educational Times Reprints^ London, 1865, vol. 11, p. 105.
CH. X]
MISCELLANEOUS PROBLEMS
237
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 is 180180.
Arrangements by Rows and Columns. A not uncommon trick, which rests on a species of shuffling, depends on the obvious fiict that if n^ 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 trick is 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. For instance, take the
1
5
9 13
2 6
10 14
3
7
11 15
4
8
12 16
1 2 3
4
5 6
8
9 10
11 12
13 14 15 16
Figure L
Figure ii.
238
MISCELLANEOUS PROBLEMS
[CH. X
case of 16 cards. The first and second arrangements may be represented by figures i and ii. Suppose we are told that in figure i the card is in the third row, it must be either 9, 10, 11, 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.
Determination of a selected pair of cards out of 4?i(7i + l) GIVEN PAIRS*. 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 dimen- sions 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
1
4
■
2 9
3
10
5 11
7
1
13
6 8
12 14
15
18
16
19
17 20
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 above.
* Bachet, problem xvii, avertissement, p. 146 et seq.
CH. X] MISCELLANEOUS PROBLEMS 239
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 mih, is mentioned as containing the cards, then the required pair of cards are the mth. and (m+ l)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 pth and the ^th and suppose q>p. Then that one of the required cards which is in the qth line will be the (q — ^)th card which is below the first of the clue squares in the pth. line. The other of the required cards is in the pth 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 + l) cards divided into couples, and dealt in n rows each containing ti + 1 cards ; for there are ^n(n + l) such couples, also there are ^n(n-\-l) 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
240 MISCELLANEOUS PROBLEMS [CH. X
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, iy 0, 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 well- known, but I am not aware who invented them.
Gergonne'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*. 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 trick is mentioned by Bachet, problem xvni, p. 143, but his analysis of it is insufficient.
CH. X] MISCELLANEOUS PROBLEMS 24»1
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 piles 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 br the middle one in the pack, that is, if 27 cards are used it will be the 14th card.
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 7?i"* cards was given by M. Gergonne*. Suppose the pack is arranged in m piles, each containing m^~'^ cards, and that, after the first deal, the pile indicated as containing the selected card is taken up ath ; after the second deal, is taken up 6th ; and so on, and finally after the mth deal, the pile containing the card is taken up kth. Then when the cards are collected after the mth deal the selected card will be nth from the top where
if m is even, n = Jcni^-^ — pi^-^ + ... ^-hni —.a + l, if m is odd, n = hn^"'~'^ — jm''^~' + ... —hm + a.
For example, if a pack of 256 cards (i.e. w = 4) was given, and anyone selected a card out of it, the card could be de- termined by making four successive deals into four piles of 64 cards each, and after each deal asking in which pile the
• Gergonne's Annates de Mathimatiques, Nismes, 1813-4, voL I7, pp. 276 — 283.
B. R. 16
242 MISCELLANEOUS PROBLEMS [CH. X
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 ath, after the second hth, after the third cth, and after the fourth dtli, the card will be the (64>d — 16c + 4ib — a + l)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 + 46 — a + l)th in the pile then indicated as containing it. Thus if a =3, 6 = 4, c = 1, d = 2, it will be the 62nd card in the pile indicated after the fourth deal as containing it and will be the 126th 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 ath, 6th, and cth respectively, then the card will be the (9c — 36 + a)th in the pack or will be the (9 — 36 -}- 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 ath : 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 fi:'om (i), the next 3 cards from (ii), and the remaining 9 — 3a cards from (iii).
CH. X] MISCELLANEOUS PROBLEMS 243
Suppose that the pile now indicated as containing the selected card is taken up hth : then (i) at the top of the pack are 9(6—1) cards; (ii) next are 9 — Sa 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 (6 — 1) cards will be taken from (i), the next S — a cards will be taken from (ii), the next card will be one of the three cards in (iii), and the remaining S — Sh + 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 — 36 + a.)th from the top of that pile. If the process is continued by taking up this pile as cth, then the selected card will come out in the place 9 (c — 1) + (8 — 36 + a) + 1 from the top, that is, will come out as the (9c — 36 + 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, 6=2, c = 2, hence ti = 9c — 36 + a = 14, which is the form in which the trick is usually presented, as was explained above on page 241.
I have shown that if a, 6, 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 ?ith. In this case we have to find values of a, 6, c which will satisfy the equation n = 9c — 36 + ct, where a, 6, c can have only the values 1, 2, or 3.
Hence, if we divide w 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, i.e. p is the next lowest integer to n/3 : then Sp = 9c — 36, therefore ^ = 3c — 6. Hence 6 is
16—2
24
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 22nd from the top, therefore 22 = 9c — 36 + a. The smallest number which must be sub- tracted from 22 to leave a multiple of 3 is 1, therefore a = 1. Hence 22 = 9c -36 + 1, therefore 7 = 3c -6. The smallest number which must be added to 7 to make a multiple of 3 is 2, therefore 6=2. Hence 7 = 3c — 2, therefore c = 3. Thus a = 1, 6 = 2, c = 3.
Again, suppose the card is to come out 21st. Hence 21 = 9c — 36 + a. Therefore a is the smallest number which subtracted from 21 makes a multiple of 3, therefore a = 3. Hence 6 = 3c — 6. Therefore 6 is the smallest number which added to 6 makes a multiple of 3, therefore 6 = 3. Hence 9 = 3c, therefore c = 3. Thus a = 3, 6 = 3, c = 3.
If any difficulty is experienced in this work, we can proceed thus. Let a=fl? + l, 6 = 3 — 3/, c = z-{-l; then x, y, z may have only the values 0, 1, or 2. In this case Gergonne's equation takes the form ^z -\- Zy -\- x — n — 1. Hence, if n — 1 is expressed in the ternary scale of notation, x, y, z will be determined, and therefore a, 6, c will be known.
The rule in the case of a pack of 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, 6, . . . , /j. We can effect this by dividing n continually by m, with the convention that the remainders 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 Im cards can be con- structed. C. T. Hudson and L. E. Dickson* have discussed the general case where such a pack is dealt n times, each time into I piles of m cards ; and they have shown how the piles must be
* 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.
CH. X] MISCELLANEOUS PKOBLEMS 245
taken up in order that after the nth deal the selected card may be rth 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 ecarte pack of 32 cards is dealt into four piles each of 8 cards, and that the pile which contains some selected card is picked up ath. 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.
The 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 A;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
246 MISCELLANEOUS PROBLEMS [CH. X
cards ; and what permutations will give a certain number of hits in a certain order.
Cayley* 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. Steenf 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 Avhich 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 nth hit will necessarily follow.
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 1st, 2nd, 3rd, ..., 13th 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.
* Quarterly Journal of Mathematics , 1878, vol. xv, pp. 8 — 10. t Ibid., vol. XV, pp. 230—241.
247
PAKT 11.
* 1^0 man of science should think it a waste of time to learn something of the history of his own subject ; nor is the investigation of laborious methods now fallen into disuse, or of errors once commonly accepted, the least valuable of mental disciplines."
" The most wo7'thless book of a bygone day is a record worthy of preservation. Like a telescopic star, its obscurity m,ay render it unavailable for most purposes ; but it serves, in hands which know how to use it, to determine the 2^^
(De Morgan.)
24>S