WWW.ABSTRACT.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Abstracts, online materials
 
<< HOME
CONTACTS



Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |

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

-- [ Page 20 ] --

During the 1980s, I tried several times to find 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 difficult 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 first 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 fill 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 infinitely 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 five 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 specifically 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 unconfirmed 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 first 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 first 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 first 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 filled 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 fixed point theorem, as shown by Gale [3].) Since the game is finite, there must be a winning strategy for either the first 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 first player can make an arbitrary first move, then follow the winning strategy (reflected) for a second player (imagining that the hexagon containing the first move is empty).

If the strategy requires the first 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 first player, the winning strategy will work, and the first 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 first 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 first 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 first 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 filled before the game ends.

Theorem: The first 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 suffices 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 first 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 define Ѵĵ 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 definition, such a position contains a È -path. Suppose the position is modified by filling in any subset of the empty cells with É’s stones, and further modified 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.



Pages:     | 1 |   ...   | 18 | 19 || 21 | 22 |


Similar works:

«IntAlliance Partners’ Introduction to White Paper Paging networks have been affected by significant market shifts over the past ten years, primarily resulting from the growth and popularity of cellular networks. However, paging networks not only continue to support a wide range of existing services, but are continuing to innovate with a growing number of new services. Extensive regional and national coverage, two-way communications capabilities, and the ability for paging networks to...»

«Documents for General Assembly London 2014 (to be sent to the ISCHE members beforehand and included in the conference packet) 1. Agenda for General Assembly, London 24 July 2014 2. Minutes of General Assembly, Riga 2013 3. Treasurer’s Report 2014 4. Laudation for ISCHE Prize Winners 2014 5. Nominations for Executive Committee 6. ISCHE By-Laws 7. Standing Working Group Reports 8. Standing Working Group Proposals 1. Agenda for General Assembly on 24 July 2014 I. Approval of Agenda II. Approval...»

«DOCUMENT DE TRAVAIL N° 404 HOUSEHOLDS DEBT RESTRUCTURING: EVIDENCE FROM THE FRENCH EXPERIENCE Henri Fraisse and Philippe Frouté October 2012 DIRECTION GÉNÉRALE DES ÉTUDES ET DES RELATIONS INTERNATIONALES DIRECTION GÉNÉRALE DES ÉTUDES ET DES RELATIONS INTERNATIONALES HOUSEHOLDS DEBT RESTRUCTURING: EVIDENCE FROM THE FRENCH EXPERIENCE Henri Fraisse and Philippe Frouté October 2012 Les Documents de travail reflètent les idées personnelles de leurs auteurs et n'expriment pas...»

«Socially Present Board Game Opponents André Pereira, Rui Prada, and Ana Paiva sxiƒgEsh —nd snstituto ƒuperior „é™ni™oD „e™hni™—l …niversity of vis˜onD €ortug—l {andre.a.pereira,rui.prada}@ist.utl.pt,ana.paiva@inesc-id.pt „he re—l ™h—llenge of ™re—ting ˜eliev—˜le —nd enjoy—˜le ˜o—rd Abstract. g—me —rti(™i—l opponents lies no longer in —n—lysing millions of moves per minuteF snste—dD it lies in ™re—ting opponents th—t —re so™i—lly —w—re of their...»

«Contents Committees................................ 2 List of Workshops............................. 5 Program At-a-Glance........................... 7 Detailed Program............................. 12 Monday May 5, 2014........................... 12 Tuesday May 6, 2014........................... 16 Wednesday May 7, 2014......»

«Orākei Local Board Achievements Report 12-month update – July 2012 to June 2013 Contents Orākei Local Board members 5 From the Chair 6-7 Priority 1: Being efficient and protecting our ratepayers’ rights 8-10 Orākei Economic Development Plan 8-9 Remuera Open Space 9 Levels of Service 8 Remuera Open Space 9 Priority 2: Providing better transport options 11-14 Red Light Intersection Cameras 11 Mission Bay Business District Streetscape Upgrade 11 Transport Discretionary Fund 12...»

«Local Area Mobile Computing on Stock Hardware and Mostly Stock Software Terri Watson and Brian N. Bershad School of Computer Science Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 Abstract In the Fall of 1992, the graduate Operating Systems class at Carnegie Mellon University implemented the necessary components to provide applications with a programmable interface to a mobile palmtop computer. The goal of the project was to expose project members to the area of mobile...»

«Noun Incorporation in Blackfoot Joel Dunham University of British Columbia jrwdunham@gmail.com April 7, 2009 Noun incorporation (NI) has long interested linguists due to the fact that it lies at the interface of word formation (morphology) and phrase formation (syntax). Blackfoot, an Algonquian language spoken in Alberta and Montana, has been cited numerous times in the literature as having noun incorporation constructions (Frantz (1971); Mithun (1984); Gerdts (1998); Gerdts (2003)). The...»

«Township of Haverford Climate Change Action Plan Credits and Acknowledgements ICLEI would like to extend thanks to the following individuals who made this report possible: Township of Haverford Board of Commissioners Tom Broido Larry Holmes Jan Marie Rushforth Steve D’Emilio James E. McGarrity Robert E. Trumbull Jeff Heilmann Mario Oliva William F. Wechsler Township of Haverford Environmental Advisory Council Alfred J. Baginski Pamela Kenney Tom Chiomento Carol McCabe Fred Floyd Thomas Morgan...»

«Race, Self-Selection, and the Job Search Process Author(s): Devah Pager and David S. Pedulla Source: American Journal of Sociology, Vol. 120, No. 4 (January 2015), pp. 1005-1054 Published by: The University of Chicago Press Stable URL: http://www.jstor.org/stable/10.1086/681072. Accessed: 13/07/2015 15:37 Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at. http://www.jstor.org/page/info/about/policies/terms.jsp. JSTOR is a not-for-profit...»

«Bridging the gap A guide to the Disabled Students’ Allowances (DSAs) in higher education 2013/14 www.studentfinanceni.co.uk Contents pag e Introduction Do I qualify? et? What help can I g How do I apply? re o How to find out m Introduction Who is this guide for? This guide provides information about the Disabled Students’ Allowances (DSAs) for current and prospective students in higher education who normally live in Northern Ireland. Similar arrangements apply if you live in Scotland,...»

«TALK OF THE TOWN  IMPORTANT DATES:  March 24—April 1— Easter Break (No School) March 25— Good Friday March 28— Easter Monday March 31— Arena Closes April 4— ELECTION DAY (50+ Club) April 8, 9, 10— 26th Semi-Annual Fire School (Multiplex) April 9— Beavers & Cubs Bottle Drive April 9— Bisons Hockey—2016 NHL Playoff Auction Draft (50+ Club) April 10— Summer Student application deadline April 15— Pool Lifeguard application deadline April 23— Dance Recital (Balgonie...»





 
<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.