6
$\begingroup$

It was the first meeting of the humans and the aliens, and things were going well: The humans and aliens had learned to understand each other's language and found that both were hoping for a peaceful relationship. In this spirit, the alien and human ambassador decided to play a game.

The human ambassador put a queen on a chessboard. She explained the rules of the game:

We will take turns moving this queen around the board. Each move, it must get closer to the top left corner. Whoever moves the queen to the top left corner, however, loses. The queen can move-

At which point the alien interrupted

Yes, yes. We know how queens move on our planet too!

This exchange proved to produce a fateful misunderstanding: The aliens believed queens could make the same moves as a rook or a knight - that is, they would move the piece straight up or left, or go left two and up one, or go up two and left one. The humans believed queens moved in a straight up, diagonal, or leftward line.

Not realizing this, they began playing the game. If we label the top left square $(0,0)$, the square right of it as $(1,0)$ and the square below it as $(0,1)$ and continue with coordinates analogously, then they started by placing the queen at $(2,3)$.

The human ambassador played first, moving the queen up to $(2,2)$, knowing this was a winning strategy. She was very surprised when the aliens made the knight-leap to $(1,0)$, forcing her to move to $(0,0)$ and lose. The alien ambassador smiled and asked,

How could you not have seen such a standard move?

The human ambassador immediately understood how the aliens believed the game worked, but politely said nothing. They played again, starting at $(4,2)$ this time. The aliens started, moving to $(3,2)$, believing this to be a winning move. They were very surprised when the humans moved the queen to $(1,0)$, diagonally upwards, forcing the aliens to lose. The aliens were too polite to say anything, but realized how the silly humans must believe queens moved.


Both species understanding how their opponent would move queens, they played many more games, and became very confident about it. After a while, the aliens asked,

Shall we make a bet? Whoever wins the next game will be declared the best species in the universe and will be entitled to ownership of their opponent's planet! We will make this fair: We choose the starting position, you choose which player moves first.

The aliens placed an enormous, $1000000\times 1000000$ chess board on the table. The human ambassador quickly accepted, knowing that a queen moving diagonally was far more powerful than one that could merely make knight leaps. The aliens placed the queen at the position $(170000,170002)$.

What should the human ambassador do?

$\endgroup$
  • $\begingroup$ Just to clarify, I'm assuming the top left corner is not set base on their perspectives, and the board can not be rotated to change the 'top left' corner? $\endgroup$ – Mark N May 22 '15 at 20:00
  • $\begingroup$ @MarkN Yes; the corner is fixed relative the board. $\endgroup$ – Milo Brandt May 22 '15 at 20:03
  • $\begingroup$ This is just a really distorted version of Wythoff's Nim, correct? $\endgroup$ – mdc32 May 22 '15 at 22:01
  • 1
    $\begingroup$ The dialog leaves things somewhat unclear - do both sides agree to the same set of moves for the queen, or is each side moving the queen only as 'their' rules allow it? $\endgroup$ – Steven Stadnicki May 23 '15 at 1:05
  • 1
    $\begingroup$ @StevenStadnicki Each side moves as their rules allow. $\endgroup$ – Milo Brandt May 23 '15 at 1:06
4
$\begingroup$

The human ambassador cannot win.

If either player moves to (0,x) where x>1, they lose because their opponent moves to (0,1). Similarly, (x,0) loses. (1,x) and (x,1) where x>0 also lose for the same reason.

If the human ever moves to (2,2), the alien can move to (1,0), so the human loses. But if the alien moves to (2,2), the human has no move that doesn't lose.

So if the human ever moves to (2,x) or (x,2) where x>2, they lose because the alien can move to (2,2).

If the alien moves to (2,x) or (x,2) where x>3, the human has no move that does not go to one of the previous losing positions. The alien always has such a move unless the human moves to (3,x) or (x,3).

But then the alien can move to (3,3), where the human has no move that does not lose.

So the alien always wins.

$\endgroup$
  • $\begingroup$ Everything you have looks correct, but it'd be nice to extend it to arbitrary $(x,y)$, since as it's written, it doesn't clearly address cases where $x$ and $y$ are both greater than $3$. (Since it is more complicated than "any such position the is an alien win, regardless of who starts" - even though the given position is an alien win) $\endgroup$ – Milo Brandt May 23 '15 at 1:01
  • 2
    $\begingroup$ The same reasoning shows that the human cannot win unless they can immediately move to (0,1), (1,0), or (3,3). $\endgroup$ – f'' May 23 '15 at 1:06
1
$\begingroup$

The human ambassador should prepare for war, since he will lose this game.

This reasoning is mostly due to user12408's answer, please give credit to them.

First, some observations. When I say a position is losing (winning), I mean that if either player starts there, they will lose (win).

When the smaller of $x,y$ is $0$ or $1$...

  • (0,1) and (1,0) are losing. Everything else has one of these as an option, so is winning.

When the smaller of $x,y$ is $2$...

  • the alien wins. From (2,2), he wins by moving to (1,0). From anything else, he moves to (2,2).

  • the human wins starting from (3,2) and (2,3) by moving to (1,0) or (0,1), respectively.

  • the human loses starting from all other squares whose smallest coordinate is 2. If he moves to $(2,y)$ or $(x,2)$, the alien wins [see first bullet in this section]. Else, he must move to somewhere discussed in the first section, which can't be (0,1) or (1,0), so he loses.

When both $x,y\ge 3$...

  • the alien loses starting from (3,3). The choices (3,0), (3,1), (0,3), (1,3), (2,1) and (1,2) are bad [see first section]. His other options, (2,3) and (3,2), don't work either [see second section].
  • otherwise the alien wins. When $x>3$, the winning move is $(x,2)$. When $y>3$, it is $(2,y)$.

We have shown the alien wins starting anywhere, except for the "bad" places (0,1), (1,0) and (3,3). Thus, the humans can only win if they can move to one of these places, showing that (170000,170002) is a loss for the humans if they start there. It is also a loss for the humans if the aliens start there, since it is not one of the three "bad" places. Thus, humanity is doomed by their lack of mathematical rigor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.