Question 22

There are $$π‘š$$ blue marbles and $$𝑛$$ red marbles on a table. Armaan and Babita play a game by taking turns. In each turn the player has to pick a marble of the colour of his/her choice. Armaan starts first, and the player who picks the last red marble wins. For how many choices of $$(m,n)$$ with $$1 \le m,n \le 11$$ can Armaan force a win?


Correct Answer: 66

Call the game position $$(b,r)$$ when $$b$$ blue and $$r$$ red marbles remain, with $$r\ge 1$$ (the game ends as soon as $$r=0$$).

A position is winning if the player whose turn it is can force a win from there, otherwise it is losing. We build the table of positions by using the standard rule:

β€’ A position is winning $$\Longleftrightarrow$$ it has at least one move to a losing position.
β€’ A position is losing $$\Longleftrightarrow$$ every legal move goes to a winning position.

Step 1: Base positions
If $$r=1$$, the current player can simply pick that last red marble and wins immediately. Hence for every $$b\ge 0$$, the position $$(b,1)$$ is winning.

Step 2: Positions with $$r=2$$

  • $$\,(0,2):$$ only move is $$\rightarrow(0,1)$$ (winning), so $$(0,2)$$ is losing.
  • $$\,(1,2):$$ moves are $$\rightarrow(1,1)$$ (winning) and $$\rightarrow(0,2)$$ (losing). Β There is a move to a losing position, so $$(1,2)$$ is winning.
  • $$\,(2,2):$$ moves are to $$(2,1)$$ (winning) and $$(1,2)$$ (winning). Β Both give the opponent a winning position, so $$(2,2)$$ is losing.
  • Continuing likewise, one finds that for $$r=2$$ the position is losing when $$b$$ is even and winning when $$b$$ is odd.

Step 3: Positions with $$r=3$$
Work exactly as above beginning with $$(0,3)$$. The pattern reverses: $$(b,3)$$ is losing when $$b$$ is odd and winning when $$b$$ is even.

Step 4: General parity rule for $$r\ge 2$$
Induction on $$r$$ now shows the rule:

For every $$r\ge 2$$, the position $$(b,r)$$ is losing iff $$b$$ and $$r$$ have the same parity (either both even or both odd). Otherwise it is winning.

The induction step is simple: assume the rule for $$r-1$$. β€’ If $$b$$ and $$r$$ differ in parity, the move β€œremove a red marble” goes to $$(b,r-1)$$ where parity matches, hence a losing position for the opponent, making $$(b,r)$$ winning.
β€’ If $$b$$ and $$r$$ have the same parity, removing a blue marble keeps parity the same, and removing a red marble changes parity; both successor positions are winning for the opponent by the induction hypothesis, so $$(b,r)$$ is losing.

Step 5: Counting losing starting positions
Armaan starts from $$(m,n)$$ with $$1\le m,n\le 11$$.

β€’ When $$n=1$$, the position is always winning (Step 1).
β€’ For $$n\ge 2$$, the start is losing exactly when $$m$$ and $$n$$ have the same parity.

Count these losing pairs:

Even $$n$$ in the range 2-11: $$2,4,6,8,10$$ (5 values). For each, even $$m$$ can be $$2,4,6,8,10$$ (5 choices). Total = $$5\times5 = 25$$.

Odd $$n$$ in the range 3-11: $$3,5,7,9,11$$ (5 values). For each, odd $$m$$ can be $$1,3,5,7,9,11$$ (6 choices). Total = $$5\times6 = 30$$.

Total losing starts = $$25+30 = 55$$.

Step 6: Winning starts for Armaan
Total possible pairs = $$11\times11 = 121$$.
Winning positions = $$121-55 = 66$$.

Hence Armaan can force a win for exactly 66 ordered pairs $$(m,n)$$ with $$1\le m,n\le 11$$.

Final Answer: 66

Get AI Help

Video Solution

video

Book Free CAT Mentorship

Get personalized CAT strategy from a 99%iler

500+ students mentored
CAT mentor
banner

banner

50,000+ JEE Students Trusted Our Score Calculator

Predict your JEE Main percentile, rank & performance in seconds

Ask AI