Re: [math-fun] Games of Ramsey and van der Waerden
David asks: << Can anybody tell me who is the winner of the following two games. Game of Ramsey. Two players alternately pick edges from a complete graph on 6 vertices until one of them has collected three edges that form a triangle at which point his Opponent is the winner. Game of van der Waerden. Two players alternately pick numbers from the set {1,2, . .,9} until one of them has collected three numbers which form an arithmetic progression at which point his Opponent is the winner. The point is, of course, that these games cannot end in a draw.
Darned if I know, but very interesting questions! I'd like to add (two variants of) another game, which Martin Gardner and I (and probably innumerable others) invented independently, or at least close variants of the same idea: Who wins in the Game of Squares: Players take turns placing a marker of their own color (say white or black) on the vertices of an 8x8 square grid until there is some square (tilted or not) with all four vertices having the same-colored markers on them. The player whose color it is loses. Same question for the slightly more symmetrical Game of Toral Squares: Same game but on the 64 vertices of GxG, where G is a regular octagon. (Microchallenge: How many distinct squares are there in the GxG case, where a square is defined by its set of vertices? Better, generalize to the case of G = the regular N-gon) --Dan
Game of Squares: Players take turns placing a marker of their own color (say white or black) on the vertices of an 8x8 square grid until there is some square (tilted or not) with all four vertices having the same-colored markers on them. The player whose color it is loses. ... Game of Toral Squares: Same game but on the 64 vertices of GxG, where G is a regular octagon.
How are you defining squares formed from the vertices of GxG? Do you include the "1-dimensional" ones like {a1,c1,e1,g1} (with the I-hope-obvious meaning)? Here's one way, which excludes those: a square is the image of a square in ZxZ under the quotient map (mod 8, mod 8), provided the image vertices are distinct. And here's another which includes them: embed G in R^2 in the usual way and GxG correspondingly in R^4, and then a square is, er, a square :-). I prefer the former way; I think your language implies the latter.
(Microchallenge: How many distinct squares are there in the GxG case, where a square is defined by its set of vertices? Better, generalize to the case of G = the regular N-gon)
I'll adopt my definition above, which may differ from yours. You can get a square with (0,0) as one vertex by picking any other vertex (a,b) and then continuing with (a-b,a+b), (-b,a), and every square with (0,0) as a vertex arises thus. This works unless two vertices are the same, which happens iff (a-b,a+b)=(0,0), <=> (a,b)=(n/2,n/2). So the squares (without a vertex pinned, now) are { { (x,y), (x+a,y+b), (x+a-b,y+a+b), (x-b,y+a) } : x,y,a,b in Z/nZ, (a,b) neither (0,0) nor (n/2,n/2) } and the only remaining question is how many times each square has now been counted when we list the tuples (x,y,a,b). Four times at least, via f : (x,y,a,b) -> (x+a,y+b,-b,a) which has f^4=identity, and all orbits of size 4. And, unless I've goofed, which I probably have, that's all. So the number of squares is if n is odd: n^2(n^2-1)/4 if n is even: n^2(n^2-2)/4 I *think* all that changes if we adopt the embed-in-R^4 definition is that when 4|n we get an extra 2(n/4)=n/2 squares, but my 4-dimensional intuition is pretty dicey and I'm too lazy to check :-). -- g
A simple pairing strategy guarantees Player 2 a win or draw in the Game of Toral Squares. On a 2k x j torus, Player 2 answers (a,b) with (a+k,b). - Scott
David asks:
Who wins in the
Game of Squares: Players take turns placing a marker of their own color (say white or black) on the vertices of an 8x8 square grid until there is some square (tilted or not) with all four vertices having the same-colored markers on them. The player whose color it is loses.
Same question for the slightly more symmetrical
Game of Toral Squares: Same game but on the 64 vertices of GxG, where G is a regular octagon.
The second player can always win the Game of van der Waerden. The first round, player 2 picks whichever of 1,2,8, and 9 is closest to player 1's first move with the same parity. The second move, pick one of those four with the opposite parity, from the other end of the range if possible (e.g., if the your first pick was 2, take 9 if possible, otherwise 1). On player 2's third move, with one exception it is always possible to leave a position such that at least 2 of the 3 remaining numbers will not create an arithmetic sequence; on the next turn, 1 will be left, forcing the win. The exception is when player 1 has 1,2,5 and player 2 has 8,9 (or similarly, player 1 has 5,8,9 and player 2 has 1,2). In this case, take 4 (6); 3 (7) will then be playable on the next turn, since player 1 can't take it. I would be quite surprised if player 2 is not the winner of the game of Ramsey, as well. Besides having an extra edge all the time, the first move involves no real choice - all edges are equivalent - so the usual advantage of going first is not there. (Of course, player 2's first move has only 2 distinct options.) And, player 1 winds up with 1 more edge. Franklin T. Adams-Watters David asks: << Can anybody tell me who is the winner of the following two games. Game of Ramsey. Two players alternately pick edges from a complete graph on 6 vertices until one of them has collected three edges that form a triangle at which point his Opponent is the winner. Game of van der Waerden. Two players alternately pick numbers from the set {1,2, . .,9} until one of them has collected three numbers which form an arithmetic progression at which point his Opponent is the winner. The point is, of course, that these games cannot end in a draw.
________________________________________________________________________ Check Out the new free AIM(R) Mail -- 2 GB of storage and industry-leading spam and email virus protection.
participants (4)
-
Daniel Asimov -
franktaw@netscape.net -
Gareth McCaughan -
Scott Huddleston