The Student Room Group

The Proof is Trivial!

Scroll to see replies

Original post by Lord of the Flies
Tile the chessboard with dominoes. Winning strategy for player 1: always stay on the current domino.


Yep, correct :smile:

Posted from TSR Mobile
Original post by Renzhi10122


Can you please explain as I don't get it .
Original post by demigawdz
Can you please explain as I don't get it .


Take your chessboard and split it into 32 2*1 dominoes (all lined vertically for example). The king will initially be on one of those dominoes, and the first player simply moves onto the other free spot of the domino. The second player has to move onto a new domino, and the first player simply moves onto the other spot on the same domino.
Original post by Renzhi10122
Take your chessboard and split it into 32 2*1 dominoes (all lined vertically for example). The king will initially be on one of those dominoes, and the first player simply moves onto the other free spot of the domino. The second player has to move onto a new domino, and the first player simply moves onto the other spot on the same domino.

Ahhh ok.
It all makes sense now.
ty
You might want to consider what happens when we replace the king with a knight. :biggrin:

Whilst we're on 2-player board games, here's something fun: consider an m x n chess board. Players take turns in painting the board. When you paint a square, you must paint all squares above it & to the right of it (i.e. if I paint (a,b) I must paint {(x,y) | x a, y b}). You must always paint at least one square that has not been painted on. Game ends when the board is entirely painted. Last player to paint loses.

Who has a winning strategy?
(edited 8 years ago)
Original post by Lord of the Flies
You might want to consider what happens when we replace the king with a knight. :biggrin:

Whilst we're on 2-player board games, here's something fun: consider an m x n chess board. Players take turns in painting the board. When you paint a square, you must paint all squares above it & to the right of it (i.e. if I paint (a,b) I must paint all (x,y) with x a, y b). Game ends when the board is entirely painted. Last player to paint loses.

Who has a winning strategy?


Presumably we cannot paint over others, unless it's for the above and to the right?

Posted from TSR Mobile
Original post by Jammy Duel
...


Thanks and yes, would be rather silly otherwise. Added that in.
Original post by Lord of the Flies
Thanks and yes, would be rather silly otherwise. Added that in.


First thoughts are that given there are m+n-1 squares along the bottom and up the left and you want to make sure that the other person paints the last square, if m+n-1 is even then you want to go first and go straight for the bottom left square, then you just take it in turns to paint the remaining squares and the person going second loses.
I shall think about the other circumstances while making and eating lunch.
(edited 8 years ago)
Original post by Lord of the Flies
You might want to consider what happens when we replace the king with a knight. :biggrin:

Whilst we're on 2-player board games, here's something fun: consider an m x n chess board. Players take turns in painting the board. When you paint a square, you must paint all squares above it & to the right of it (i.e. if I paint (a,b) I must paint {(x,y) | x a, y b}). Game ends when the board is entirely painted. Last player to paint loses.

Who has a winning strategy?


Knights are good as well. You can tile the board with pieces like
xo
oo
ox (obviously, you flip these tiles to make them all fit)

The paint one might take a bit more time, but here's another problem:

On a finite chessboard, for which n n is it possible to place queens such that each queen is attacking n n queens? What about for an infinite chessboard?
Original post by Jammy Duel
First thoughts are that given there are m+n-1 squares along the bottom and up the left and you want to make sure that the other person paints the last square, if m+n-1 is even then you want to go first and go straight for the bottom left square, then you just take it in turns to paint the remaining squares and the person going second loses.
I shall think about the other circumstances while making and eating lunch.


But all squares to the right and above it must be coloured in? I.e., you colour in the whole chessboard if you choose the bottom left square, unless I misunderstood the question.
Original post by Renzhi10122
But all squares to the right and above it must be coloured in? I.e., you colour in the whole chessboard if you choose the bottom left square, unless I misunderstood the question.


No, it was I that misunderstood
Original post by Lord of the Flies
You might want to consider what happens when we replace the king with a knight. :biggrin:

Whilst we're on 2-player board games, here's something fun: consider an m x n chess board. Players take turns in painting the board. When you paint a square, you must paint all squares above it & to the right of it (i.e. if I paint (a,b) I must paint {(x,y) | x a, y b}). You must always paint at least one square that has not been painted on. Game ends when the board is entirely painted. Last player to paint loses.

Who has a winning strategy?


Love it.

If there is one row left, then the current-to-paint wins by leaving just one square.

If there is an m by n L-shape left, then (if n=m=2) the first drawer loses because they must leave a straight line; if n=m>2 the first drawer again loses because anything they do can be matched by the second drawer to leave a symmetrical L-shape; so for any n>m>=2 the first drawer wins by chopping down to an m-by-m L-shape.

Hence if the original board is square, the first player to paint wins by painting all but the lower-left L, then mirroring whatever the second player does.

EDIT: of course, this assumes the square is bigger than 1x1. In that case, the first painter loses, naturally.

I'll think about the rest, but I'm off to do some physical exercise :P
(edited 8 years ago)
Original post by Smaug123
Love it.

If there is one row left, then the current-to-paint wins by leaving just one square.

If there is an m by n L-shape left, then (if n=m=2) the first drawer loses because they must leave a straight line; if n=m>2 the first drawer again loses because anything they do can be matched by the second drawer to leave a symmetrical L-shape; so for any n>m>=2 the first drawer wins by chopping down to an m-by-m L-shape.

Hence if the original board is square, the first player to paint wins by painting all but the lower-left L, then mirroring whatever the second player does.

EDIT: of course, this assumes the square is bigger than 1x1. In that case, the first painter loses, naturally.

I'll think about the rest, but I'm off to do some physical exercise :P


If you think about it, the first should always win, because they can either mirror as you described or they can use their move to, in essence, turn it into a square region, or at least what's left to play with, and then start mirroring.
Original post by Jammy Duel
If you think about it, the first should always win, because they can either mirror as you described or they can use their move to, in essence, turn it into a square region, or at least what's left to play with, and then start mirroring.


Well, but then the first player loses since the second player then gets the first go on the newly created square.
Original post by Renzhi10122
Well, but then the first player loses since the second player then gets the first go on the newly created square.


No, because the first player has already created the L shape described by smaug
I suppose my wording was a tad ambiguous
Posted from TSR Mobile
(edited 8 years ago)
Original post by Jammy Duel
No, because the first player has already created the L shape described by smaug
I suppose my wording was a tad ambiguous
Posted from TSR Mobile


? I'm confused here.
Original post by Renzhi10122
? I'm confused here.


So, your first move would be to create an L, most sensibly by choosing (2,2), this leaves the L that is the left column and bottom row. From this point on, from this point on, whatever player 2 does, all player 1 needs to do is make sure that the number of clear squares across the bottom and up the side is equal after their turn.
In fact, I'm pretty sure they don't even need them to be equal, but I can't be bothered thinking of how to generalise it when keeping things equal would suffice.
Of you want I could give you an example to demonstrate if you still don't get it to explain the method.

Also wondering what a solution would be in higher dimensions.

Posted from TSR Mobile
Original post by Jammy Duel
So, your first move would be to create an L, most sensibly by choosing (2,2), this leaves the L that is the left column and bottom row. From this point on, from this point on, whatever player 2 does, all player 1 needs to do is make sure that the number of clear squares across the bottom and up the side is equal after their turn.
In fact, I'm pretty sure they don't even need them to be equal, but I can't be bothered thinking of how to generalise it when keeping things equal would suffice.
Of you want I could give you an example to demonstrate if you still don't get it to explain the method.

Also wondering what a solution would be in higher dimensions.

Posted from TSR Mobile


But the chessboard isn't necessarily square, so the L shape could have unequal number of squares on each branch, at which point, the second player could make them equal and win.
Original post by Jammy Duel
So, your first move would be to create an L, most sensibly by choosing (2,2), this leaves the L that is the left column and bottom row. From this point on, from this point on, whatever player 2 does, all player 1 needs to do is make sure that the number of clear squares across the bottom and up the side is equal after their turn.
In fact, I'm pretty sure they don't even need them to be equal, but I can't be bothered thinking of how to generalise it when keeping things equal would suffice.
Of you want I could give you an example to demonstrate if you still don't get it to explain the method.

Also wondering what a solution would be in higher dimensions.

Posted from TSR Mobile


As Renzhi says: if the board is not square, the first player loses by making an L, because the second player then evens up the L and can then force a win.
Original post by Renzhi10122

On a finite chessboard, for which n n is it possible to place queens such that each queen is attacking n n queens? What about for an infinite chessboard?
Are you sure this is the question you intended to ask? I remember a (very good) similar case where you were placing n black and n white queens on an infinite board such that no black piece can take a white piece and vice versa. Did you mean to ask this?

Otherwise I'm just getting n=3, simply by the fact that one queen must be the furthest left and the furthest down, thereby meaning it can at most interact with 3 other pieces (right, right/up diagonal and up). Unless I'm misreading this at 5am

Quick Reply