# Game theory, need help

1. Feb 24, 2012

### 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).

2. Feb 24, 2012

### 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)?

3. Feb 24, 2012

### HaCkeMatician

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

4. Feb 24, 2012

### CaptFirePanda

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.

Last edited by a moderator: Feb 24, 2012
5. Feb 24, 2012

### HaCkeMatician

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

6. Feb 24, 2012

### 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.

7. Feb 24, 2012

### 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.

8. Feb 24, 2012

### Bacle2

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

9. Feb 24, 2012

### 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.

10. Feb 24, 2012

### HaCkeMatician

alan2 you are absolutely right, Thanks aloooooot