From rjc@maths.ex.ac.uk Fri Nov 6 09:31:39 CST 1998 Article: 219444 of sci.math Path: news.math.niu.edu!husk.cso.niu.edu!vixen.cso.uiuc.edu!howland.erols.net!news.maxwell.syr.edu!nntp2.dejanews.com!nnrp1.dejanews.com!not-for-mail From: Robin Chapman Newsgroups: sci.math Subject: Re: a game Date: Wed, 04 Nov 1998 09:06:59 GMT Organization: University of Exeter Lines: 52 Message-ID: <71p5fj$19n$1@nnrp1.dejanews.com> References: NNTP-Posting-Host: 194.83.240.16 X-Article-Creation-Date: Wed Nov 04 09:06:59 1998 GMT X-Http-User-Agent: Mozilla/4.04 [en] (X11; I; Linux 2.0.35 i586; Nav) X-Http-Proxy: 1.0 ginger.wwwcache.ja.net:8080 (Squid/1.NOVM.20), 1.0 x1.dejanews.com:80 (Squid/1.1.22) for client unknown, 194.83.240.16 Xref: news.math.niu.edu sci.math:219444 In article , Kobboi wrote: > > I would like to present the following problem, related to a game > I played on a computer once, but I can't remember the name. > > o o o > x x x x > o o o > x x x x > o o o > x x x x > o o o > > Two players 'o' and 'x' connect adjacent 'o's and 'x's respectively > trying to reach the other side ('o' : top to bottom, 'x' : left to right) > > After 2 moves each, the board may look like this > > o o o > xxxxx o x x > o o o > x x x x > o x o o > x x x x > o ooooo > > Prove (or give a counterexample, but I think that will be difficult) > that, no matter how bad the players are, there is always a winner. > (board size shouldn't matter, I think) This is the game of Gale (invented/named after David (?) Gale). I read about it in one of Martin Gardner's early Scientific American collections. He pointed out its similarities to Hex. He didn't give a proof of the fact it cannot end in a draw, but like Hex he showed that this fact meant that a "strategy stealing" argument ensured that the first player could force a win. Much later on he gave an explicit winning strategy. The only place I've seen formal proofs that Hex-type games cannot end in a draw is Ken Binmore's book "Fun and Games" (I don't recall publisher and date). These results can be used to prove the 2-dimensional form of Brouwer's fixed point theorem. Robin Chapman + "They did not have proper SCHOOL OF MATHEMATICal Sciences - palms at home in Exeter." University of Exeter, EX4 4QE, UK + rjc@maths.exeter.ac.uk - Peter Carey, http://www.maths.ex.ac.uk/~rjc/rjc.html + Oscar and Lucinda, chapter 20 -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own From Sillke@mathematik.uni-bielefeld.de Fri Nov 6 09:33:02 CST 1998 Article: 219748 of sci.math Path: news.math.niu.edu!husk.cso.niu.edu!vixen.cso.uiuc.edu!howland.erols.net!dca1-hub1.news.digex.net!digex!newscore.univie.ac.at!newsfeed.de.ibm.net!ibm.net!ar4news.dlh.de!ar4dec01!news From: Torsten Sillke Newsgroups: sci.math Subject: Re: a game Date: Wed, 04 Nov 1998 18:11:22 +0100 Organization: LH Systems AE/NET Lines: 106 Message-ID: <36408AB9.63073D57@lhsystems.com> References: Reply-To: Sillke@mathematik.uni-bielefeld.de NNTP-Posting-Host: 132.186.1.48 Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Mailer: Mozilla 4.03 [en] (X11; I; HP-UX B.10.10 9000/712) Xref: news.math.niu.edu sci.math:219748 Kobboi wrote: > > I would like to present the following problem, related to a game > I played on a computer once, but I can't remember the name. > > o o o > x x x x > o o o > x x x x > o o o > x x x x > o o o > > Two players 'o' and 'x' connect adjacent 'o's and 'x's respectively > trying to reach the other side ('o' : top to bottom, 'x' : left to right) > > After 2 moves each, the board may look like this > > o o o > xxxxx o x x > o o o > x x x x > o x o o > x x x x > o ooooo > > Prove (or give a counterexample, but I think that will be difficult) > that, no matter how bad the players are, there is always a winner. > (board size shouldn't matter, I think) > > Kobboi The game you describe is called 'Gale' or 'Bridg-it'. Look into the two books of Martin Gardner for Bridg-it and Hex. In my reference list I have two articles which give proofs for Hex. These dual graphs in Bridg-it are used in percolation theory too. MG3SA: New Mathematical Diversions from Scientific American MG3SA: Simon & Schuster (1966) MG3SA.18 Bridg-it and Other Games MG3SA.18. winning Bridg-it, pairing stategy (Shannon switching game) MG3SA.18. Connections (ASS, 1992) = Bridg-it board: connect or circle MG3SA.18.b Directed switching games on graphs and matroids, JoCT B60 (1986)237 MG3SA.18.c Shannon switching games without terminals, draft (I), see II, III MG3SA.18.c Graphs and Combinatorics 5 (1989) 275-82 (II), 8 (1992) 291-7 (III) MG1SA: The Scientific American Book of MG1SA: Mathematical Puzzles and Diversions MG1SA: Simon & Schuster (1959) MG1SA.8 The Game of Hex MG1SA.8. Piet Hein invented Hex 1942 (Parker Brothers Inc. 1952) 11*11 board MG1SA.8. John F. Nash independently invented Hex 1948 (14*14 board) MG1SA.8. there exists a first player winning strategy. Rex -> MG12SA.12 MG1SA.8. Rex (reverse Hex) odd board second even board first player win MG1SA.8. C. Shannon suggest an equilateral triangle. the aim is to connect MG1SA.8. the three sides with a tree (the corner belong to both sides). MG1SA.8. Hex and Shannon's Hex is a first player win. n*(n+1) Hex (pairing) MG1SA.8. variations of hex: Schensted, Madcrack Y and Poly Y -> MG75.12SA.117 MG1SA.8.a Beck, et al, Excursions into Mathematics, 1970, 327-339 MG1SA.8.a Hex 14*14 board, Beck's Hex, Hex has a first player move that loses MG1SA.8.b a winning opening in Reverse Hex, JoRM 7 (1974) 189-192 MG1SA.8.c some variants of Hex (Vex, Tex), JoRM 8 (1975/76) 120-122 MG1SA.8.d Hex must have a winner: an inductive proof, M. Mag. 49 (1976)85-86 MG1SA.8.e C. Berge, Some Remarks about a Hex Problem (14*14 board) MG1SA.8.e in: (ed. D. A. Klarner) The mathematical Gardner, p25-27 MG1SA.8.f Hex and the Brouwer Fixed-Point Theorem, AMM 86 (1979) 818-827 MG1SA.8.f there exists a connection in Hex <-> Brouwer Fixed-Point Theorem MG1SA.8.f only one pair can be connected <-> discrete Jordan Curve Theorem MG1SA.8.g Havannah (C. Freeling), Games&Puzzles No 79 (Winter 1980) 4-7,32 MG1SA.8.g Hexagon (length 8), connect two corners, three sides or build a ring MG1SA.8.h Hex is PSPACE-Complete, Acta Infomatica 15 (1981) 167-191 (German) MG1SA.8.i Three Person Winner-Take-All Games with McCarthy's Revenge Rule, MG1SA.8.i The College Math. Jour. 16:5 (Nov 1985) 386-394 (P. D. Straffin) MG1SA.8.i Three person Hex played on a hexagon (connect opposite edges), as MG1SA.8.i soon as it is no longer possible for a player to connect his two MG1SA.8.i edges, that player is eliminated and may not place any more marks MG1SA.8.j Hex Games and Twist Maps on the Annulus, AMM 98 (1991) 803-811 -- Torsten Sillke