# «Contents Ü Foreword Elwyn Berlekamp and Tom Rodgers ½ I Personal Magic ¿ Martin Gardner: A “Documentary” Dana Richards ½¿ Ambrose, Gardner, ...»

During the 1980s, I tried several times to ﬁnd an easy way to generate the solutions. I have now arrived at a reasonably simple approach that turns

** ¾I have not seen these editions.SOME DIOPHANTINE RECREATIONS 227**

out to be essentially a generalisation and extension of Ozanam’s method.

Glaisher’s paper contains most of the ideas involved, but he is so verbose and gives so many pages of tabular examples, special cases, and generalizations that it is often difﬁcult to see where he is going — it is not until the 51st page that he gives the solutions for the problem (10, 30, 50), which he starts considering on the ﬁrst page. He also assumes that the are an arithmetic progression, but it is not until late in the paper that one sees that he solves versions that are not in arithmetic progression by the simple expedient of inserting extra values. By (4) below, this doesn’t change the problem, but I prefer to deal with the original values. Ayyangar [2] gives a much simplied general method for the Indian version of the problem and says many of his solutions are not given by Glaisher’s method on page 19 — although I can’t tell if Glaisher intends this to be a complete solution. Ayyangar’s method is quite similar to my method, so I later sketch his method in my notation and ﬁll in a gap.

Most previous methods yielded solutions involving some choices, subject to some conditions, but did not thoroughly check that all solutions are obtained. No one else has noticed that the number of solutions in the Western version can be readily computed. Indeed, whenever Glaisher gives the number of solutions, he displays or indicates all of them.

Ø person has items to Consider the problem ´ ½ ¾ Ò µ, i.e., the ¾ ¡ ¡ ¡ Ò, and we assume Ò ½ sell. We can reorder them so that ½ to avoid triviality. Let be the number of items that the Ø person sells at the higher price, and let be the number of items that the Ø person sells

**at the lower price. Then we have the following:**

´½µ · ´¾µ · where is the constant amount received. We have ¾Ò · ¿ unknowns connected by these ¾Ò equations. We thus expect a three-dimensional solution set. Normally the objects being sold are indivisible, so we want the numbers to be integers.

Because of the symmetry between and, we can assume and have

## ¾ ¡¡¡ ¾ ¡ ¡ ¡ Ò.

. This makes ½ Ò and ½ assumed (One can reverse and in order to make the s increase, but the amounts sold at the higher price are the smaller numbers and hence are easier to deal with.) ¾ · ¾, we get ´ ½ ¾ µ ´ ¾ ½ µ. Hence From ½ · ½ is a rational number, and we can assume that and are integers with no common factor, i.e., that ´ µ ´ µ ½. This is equivalent to scaling the prices in equations (2) and reduces the dimensionality of the 228 D. SINGMASTER

The Indian Version As mentioned earlier, the Indian version is somewhat different and gives inﬁnitely many solutions. To illustrate, consider the following problem from Bhaskara, used as an example in Ayyangar.

Example instanced by ancient authors: a stanza and a half.

Three traders, having six, eight, and a hundred, for their capitals respectively, bought leaves of betle [or fruit] at an uniform rate; and resold [a part] so: and disposed of the remainder at one for ﬁve panas; and thus became equally rich. What was [the rate of] their purchase? and what was [that of] their sale?

This requires some explanation. Here the numbers are not the numbers of objects, but the capitals (in panas) of each trader. It is assumed that you can buy items per pana, so the the numbers of items will be and our equation (1) becomes ´½¼µ · Further, we are speciﬁcally given the greater price, and it is understood that the lesser price corresponds to selling ¬ items per pana, i.e., ½ ¬, where ¬ is an integer. Ayyangar’s translation of the problem 232 D. SINGMASTER

which is instanced by ancient writers as an example of a solution resting on unconﬁrmed ground, has been by some means reduced to equation; and such a supposition introduced, as has brought out a result in an unrestricted case as in a restricted one. In the like suppositions, when the operation, owing to restriction, disappoints; the answer must by the intelligent be elicited by the exercise of ingenuity.” Amen!

For ease of expression, we let ¬ ¬, so our equations become

## ´½¼¼ µ · ¬¬

References [1] Alcuin. Problems to Sharpen the Young. Translated by John Hadley; annotated by David Singmaster and John Hadley. Math. Gaz. 76,(475), Mar 1992, pp. 102–

126. See No. 16: “De duobus hominibus boves ducentibus — Two men leading oxen.” [2] Ayyangar, A. A. Krishnaswami. “A classical Indian puzzle-problem.” J. Indian Math. Soc. 15, 1923–24, pp. 214–223.

[3] Bachet, Claude-Gaspar. Problemes plaisants & delectables qui se font par les nombres. 1st ed., P. Rigaud, Lyon, 1612; Prob. 21, pp. 106–115.

2nd ed., P. Rigaud, Lyon, 1624; Prob. 24, pp. 178–186..

Revised by A. Labosne, Gauthier-Villars, Paris. 3rd ed., 1874; 4th ed., 1879; 5th ed., 1884. 5th ed. reprinted by Blanchard, Paris, 1959; Prob. 24, pp. 122–126.

[4] Bhaskara, Bijanganita, aka Bhâskara, Bîjaganita, 1150. In: Henry Thomas Colebrooke, trans.; Algebra, with Arithmetic and Mensuration from the Sanscrit of Brahmegupta and Bhascara. John Murray, London, 1817. (There have been several reprints, including Sandig, Wiesbaden, 1973.) Chap. 6, v. 170, pp. 242–244.

[5] Bonnycastle, John. An Introduction to Algebra, with Notes and Observations; designed for the Use of Schools, and Other Places of Public Education, 1782. The ﬁrst nine editions appeared “without any material alterations.” In 1815, he produced a 10 Ø ed., “an entire revision of the work,” which “may be considered as a concise abridgment” of his two-volume Treatise on Algebra, 1813. I examined the 7 Ø edition, J. Johnson, London, 1805, and the 13Ø edition, J. Nunn et al., London, 1824, which may be the same as the 1815 edition.

[6] Bunt, Lucas N. H., et al. The Historical Roots of Elementary Mathematics. PrenticeHall, 1976, p. 33.

[7] Chiu Chang Suan Ching, “Nine Chapters on the Mathematical Art,” c. 150 B.C.;

Translated into German by K. Vogel; Neun Bucher arithmetischer Technik; Vieweg, Braunschweig, 1968. Nos. 10, 12, 13, pp. 86–88.

[8] Diophantos, Arithmetica. In: T. L. Heath; Diophantos of Alexandria; 2nd ed., Oxford University Press, 1910; reprinted by Dover, 1964. Book I, nos. 15, 18, 19, pp. 134–136.

[9] The Demaundes Joyous. Wynken de Worde, London, 1511. Facsimile with transcription and commentary by John Wardroper, Gordon Fraser Gallery, London,

## SOME DIOPHANTINE RECREATIONS 235

1971, reprinted 1976. This is the oldest riddle collection printed in England, surviving in a single example in the Cambridge University Library. Prob. 50, p. 6 of the facsimile, pp. 26–27 of the transcription.[10] Euclid, Opera. Edited by J. L. Heiberg and H. Menge, Teubner, Leipzig, 1916.

Vol. VIII, pp. 286–287.

Fibonacci, aka Leonardo Pisano. Liber Abbaci. (1202); 2 Ò edition, 1228. In: Scritti [11] di Leonardo Pisano, vol. I, edited and published by B. Boncompagni, Rome, 1857, pp. 298–302.

[12] Glaisher, J. W. L. “On certain puzzle-questions occurring in early arithmetical writings and the general partition problems with which they are connected.” Messenger of Mathematics, 53, 1923–24, pp. 1–131.

[13] Alkarkh, Abo^ Beqr Mohammed Ben Alhacen, aka al-Karagi. Untitled manu uscript called “Alfakhrî,” c. 1010. MS 952, Supp. Arabe de la Bibliotheque Imperiale, Paris. Edited into French by Franz Woepcke as “Extrait du Fakhrî,” L’Imprimerie Imperiale, Paris, 1853. Reprinted by Georg Olms Verlag, Hildesheim, 1982. Sect. 3, no. 5, p. 90.

[14] Loyd, Sam. Sam Loyd’s Cyclopedia of 5,000 Puzzles, Tricks and Conundrums. Edited by Sam Loyd II. Lamb Publishing, 1914; Pinnacle or Corwin, 1976, pp. 53 and 346.

[15] Mahavira, aka Mahâvîrâ(cârya). “Ganita-sâra-sangraha,” A.D. 850. Translated by M. Ragacarya. Government Press, Madras, 1912.

[16] Metrodorus (compiler). The Greek Anthology. Translated by W. R. Paton. Loeb Classical Library, Harvard University Press, Cambridge, Mass., and Heinemann, London, 1916–18., Vol. 5.

[17] Ozanam, Jacques. Recreations Mathematiques et Physiques, Paris, 1694 (not seen).

Reprint, Amsterdam, 1696; prob. 24, pp. 79–80. English version: Recreations Mathematical and Physical, R. Bonwick, et al., London, 1708; prob. 24, pp. 68–70.

New edition, edited by Grandin, four vols., C. A. Jombert, Paris, 1725; prob. 28, pp. 201–210.

[18] Sridhara, aka Srîdharâcârya, Pâtîganita, c. 900. Transcribed and translated by K. S. Shukla. Lucknow University, Lucknow, 1959. V. 60-62, ex. 76–77, pp. 44–49 and 94.

[19] Tartaglia, Nicolo. General Trattato di Numeri et Misure. Curtio Troiano, Venice,

1556. Part 1, book 16, prob. 136–139, pp. 256r–256v.

[20] Tropfke, Johannes, Geschichte der Elementarmathematik. Revised by Kurt Vogel, Karin Reich, and Helmuth Gericke. 4 Ø edition, Vol. 1: Arithmetik und Algebra.

De Gruyter, Berlin, 1980.

Who Wins Misère Hex?

Jeffrey Lagarias and Daniel Sleator Hex is an elegant and fun game that was ﬁrst popularized by Martin Gardner [4]. The game was invented by Piet Hein in 1942 and was rediscovered by John Nash at Princeton in 1948.

Two players alternate placing white and black stones onto the hexagons of an Æ ¢ Æ rhombus-shaped board. A hexagon may contain at most one stone.

A game of 7 ¢ 7 Hex after three moves.

White’s goal is to put white stones in a set of hexagons that connect the top and bottom of the rhombus, and Black’s goal is to put black stones in a set of hexagons that connect the left and right sides of the rhombus. Gardner credits Nash with the observation that there exists a winning strategy for the ﬁrst player in a game of hex.

The proof goes as follows. First we observe that the game cannot end in a draw, for in any Hex board ﬁlled with white and black stones there must be either a winning path for white, or a winning path for black [1, 3]. (This fact is equivalent to a version of the Brouwer ﬁxed point theorem, as shown by Gale [3].) Since the game is ﬁnite, there must be a winning strategy for either the ﬁrst or the second player. Assume, for the sake of contradiction, 238 J. LAGARIAS AND D. SLEATOR that the second player has a winning strategy. The ﬁrst player can make an arbitrary ﬁrst move, then follow the winning strategy (reﬂected) for a second player (imagining that the hexagon containing the ﬁrst move is empty).

If the strategy requires the ﬁrst player to move in this non-empty cell, the player simply chooses another empty cell in which to play, and now imagines that this one is empty. Since the extra stone can only help the ﬁrst player, the winning strategy will work, and the ﬁrst player wins. This contradicts our assumption that the second player has a winning strategy. Of course this proof is non-constructive, and an explicit winning strategy for the ﬁrst player is not known.

The purpose of this note is to analyze a variant of Hex that we call Misère Hex. The difference between normal Hex and Misère Hex is that the outcome of the game is reversed: White wins if there is a black chain from left to right, and Black wins if there is a white chain from top to bottom. Misère Hex has also been called Reverse Hex and Rex.

Contrary to one’s intuition, it is not the case that the second player can always win at Misère Hex. In fact, the winner depends on the parity of Æ; on even boards the ﬁrst player can win, and on odd boards the second player can win.

This fact is mentioned in Gardner’s July 1957 column on Hex. Gardner attributes the discovery to Robert Winder, who never published his proof.

As in the case of Hex, the proof of the existance of a winning strategy does not shed any light on what that strategy is. A small step was made in that direction by Ron Evans [2] who showed that for even Æ, the ﬁrst player can win by moving in an acute corner. An abstract theory of “Division games,” which includes Hex and Misère Hex as special cases, was later developed by Yamasaki [5].

Here we present an elementary proof showing who wins Misère Hex. In addition to showing who wins, our result shows that in optimal play the loser can force the entire board to be ﬁlled before the game ends.

Theorem: The ﬁrst player has a winning strategy for Misère Hex on an Æ ¢ Æ board when Æ is even, and the second player has a winning strategy when Æ is odd. Furthermore, the losing player has a strategy that guarantees that every cell of the board must be played before the game ends.

Proof. It sufﬁces to prove the second assertion, because it shows that the parity of the number of cells on the board determines which player has the winning strategy.

Because the game cannot end in a draw, either the second player or the ﬁrst player has a winning strategy. Let È be the player who has a winning strategy, and let É be the other player. For any winning strategy Ä for È WHO WINS Misère HEX? 239 deﬁne Ñ´Äµ to be the minimum (over all possible games of Misère Hex in which È plays strategy Ä) of the number of cells left uncovered at the end of the game. We must show that Ñ´Äµ ¼.

We shall make use of the following monotonicity property of the game.

Consider a terminal position of a game that is a win for É. By deﬁnition, such a position contains a È -path. Suppose the position is modiﬁed by ﬁlling in any subset of the empty cells with É’s stones, and further modiﬁed by changing any subset of É’s stones into È ’s stones. The position is still a win for É, because none of these changes would interfere with the È -path.