Conference rusure::math

>Two players take turns announcing triplets of non-negative integers.
>If a triplet (a,b,c) is announced, then for the rest of the game no
>player is allowed to name a triplet (d,e,f) with d>=a,e>=b, and f>=c.
>The first player who is forced to play (0,0,0) loses.  Every
>game must terminate (check!), so either the first or the second
>>player has a winning strategy.  Which player has the advantage?
 
>Here is a sample game:
> 
>Player 1     Player 2
>--------     --------
>(0,0,2)      (0,1,0)
>(50,0,1)     (50,0,0)
>(0,0,1)      (1,0,0)
>(0,0,0)<-- Player 2 wins!
 
Looks like fun, but I would like some clarification of the rules. As I read 
them, Player 1's move of (50,0,1) is illegal, as zeroes have been played 
already in all positions. 

Please clarify. I can use the money!

Lynn Yarbrough 

        The (d,e,f) that you compare (a,b,c) to must all be from
        the same triplet.  So (a,b,c)=(50,0,1) is legal because
        both c=1 is less than the f=2 in (0,0,2) and b=0 is less
        than the e=1 in (0,1,0).  However, after all three of
        (1,0,0), (0,1,0), and (0,0,1) have been played, then
        player one must play (0,0,0) and therefore loses.
        
        Question:
        
>The first player who is forced to play (0,0,0) loses.  Every
>game must terminate (check!), so either the first or the second
>>player has a winning strategy.  Which player has the advantage?
        
        Assuming it is true that every game must terminate, is it
        then a trivial observation or a deep and subtle result
        that "either the first or the second player has a winning
        strategy"?
        
        Dan

        Conjecture:
        
        Call any of the plays (1,0,0), (0,1,0), or (0,0,1) a unit
        vector. :-)  In any game in which all three unit vectors
        are played, the player playing the last of them won.
        
        Dan

>Here is a sample game:
> 
>Player 1     Player 2
>--------     --------
>(0,0,2)      

This loses, but it may not be an error :-)

>		(0,1,0)

Correct

>(50,0,1)     

Giving player 2 some rope...

>		(50,0,0)

Incorrect: (51,0,0) wins

>(0,0,1)      

Player 1 throws away his opportunity:  (49,0,1) would have won the game

		>(1,0,0)
>(0,0,0)<-- Player 2 wins!
 
Regards,
Andrew.

>Two players take turns announcing triplets of non-negative integers.
>If a triplet (a,b,c) is announced, then for the rest of the game no
>player is allowed to name a triplet (d,e,f) with d>=a,e>=b, and f>=c.
>The first player who is forced to play (0,0,0) loses.  Every
>game must terminate (check!), so either the first or the second
>player has a winning strategy.  Which player has the advantage?

	The easiest way to "see" that the game must terminate is 
geometric, but given the medium we are using here, I will translate the
idea into algebraic form.

	Let {(a_i,b_i,c_i) | i = 1,...,I} be the set of moves made so far.
Write (a,b,c) =<< (d,e,f) if a =< d, b =< e, c =< f.   Write (a,b,c) << (d,e,f)
if in addition one of the three inequalities in the components is strict.
Let A_I = min(i)(a_i), similarly B_I = min(i)(b_i), C_I = min(i)(c_i).   The key
question to ask is:  how many moves can we continue to make such that at each 
move J (A_J,B_J,C_J) >>= (A_I,B_I,C_I)?    

	If we can show that this number of moves is *finite*, then we are
home, since there is then a K such that A_K = B_K = C_K = 0, and a finite
number of moves after that the game ends.

	So given (A_I,B_I,C_K), let j,k,l be such that a_j = A_I, b_k = B_I
and c_l = C_I.   We are interested in counting the future moves (a,b,c) such
that the cumulative minimum in each dimension does not decrease:  i.e.:
(a,b,c) >>= (A_I,B_I,C_I).   From the rules of the game we know that:
		(i) either b < b_j or c < c_j
		(ii) either a < a_k or c < c_k
		(iii) either a < a_l or b < b_l

	So, at least *two* of the three values {a,b,c} are bounded to a
finite range.   wlog, say a & b are bounded to {A_I,...,Amax} & {B_I,...,Bmax}
respectively.   c is not bounded yet, but the essential point is that as soon
as a player plays a move (a,b,c), where a & b are bounded as above, then any
future move (a,b,c') must have c' < c.   So there are only a finite possible
number of future moves of the form (a,b,?).

	Thus any game can last only a finite number of turns.

-------------------------------------------------------------------------------

	That's straightforward enough, but the analysis of how to actually win
the game seems much more complicated.   It is clear that the 1-dimensional
game and the 2-dimensional game are wins for the first player, with the only 
winning moves being (1) and (2,0) or (1,1) [or (0,2), obviously, but we'll
assume all statements include their symmetries from now on] respectively.

	In 3 dimensions, (1,0,0) and (2,0,0) are evidently losses for
the first player, and the rubicon to understanding how this game might work
out is perhaps to analyse the consequences of the opening move (3,0,0).

	This I am working on.

Regards,
Andrew.

	Re: -.2.   If the game must teminate in a finite time, then it is
straightforward to see that one player must have a winning strategy.   Suppose
that neither player has a winning strategy.   Then P1 has non moves that force
a win, but he certainly has one that avoids a forced loss.   So he plays it.
Now P2 is in the same position.   Hence we deduce that there is a game of
infinite length, contrary to the assumption.

	Re: .3.   (0,0,1) effectively reduces the game to a two-dimensional
one.   Hence if (1,0,0) & (0,1,0) have already been played, (0,0,1) is a
winning move.

	(1,0,0) as an initial move loses to (0,1,1,) or (0,2,0)
&	(2,0,0) as an initial move loses to (0,1,0) and possibly others.

	If you begin:
	(1,1,0) (1,0,1) (0,1,1) (a,0,0), (0,b,0), (0,0,c) then you are just
playing Nim!

	In the two dimensional world, what happens after the beginning:
	(a,0) (0,b)?
If a=b, then P1 wins with (1,1) and he's playing Nim
If a=1, then P1 wins with (0,1)
If a=2, then P1 wins with (1,b-1)

If a=3, & b=4, then P1 wins with (1,2) only.

    Re .6, .3:
    
    Which is to say that the *second* player to play a 'unit vector' loses.
    
    
    Therefore:  One of the keys to the game is figuring out how to avoid
    being the second player to play a unit vector.
    
    
    --  Barry

	A couple of not-entirely-trivial remarks on the 2-dimensional game,
which I think are important, even though we know who wins the 2-dimensional
game as long as optimal play has always been used.

	It's shows just how subtle this game is even at the 2-dimensional
level.

	(a,0) (0,b) is a win for P1, as long as one of a & b > 1.   Why?
Well, *either* (a-1,b-1) is a winning move, or it is not.   If not, there
is some move (c,d) for P2 which defeats it.   But P1 can play (c,d) directly,
instead of (a-1,b-1), since (c,d) *subsumes* (a-1,b-1), he will achieve a
winning position for himself.   Love it.

	Of course this generalizes to the 3-dimensional case immediately:
(a,0,0) (0,b,0) (0,0,c) is a win for P2 as long as one of a,b,c is > 1.

	Returning to Flatland, suppose that the game has gone:
	(3,0) (0,z), (1,y), (2,x) where x =< y =< z

	Then we can pictorially regard the possible moves as:

1	************
2	*******************
3	********************************

where there are x, y & z stars in first, second & third rows respectively.
A move corresponds to shooting a star, and all the stars to the right and
above it.   Shooting the bottom left hand star loses the game.

	Write the *game* as [x,y,z], not to be confused with the move in the
3-dimensional game (a,b,c).   Note that x,y & z denote the *number* of stars
(ie valid moves) in that row.

	If z > x+y+1, then P1 can win.   Suppose not, then to every move
(except the auto-lose bottom left move) there is a counter-move.   The
counter-move cannot be a star in the same row, or the subsumption fiddle
mentioned above leads to a contradiction.   Similarly, no move can be the
counter-move for two moves which are in the same row.

	So, each (non-trivial) move has one or two counter-moves.   If two,
each counter-move will be for a different row.   But if there are too many
stars in the bottom row, it is impossible to have a counter-move for each of
them!   Hence the result: z > x+y+1 => P1 wins.

	From this we can see that for all x < y, there exists a unique z(x,y)
> x, such that [x,min(y,z),z] is a losing position.   This insight allows us
to jump for the correct hypothesis hanging in the dark, and to prove it 
inductively.

	Hypothesis:
	Let 0 =< x =< y.   Then there is a unique z = z(x,y) such that
[x,min(y,z),z] is a lost game.
		z(0,y) = y+1
		z(1,y) = 2
		z(x,y) = x+y

Proof:
	Uniqueness is trivial.   Next use induction to show z(0,y) = y+1,
which should be familiar.   z(1,y) = 2 is a rotation of z(0,2) = 3.   Next
z(2,2) = 4 is any easy exercise.   Now use induction on y, to get z(2,y)=2+y,
and finally induction on x to get the full result.

Regards,
Andrew.

	Let's generalize into 3-d again from the previous reply.   We will
say "(a,b,%) is legal", to mean that for fixed a & b, and arbitrarily
large c, (a,b,c) can be played.  Suppose we are playing the game, and we find 
ourselves in a position such that:

	(i) (0,0,%) is legal
	(ii) for no other a,b is (a,b,%) legal
	(iii) for no a,c is (a,%,c) legal
	(iv) for no b,c is (%,b,c) legal

	(Loosely, "there is only one straight road to infinity.")

	Then by a simple extension of the arguments given in the previous
reply, the player to move can win.   Note the "unit vector" heuristic discussed
earlier is a trivial special case of this.

	How do you get to this desirable position?   We could explore the games
that result from the opening (3,0,0) (0,3,0), since this is the simplest
situation that we don't understand.

Regards,
Andrew.

	As before, will say "(a,b,%) is legal", to mean that for fixed a & b, 
and arbitrarily large c, (a,b,c) can be played.  Suppose we are playing the 
game, and we find ourselves in a position such that:

	(i) (a,b,%) is legal <=> (a=0 & b=0)
	(ii) (a,%,c) is legal <=> (a=0 & c=0)
	(iii) (%,b,c) is legal <=> (b=0 & c=0)

	(Loosely, "there are three orthogonal straight roads to infinity.")

	Then I allege that the player to move has exactly three winning moves.

	I believe that I have a proof of this, which involves the idea of
extending the catchment area, C, of moves which are automatic losses from
C = {origin} to C = {x-axis} union {y-axis}.   If the counter-move subsumption
arguments will work for this new game (and I don't see why they shouldn't)
then the result above will follow.

	The next step in understanding this game is to be able to handle the
case where w've got parallel roads to infinity, eg: following (3,0,0) (0,3,0).
I still don't grok those.

regards,
Andrew.