Aashna and Radhika see the integers $1$ to $211$ written on a blackboard. They alternate turns and in every step each of them wipes out any $11$ numbers until only $2$ numbers are left on the blackboard. If the difference of these $2$ numbers (by subtracting the smaller from the larger) is $\geq 111$, the first player wins, otherwise the second. If you were Aashna, would you chose to play 1st or 2nd and why?

By intuition only – I don’t see how I can prove it:

Since there are 19 turns ($19\times 11=209$ numbers + 2 on the blackboard), I would choose to play 1st. In my 1st move I would wipe out numbers 101 to 111 since these are the only ones that do not have a pair to meet the rule. Then for whichever numbers Radhika would remove, I would respond by removing the numbers that would have a difference of 111, for example for 92 I wipe out 203 etc. If Radhika chose to remove pairs with difference equal to 111, there would still be a single number, for which I would remove its pair and then I would also remove pairs with difference 111 or 112 and so on.

Does this method guarantee a win?

  • $\begingroup$ Use $\ge$ for $\ge$. $\endgroup$ – Shaun Sep 18 '18 at 11:35
  • $\begingroup$ Use $\times$ for $\times$. $\endgroup$ – Shaun Sep 18 '18 at 11:36
  • 2
    $\begingroup$ @Shaun: thanks, edited. $\endgroup$ – Reyansh Laghari Sep 18 '18 at 11:40

There are $100$ pairs with difference $111$: $\{1,112\}$, $\{2,113\}$, $\ldots$, $\{100,211\}$. As you noticed, there are $11$ numbers that are unpaired are $101$, $102$, $\ldots$, $111$. Since the second player can eliminate at most $9\cdot 11$ numbers, the second player does not touch at least one pair of difference $111$. Thus, if the first player does not play stupidly by corrupting these pairs, then the first player can always win.

You have recommended a good strategy. In the first move, the first player proceeds by removing the $11$ unpaired numbers $101$, $102$, $\ldots$, $111$. Every turn after the second player played, if the number $x\in\{x,y\}$ with $|x-y|=111$ was remove but $y$ was not, then the first player responds by removing $y$. Since $11$ is odd, the number of such $x$'s that the second player removed must be odd. Thus, the first player will remove an odd number of such $y$'s. If the first player has not completed the turn (i.e., fewer than $11$ numbers have been played), then there are an even numbers left to remove. Then, the first player remove both numbers form some pairs with difference $111$ until the turn is finished. Therefore, by the end of the $(2k+1)$-st turn, only $11k$ pairs of difference $111$ have been killed (and other pairs are completely untouched).


If you chose to play first you would have 10 turns. -> 10 x 11 = 110

If you chose to play second you would have 9 turns. -> 9 x 11 = 99

If you are second and remove every high number starting with 211 while the first removes the low numbers you would stop at 211 - 99 = 112.

The last left numbers would be 112 and one number (between 1 and 112).

The first would then only win if that number is 1, because 112 - 1 = 111 (which is >= 111).

If it was the opposite and you would play first you could remove 110 numbers and you would win if the difference is >= 111. There are only 211-111 = 100 numbers with a difference >= 111. Remove all of them and you win.

So your chance of winning by playing first is 100%.


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.