## BdMO National Primary 2020 P8

Mursalin
Posts:68
Joined:Thu Aug 22, 2013 9:11 pm
BdMO National Primary 2020 P8
শাকুর আর তিহাম কয়েন নিয়ে একটা খেলা খেলছে। একটা টেবিলে $$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)?
This section is intentionally left blank.

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Contact:

### Shakur should be afraid of the evil number $3$

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}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm

### Re: Shakur should be afraid of the evil number $3$

Anindya Biswas wrote:
Wed Mar 17, 2021 5:53 pm
You do know this is overkill for primary students. A simpler approach,
Solution:
Explanation:
The Mathematician does not study math because it is useful; he studies it because he delights in it, and he delights in it because it is beautiful.
-Henri Poincaré

Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Contact:

### Re: Shakur should be afraid of the evil number $3$

Mehrab4226 wrote:
Wed Mar 17, 2021 8:27 pm
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.
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Mehrab4226
Posts:230
Joined:Sat Jan 11, 2020 1:38 pm
### Re: Shakur should be afraid of the evil number $3$
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.