wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Pawn on a NxN chessboard
        
(Message started by: grad on Aug 29th, 2010, 2:29am)
Title: Pawn on a NxN chessboard
Post by grad on Aug 29th, 2010, 2:29am
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?
Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 29th, 2010, 6:34am
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, [hide]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.[/hide]
Title: Re: Pawn on a NxN chessboard
Post by JohanC on Aug 29th, 2010, 10:58am

on 08/29/10 at 06:34:22, towr wrote:
... at most 63 moves....

Nice analysis.
Maybe N should be taken into account, especially the possibility of N odd?
An interesting observation is that each player [hide]stays on his/her own color[/hide].
Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 29th, 2010, 11:17am
I think that [hide]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.[/hide]
Title: Re: Pawn on a NxN chessboard
Post by grad on Aug 29th, 2010, 12:08pm

on 08/29/10 at 06:34:22, towr wrote:
So if player one could ensure that no dead ends occur, he would always win.


I, too, believe that [hide]if N is even then player A can always find a winning strategy and if N is odd player B wins.[/hide] But there must be a way to actually prove that no dead end occurs or something similar...
Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 29th, 2010, 12:36pm
I gave a strategy that guarantees a win. Isn't that proof enough, or does it need further explanation?
Title: Re: Pawn on a NxN chessboard
Post by ThudanBlunder on Aug 29th, 2010, 12:59pm

on 08/29/10 at 12:36:50, 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'?
Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 29th, 2010, 1:15pm

on 08/29/10 at 12:59:50, 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 (http://en.wikipedia.org/wiki/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 08/29/10 at 12:59:50, 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.  :P
Title: Re: Pawn on a NxN chessboard
Post by ThudanBlunder on Aug 29th, 2010, 1:38pm
The first thing I would do with such a board is turn it round 90o.  :P
Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 29th, 2010, 1:43pm
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.
Title: Re: Pawn on a NxN chessboard
Post by ThudanBlunder on Aug 29th, 2010, 1:49pm

on 08/29/10 at 13:43:38, 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.
Title: Re: Pawn on a NxN chessboard
Post by grad on Aug 29th, 2010, 6:29pm
Oh, ok!  ;D I didn't notice the domino thing in your first post  :-[

Yes, I think that is a nice strategy! Thank you towr!
Title: Re: Pawn on a NxN chessboard
Post by ThudanBlunder on Aug 30th, 2010, 6:03am

on 08/29/10 at 06:34:22, towr wrote:
Actually, if you tile the chessboard with dominoes horizontally (or vertically)...



on 08/29/10 at 13:15:36, towr wrote:
All circumstances where you actually follow the strategy and don't use a strategy that's only superficially similar.  :P

Can I write A (v B) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif A http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/oplus.gif B or are they just superficially similar?
Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 30th, 2010, 6:14am
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.
Title: Re: Pawn on a NxN chessboard
Post by ThudanBlunder on Aug 30th, 2010, 6:30am

on 08/30/10 at 06:14:32, 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.  ;D
Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 30th, 2010, 7:03am

on 08/30/10 at 06:30:49, 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.
Title: Re: Pawn on a NxN chessboard
Post by ThudanBlunder on Aug 30th, 2010, 7:38am

on 08/30/10 at 07:03:45, 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) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 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.)

Title: Re: Pawn on a NxN chessboard
Post by towr on Aug 30th, 2010, 8:19am

on 08/30/10 at 07:38:51, ThudanBlunder wrote:
But A (v B) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/equiv.gif 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.
Title: Re: Pawn on a NxN chessboard
Post by Grimbal on Aug 31st, 2010, 8:15am
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.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board