PG26839.B00125
[PDF page 124] 108 MISCELLANEOUS MATHEMATICAL RECREATIONS. [CH. IV that for the same values ofn, we can solve the analogous arrangements of 3m × n girls. To the original theorem J.J. Sylvester* added the corollary that the school of 15 girls could walk out in triplets on13 × 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 ofa abreast can be arranged so that every possible combination ofb of them may walk abreast once and only once has been solved for various cases. Suppose that this greatest number of ways isy. It is obvious that, if all thex girls are to walk out each day in rows ofa abreast, thenx must be an exact multiple ofa and the number of rows formed each day isx/a. If such an arrangement can be made for z days, then we have a solution of the problem to arrangex girls to walk out in rows ofa abreast for z days so that they all go out each day and so that every possible combination ofb 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 ifx = 2n, a = 2, b = 2, in which case y = n(2n − 1), z = 2 n − 1. If we take the casex = 15, a = 3, b = 2, we find y = 35; and it happens that these 35 rows can be divided into7 sets, each of which contains all the symbols; hencez = 7. More generally, ifx = 5 × 3m, 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†in 1850. In the same memoir he also proved that, ifp is a prime, and ifx = pm, a = p, b = 2, then y = ( pm − 1)/(p − 1); if x = ( p2 + p + 1)(p + 1) where p2 + p + 1 has no divisor less thanp + 1, a = p + 1, b = 2, then y = x(x − 1)/p(p + 1); if x = p3 + p + 1, a = p + 1, b = 2, then y = x; * Philosophical Magazine, July, 1850, series 3, vol.xxxvii, p. 52; a solution by Sylvester is given in thePhilosophical Magazine, May, 1861, series 4, vol.xxi, p. 371. † Cambridge and Dublin Mathematical Journal, 1850, vol.v, pp. 255–262.

PG26839.B00126
[PDF page 125] CH. IV] PROBLEMS CONNECTED WITH A PACK OF CARDS. 109 and Sylvester’s result that ifx = 15, a = 3, b = 3, y = 455, z = 91. Three years later Kirkman* solved the problem whenx = 2 n, a = 4, b = 3. Lastly, in 1893, Sylvester† published the solution whenx = 9, a = 3, b = 3, in which casey = 84, z = 28; and stated that a similar method was applicable whenx = 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‡ 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 ofy, if x = 2 n − 1, a = 3, b = 2. Shortly afterwards Mr W. Lea§showed that ifx = 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 wherex is an exact multiple ofa. Problems connected with a Pack of Cards.Imentioned in chapteri that an ordinary pack of playing cards could be used to il- lustrate many tricks depending on simple properties of numbers. Most of these involve the relative position of the cards. The principle of solu- tion generally consists in re-arranging the pack in a particular manner so as to bring the card into some definite position. Any such rearrange- ment is a species of shuffling. I shall treat in succession of problems connected withshuffling a pack, arrangements by rows and columns, the determination of a pair out of 1 2 n(n + 1) pairs, Gergonne’s pile problem, and the game known as the mouse trap. Shuffling a Pack. Any system ofshuffling a pack of cards, if carried out consistently, leads to an arrangement which can be cal- culated; but tricks that depend on it generally require considerable * Ibid., 1853, vol.viii, pp. 38–42. † Messenger of Mathematics, February, 1893, vol.xxii, pp. 159–160. ‡ Educational Times Reprints, London, 1867, vol.viii, pp. 32–33. § Ibid., 1868, vol.ix, pp. 35–36; and 1874, vol.xxii, pp. 74–76; see also the volume for 1869, vol.xi, p. 97.

PG26839.B00127
[PDF page 126] 110 MISCELLANEOUS MATHEMATICAL RECREATIONS. [CH. IV technical skill. Suppose for instance that a pack ofn 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*. The following are some of the results and are not difficult to prove directly. If the pack contains6p + 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, the18th card will remain the 18th card. Again, if a pack of10p+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 of32 cards is shuffled as described above, the7th and the 20th cards will change places. More generally, one shuffle of a pack of2p cards will move the card which was in thex0th place to thex1th place, wherex1 = 1 2(2p+x0+1) if x0 is odd, and x1 = 1 2(2p − x0 + 2) if x0 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 thex0th place to thexmth place where 2m+1xm = (4p + 1)(2m−1 ± 2m−2 ± · · · ±2 ± 1) ± 2x0 + 2m ± 1, the sign ± representing an ambiguity of sign. Again, in any pack ofn cards after a certain number of shufflings, not greater thann, 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 putxm = x0 and find the smallest value of m which satisfies the resulting equation for all values ofx0 from 1 to 2p. It follows that, ifm is the least number which makes4m − 1 divisible by 4p + 1, then m shuffles will be required if either2m + 1or 2m − 1 is divisible by4p + 1, otherwise2m shuffles will be required. The number * Monge’s investigations are printed in theMé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 theNouvelles 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.

PG26839.B00128
[PDF page 127] CH. IV] PROBLEMS CONNECTED WITH A PACK OF CARDS. 111 for a pack of2p+1 cards is the same as that for a pack of2pcards. With an écarté pack of32 cards, six shuffles are sufficient; with a pack of2n cards, n + 1 shuffles are sufficient; with a full pack of52 cards, twelve shuffles are sufficient; with a pack of13 cards ten shuffles are sufficient; while with a pack of50 cards fifty shuffles are required; and so on. Mr 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 ofn cards, the cards will ultimately fall into their initial positions after a number of shufflings not greater than the greatest possiblel.c.m. of all numbers whose sum is n. For suppose that any particular position is occupied after the1st, 2nd, . . ., pth shuffles by the cardsA1, A2, . . . , Ap respectively, and that initially the position is occupied by the cardA0. Suppose further that after thepth shuffleA0 returns to its initial position, thereforeA0 = Ap. Then at the second shufflingA2 succeeds A1 by the same law by which A1 succeeded A0 at the first; hence it follows that previous to the second shuffling A2 must have been in the place occupied byA1 previous to the first. Thus the cards which after the successive shuffles take the place initially occupied byA1 are A2, A3, . . . , Ap, A1; that is, after the pth shuffle A1 has returned to the place initially occupied by it: and so for all the other cardsA2, A3, . . . , Ap−1. Hence the cardsA1, A2, . . . , Ap form a cycle ofp cards, one or other of which is always in one or other ofp positions in the pack, and which go through all their changes inp shufflings. Let the number n of the pack be divided intop, q, r, . . .such cycles, whose sum isn; 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 of52 cards, the greatestl.c.m. of numbers whose sum is 52 will be found by trial to be180180. Arrangements by Rows and Columns. A not uncommon trick, which rests on a species of shuffling, depends on the obvious fact that if n2 cards are arranged in the form of a square ofn 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 * Educational Times Reprints, London, 1865, vol.ii, p. 105.

PG26839.B00129
[PDF page 128] 112 MISCELLANEOUS MATHEMATICAL RECREATIONS. [CH. IV 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Figure i. 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16 Figure ii. 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 either9, 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 either1, 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.

PG26839.B00130
[PDF page 129] CH. IV] PROBLEMS CONNECTED WITH A PACK OF CARDS. 113 Determination of a selected pair of cards out of 1 2 n(n + 1) 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 is10. 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 1 2 3 5 7 4 9 10 11 13 6 12 15 16 17 8 14 18 19 20 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 mth, is mentioned as containing the cards then the required pair of cards are the mth and (m + 1)th cards in that line. These * Bachet, problem xvii, avertissement, p. 146et seq.

PG26839.B00131
[PDF page 130] 114 MISCELLANEOUS MATHEMATICAL RECREATIONS. [CH. IV occupy the clue squares of that line. Next, if two lines are mentioned, then proceed as follows. Let the two lines be thepth and theqth and suppose q > p. Then that one of the required cards which is in theqth line will be the(q −p)th card which is below the first of the clue squares in the pth line. The other of the required cards is in thepth 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 ofn(n + 1)cards divided into couples, and dealt inn rows each containing n + 1cards; for there are1 2 n(n + 1)such couples, also there are 1 2 n(n + 1) homogeneous products of two dimensions which can be formed out ofn things. Bachet gave the diagrams for the cases of20, 30, and42 cards: these the reader will have no difficulty in constructing for himself, and I have enunciated the rule for20 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 sentenceMatas dedit nomen Cocis. This sentence must be imagined as written on the table, each word forming one line, The first card is dealt on theM. The next card (which is the pair of the first) is placed on the secondm in the sentence, that is, third in the third row. The third card is placed on thea. The fourth card (which is the pair of the third) is placed on the seconda, that is, fourth in the first row. Each of the next two cards is placed on at, 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 ana, and similarly each of any of the other pairs by ane, i, o, c, d, m, n, s, or t respectively. Now the sentenceMatas dedit nomen Cociscontains 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

PG26839.B00132
[PDF page 131] CH. IV] PROBLEMS CONNECTED WITH A PACK OF CARDS. 115 can be formed out of four things is20, and of these the number consist- ing of products in which three things are alike and those in which three things are different is8. This leads to a trick with8 trios of things, which is similar to that last given–the cards being arranged in the order indicated by the sentenceLanata levete livini novoto. I believe that these arrangements by sentences are 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 fol- lows. 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 as- sume 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, if27 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. * The trick is mentioned by Bachet, problemxviii, p. 143, but his analysis of it is insufficient.

PG26839.B00133
[PDF page 132] 116 MISCELLANEOUS MATHEMATICAL RECREATIONS. [CH. IV Gergonne’s Generalization.The general theory for a pack ofmm cards was given by M. Gergonne*. Suppose the pack is arranged inm piles, each containing mm−1 cards, and that, after the first deal, the pile indicated as containing the selected card is taken upath; after the second deal, is taken upbth; and so on, and finally after themth 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 = kmm−1 − jmm−2 + · · · + bm − a + 1 , if m is odd, n = kmm−1 − jmm−2 + · · · − bm + a . For example, if a pack of256 cards (i.e. m = 4) was given, and anyoneselectedacardoutofit, thecardcouldbedeterminedbymaking four successive deals into four piles of64 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 upath, after the second bth, after the thirdcth, and after the fourthdth, 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 ifa = 3, b = 4, c = 1, d = 2, it will be the62nd card in the pile indicated after the fourth deal as containing it and will be the126th 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 upath, bth, and cth 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. * Gergonne’sAnnales de Mathématiques, Nismes, 1813–4, vol.iv, pp. 276–283.

PG26839.B00134
[PDF page 133] CH. IV] PROBLEMS CONNECTED WITH A PACK OF CARDS. 117 The method of proof will be illustrated sufficiently by considering the usual case of a pack of twenty-seven cards, for whichm = 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 upath: then (i) at the top of the pack there area − 1 piles each containing nine cards; (ii) next there are9 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 bottom3(a − 1) cards will be taken from (i), the next3 cards from (ii), and the remaining9 − 3a cards from (iii). Suppose that the pile now indicated as containing the selected card is taken up bth: 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 next3 − 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 ascth, then the selected card will come out in the place9(c − 1) + (8− 3b + a) + 1from 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 = 9 c − 3b + a = 14, which is the form in which the trick is usually presented, as was explained above on page 115. I have shown that ifa, b, c are known, thenn is determined. We may modify the rule so as to make the selected card come out in any assigned position, say thenth. In this case we have to find values of a, b, c which will satisfy the equationn = 9 c − 3b + a, where a, b, c can have only the values1, 2, or 3. Hence, if we dividen by 3 and the remainder is1 or 2, this remain- der will bea; but, if the remainder is0, we must decrease the quotient by unity so that the remainder is3, and this remainder will bea. In

PG26839.B00135
[PDF page 134] 118 MISCELLANEOUS MATHEMATICAL RECREATIONS. [CH. IV other wordsa is the smallest positive number (exclusive of zero) which must be subtracted fromn to make the difference a multiple of3. Next let p be this multiple,i.e. p is the next lowest integer ton/3: then 3p = 9c − 3b, thereforep = 3c − b. Hence b is the smallest positive number (exclusive of zero) which must be added top 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 out22nd from the top, therefore22 = 9 c − 3b + a. The smallest number which must be subtracted from22 to leave a multiple of 3 is 1, therefore a = 1. Hence 22 = 9c − 3b + 1, therefore7 = 3c − b. The smallest number which must be added to7 to make a multiple of 3 is 2, therefore b = 2. Hence 7 = 3 c − 2, therefore c = 3. Thus a = 1, b = 2, c = 3. Again, suppose the card is to come out21st. Hence 21 = 9c−3b+a. Therefore a is the smallest number which subtracted from21 makes a multiple of 3, therefore a = 3. Hence 6 = 3 c − 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, ifn − 1 is expressed in the ternary scale of notation, x, y, z will be determined, and thereforea, b, c will be known. The rule in the case of a pack ofmm 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 finda, b, . . . , k. We can ef- fect this by dividingn continually bym, with the convention that the remainder are to be alternately positive and negative and that their numerical values are to be not greater thanm or less than unity. An analogous theorem with a pack oflm cards can be constructed. C.T. Hudson and L.E. Dickson* have discussed the general case where such a pack is dealtn times, each time intol piles ofm cards; and they have shown how the piles must be taken up in order that after thenth deal the selected card may berth from the top. The principle will be sufficiently illustrated by one example treated in a manner analogous to the cases already discussed. For instance, * Educational Times Reprints, 1868, vol.ix, pp. 89–91; andBulletin of the Amer- ican Mathematical Society, New York, April, 1895, vol.i, pp. 184–186.
