BdMO National 2021 Junior Problem 12

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
User avatar
Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:
BdMO National 2021 Junior Problem 12

Unread post by Anindya Biswas » Mon Apr 12, 2021 1:12 pm

\(1 < N \leq 2021\) একটা ধনাত্মক পূর্ণসংখ্যা। \(1, 2, 3, \cdots, N\) সংখ্যাগুলো একটা সারিতে এই ক্রমে সাজানো আছে। জয়দীপ আর মুরসালিন একটা খেলা খেলছে যেখানে তারা পালাক্রমে সারির যেকোনো দুটো পরপর সংখ্যা বাছাই করে, মুছে দেয় এবং তাদের যোগফল বা গুণফলটা লিখে দেয়। ফলে প্রতি চালে সংখ্যাগুলোর সংখ্যা ঠিক এক করে কমে যায়। খেলায় প্রথম চালটা জয়দীপ দেয়। খেলাটা শেষ হয় যখন খালি একটা সংখ্যা বাকি থাকে এবং জয়দীপ জেতে যদি আর কেবল যদি সেই সংখ্যাটা বিজোড় হয়। \(N\)-এর সম্ভাব্য যেসব মানের জন্য জয়দীপের একটা জেতার স্ট্র্যাটেজি আছে, তাদের যোগফল কত?

Let $1<N\leq2021$ be a positive integer. The numbers $1, 2, 3,\cdots,N$ are written in a row in this order. Joydip and Mursalin play a game where they each take turns erasing two consecutive numbers from the board and replacing them with either their sum or their product. As a result, the number of numbers goes down by one in each turn. Joydip goes first. The game ends when there is only a single number left and Joydip wins if and only if this number is odd. What is the sum of all possible values of $N$ for which Joydip has a winning strategy?
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

noobra
Posts:3
Joined:Wed Mar 24, 2021 4:11 pm

Re: BdMO National 2021 Junior Problem 12

Unread post by noobra » Thu Aug 05, 2021 7:54 pm

Can someone give a solution to this problem?

User avatar
Anindya Biswas
Posts:263
Joined:Fri Oct 02, 2020 8:51 pm
Location:Magura, Bangladesh
Contact:

Re: BdMO National 2021 Junior Problem 12

Unread post by Anindya Biswas » Thu Aug 05, 2021 11:43 pm

Anindya Biswas wrote:
Mon Apr 12, 2021 1:12 pm
\(1 < N \leq 2021\) একটা ধনাত্মক পূর্ণসংখ্যা। \(1, 2, 3, \cdots, N\) সংখ্যাগুলো একটা সারিতে এই ক্রমে সাজানো আছে। জয়দীপ আর মুরসালিন একটা খেলা খেলছে যেখানে তারা পালাক্রমে সারির যেকোনো দুটো পরপর সংখ্যা বাছাই করে, মুছে দেয় এবং তাদের যোগফল বা গুণফলটা লিখে দেয়। ফলে প্রতি চালে সংখ্যাগুলোর সংখ্যা ঠিক এক করে কমে যায়। খেলায় প্রথম চালটা জয়দীপ দেয়। খেলাটা শেষ হয় যখন খালি একটা সংখ্যা বাকি থাকে এবং জয়দীপ জেতে যদি আর কেবল যদি সেই সংখ্যাটা বিজোড় হয়। \(N\)-এর সম্ভাব্য যেসব মানের জন্য জয়দীপের একটা জেতার স্ট্র্যাটেজি আছে, তাদের যোগফল কত?

Let $1<N\leq2021$ be a positive integer. The numbers $1, 2, 3,\cdots,N$ are written in a row in this order. Joydip and Mursalin play a game where they each take turns erasing two consecutive numbers from the board and replacing them with either their sum or their product. As a result, the number of numbers goes down by one in each turn. Joydip goes first. The game ends when there is only a single number left and Joydip wins if and only if this number is odd. What is the sum of all possible values of $N$ for which Joydip has a winning strategy?
We wil call $N$ a "good" number if Joydip vaiya has a winning strategy.
Claim 1 : If $N$ is good, then $N$ is even.
Proof : Let's assume, $N$ is odd. Then, for the alternating nature of this game, the last move (when there are only $2$ numbers left) will be given by Mursalin vai. We know that for any pair of integers $a,b$ at least one of $a+b$ or $ab$ must be even. So, Mursalin vaiya would be able to write a number which is even and Joydip vaiya loses. So, a good number must be even.

Claim 2 : If $N$ is even, then $N$ is good.
Proof : We will only consider $\pmod{2}$. Note that,
$(1,2,3,\dots,N-1,N)\equiv(1,0,1,\dots,1,0)\pmod{2}$
Which is a alternating pattern of $1$ and $0$, starting from $1$, ending at $0$.
Now, after every move by Joydip's vaiya, there will be an odd number of numbers left on the row.
Our claim is, no matter which position Mursalin vaiya moves to, Joydip vaiya would be able move to a position where the numbers are in alternating pattern in mod $2$, starting and ending at $1$.

We can prove it in induction style, for the base case, Joydip vaiya would simply add the last $2$ numbers in the row, which will result in,
$\underbrace{(1,0,1,\dots,0,1)}_{N-1}$, an alternating pattern, starting and ending at $1$, consisting of an odd number of numbers in the row.

Inductive step : Let's assume, after some nonnegative number of moves, Joydip vaiya moves to the position $P_k=\underbrace{(1,0,1,\dots,0,1)}_{k}$ where $k$ is an odd integer, $3\leq k\leq N-1$. We have to show that no matter which position Mursalin vaiya moves from here, Joydip vaiya can move to the position $P_{k-2}=\underbrace{(1,0,1,\dots,0,1)}_{k-2}$.

Now, according to the rule of the game, Mursalin vaiya must choose $2$ consecutive numbers $a,b$. For the alternating nature of the current position. Now, either $(a,b)\equiv(1,0)\pmod{2}$
or, $(a,b)\equiv(0,1)\pmod{2}$.
For the first case, the number coming after $a,b$ must be $1$ in mod $2$.
For the second case, the number coming before $a,b$ must be $1$ in mod $2$.
So, for either case, we can consider a number before or after Mursalin vaiya's chosen numbers, giving us the triplet $(1,0,1)$ which is equivalent to $(a,b,1)$ or $(1,a,b)$ in mod $2$.
From here, we can easily see that, Mursalin vaiya can remove at most $1$ of this $1$s from this triplet since he is limited to operate on only $2$ consecutive numbers here. So, using the other $1$, Joydip vaiya can add or multiply the number given by Mursalin vaiya after the operation to get to $1$.
Example : $(1,0,1)\xrightarrow{M}(1,x)\xrightarrow{J}(1)$. [Here, either $x\cdot1$ or $x+1$ must be odd]

So, after performing this algorithm, the whole triplet $(1,0,1)$ turns to just $(1)$. The rest of the numbers are untouched. So, considering them, Joydip vaiya has now reached the position $P_{k-2}=\underbrace{(1,0,1,\dots,0,1)}_{k-2}$.
So, by induction, Joydip vaiya can always maintain this pattern after his turns.
If Joydip vaiya follows this algorithm, in the last turn, the number will become $(1)$, fulfilling the condition for Joydip vaiya to win.

So, our answer is, $2+4+6+\cdots+2020=\boxed{1021110}$
"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is."
John von Neumann

Post Reply