Author |
Topic: Pawn on a NxN chessboard (Read 1747 times) |
|
grad
Newbie
Gender: 
Posts: 14
|
 |
Pawn on a NxN chessboard
« on: Aug 29th, 2010, 2:29am » |
 Quote  Modify
|
Hi! I 've been told this riddle but I can't find a solution!
Two friends play a strange game on a NxN chessboard. There is only one pawn in one corner of the chessboard and every player can move the pawn in his turn. The legal move for the pawn is one square forward, backwards, left or right. The pawn cannot move to a square that was before! The first player who cannot find a legal move loses. Can a player always win in this game? How?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #1 on: Aug 29th, 2010, 6:34am » |
Quote Modify
|
The squares will run out eventually; there can be at most 63 moves. So if player one could ensure that no dead ends occur, he would always win. I think that's possible.
Actually, if you tile the chessboard with dominoes horizontally (or vertically), player one can always complete a domino, and player two always starts one. Therefore player one has the last move, regardless of whether a full tour of the board is made or not.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Pawn on a NxN chessboard
« Reply #2 on: Aug 29th, 2010, 10:58am » |
Quote Modify
|
on Aug 29th, 2010, 6:34am, towr wrote:
Nice analysis.
Maybe N should be taken into account, especially the possibility of N odd?
An interesting observation is that each player stays on his/her own color.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #3 on: Aug 29th, 2010, 11:17am » |
Quote Modify
|
I think that by the same reasoning that player one wins for even N, player two will win for odd N. Although the tiling will be slightly different, it's easy enough to snake through the rest of the squares.
|
| « Last Edit: Aug 29th, 2010, 11:32am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
grad
Newbie
Gender:
Posts: 14
|
|
Re: Pawn on a NxN chessboard
« Reply #4 on: Aug 29th, 2010, 12:08pm » |
Quote Modify
|
on Aug 29th, 2010, 6:34am, towr wrote:| So if player one could ensure that no dead ends occur, he would always win. |
|
I, too, believe that if N is even then player A can always find a winning strategy and if N is odd player B wins. But there must be a way to actually prove that no dead end occurs or something similar...
|
| « Last Edit: Aug 29th, 2010, 12:09pm by grad » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #5 on: Aug 29th, 2010, 12:36pm » |
Quote Modify
|
I gave a strategy that guarantees a win. Isn't that proof enough, or does it need further explanation?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Pawn on a NxN chessboard
« Reply #6 on: Aug 29th, 2010, 12:59pm » |
Quote Modify
|
on Aug 29th, 2010, 12:36pm, towr wrote:| I gave a strategy that guarantees a win. Isn't that proof enough, or does it need further explanation? |
|
Proofs by diktat usually require further explanation.
Let's say the pawn starts at a1
and
P1 moves it to a2
P2 moves it to b2
P1 moves it to b3
P2 moves it to b4
P1 moves it to a4
P2 moves it to a3
and
P1 cannot 'complete the domino'.
So under what circumstances does your proof 'guarantee a win'?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #7 on: Aug 29th, 2010, 1:15pm » |
Quote Modify
|
on Aug 29th, 2010, 12:59pm, ThudanBlunder wrote:Proofs by diktat usually require further explanation.
Let's say the pawn starts at a1
and
P1 moves it to a2
P2 moves it to b2
P1 moves it to b3
|
|
That's the wrong move, the domino lies on b1b2, so player one should go to b1. You're not following a domino tiling of the board as instructed.
Say X is a black square, O is a white square and [XO] and [OX] form a domino, then the board could look like:
[XO][XO][XO][XO]
[OX][OX][OX][OX]
[XO][XO][XO][XO]
[OX][OX][OX][OX]
[XO][XO][XO][XO]
[OX][OX][OX][OX]
[XO][XO][XO][XO]
[OX][OX][OX][OX]
(There are of course many valid tilings, but they do need to be complete tilings, you can't randomly plonk the dominoes in, leaving gaps, and hope it'll work. Horizontal or vertical tiling is simplest for even N; for odd N ignore the starting square, and then tile one column vertically, the rest horizontally.
Actually, the move where it really goes wrong is when you pick a4, because that makes any (complete) tiling impossible.)
on Aug 29th, 2010, 12:59pm, ThudanBlunder wrote:| So under what circumstances does your proof 'guarantee a win'? |
|
All circumstances where you actually follow the strategy and don't use a strategy that's only superficially similar. 
|
| « Last Edit: Aug 30th, 2010, 1:25am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Pawn on a NxN chessboard
« Reply #8 on: Aug 29th, 2010, 1:38pm » |
Quote Modify
|
The first thing I would do with such a board is turn it round 90o.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #9 on: Aug 29th, 2010, 1:43pm » |
Quote Modify
|
Yeah, well, I don't play chess...
Speaking of which, would you happen to know a good chess-database for my father? He's been complaining that the one he has in fritz11 has too many poor quality games in it; and since you seem to like chess, I've been meaning to ask if you might have any recommendations.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Pawn on a NxN chessboard
« Reply #10 on: Aug 29th, 2010, 1:49pm » |
Quote Modify
|
on Aug 29th, 2010, 1:43pm, towr wrote:
Speaking of which, would you happen to know a good chess-database for my father? He's been complaining that the one he has in fritz11 has too many poor quality games in it; and since you seem to like chess, I've been meaning to ask if you might have any recommendations. |
|
Yes, I know ware to find some. I will PM you about that.
Of course, there are many free ones out there too.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
grad
Newbie
Gender:
Posts: 14
|
|
Re: Pawn on a NxN chessboard
« Reply #11 on: Aug 29th, 2010, 6:29pm » |
Quote Modify
|
Oh, ok!  I didn't notice the domino thing in your first post 
Yes, I think that is a nice strategy! Thank you towr!
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Pawn on a NxN chessboard
« Reply #12 on: Aug 30th, 2010, 6:03am » |
Quote Modify
|
on Aug 29th, 2010, 6:34am, towr wrote:
Actually, if you tile the chessboard with dominoes horizontally (or vertically)... |
|
on Aug 29th, 2010, 1:15pm, towr wrote:
All circumstances where you actually follow the strategy and don't use a strategy that's only superficially similar.
|
|
Can I write A (v B)  A  B or are they just superficially similar?
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #13 on: Aug 30th, 2010, 6:14am » |
Quote Modify
|
In this case they are exclusive, since they are two alternative simplest tilings.
Other tilings work (which use both horizontal and vertically aligned dominoes), but if you leave open spaces then it's not a proper tiling in the first place.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Pawn on a NxN chessboard
« Reply #14 on: Aug 30th, 2010, 6:30am » |
Quote Modify
|
on Aug 30th, 2010, 6:14am, towr wrote:| In this case they are exclusive, since they are two alternative simplest tilings. |
|
Then it is the given strategy [horizontally (or vertically)...] that is 'only superficially similar' to the intended stategy.
Hence my earlier request for clarification of (what appeared to be) your proof by diktat.
|
| « Last Edit: Aug 30th, 2010, 6:50am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #15 on: Aug 30th, 2010, 7:03am » |
Quote Modify
|
on Aug 30th, 2010, 6:30am, ThudanBlunder wrote:| Then it is the given strategy [horizontally (or vertically)...] that is 'only superficially similar' to the intended stategy. |
|
No, that is a perfectly valid winning strategy. What you tried to do in your example, however, wasn't; because you were just putting the dominoes wherever, and not according to any tiling of the board. That was what was superficially similar: putting dominoes on the board, but not doing a tiling as it ought have been.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Pawn on a NxN chessboard
« Reply #16 on: Aug 30th, 2010, 7:38am » |
Quote Modify
|
on Aug 30th, 2010, 7:03am, towr wrote:
No, that is a perfectly valid winning strategy. What you tried to do in your example, however, wasn't; because you were just putting the dominoes wherever, and not according to any tiling of the board. That was what was superficially similar: putting dominoes on the board, but not doing a tiling as it ought have been. |
|
I presented no strategy for a forced win and made no effort to do so.
But A (v B) A v B
In plain English this means cover the board with horizontally or vertically placed tiles. Or both. (This allows the configuration I gave.)
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Pawn on a NxN chessboard
« Reply #17 on: Aug 30th, 2010, 8:19am » |
Quote Modify
|
on Aug 30th, 2010, 7:38am, ThudanBlunder wrote:But A (v B) A v B
In plain English this means cover the board with horizontally or vertically placed tiles. Or both. (This allows the configuration I gave.) |
|
Except for the part where IT ISN'T A TILING. So it does not adhere to the strategy I gave, even IF you insist on interpreting the "or" as "and/or". Please stop ignoring the requirement that it has to be a tiling. It is right there in my first post in this thread: "if you tile the chessboard ...".
And I'll remind you that in the English language, even British English, "or" is very most often used as an exclusive or. You may also noticed that I use "or", not "v". If I had wanted to capture the strategy in mathematically terms, I would have attempted to do so.
|
| « Last Edit: Aug 30th, 2010, 8:20am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Pawn on a NxN chessboard
« Reply #18 on: Aug 31st, 2010, 8:15am » |
Quote Modify
|
My 2 cents
As far as I can tell towr's proof is correct. But since the existence of a tiling wasn't established at first, ThudanBlunder's request for clarification was legitimate, I guess.
So you are both right. Let's move on.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print