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$
1

1 Answer 1

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$
13
  • $\begingroup$ is there a special reason why you chose 4 @barakmanos? $\endgroup$ Sep 24, 2014 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$ Sep 24, 2014 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$ Sep 24, 2014 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, 2014 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$ Sep 25, 2014 at 10:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .