Winning Strategy for Player 1 in the 10x20 Lattice Game

[HaCkeMatician]

the 10 X 20 lattice game has the following rules:
- two players alternate picking points (x,y) in the plane. the points must have integer coordinates(lattice points) and we must have 1 ≤ x ≤ 10
1 ≤ y ≤ 20
- first player must begin from (1,1). that is, player 1 can choose any point with one coordinate or the other being 1.
- if one player choose the point (x,y), then the next player must take a point of the form
( x,y' ), y' > y
or ( x',y), x' > x. for example, player 2's first turn can be to choose (1,6) or (5,1), but not (2,3).
- the winner is the player that chooses (10,20)
> the first player has a winning strategy; that is, no matter what player 2 does, there is a reply by player 1 that will inevitably lead to victory. Hint (9, 19) is a winning position
- a choice that guarantees an eventual win. Figure out why and work from there.
find a winning strategy for player 1 and prove its correctness. Then, generalize this idea to any size of lattice ( Player 1 is not always the one who wins).

 

[Bacle2]

" first player must begin from (1,1). that is, player 1 can choose any point with one coordinate or the other being 1."

This seems ambiguous: is the starting position (1,1), or one of (1,y) or (x,1)?

 

[HaCkeMatician]

player 1 can choose any point with one coordinate or the other being 1

 

[CaptFirePanda]

" first player must begin from (1,1). that is, player 1 can choose any point with one coordinate or the other being 1."

This seems ambiguous: is the starting position (1,1), or one of (1,y) or (x,1)?

Based on the rules of choosing either (x',y) or (x,y'), I'm thinking that the first player assumes that (1,1) was the initial "pick" so to speak and must pick (1,y') or (x',1).

Also, I would say that forcing things as close to 10,20 as quickly as possible is the best strategy for #1 to win.

 

[HaCkeMatician]

what the wrong if for example player one choose (1,2) and player 2 choose (3,2)

 

[CaptFirePanda]

I don't think there is anything wrong with those choices. They don't break any of the rules as far as I can see.

 

[alan2]

Consider any diagonal through the winning point. It is irrelevant whether the matrix is square or rectangular, or how large it is. The first player to choose a point on this diagonal wins. In a square game, choosing (1,1) always wins. In your rectangular game, choosing (1,11) always wins. Try it with a 2x2, 3x3, 4x4 then generalize it and you will see the strategy. The second player to move can not win this game.

 

[Bacle2]

Maybe going backwards from the winning position (9,19) would help, i.e., how would
one arrive at (9,19).

 

[alan2]

Yes, starting from the winning point and working backwards is a common method for finding the winning strategy. In this case, the first to get to the diagonal wins. Player 1 can always start on the diagonal and thus win.

 

[HaCkeMatician]

alan2 you are absolutely right, Thanks aloooooot