BdMO National Primary 2020 P8

[Mursalin]

শাকুর আর তিহাম কয়েন নিয়ে একটা খেলা খেলছে। একটা টেবিলে \(N\)-টা কয়েন আছে যেখানে \(N\) একটা ধনাত্মক পূর্ণসংখ্যা। তারা পালাক্রমে টেবিল থেকে দুইয়ের পূর্ণসাংখ্যিক পাওয়ার (যেমন \(1, 2, 4, 8, 16, 32, \cdots\)) সংখ্যক কয়েন টেবিল থেকে সরিয়ে ফেলে। যে টেবিল থেকে শেষ কয়েনটা সরিয়ে ফেলতে পারবে, সে জিতে যাবে। যদি শাকুর প্রথম চাল দেয় এবং \(N < 1000\) হয়, তাহলে \(N\)-এর কয়টা মানের জন্য শাকুরের জেতার স্ট্র্যাটেজি আছে (যদি তিহাম নিখুঁতভাবে খেলে)?


Shakur and Tiham play a game with coins. There are \(N\) coins on a table where \(N\) is a positive integer. The players take turns removing a number of coins that is an integer power of \(2\) (such as \(1, 2, 4, 8, 16, 32, \cdots\)). The person who removes the last coin from the table wins. If Shakur goes first and \(N\) is a positive integer less than \(1000\), for how many values of \(N\) does Shakur have a winning strategy (even if Tiham plays perfectly)?

[Anindya Biswas]

The problem is asking for the numbers $N$ for which Shakur can force a win. Just like tic-tac-toe, but in that case, if both player plays perfectly, the game always ends up in a draw. But in this game, clearly draw isn't a case.
We define, $f:\mathbb{N}\cup\{0\}\to\{0,1\}$ such that
\[\forall N\geq1,f(N) =\left\{\begin{array}{100}1 & \mbox{if Shakur has a winning strategy for }N \\0 & \mbox{otherwise}\end{array}\right.\]
We also define$f(0)=0$ since if it's your turn and the number of coins is $0$, that means you lost and the game terminates.

$\text{Lemma :}$ Let $k(N)$ be the greatest integer for which $N\geq2^{k(N)}$. Then,
\[1-f(N)=\prod_{j=0}^{k(N)}f(N-2^j)\]
$\text{Proof :}$
Let's consider the product, \[P_N=\prod_{j=0}^{k(N)}f(N-2^j)\] Where $k(N)$ is the greatest integer for which $N-2^{k(N)}\geq0$.
Since $\forall j, 0\leq j\leq k, f(N-2^j)\in\{0,1\}$, we conclude that $P_N\in\{0,1\}$

• Case 1 : $P_N=1$
  $P_N=1$ if and only if $\forall j, 0\leq j\leq k(N), f(N-2^j)=1$.
  So, whatever power of $2$ Shakur chooses, he will always end up with a number that ensures win for Tiham. So, Shakur does not have a winning strategy for $N$.
  $\therefore f(N)=0\Longrightarrow1-f(N)=1=P_N$.
  So, our lemma is true for $P_N=1$.

• Case-2 : $P_N=0$
  $P_N=0$ if and only if $\exists j, 0\leq j\leq k(N), f(N-2^j)=0$
  In this case, Shakur would choose $2^j$ such that $f(N-2^j)=0$. Now, in Tiham's turn, he has got a number for which he does not have a winning strategy. That means he cannot force a win from here. So, if Shakur plays perfectly, he would win, since if he loses even after playing perfectly, that means Tiham has a winning strategy for $N-2^j$ which is obviously not the case. So, Shakur has a winning strategy for $N$.
  $\therefore f(N)=1\Longrightarrow1-f(N)=0=P_N$.
  So, our lemma is true for $P_N=0$

This completes the proof of our lemma. $\text{Q.E.D.}$

Now we will prove the following claim using the principle of mathematical induction.
$\text{Claim :}$ \[f(N) =\left\{\begin{array}{100}0 & \mbox{if }3|N \\1 & \mbox{otherwise}\end{array}\right.\]

• Base case : $N\in\{0,1,2\}$
  We use our $\text{Lemma}$ and we get,
  $f(0)=0$,
  $f(1)=1-f(0)=1$,
  $f(2)=1-f(1)f(0)=1$

• Induction Hypothesis : Let's assume out claim is true for $N\in\{0,1,2,\dots,3m,3m+1,3m+2\}$ where $m\in\mathbb{N}\cup\{0\}$
  We will prove that our claim is also true for $N\in\{3m+3,3m+4,3m+5\}$

• Inductive Step :
  • $N=3m+3$
    Using our lemma,
    $f(N)=1-P_{3m+3}=1-f(3m+2)f(3m+1)\cdots f\left(3m+3-2^{k(3m+3)}\right)$
    Since $\forall j, 0\leq j\leq k(3m+3), 3\nmid3m+3-2^j$
    By our induction hypothesis, we get, $f(3m+3-2^j)=1\Longrightarrow P_{3m+3}=1\Longrightarrow f(N)=0$.
  • $N=3m+4$
    In this case, we have, $f(N-1)=0\Longrightarrow P_N=0\Longrightarrow f(N)=1$
  • $N=3m+5$
    In this case, we have, $f(N-2)=0\Longrightarrow P_N=0\Longrightarrow f(N)=1$

So, by Principle of mathematical induction, our claim is proved for all $N\in\mathbb{N}\cup\{0\}$. $\text{Q.E.D.}$

So, the number of $N$s between $1$ and $999$ for which Shakur has a winning strategy is,
\[\boxed{\sum_{k=1}^{999}f(k)=\sum_{3\nmid k, 1\leq k\leq999}1=666}\]

[Mehrab4226]

The problem is asking for the numbers $N$ for which Shakur can force a win. Just like tic-tac-toe, but in that case, if both player plays perfectly, the game always ends up in a draw. But in this game, clearly draw isn't a case.
We define, $f:\mathbb{N}\cup\{0\}\to\{0,1\}$ such that
\[\forall N\geq1,f(N) =\left\{\begin{array}{100}1 & \mbox{if Shakur has a winning strategy for }N \\0 & \mbox{otherwise}\end{array}\right.\]
We also define$f(0)=0$ since if it's your turn and the number of coins is $0$, that means you lost and the game terminates.

$\text{Lemma :}$ Let $k(N)$ be the greatest integer for which $N\geq2^{k(N)}$. Then,
\[1-f(N)=\prod_{j=0}^{k(N)}f(N-2^j)\]
$\text{Proof :}$
Let's consider the product, \[P_N=\prod_{j=0}^{k(N)}f(N-2^j)\] Where $k(N)$ is the greatest integer for which $N-2^{k(N)}\geq0$.
Since $\forall j, 0\leq j\leq k, f(N-2^j)\in\{0,1\}$, we conclude that $P_N\in\{0,1\}$

• Case 1 : $P_N=1$
  $P_N=1$ if and only if $\forall j, 0\leq j\leq k(N), f(N-2^j)=1$.
  So, whatever power of $2$ Shakur chooses, he will always end up with a number that ensures win for Tiham. So, Shakur does not have a winning strategy for $N$.
  $\therefore f(N)=0\Longrightarrow1-f(N)=1=P_N$.
  So, our lemma is true for $P_N=1$.

• Case-2 : $P_N=0$
  $P_N=0$ if and only if $\exists j, 0\leq j\leq k(N), f(N-2^j)=0$
  In this case, Shakur would choose $2^j$ such that $f(N-2^j)=0$. Now, in Tiham's turn, he has got a number for which he does not have a winning strategy. That means he cannot force a win from here. So, if Shakur plays perfectly, he would win, since if he loses even after playing perfectly, that means Tiham has a winning strategy for $N-2^j$ which is obviously not the case. So, Shakur has a winning strategy for $N$.
  $\therefore f(N)=1\Longrightarrow1-f(N)=0=P_N$.
  So, our lemma is true for $P_N=0$

This completes the proof of our lemma. $\text{Q.E.D.}$

Now we will prove the following claim using the principle of mathematical induction.
$\text{Claim :}$ \[f(N) =\left\{\begin{array}{100}0 & \mbox{if }3|N \\1 & \mbox{otherwise}\end{array}\right.\]

• Base case : $N\in\{0,1,2\}$
  We use our $\text{Lemma}$ and we get,
  $f(0)=0$,
  $f(1)=1-f(0)=1$,
  $f(2)=1-f(1)f(0)=1$

• Induction Hypothesis : Let's assume out claim is true for $N\in\{0,1,2,\dots,3m,3m+1,3m+2\}$ where $m\in\mathbb{N}\cup\{0\}$
  We will prove that our claim is also true for $N\in\{3m+3,3m+4,3m+5\}$

• Inductive Step :
  • $N=3m+3$
    Using our lemma,
    $f(N)=1-P_{3m+3}=1-f(3m+2)f(3m+1)\cdots f\left(3m+3-2^{k(3m+3)}\right)$
    Since $\forall j, 0\leq j\leq k(3m+3), 3\nmid3m+3-2^j$
    By our induction hypothesis, we get, $f(3m+3-2^j)=1\Longrightarrow P_{3m+3}=1\Longrightarrow f(N)=0$.
  • $N=3m+4$
    In this case, we have, $f(N-1)=0\Longrightarrow P_N=0\Longrightarrow f(N)=1$
  • $N=3m+5$
    In this case, we have, $f(N-2)=0\Longrightarrow P_N=0\Longrightarrow f(N)=1$

So, by Principle of mathematical induction, our claim is proved for all $N\in\mathbb{N}\cup\{0\}$. $\text{Q.E.D.}$

So, the number of $N$s between $1$ and $999$ for which Shakur has a winning strategy is,
\[\boxed{\sum_{k=1}^{999}f(k)=\sum_{3\nmid k, 1\leq k\leq999}1=666}\]

You do know this is overkill for primary students. A simpler approach,
Solution:

We claim that S(Shakur) cannot win when $3|N$
Proof:
It is easy to see that when there are $3$ coins S will definitely lose.
Let's say $N$ is a multiple of $3$. If S(Shakur) takes any power of 2 coins, there will never be a multiple of 3 coins remaining on the table. So T(Tiham) can easily take another 1 or 2 coins and get a multiple of 3 on the table. Now the number of coins n the table is a multiple of $3 <N$. So similar things will happen and S will have a turn when there are 3 coins on the table. So, S will lose. $\square$
If N is not a multiple of 3, then there $N=3k+1$ or $N=3k+2$ so S can take either 1 or 2 coins from the table and make the number of coins on the table a multiple of 3. So T will lose as he has to start with a multiple of 3.

So the total number of multiples of 3 between 1-999 is 333. So the number of N for which S will have a strategy to win is $999-333=666$(Ans)

Explanation:

Let us think about $N=1,2,3,4,5,6$. By this, we can grasp the problem and also what is going on. I will denote shakher by S and Tiham by T.
Now, if $N=1$ S will win easily by taking the coin.
if $N=2$ S will also win easily by taking the 2 coins.

if $N=3$ S cannot win, because he has only 2 move each will lead to T's victory.

if $N=4$ S will win again by taking the 4 coins as 4 is a power of 2

if $N=5$ S can win again. Because S can take 2 coins and make 3 coins on the table making T's win impossible. Because this is just as when $N=3$ but T is taking the first move so S will win.

if $N=6$ S will lose because he has 3 choices take $1,2 or,4$ coins.But each will lead to T's victory. If we take 1 T can win using S's strategy when$ N=5$ and for the other 2 choices T can take all the coins on the table.

By now we can understand that multiples of 3 are a little bit weird. So S should probably avoid getting a multiple of 3 on the table when it is S's turn. He can also do another thing very cleverly. That is giving a multiple of 3 in T's turn. So by now, we have a conjecture. That is if S has a multiple of 3 on the table S will lose, or S will not have a winning strategy. The rest proof is in the solution section.

[Anindya Biswas]

You do know this is overkill for primary students.

Yeah, I know, It's actually fun that $80\%$ of what I wrote is irrelevant. But I could not resist sharing the idea of taking a product or using a indicator function. Maybe it would be relevant in some other problem.
Congratulations for your $100^{\text{th}}$ post by the way. I think you are the first person to reach $100$ ever since the forum activated again after a long sleep.

[Mehrab4226]

You do know this is overkill for primary students.

Congratulations for your $100^{\text{th}}$ post by the way. I think you are the first person to reach $100$ ever since the forum activated again after a long sleep.

Thanks . It is maybe because there aren't that many people posting in the forum