Peter and Bob

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathuz

1512 posts

mathuz

#1 h Apr 30, 2014, 11:48 AM • 2 Y

Y by Adventure10, Mango247

Peter and Bob play a game on a $n\times n$ chessboard. At the beginning, all squares are white apart from one black corner square containing a rook. Players take turns to move the rook to a white square and recolour the square black. The player who can not move loses. Peter goes first. Who has a winning strategy?

This post has been edited 1 time. Last edited by mathuz, May 3, 2014, 1:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chaotic_iak

2932 posts

chaotic_iak

#2 h Apr 30, 2014, 11:52 AM • 3 Y

Y by mathuz, Adventure10, Mango247

Where are the rooks? Do Peter and Bob control one rook each or one rook together or some other number of rooks?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sayakalah

5 posts

sayakalah

#3 h Apr 30, 2014, 12:48 PM • 3 Y

Y by mathuz, Adventure10, and 1 other user

"the board is white(all cells), only for the CORNER cells- black and they have ROOKS.", I think Peter and Bob are allowed to move one of the rooks in each turn, and there is no rooks on the white cells, but we need to confirm this to the author.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathuz

1512 posts

mathuz

#4 h Apr 30, 2014, 3:16 PM • 2 Y

Y by Adventure10, Mango247

we have $1$ -corner cell and $1$ rooks on the corner cell.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathuz

1512 posts

mathuz

#5 h May 3, 2014, 2:02 PM • 2 Y

Y by Adventure10, Mango247

chaotic_iak wrote:

Where are the rooks? Do Peter and Bob control one rook each or one rook together or some other number of rooks?

You are right! Sorry I have mistake! Edited.

On the board there is one rook on corner cell.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sabbasi

248 posts

sabbasi

#6 h Jun 22, 2014, 3:41 AM • 1 Y

Y by Adventure10

Someone please check this solution:

Peter can always win by always moving the maximum amount that he can vertically.

Firstly we can show that every time Bob moves he does so horizontally and the black squares that he draws all either share an edge with the edge of the board or with black squares he previously drew. To prove this, note that it is true for the first move since Peter goes to the end of the board. Now consider some point in the game after Peter has made a move. If Peter reached the end of the board, Bob must move along the end. Otherwise Peter must have reached a black square along a row drawn by Bob. The drawing of this row had a vertical column drawn by Peter before and after it, so all of Bob's squares will be adjacent to the horizontal row (since he is bounded by the vertical columns).

As a result of this, Bob's moves will always stack along the top and bottom of the board, so in other words, no square drawn by Bob can be untouched by the board or another square drawn by him both above it and below it. So this means that when Peter moves, he will always completely fill his column.

The only other thing we have to show is that Peter always will have a column to fill. This is true because if Peter reaches a column he hasn't touched yet, at most n - 1 moves must have passed (since otherwise he moved through every column) but that means Bob has only drawn n-1 rows, so there's no way that this new column could be filled after Bob's move.

Peter always has a move so Bob must be the loser.

Solution 2 : I also just realized that Peter always cuts off a new uncolored section with more rows and columns, which will eventually lead to his win since Bob can only win after Peter's move if Peter cuts off a 1xn rectangle. So I think this works too

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

johnkwon0328

188 posts

johnkwon0328

#7 h Jul 25, 2014, 4:03 AM • 1 Y

Y by Adventure10

sabbasi wrote:

Someone please check this solution:

Peter can always win by always moving the maximum amount that he can vertically.

I think your solution is incorrect. Bob can also be a loser considering n=1.

My solution:

n is odd -> Bob wins, n is even -> Peter wins

case 1: n is even

Peter can always win by moving rook from (i, j) to (n+1-i, j) every time.

case 2: n is odd

WLOG we can assume that at the beginning, rook is on (n,1), and Peter moved it to (n,2).
Bob can win by using the following method. Assume that Peter placed the rook on (i, j).
If i<n, Bob can place rook on (n-i, j).
If i=n, Bob can place rook on nth column, because on Bob's turn, number of white cells in nth column is odd.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sabbasi

248 posts

sabbasi

#8 h Jul 25, 2014, 1:31 PM • 2 Y

Y by Adventure10, Mango247

n=1 is an exception but in every other case that I tried Peter wins using this strategy.
Also you should provide some proof for your strategies since it's not obvious why/if they work.

Here I'll prove that Peter can win in a 3x3
label the cells from (1,1) to (3,3). Peter starts by going from (1,1) to (1,3).
Case 1: Bob goes to (2,3)
Then Peter moves to (2,1), Bob is forced to move to (3,1) then Peter moves to (3,3) and wins
Case 2: Bob goes to (3,3)
Then peter moves to (3,1) Bob is forced to go to (2,1) then Peter moves to (2,3) and wins.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

BSJL

641 posts

BSJL

#9 h Jul 25, 2014, 1:36 PM • 2 Y

Y by Adventure10, Mango247

Do you consider the case that Bob goes to (1,2)?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sabbasi

248 posts

sabbasi

#10 h Jul 25, 2014, 2:10 PM • 2 Y

Y by Adventure10, Mango247

@BSJL

I do not understand your concern. I suspect there is confusion in understanding the problem. Both players move the rook, and every square the rook moves over turns black, and black squares can't be moved on at all times. At least that is what the version here would suggest: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=125&t=587460 but that version was the only way I could think of playing anyways. Since if paths are not drawn, it is only dependent on parity, and if paths are self intersecting the game doesn't need to end. So clearly (2,3) and (3,3) are the only possible moves by Bob.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

johnkwon0328

188 posts

johnkwon0328

#11 h Jul 26, 2014, 3:51 AM • 1 Y

Y by Adventure10

sabbasi wrote:

At least that is what the version here would suggest: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=125&t=587460 but that version was the only way I could think of playing anyways.

Thanks for the link. I had some kind of confusion understanding this problem. I didn't realized that the path of the rook was colored.(the problem wasn't clear in the version of this post, actually)

But I cannot understand why it depends on parity, if the path is not drawn. I think that this game can come to the end before every cell is colored...

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sabbasi

248 posts

sabbasi

#12 h Jul 26, 2014, 5:51 AM • 1 Y

Y by Adventure10

Sorry that was a comment I made because I thought I had a strategy. But yeah this problem statement isn't clear.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Niosha

18 posts

Niosha

#13 h Mar 1, 2015, 5:29 PM • 4 Y

Y by SockFoot, newovertimee, Alireza_Amiri, Adventure10

I'm agree with Johnkwon. I had another strategy:
If n is odd: Bob wins. it's enough to divide our chessboard into $1\times 2$ rectangles. And then when Peter moves Bob can move to the second square.
If n is even: Peter wins . Like first situation just in the first move Peter goes to the (1,n) and then we should divide remain squares into $1\times 2$ rectangles. So Peter wins

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mathtastic

3258 posts

mathtastic

#14 h Mar 1, 2015, 5:54 PM • 1 Y

Y by Adventure10

In fact, they shouldn't divide the board into dominoes because that makes their strategies obvious to the other player. The players can just pair the squares randomly

.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PCChess

548 posts

PCChess

#15 h Mar 30, 2021, 4:14 AM • 1 Y

Y by Mango247

I claim that Peter wins if $n$ is even and Bob wins when $n$ is odd. For simplicity, let the squares be denoted $(i,j)$ , where a square is located in the $i$ th column from the left and $j$ th row from the bottom. WLOG, let the rook start at $(n,n)$ and let Peter's first move be along the top row.

First we will prove that Peter wins when $n$ is even. Consider the vertical line $m$ between the $n/2$ and $n/2+1$ column. For whatever Bob's first move is, Peter will just move the rook to the square that is the reflection of Bob's last move across $m$ . Peter's move is always legal, since each square has exactly one reflection and each square is in the same row as its reflection across $m$ . Since Peter can always play the mirrored square of Bob, Peter will win.

Now consider when $n$ is odd. After Peter's first move, let Bob move to another square in the top row. Consider the horizontal line $\ell$ that is between the $(n-1)/2$ and $(n+1)/2$ row. If Peter moves to a square in a top row, Bob will move to a square in the top row. If Peter moves to a square not in the top row, Bob will move to the reflection of Peter's square over line $\ell$ . Note that there are an even number of squares in the top row if the starting square $(n,n)$ is not considered, so if Peter moves to a square in the top row Bob will always be able to move to a square in the top row. Moreover, for the squares not in the top row, each square corresponds to exactly one another square that is its reflection over $\ell$ , and these two squares are always in the same column. Hence, if Peter moves to a square not in the top row, Bob will always be able to move to its reflection across $\ell$ . Since Bob always has a response to whatever square Peter moves to, Bob wins for odd $n$ .

This post has been edited 1 time. Last edited by PCChess, Mar 30, 2021, 4:14 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#16 h Aug 24, 2023, 3:04 PM • 7 Y

Y by centslordm, Fatemeh06, EpicNumberTheory, KK_1729, quantam13, Eka01, guruguha9

El clásico

Peter wins iff $n$ is even. If $n$ is even, his strategy is to divide the board into $1 \times 2$ rectangles; whenever a rook enters a rectangle (including on the first move) he moves it to the other cell. If $n$ is odd, Bob's strategy is to divide the board except for the starting cell into $1 \times 2$ rectangles and employ the same strategy. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

chakrabortyahan

377 posts

chakrabortyahan

#17 h Oct 14, 2023, 5:24 PM • 1 Y

Y by iamahana008

I saw this problem 3 times last week USSR 78, Bmo 1 2023 and now this
Peter has a winning strategy if $n$ is even and Bob has one if $n$ is odd. We break the whole board into $2 \cdot 1$ dominoes and note that if $n$ is even then $\text{Peter}$ has always a move if $\text{Bob}$ has a move because the square where $\text{Bob}$ moves is part of some domino and by his move $\text{Bob}$ bridges two dominoes always. So, B will be exhausted of his moves.
Similarly, for $n$ odd $\text{Bob}$ has a similar winning strategy .

Z K Y