Sources page biographical material

A B R A C

A B R A

A B R

A B

A
On pp. 39-40 he describes and illustrates an inscription on the Stele of Moschion from Egypt, c300. This is a 39 x 39 square with a Greek text from the middle to the corner, e.g. like the example in the following entry. The text reads: ΟΥIΡIΔIΜΟΥΧIΩΝΥΓIΑΥΘΕIΥΤΟΝΠΟΔΑIΑΤΠΕIΑIΥ which means: Moschion to Osiris, for the treatment which cured his foot. Millington does not ask for the number of ways to read the inscription, which is 4 BC(38,19) = 14 13810 55200.

Curiosities for the Ingenious selected from The most authentic Treasures of E D C D E

Nature, Science and Art, Biography, History, and General Literature. D C B C D

(1821); 2nd ed., Thomas Boys, London, 1822. Remarkable epitaph, C B A B C

p. 97. Word diamond extended to a square, based on 'Silo Princeps Fecit', D C B C D

with the ts at the corners. An example based on 'ABCDEF' is shown E D C D E

at the right. Says this occurs on the tomb of a prince named Silo at the

entrance of the church of San Salvador in Oviedo, Spain. Says the epitaph can be read in 270 ways. I find there are 4 BC(16, 8) = 51490 ways.

In the churchyard of St. Mary's, Monmouth, is the gravestone of John Rennie, died 31 May 1832, aged 33 years. This has the inscription shown below. Further down the stone it gives his son's name as James Rennie. Apparently an N has been dropped to get a message with an odd number of letters. I have good photos. Nothing asks for the number of ways of reading the inscription. I get 4 BC(16,9) = 45760 ways.

eineRnhoJsJohnRenie

ineRnhoJsesJohnReni

neRnhoJseiesJohnRen

eRnhoJseiliesJohnRe

RnhoJseileliesJohnR

nhoJseilereliesJohn

hoJseilerereliesJoh

oJseilereHereliesJo

hoJseilerereliesJoh

nhoJseilereliesJohn

RnhoJseileliesJohnR

eRnhoJseiliesJohnRe

neRnhoJseiesJohnRen

ineRnhoJsesJohnReni

eineRnhoJsJohnRenie
Nuts to Crack I (1832), no. 200. The example from Curiosities for the Ingenious with 'SiloPrincepsFecit', but no indication of what is wanted -- perhaps it is just an amusing picture.

W. Staniforth. Letter. Knowledge 16 (Apr 1893) 74-75. Considers 1 2 3 4 5 6

"figure squares" as at the right. "In how many different ways may 2 3 4 5 6 7

the figures in the square be read from 1 to 11 consecutively?" 3 4 5 6 7 8

He computes the answers for the n x n case for the first few 4 5 6 7 8 9

cases and finds a recurrence. "Has such a series of numbers any 5 6 7 8 9 10

mathematical designation?" The editor notes that he doesn't 6 7 8 9 10 11

know.

J. J. Alexander. Letter. Knowledge 16 (May 1893) 89. Says Staniforth's numbers are the sums of the squares of the binomial coefficients BC(n, k), the formula for which is BC(2n, n). Editor say he has received more than one note pointing this out and cites a paper on such figure squares by T. B. Sprague in the Transactions of the Royal Society of Edinburgh -- ??NYS, no more details provided.

Loyd. Problem 12: The temperance puzzle. Tit Bits 31 (2 & 23 Jan 1897) 251 & 307. Red rum & murder. = Cyclopedia, 1914, The little brown jug, pp. 122 & 355. c= MPSL2, no. 61, pp. 44 & 141. Word diamond based on 'red rum & murder', i.e. the central line is redrum&murder. He allows a diagonal move from an E back to an inner R and this gives 372 paths from centre to edge, making 372² = 138,384 in total.

Dudeney. Problem 57: The commercial traveller's puzzle. Tit Bits 33 (30 Oct & 20 Nov 1897) 82 & 140. Number of routes down and right on a 10 x 12 board. Gives a general solution for any board.

Dudeney. A batch of puzzles. The Royal Magazine 1:3 (Jan 1899) 269-274 & 1:4 (Feb 1899) 368-372. A "Reviver" puzzle. Complicated pattern based on 'reviver'. 544 solutions.

Dudeney. Puzzling times at Solvamhall Castle. London Magazine 7 (No. 42) (Jan 1902) 580 584 & 8 (No. 43) (Feb 1902) 53-56. The amulet. 'Abracadabra' in a triangle with A at top, two B's below, three R's below that, etc. Answer: 1024. = CP, 1907, No. 38, pp. 64-65 & 190. CF Millington at beginning of this section.

Dudeney. CP. 1907.

Prob. 30: The puzzle of the canon's yeoman, pp. 55-56 & 181-182. Word diamond based on 'was it a rat I saw'. Answer is 63504 ways. Solution observes that for a diamond of side n+1, with no diagonal moves, the number of routes from the centre to an edge is 4(2ⁿ-1) and the number of ways to spell the phrase is this number squared. Analyses four types with the following central lines: A   'yoboy'; B - 'level'; C - 'noonoon'; D   'levelevel'.

In A, one wants to spell 'boy', so there are 4(2ⁿ-1) solutions.

In  B, one wants to spell 'level' and there are [4(2ⁿ-1)]² solutions.

In C, one wants to spell 'noon' and there are 8(2ⁿ-1) solutions.

In D, one wants to spell 'level' and there are complications as one can start and finish at the edge. He obtains a general formula for the number of ways. Cf Loyd, 1914.

Prob. 38: The amulet, pp. 64-65 & 190. See: Dudeney, 1902.

Pearson. 1907. Part II: A magic cocoon, p. 147. Word diamond based on 'cocoon', so the central line is noocococoon. Because one can start at the non central Cs, and can go in as well as out, I get 948 paths. He says 756.

Loyd. Cyclopedia. 1914. Alice in Wonderland, pp. 164 & 360. = MPSL1, no. 109, pp. 107 & 161 162. Word diamond based on 'was it a cat I saw'. Cf Dudeney, 1907.

Dudeney. AM. 1917.

Prob. 256: The diamond puzzle, pp. 74 & 202. Word diamond based on 'dnomaidiamond'. This is type A of his discussion in CP and he states the general formula. 252 solutions.

Prob. 257: The deified puzzle, pp. 74-75 & 202. Word diamond based on 'deifiedeified'. This is type D in CP and has 1992 solutions. He says 'madamadam' gives 400 and 'nunun' gives 64, while 'noonoon' gives 56.

Prob. 258: The voter's puzzle, pp. 75 & 202. Word diamond built on 'rise to vote sir'. Cites CP, no. 30, for the result, 63504, and the general formula.

Prob. 259: Hannah's puzzle, pp. 75 & 202. 6 x 6 word square based on 'Hannah' with Hs on the outside, As adjacent to the Hs and four Ns in the middle. Diagonal moves allowed. 3468 ways.

Wood. Oddities. 1927. Prob. 44: The amulet problem, p. 39. Like the original ABRACADABRA triangle, but with the letters in reverse order.

Collins. Book of Puzzles. 1927. The magic cocoon puzzle, pp. 169-170. As in Pearson.

Loyd Jr. SLAHP. 1928. A strolling pedagogue, pp. 38 & 97. Number of routes to opposite corner of a 5 x 5 array of points.

D. F. Lawden. On the solution of linear difference equations. MG 36 (No. 317) (Sep 1952) 193-196. Develops use of integral transforms and applies it to find that the number of king's paths going down or right or down right from (0, 0) to (n, n) is P_n(3) where P_n(x) is the Legendre polynomial.

Leo Moser. King paths on a chessboard. MG 39 (No. 327) (Feb 1955) 54. Cites Lawden and gives a simpler proof of his result P_n(3).

Anon. Puzzle Page: Check this. MTg 36 (1964) 61 & 27 (1964) 65. Find the number of king's routes from corner to corner when he can only move right, down or right down. Gets 48,639 routes on 8 x 8 board.

Ripley's Puzzles and Games. 1966. P. 32. Word diamond laid out differently so A A A

one has to read from one side to the opposite side. Rotating by 45^o, one gets B B 

the pattern at the right for edge three. One wants the number of ways to C C C

read ABCDEF. In general, when the first line of As has n positions, D D 

the total number of ways to reach the first row is n. For each successive E E E

row, the total number is alternately twice the number for the previous row less F F 

twice the end term of that row or just twice the the number for the previous

row. In our example with n = 3, the number of ways to reach the second row is 4 = 2x3 - 2x1. The number of ways to reach the third row is 8 = 2x4. The number of ways to reach the fourth row is 12 = 2x8 - 2x2, then we get 24 = 2 x 12; 36 = 2x24   2x6. It happens that the first n end terms are the central binomial coefficients BC(2k,k), so this is easy to calculate. I find the total number of routes, for n = 2, 3, ..., 7, is 4, 18, 232, 1300, 6744, 33320, the last being the desired and given answer for the given problem.

Pál Révész. Op. cit. in 5.I.1. 1969. On p. 27, he gives the number of routes for a king moving forward on a chessboard and a man moving forward on a draughtsboard.

Putnam. Puzzle Fun. 1978. No. 8: Level - level, pp. 3 & 26. Form a wheel of 16 points labelled LEVELEVELEVELEVE. Place 4 Es inside, joined to two consecutive Vs and the intervening L. Then place a V in the middle, joined to these four Es. How many ways to spell LEVEL? He gets 80, which seems right.
5.Z. CHESSBOARD PLACING PROBLEMS
See MUS I 285-318, some parts of the previous chapter and the Appendix in II 351-360. See also 5.I.1, 6.T.

There are three kinds of domination problems.

In strong domination, a piece dominates the square it is on.

In weak domination, it does not, hence more pieces may be needed to dominate the board.

Non attacking domination is strong domination with no piece attacking another. Graph theorists say the pieces are independent. This also may require more pieces than strong domination, but it may require more or fewer pieces than weak domination.

The words 'guarded' or 'protected' are used for weak domination, but 'unguarded' or 'unprotected' may mean either strong or non attacking domination.

Though these results seem like they must be old, the ideas seem to have originated with the eight queens problem, c1850, (cf 5.I.1) and to have been first really been attacked in the late 19C. There are many variations on these problems, e.g. see Ball, and I will not attempt to be complete on the later variations. In recent years, this has become a popular subject in graph theory, where the domination number, γ(G), is the size of the smallest strongly dominating set on the graph G and the independent domination number, i(G), is the size of the smallest non-attacking (= independent) dominating set.

Mario Velucchi has a web site devoted to the non-dominating queens problem and related sites for similar problems. See: http://www.bigfoot.com/~velucchi/papers.html and http://www.bigfoot.com/~velucchi/biblio.html.

Ball. MRE, 3rd ed., 1896, pp. 109-110: Other problems with queens. Says: "Captain Turton has called my attention to two other problems of a somewhat analogous character, neither of which, as far as I know, has been hitherto published, ...." These ask for ways to place queens so as to attack as few or as many cells as possible -- see 5.Z.2.

Ball. MRE, 4th ed., 1905, pp. 119-120: Other problems with queens; Extension to other chess pieces. Repeats above quote, but replaces 'hitherto published' by 'published elsewhere', extends the previous text and adds the new section.

Ball. MRE, 5th ed., 1911. Maximum pieces problem; Minimum pieces problem, pp. 119 122. [6th ed., 1914 adds that Dudeney has written on these problems in The Weekly Dispatch, but this is dropped in the 11th ed. of 1939.] Considerably generalizes the problems. On the 8 x 8 board, the maximum number of non-attacking kings is 16, queens is 8, bishops is 14 [6th ed., 1914, adds there are 256 solutions], knights is 32 with 2 solutions and rooks is 8 with 8⁸ solutions [sic, but changed to 8! in the 6th ed.]. The minimum number of pieces to strongly dominate the board is 9 kings, 5 queens with 91 inequivalent solutions [the 91 is omitted in the 6th ed., since it is stated later], 8 bishops, 12 knights, 8 rooks. The minimum number of pieces to weakly dominate the board is 5 queens, 10 bishops, 14 knights, 8 rooks.

Dudeney. AM. 1917. The guarded chessboard, pp. 95 96. Discusses different ways pieces can weakly or non attackingly dominate n x n boards.

G. P. Jelliss. Multiple unguard arrangements. Chessics 13 (Jan/Jun 1982) 8 9. One can have 16 kings, 8 queens, 14 bishops, 32 knights or 8 rooks non attackingly placed on a 8 x 8 board. He considers mixtures of pieces -- e.g. one can have 10 kings and 4 queens non attacking. He tries to maximize the product of the numbers of each type in a mixture -- e.g. scoring 40 for the example.
5.Z.1. KINGS
Ball. MRE, 4th ed., 1905. Other problems with queens; Extension to other chess pieces, pp. 119-120. Says problems have been proposed for k kings on an n x n, citing L'Inter. des math. 8 (1901) 140, ??NYS.

Gilbert Obermair. Denkspiele auf dem Schachbrett. Hugendubel, Munich, 1984. Prob. 27, pp. 29 & 58. 9 kings strongly, and 12 kings weakly, dominate an 8 x 8 board.

5.Z.2. QUEENS
Here the graph is denoted Q_n, but I will denote γ(Q_n) by γ(n) and i(Q_n) by i(n).
Murray. Pp. 674 & 691. CB249 (c1475) shows 16 queens weakly dominating an 8 x 8 board, but the context is unclear to me.

de Jaenisch. Op. cit. in 5.F.1. Vol. 3, 1863. Appendice, pp. 244-271. Most of this is due to "un de nos anciens amis, M^r de R***". Finds and describes the 91 ways of placing 5 queens so as to non-attackingly dominate the 8 x 8 board. Then considers the n x n board for n = 2, ..., 7 with strong and non-attacking domination. Up through 5, he gives the number of pieces being attacked in each solution which allows one to determine the weak solutions. For n < 6, he gets the answers in the table below, but for n = 6, he gets 21 non-attacking solutions instead of 17?.

Ball. MRE, 3rd ed., 1896. Other problems with queens, pp. 109-110. "Captain [W. H.] Turton has called my attention to two other problems of a somewhat analogous character, neither of which, as far as I know, has been hitherto published, or solved otherwise than empirically." The first is to place 8 queens so as to strongly dominate the fewest squares. The minimum he can find is 53. (Cf Gardner, 1999.) The second is to place m queens, m  5, so as to strongly dominate as many cells as possible. With 4 queens, the most he can find is 62.

Dudeney. Problem 54: The hat peg puzzle. Tit Bits 33 (9 & 30 Oct 1897) 21 & 82. Problem involves several examples of strong domination by 5 queens on an 8 x 8 board leading to a non attacking domination. He says there are just 728 such. This = 8 x 91. = Anon. & Dudeney; A chat with the Puzzle King; The Captain 2 (Dec? 1899) 314-320; 2:6 (Mar 1900) 598-599 & 3:1 (Apr 1900) 89. = AM; 1917; pp. 93-94 & 221.

Ball. MRE, 4th ed., 1905, loc. cit. in 5.Z.1. Extends 3rd ed. by asking for the minimum number of queens to strongly dominate a whole n x n board. Says there seem to be 91 ways of having 5 non-attacking queens on the 8 x 8, citing L'Inter. des Math. 8 (1901) 88, ??NYS.

Ball. MRE, 5th ed., 1911, loc. cit. in 5.Z. On pp. 120-122, he considers queens and states the minimum numbers of queens required to strongly dominate the board and the numbers of inequivalent solutions for 2 x 2, 3 x 3, ..., 7 x 7, citing the article cited in the 4th ed. and Jaenisch, 1862, without a volume number. For n = 7, he gives the same unique solution for strongly dominating as for non-attacking dominating. [In the 6th ed., this is corrected and he says it is a solution.] He says Jaenisch also posed the question of the minimum number of non-attacking queens to dominate the board and gives the numbers and the number of inequivalent ways for the 4 x 4, .., 8 x 8, except that he follows Jaenisch in stating that there are 21 solutions on the 6 x 6. [This is changed to 17 in the 6th ed.]

Dudeney. AM. 1917. Loc. cit. in 5.Z. He uses 'protected' for 'weakly', but he seems to copy the values for 'strongly' from Jaenisch or Ball. His 'not protected' seems to mean 'non-attacking'. However, some values are different and I consequently am very uncertain as to the correct values??

Pál Révész. Op. cit. in 5.I.1. 1969. On pp. 24 25, he shows 5 queens are sufficient to strongly dominate the board and says this is minimal.

Below, min. denotes the minimum number of queens to dominate and no. is the number of inequivalent ways to do so.
STRONG WEAK NON-ATTACKING

n min. no. min. no. min. no.

1 1 1 0 0 1 1

2 1 1 2 2 1 1

3 1 1 2 5 1 1

4 2 3 2 3 3 2

5 3 37 3 15 3 2

6 3 1 4 2 4 17?

7 4 4 5? 4 1

8 5 150 5 41 5 91

Rodolfo Marcelo Kurchan, proposer; Henry Ibstedt & proposer, solver. Prob. 1738 -- Queens in space. JRM 21:3 (1989) 220 & 22:3 (1989) 237. How many queens are needed to strongly dominate an n x n x n cubical board? For n = 3, 4, ..., 9, the best known numbers are: 1, 4, 6, 8, 14, 20, 24. The solution is not clear if these are minimal, but it seems to imply this.

Martin Gardner. Chess queens and maximum unattacked cells. Math Horizons (Nov 1999). Reprinted in Workout, chap. 34. Considers the problem of Turton described in Ball, 3rd ed, above: place 8 queens on an 8 x 8 board so as to strongly dominate the fewest squares. That is, leave the maximum number of unattacked squares. More generally, place k queens on an n x n board to leave the maximum number of unattacked squares. He describes a simple problem by Dudeney (AM, prob. 316) and recent work on the general problem. He cites Velucchi, cf below, who provides the following table of maximum numbers of unattacked cells and number of solutions for the maximum. I'm not sure if some of these are still only conjectured.

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

Max 0 0 0 1 3 5 7 11 18 22 30 36 47 56 72 82 97

Sols 0 0 0 25 1 3 38 7 1 1 2 7 1 4 3 1
Mario Velucchi has a web site devoted to the non-dominating queens problem and related sites for similar problems. See: http://www.bigfoot.com/~velucchi/papers.html and http://www.bigfoot.com/~velucchi/biblio.html.

A. P. Burger & C. M. Mynhardt. Symmetry and domination in queens graphs. Bull. Inst. Combinatorics Appl. 29 (May 2000) 11-24. Extends results to n = 30, 45, 69, 77. Summarizes the field, with 14 references, several being earlier surveys. The table below gives all known values. It will be seen that the case n = 4k + 1 seems easiest to deal with. The values separated by strokes, /, indicate cases where the value is one of the two given values, but it is not known which.

n 4 5 6 7 8 9 10 11 12 13 14 15 16 17

γ(n) 2 3 3 4 5 5 5 5 6 7 7/8 8/9 8/9 9

i(n) 3 3 4 4 5 5 5 5 7 7 8 9 9 9
n 18 19 21 25 29 30 31 33 37 41 45 49 53 57

γ(n) 9 10 11 13 15 15 16 17 19 21 23 25 27 29

i(n) 11 13 17 23
n 61 69 77

γ(n) 31 35 39

5.Z.3. BISHOPS
Dudeney. AM. 1917. Prob. 299: Bishops in convocation, pp. 89 & 215. There are 2ⁿ ways to place 2n 2 bishops non attackingly on an n x n board. At loc. cit. in 5.Z, he says that for n = 2, ..., 8, there are 1, 2, 3, 6, 10, 20, 36 inequivalent placings.

Pál Révész. Op. cit. in 5.I.1. 1969. On pp. 25 26, he shows the maximum number of non attacking bishops on one colour is 7 and there are 16 ways to place them.

Obermair. Op. cit. in 5.Z.1. 1984. Prob. 17, pp. 23 & 50. 8 bishops strongly, and 10 bishops weakly, dominate the 8 x 8 board.
5.Z.4. KNIGHTS
Ball. MRE, 4th ed., 1905. Loc. cit. in 5.Z.1. Says questions as to the maximum number of non-attacking knights and minimum number to strongly dominate have been considered, citing L'Inter. des math. 3 (1896) 58, 4 (1897) 15-17 & 254, 5 (1898) 87 [5th ed. adds 230 231], ??NYS.

Dudeney. AM. 1917. Loc. cit. in 5.Z. Notes that if n is odd, one can have (n²+1)/2 non attacking knights in one way, while if n is even, one can have n²/2 in two equivalent ways.

Irving Newman, proposer; Robert Patenaude, Ralph Greenberg and Irving Newman, solvers. Problem E1585 -- Nonattacking knights on a chessboard. AMM 70 (1963) 438 & 71 (1964) 210-211. Three easy proofs that the maximum number of non-attacking knights is 32. Editorial note cites Dudeney, AM, and Ball, MRE, 1926, p. 171 -- but the material is on p. 171 only in the 11th ed., 1939.

Gardner. SA (Oct 1967, Nov 1967 & Jan 1968) c= Magic Show, chap. 14. Gives Dudeney's results for the 8 x 8. Golomb has noted that Greenberg's solution of E1585 via a knight's tour proves that there are only two solutions. For the k x k board, k = 3, 4, ..., 10, the minimal number of knights to strongly dominate is: 4, 4, 5, 8, 10, 12, 14, 16. He says the table may continue: 21, 24, 28, 32, 37. Gives numerous examples.

Obermair. Op. cit. in 5.Z.1. 1984. Prob. 16, pp. 21 & 47. 14 knights are necessary for weak domination of the 8x8 board.

E. O. Hare & S. T. Hedetniemi. A linear algorithm for computing the knight's domination number of a k x n chessboard. Technical report 87 May 1, Dept. of Computer Science, Clemson University. 1987?? Pp. 1 2 gives the history from 1896 and Table 2 on p. 13 gives their optimal results for strong domination on k x n boards, 4  k  9, k  n  12 and also for k = n = 10. For the k x k board, k = 3, ..., 10, they confirm the results in Gardner.

Anderson H. Jackson & Roy P. Pargas. Solutions to the N x N knight's cover problem. JRM 23:4 (1991) 255-267. Finds number of knights to strongly dominate by a heuristic method, which finds all solutions up through N = 10. Improves the value given by Gardner for N = 15 to 36 and finds solutions for N = 16, ..., 20 with 42, 48, 54, 60, 65 knights.
5.Z.5. ROOKS
É. Lucas. Théorie des Nombres. Gauthier Villars, Paris, 1891; reprinted by Blanchard, Paris, 1958. Section 128, pp. 220 223. Determines the number of inequivalent placings of n nonattacking rooks on an n x n board in general and gives values for n  12. For n = 1, ..., 8, there are 1, 1, 2, 7, 23, 115, 694, 5282 inequivalent ways.

Dudeney. AM. 1917. Loc. cit. at 5.Z. Notes there are n! ways to place n non attacking rooks and asks how many of these are inequivalent. Gives values for n = 1, ..., 5. AM prob. 296, pp. 88 & 214, is the case n = 4.

D. F. Holt. Rooks inviolate. MG 58 (No. 404) (Jun 1974) 131 134. Uses Burnside's lemma to determine the number of inequivalent solutions in general, getting Lucas' result in a more modern form.
5.Z.6. MIXTURES
Ball. MRE, 5th ed., 1911. Loc. cit. in 5.Z. P. 122: "There are endless similar questions in which combinations of pieces are involved." 4 queens and king or queen or bishop or knight or rook or pawn can strongly dominate 8 x 8.

King. Best 100. 1927.

No. 77, pp. 30 & 57. 4 queens and a rook strongly dominate 8 x 8.

No. 78, pp. 30 & 57. 4 queens and a bishop strongly dominate 8 x 8.

5.AA. CARD SHUFFLING
New section. I have been meaning to add this sometime, but I have just come across an expository article, so I am now starting. The mathematics of this gets quite formidable. See 5.AD for a somewhat related topic.

A faro, weave, dovetail or perfect (riffle) shuffle starts by cutting the deck in half and then interleaving the two halves. When the deck has an even number of cards, there are two ways this can happen -- the original top card can remain on top (an out shuffle) or it can become the second card of the shuffled deck (an in shuffle). E.g. if our deck is 123456, then the out shuffle yields 142536 and the in shuffle yields 415263. Note that removing the first and last cards converts an out shuffle on 2n cards to an in shuffle on 2n-2 cards. When the deck has an odd number of cards, say 2n+1, we cut above or below the middle card and shuffle so the top of the larger pile is on top, i.e. the larger pile straddles the smaller. If the cut is below the middle card, we have piles of n+1 and n and the top card remains on top, while cutting above the middle card leaves the bottom card on bottom. Removing the top or bottom card leaves an in shuffle on 2n cards.

Monge's shuffle takes the first card and then alternates the next cards over and under the resulting pile, so 12345678 becomes 86421357.

At G4G2, 1996, Max Maven gave a talk on some magic tricks based on card shuffling and gave a short outline of the history. The following is an attempt to summarise his material. The faro shuffle, done by inserting part of the deck endwise into the other part, but not done perfectly, began to be used in the early 18C and a case of cheating using this is recorded in 1726. The riffle shuffle, which is the common American shuffle, depends on mass produced cards of good quality and began to be used in the mid 19C. However, magicians did not become aware of the possibilities of the perfect shuffle until the mid 20C, despite the early work of Stanyans C. O. Williams and Charles T. Jordan in the 1910s.

Hooper. Rational Recreations. Op. cit. in 4.A.1. 1774. Vol. 1, pp. 78-85: Of the combinations of the cards. This describes a shuffle, where one takes the top two cards, then puts the next two cards on top, then the next three cards underneath, then the next two on top, then the next three underneath. For ten cards 1234567890, it produces 8934125670, a permutation of order 7. Tables of the first few repetitions are given for 10, 24, 27 and 32 cards, having orders 7, 30, 30, 156.

The Secret Out. 1859. Permutation table, pp. 394-395 (UK: 128-129). Describes Hooper's shuffle for ten cards.

Bachet-Labosne. Problemes. 3rd ed., 1874. Supp. prob. XV, 1884: 214-222. Discusses Monge's shuffle and its period.

John Nevil Maskelyne. Sharps and Flats. 1894. ??NYS -- cited by Gardner in the Addendum of Carnival. "One of the earliest mentions". Called the "faro dealer's shuffle".

Ahrens. MUS I. 1910. Ein Kartenkunststück Monges, pp. 152-145. Expresses the general form of Monge's shuffle and finds its order for n = 1, 2, ..., 10. Mentions the general question of finding the order of a shuffle.

Charles T. Jordan. Thirty Card Mysteries. The author, Penngrove, California, 1919 (??NYS), 2nd ed., 1920 (?? I have copy of part of this). Cited by Gardner in the Addendum to Carnival. First magician to apply the shuffle, but it was not until late 1950s that magicians began to seriously use and study it. The part I have (pp. 7-10) just describes the idea, without showing how to perform it. The text clearly continues to some applications of the idea. This material was reprinted in The Bat (1948-1949).

Frederick Charles Boon. Shuffling a pack of cards and the theory of numbers. MG 15 (1930) 17-20. Considers the Out shuffle and sees that it relates to the order of 2 (mod 2n+1) and gives some number theoretic observations on this. Also considers odd decks.

J. V. Uspensky & M. A. Heaslet. Elementary Number Theory. McGraw-Hill, NY, 1939. Chap. VIII: Appendix: On card shuffling, pp. 244-248. Shows that an In shuffle of a deck of 2n cards takes the card in position i to position 2i (mod 2n+1), so the order of the permutation is the exponent or order of 2 (mod 2n+1), which is 52 when n = 26. [Though not discussed, this shows that the order of the Out shuffle is the order of 2 (mod 2n-1), which is only 8 for n = 26. And the order of a shuffle of 2n+1 cards is the order of 2 (mod 2n+1).] Monge's shuffle is more complex, but leads to congruences (mod 4n+1) and has order equal to the smallest exponent e such that 2^e  ±1 (mod 4n+1), which is 12 for n = 26.

T. H. R. Skyrme. A shuffling problem. Eureka 7 (Mar 1942) 17-18. Describes Monge's shuffle with the second card going under or over the first. Observes that in the under shuffle for an even number of cards, the last card remains fixed, while the over shuffle for an odd number of cards also leaves the last card fixed. By appropriate choice, one always has the n-th card becoming the first. Finds the order of the shuffle essentially as in Uspensky & Heaslet. Makes some further observations.

N. S. Mendelsohn, proposer and solver. Problem E792 -- Shuffling cards. AMM 54 (1947) 545 ??NYS & 55 (1948) 430-431. Shows the period of the out shuffle is at most 2n-2. Editorial notes cite Uspensky & Heaslet and MG 15 (1930) 17-20 ??NYS.

Charles T. Jordan. Trailing the dovetail shuffle to its lair. The Bat (Nov, Dec 1948; Jan, Feb, Mar, 1949). ??NYS -- cited by Gardner. I have No. 59 (Nov 1948) cover & 431-432, which reprints some of the material from his book.

Paul B. Johnson. Congruences and card shuffling. AMM 63 (1956) 718-719. ??NYS -- cited by Gardner.

Alexander Elmsley. Work in Progress. Ibidem 11 (Sep 1957) 222. He had previously coined the terms 'in' and 'out' and represented them by I and O. He discovers and shows that to put the top card into the k th position, one writes k-1 in binary and reads off the sequence of 1s and 0s, from the most significant bit, as I and O shuffles. He asks but does not solve the question of how to move the k-th card to the top -- see Bonfeld and Morris.

Alexander Elmsley. The mathematics of the weave shuffle, The Pentagram 11:9 (Jun 1957) 70 71; 11:10 (Jul 1957) 77-79; 11:11 (Aug 1957) 85; 12 (May 1958) 62. ??NYR -- cited by Gardner in the bibliography of Carnival, but he doesn't give the Ibidem reference in the bibliography, so there may be some confusion here?? Morris only cites Pentagram.

Solomon W. Golomb. Permutations by cutting and shuffling. SIAM Review 3 (1961) 293 297. ??NYS -- cited by Gardner. Shows that cuts and the two shuffles generate all permutations of an even deck. However, for an odd deck of n cards, the two kinds of shuffles can be intermixed and this only changes the cyclic order of the result. Since cutting also only changes the cyclic order, the number of possible permutations is n times the order of the shuffle.

Gardner. SA (Oct 1966) = Carnival, chap. 10. Defines the in and out shuffles as above and gives the relation to the order of 2. Notes that it is easier to do the inverse operations, which consist of extracting every other card. Describes Elmsley's method. Addendum says no easy method is known to determine shuffles to bring the k th card to the top.

Murray Bonfeld. A solution to Elmsley's problem. Genii 37 (May 1973) 195-196. Solves Elmsley's 1957 problem by use of an asymmetric in-shuffle where the top part of the deck has 25 cards, so the first top card becomes second and the last two cards remain in place. (If one ignores the bottom two cards this is an in-shuffle of a 50 card deck.)

S. Brent Morris. The basic mathematics of the faro shuffle. Pi Mu Epsilon Journal 6 (1975) 86-92. Obtains basic results, getting up to Elmsley's work. His reference to Gardner gives the wrong year.

Israel N. Herstein & Irving Kaplansky. Matters Mathematical. 1974; slightly revised 2nd ed., Chelsea, NY, 1978. Chap. 3, section 4: The interlacing shuffle, pp. 118-121. Studies the permutation of the in shuffle, getting same results as Uspensky & Heaslet.

S. Brent Morris. Faro shuffling and card placement. JRM 8:1 (1975) 1-7. Shows how to do the faro shuffle. Gives Elmsley's and Bonfeld's results.

Persi Diaconis, Ronald L. Graham & William M. Kantor. The mathematics of perfect shuffles. Adv. Appl. Math. 4 (1983) 175-196. ??NYS.

Steve Medvedoff & Kent Morrison. Groups of perfect shuffles. MM 60:1 (1987) 3-14. Several further references to check.

Walter Scott. Mathematics of card sharping. M500 125 (Dec 1991) 1-7. Sketches Elmsley's results. States a peculiar method for computing the order of 2 (mod 2n+1) based on adding translates of the binary expansion of 2n+1 until one obtains a binary number of all 1s. The number of ones is the order a and the method is thus producing the smallest a such that 2^a-1 is a multiple of 2n+1.

John H. Conway & Richard K. Guy. The Book of Numbers. Copernicus (Springer-Verlag), NY, 1996. Pp. 163-165 gives a brief discussion of perfect shuffles and Monge's shuffle.

5.AB. FOLDING A STRIP OF STAMPS
É. Lucas. Théorie des Nombres. Gauthier Villars, Paris, 1891; reprinted by Blanchard, Paris, 1958. P. 120.

Exemple II -- La bande de timbres-poste. -- De combien de manières peut-on replier, sur un seul, une bande de p timbres-poste?

Exemple III -- La feuille de timbres-poste. -- De combien de manières peut-on replir, sur un seul, une feuille rectangulaire de pq timbres-poste?

"Nous ne connaissons aucune solution de ces deux problèmes difficiles proposés par M. Em. Lemoine."

M. A. Sainte-Laguë. Les Réseaux (ou Graphes). Mémorial des Sciences Mathématiques, fasc. XVIII. Gauthier-Villars, Paris, 1926. Section 62: Problème des timbres-poste, pp. 39 41. Gets some basic results and finds the numbers for a strip of n, n = 1, 2, ..., 10 as: 1, 2, 6, 16, 50, 144, 448, 7472, 17676, 41600.

Jacques Devisme. Contribution a l'étude du problème des timbres-poste. Comptes-Rendus du Deuxième Congrès International de Récréation Mathématique, Paris, 1937. Librairie du "Sphinx", Bruxelles, 1937, pp. 55-56. Cites Lucas (but in the wrong book!) and Sainte-Laguë. Studies the number of different forms of the result, getting numbers: 1, 2, 3, 8, 18, 44, 115, 294, 783.

5.AC. PROPERTIES OF THE SEVEN BAR DIGITAL DISPLAY

┌─┐ 2

The seven bar display, in the form of a figure 8, as at the right, is │ │ 1 3

now the standard form for displaying digits on calculators, clocks, etc. ├─┤ 4

This lends itself to numerous problems of a combinatorial/numerical │ │ 5 7

New Section. └─┘ 6