5
$\begingroup$

The game begins with a row of $n$ numbers, in increasing order from $1$ to $n$. For example, if $n=7$, we have a row of numbers $(1,2,3,4,5,6,7)$.

On each turn, a player must either remove 1 number, or remove 2 consecutive numbers. For example, the first player to move can remove $2$ or remove 5 and 6 together.

The player who removes the last number wins. Is there a winning strategy for the player who goes first?

p.s. Sorry for the initial confusion. Here are some clarifications. (1) There are two players. (2) Let's say 4 is removed on the first turn. This does NOT make 3, 5 consecutive. So a player can never remove 3 and 5 together.

$\endgroup$
6
$\begingroup$

Example strategy for $n=7$:

The first player takes $4$, and then until the last element:

  • If the second player takes $x$, then the first player takes $8-x$.

  • If the second player takes $(x,x+1)$, then the first player takes $(7-x,8-x)$.


General strategy for an odd $n$:

The first player takes $\dfrac{n+1}{2}$, and then until the last element:

  • If the second player takes $x$, then the first player takes $n+1-x$.

  • If the second player takes $(x,x+1)$, then the first player takes $(n-x,n+1-x)$.


General strategy for an even $n$:

The first player takes $(\dfrac{n}{2},\dfrac{n}{2}+1)$, and then until the last element:

  • If the second player takes $x$, then the first player takes $n+1-x$.

  • If the second player takes $(x,x+1)$, then the first player takes $(n-x,n+1-x)$.


Conceptual proof:

A pickable element is either a single number or a pair of consecutive numbers.

You can think of the element in the middle as a mirror.

It is the only pickable element that doesn't have a "reflecting counterpart".

So by picking this element first, you guarantee that for every element that your opponent picks, you can pick the corresponding element (located on "the other side of the mirror"), thus win the game...

$\endgroup$
  • $\begingroup$ is there a special reason why you chose 4 @barakmanos? $\endgroup$ – Sherlock Holmes Sep 24 '14 at 8:12
  • $\begingroup$ @SherlockHolmes: Yes, once you pick $X=4$, the other player cannot pick $8-X$ (because you've already picked it). $\endgroup$ – barak manos Sep 24 '14 at 8:13
  • $\begingroup$ I thought the question as worded was just to find a winning strategy for n numbers, not for n=7 though? $\endgroup$ – Sherlock Holmes Sep 24 '14 at 8:15
  • 1
    $\begingroup$ @SherlockHolmes I really appreciate your help. I think I understand that the point is for the first player to remove the center number (if n is odd) or the centermost two numbers (if n is even) to create a mirroring strategy. Thank you so much. $\endgroup$ – user12488 Sep 24 '14 at 8:18
  • 1
    $\begingroup$ @Trismegistos: Think of the element in the middle as a mirror. It is the only element that doesn't have a "reflecting counterpart". So for every other element that the second player picks, the first player can pick the corresponding element located "on the other side of the mirror". In the case of $n=7$, this element is $4$. In the general case of an odd $n$, this element is a single number $\frac{n+1}{2}$. In the general case of an even $n$, this element is a pair of numbers $\frac{n}{2},\frac{n}{2}+1$. $\endgroup$ – barak manos Sep 25 '14 at 10:48

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.