Question

Anant and Kapil play a game: Anant starts by writing 1 on a blackboard. Following that, they play alternatively as follows: If the number on the board is $n$, the player erases $n$ and writes either $n + 1$ or $2n$, provided the number to be written is not greater than $2^{2019}$. The person who writes $2^{2019}$ on the blackboard first wins. Who has a winning strategy, Anant or Kapil?


- From Mimamsa 2019 [A National Level Science Quiz]

Answer 1

Before going deeper into the answer, Let's look a basic principle,

If a is not a factor of p ( which is a prime), then it follows that p^n will not have a in its factors. In other words, multiplying p by positive natural numbers including a, then you will never obtain p^n.

So, The winner is one who writes 2^2019 on the board.

Let's say we have 4 cases,

⇒Both players use 2n strategy

⇒ Both players use n+1 strategy

⇒ both players use random strategies.

Since, We need a final winner definitely

We eliminate the third case " players using random strategies"

Why should we eliminate. Let's take an example :

Anant writes 1

Kapil erases 1 and writes 2 ( Both 2n, n +1 yield same here)

Now anant writes 4 ( 2n strategy )

So, If Kapil writes 5 ( using n +1 strategy)

Once 5 comes, You can not go with multiplying or probably doing random things to obtain 2^2019.

So this chance of players using random strategies is eliminated so as to get a final winner.

Now, Look at the first case

Both players using 2n strategy

Anant ( 1st chance of the game) : 1 Odd chance of the game.

Kapil ( uses 2n) : 1*2 = 2^1 [ Even]

Anant ( uses 2n) : 4= 2^n [ Odd]

So let's continue the game with players using 2n on their chance.

We observe that,

2^0 ( Even power) - Odd chance of the game

2^1 ( Odd power) - Even chance

So generalizing, A player who will write 2^n ( such that n is odd, since n = 2019), He will have to be playing Even chance of the game.

Anant writes first, Hence he always plays the odd chance. Thus, Kapil wins.

Now, The case of players writing/using only *n+1* strategy.

Odd chance : Anant - 1 = 1 * 1

Even chance : Kapil - 1 + 1 = 2 =

...

...

...

8th chance = 1 + 7 = 8

16th chance = 1 + 15 = 16

So, 2^2019 th chance will give 2^2019

Anant plays first, so he always plays the odd chance. Since, 2^2019 comes in even chance, kapil will be the winner

There is one more possible case, Players obtain 2^n from there, both will follow only one of strategy to go 2^(n+1) and from there, both will follow only one of strategy to reach 2^(n+2). Such case can have anyone as the winner. But, It's very rare that both will be playing with one of the strategy and reaching 2^n everytime. So this case, can't have a generalized winner. And mostly, In practical conditions you won't have a winner.

Answer 2

Answer :-

Kapil

Reason :-

Now we are going to observe Three Main case :-

⟨i⟩ Both the players will use the same sequence.

⟨ii⟩ Both the players use different sequence.

⟨iii⟩ Both of them use random sequence.

Now we will first cancel out our third case as if they use random sequence hence the winner can be anyone . It is not a possible case to answer.

Now looking forward to the first case.

If they use same sequence either it will be 2n or n + 1

Now as the first number is 1 :-

Then via 2n

Anant is the first one to write , so the next one will be Kapil .

The number goes

1 , 2 , 4 , 8 , 16 ...

Now as we are able to see

1 , 4 , 16. ..... which means that the Even power of 2 ( exept 1) is written by Anant

And 2 , 8 , 32....... the odd Power of 2 is written by Kapil

Now as 2²⁰¹⁹ is a odd Power of 2

Hence Kapil will be the winner .

Now when they will follow the sequence of n+1

the series will be

1 , 2 , 3 , 4 ........

Now here

1 , 3 , 5 ..... are the numbers written by Anant which are odd

And 2 , 4 , 6 ....... are the numbers written by Kapil .

Now as 2²⁰¹⁹ is a even number

So the winner will be Kapil.

Case two :- Both of them use alternate sequence.

Now here are three possiblity here .

(i)One use 2n and another use n + 1

(ii) One use n+1 and another use 2n

(iii) Both of them use 2n and n + 1 in alternate.

(i) Now if one use 2n and another use n + 1

The sequence :-

1 , 2 , 3 , 6 , 7 , 14 , 15 , 30 ..... in this case there is a possibility that they never write 2²⁰¹⁹ So this case is not valid.

(ii) Now if one use n+1 and another use 2n

The sequence :-

1 , 2 , 4 , 5 , 10 , 11 , 22 , 23..... in this case also there is a possibility that they never write 2²⁰¹⁹ So this case is also not valid.

(iii) If they use alternate.

If Anant and Kapil Both start from 2n

1 , 2 , 3 , 4 , 8 , 16 , 17 , 18 , ....... Here also there is no possible case to find out who will write 2²⁰¹⁹

If Anant and Kapil Both start from n+1

1 , 2 , 4 , 8 , 9 , 10 , 20 , 40 ...... Here also there is no possible case to find out who will write 2²⁰¹⁹

So we can also say that if both of them will start from alternate sequence then also there will be no possible case .

So there is more chances of Kapil to win the game.