1
$\begingroup$

I'm asked to do answer the following question:

Two players are playing a game. They have a gameboard with boxes $1-100.$ When it's player 1's turn, he places a goose (this is a Dutch game) on one of the boxes. If this is box t, player $2$ is not allowed to put another goose on $t-20, t-10, t, t+10$ or $t+20.$ So, one cannot place a goose at box $11$ if there is already a goose on $1, 21$ or $31$ (91 doesn't count here). The player who cannot place a goose on one of the boxes anymore, has lost the game. After how many turns do we know who the winner is?

I think it might have to do something with the pigeonhole principle, but I'm not sure how to prove this.

Is there someone who knows how to start this?

$\endgroup$
  • $\begingroup$ Just to clarify, placing a goose on box $t$ forbids future placements on boxes $\{t-20, t-10, t, t+10, t+20\} \cap \{1\ldots 100\}$ (for both players)? $\endgroup$ – Robert Israel Mar 8 '17 at 19:45
  • $\begingroup$ In principle we know it on turn 0, since this game is solvable. But I'm guessing what you're asking is more along the lines of "What is the maximum number of turns a game can take?". $\endgroup$ – eyeballfrog Mar 8 '17 at 19:51
  • 2
    $\begingroup$ I love that 'it is a Dutch game' instantly explains why it should be a goose! Everything instantly makes sense now. $\endgroup$ – user334732 Mar 8 '17 at 21:32
  • $\begingroup$ yes, @RobertIsrael, thats what I mean! $\endgroup$ – jbuser430 Mar 9 '17 at 10:14
  • $\begingroup$ @eyeballfrog yes thats what I mean $\endgroup$ – jbuser430 Mar 9 '17 at 10:14
0
$\begingroup$

Here is a winning strategy for player 2.

If player $1$ plays a goose on box $t$, then player $2$ plays on box $t+1$ if $t$ is odd, $t-1$ if $t$ is even.

By induction, we can show that in each pair $(2i-1,2i)$, $i=1\ldots50$, after player 2's turn either both are allowed or both are forbidden. Thus it is always possible for player 2 to follow this strategy, no matter what player 1 does.

$\endgroup$
  • $\begingroup$ okay this sounds like a good strategy! but how can I see after how many rounds one has won? $\endgroup$ – jbuser430 Mar 9 '17 at 10:13
  • $\begingroup$ The game can take different amount of turns. For example, 20 geese at 21,22,...,30 and 71,72,...,80 prevent any further goose from being placed anywhere. If both players alternatively put geese at these points, the game will be over after 20 turns (10 turns by player). Similarly, 40 geese at 1,2,...,10 and 31,32,...,40 and 61,62,...,70 and 91,92,...,100 are allowed according to the rules, and thus the game would end after 40 turns. Both scenarios are possible even under the strategy Robert described. It is relatively straightforward to see that these are min and max game length. $\endgroup$ – Ingix Mar 9 '17 at 12:33

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.