শাকুর আর তিহাম কয়েন নিয়ে একটা খেলা খেলছে। একটা টেবিলে \(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)?

## BdMO National Primary 2020 P8

This section is intentionally left blank.

- Anindya Biswas
**Posts:**264**Joined:**Fri Oct 02, 2020 8:51 pm**Location:**Magura, Bangladesh-
**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\}$

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.\]

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}\]

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$

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$

- $N=3m+3$

**, our claim is proved for all $N\in\mathbb{N}\cup\{0\}$. $\text{Q.E.D.}$***Principle of mathematical induction*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**Location:**Dhaka, Bangladesh

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

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

Solution:

*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:**264**Joined:**Fri Oct 02, 2020 8:51 pm**Location:**Magura, Bangladesh-
**Contact:**

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

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**Location:**Dhaka, Bangladesh

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

Thanks . It is maybe because there aren't that many people posting in the forumAnindya Biswas wrote: ↑Wed Mar 17, 2021 9:17 pm

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.

*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é