Kvant Math Problem 1057

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m17s
Source on kvant.digital

Problem

Two players take turns writing natural numbers on the board not exceeding $p$. The rules of the game forbid writing divisors of numbers that have already been written on the board. The player who cannot make the next move loses.

Determine which player has a winning strategy for $p=10$, and describe it.
Determine which player has a winning strategy for $p=1000$.

D. V. Fomin

Exploration

A move consists of writing a number that is not a divisor of any previously written number. If a number $n$ has been written, then every divisor of $n$ becomes permanently forbidden. The set of legal moves therefore shrinks by removing the downward closure of each chosen number in the divisibility poset.

It is useful to look at maximal elements. Among the numbers not exceeding $p$, the numbers greater than $p/2$ have no multiples other than themselves, hence none of them divides any other number $\le p$. Such numbers are maximal in the divisibility order.

For $p=10$, the maximal numbers are $6,7,8,9,10$. If one of them is played, only its divisors are removed. Trying a few moves suggests a pairing phenomenon. The numbers split into chains

$$1\mid 2\mid 4\mid 8,\qquad 3\mid 6,\qquad 5\mid 10,\qquad 7,\qquad 9.$$

The maximal elements are $8,6,10,7,9$. There are five of them, an odd number. Since every legal position contains at least one maximal available element, perhaps the game is equivalent to removing maximal elements one by one. Testing this idea on $p=10$ gives five moves altogether, suggesting a first-player win.

For general $p$, let $M(p)$ be the set of numbers in $(p/2,p]$. Every number $m\in M(p)$ is maximal. Every number $n\le p$ divides at least one maximal element, because some odd multiple of $n$ eventually lies in $(p/2,p]$. Indeed, write $p=nq$. Choosing the largest odd integer $r\le q$ gives

$$\frac q2<r\le q,$$

hence

$$\frac p2<nr\le p.$$

Thus every number belongs to the divisor set of at least one maximal element.

This suggests identifying each move with the removal of one maximal element. If a maximal element $m$ is played, only divisors of $m$ are affected; every other maximal element remains available. Conversely, if a nonmaximal number $n$ is played, at least one maximal multiple of $n$ is removed from future consideration. It becomes natural to regard each maximal element as an independent token. The number of tokens is

$$|M(p)|=p-\left\lfloor \frac p2\right\rfloor=\left\lceil\frac p2\right\rceil.$$

For $p=10$ this gives $5$ tokens, odd. For $p=1000$ it gives $500$ tokens, even. The crucial point is proving rigorously that every move removes exactly one maximal token and that the game ends precisely when all maximal tokens have been removed.

Problem Understanding

We have the set ${1,2,\dots,p}$. Players alternately choose numbers. After a number has been chosen, all of its divisors become forbidden forever. A player unable to move loses.

This is a Type A problem. We must determine which player has a winning strategy for the two specified values of $p$ and justify the strategies.

The core difficulty is understanding the structure of legal positions. The game appears complicated because choosing one number can forbid many others. The key idea is that the relevant objects are the maximal numbers, namely those exceeding $p/2$. Every number divides at least one such maximal number, and each move can be interpreted as eliminating exactly one maximal number from play.

The expected answer is that the first player wins for $p=10$ and the second player wins for $p=1000$, because the numbers exceeding $p/2$ are $5$ in the first case and $500$ in the second.

Proof Architecture

Lemma 1. A number $m$ with $p/2<m\le p$ is maximal in the divisibility order on ${1,\dots,p}$, because any multiple of $m$ larger than $m$ exceeds $p$.

Lemma 2. Every number $n\le p$ divides at least one maximal element, because if $q=\lfloor p/n\rfloor$, the largest odd integer $r\le q$ satisfies $q/2<r\le q$, yielding a maximal multiple $nr$.

Lemma 3. A move is legal exactly when there exists at least one maximal element not yet eliminated that is divisible by the chosen number.

Lemma 4. Every legal move eliminates exactly one previously noneliminated maximal element, namely the chosen number if it is maximal, or one of its maximal multiples if it is not.

Lemma 5. After $k$ moves, exactly $k$ maximal elements have been eliminated.

Lemma 6. The game ends precisely when all maximal elements have been eliminated.

The hardest point is Lemma 4. One must show that a legal move always corresponds to the elimination of a new maximal element and cannot eliminate none.

Solution

Let

$$M={m\in{1,\dots,p}: m>p/2}.$$

By Lemma 1, these are exactly the maximal elements of the divisibility poset on ${1,\dots,p}$.

For each $m\in M$, think of $m$ as a token.

We say that a maximal element $m$ has been eliminated if some chosen number divides $m$. Since the rules forbid choosing a divisor of any previously chosen number, once a divisor of $m$ has been chosen, every divisor of $m$ is forever unavailable. Thus the status of $m$ depends only on whether some chosen number divides it.

We first prove that every number belongs to at least one maximal element.

Let $n\le p$, and let

$$q=\left\lfloor \frac pn\right\rfloor .$$

Choose $r$ to be the largest odd integer with $r\le q$.

If $q$ is odd, then $r=q$, and

$$r>\frac q2.$$

If $q$ is even, then $r=q-1$, and

$$r=q-1\ge \frac q2+1>\frac q2.$$

Hence in both cases

$$\frac q2<r\le q.$$

Multiplying by $n$ gives

$$\frac p2<nr\le p.$$

Therefore $nr\in M$, and $n\mid nr$. Every number divides at least one maximal element.

Now consider a legal move choosing a number $n$.

Since the move is legal, $n$ is not a divisor of any previously chosen number. Suppose every maximal multiple of $n$ had already been eliminated. Then for each maximal multiple $m$ of $n$, some earlier chosen number would divide $m$. Since that earlier chosen number also divides $n$, the number $n$ would be a divisor of a previously chosen number, contradicting legality.

Thus at least one maximal multiple of $n$ is not yet eliminated. After choosing $n$, every maximal multiple of $n$ becomes eliminated. In particular, at least one previously noneliminated maximal element is eliminated.

On the other hand, a maximal element can become eliminated only once. Hence each move increases the number of eliminated maximal elements by exactly one. By induction on the number of moves, after $k$ moves exactly $k$ maximal elements have been eliminated.

The game terminates exactly when no legal move remains. If all maximal elements have been eliminated, every number divides some maximal element, and therefore every number is forbidden. No move is possible.

Conversely, if some maximal element $m$ has not been eliminated, then no chosen number divides $m$. The number $m$ itself is therefore legal, because the only divisors of $m$ that could have been chosen would eliminate $m$. Hence a move exists.

Thus the game ends precisely when all maximal elements have been eliminated.

The total number of maximal elements is

$$|M| = p-\left\lfloor\frac p2\right\rfloor = \left\lceil\frac p2\right\rceil .$$

Since exactly one maximal element is eliminated per move, every game lasts exactly

$$\left\lceil\frac p2\right\rceil$$

moves, regardless of the choices made.

For $p=10$,

$$\left\lceil\frac{10}{2}\right\rceil=5.$$

The game always lasts $5$ moves. The first player makes moves $1,3,5$, so the first player makes the last move and wins.

A winning strategy is simply to make any legal move on each turn. Since the total number of moves is fixed and odd, the first player is guaranteed to move last.

For $p=1000$,

$$\left\lceil\frac{1000}{2}\right\rceil=500.$$

The game always lasts $500$ moves. The second player makes move $500$, the last move of the game, so the second player wins.

Therefore

$$\boxed{\text{For }p=10\text{, the first player wins; for }p=1000\text{, the second player wins.}}$$

Verification of Key Steps

The first delicate point is proving that every number divides a maximal element. Let $n=6$ and $p=10$. Then $q=\lfloor 10/6\rfloor=1$, so $r=1$ and the maximal multiple is $6$. Let $n=2$ and $p=10$. Then $q=5$, $r=5$, and the maximal multiple is $10$. The argument works because the largest odd integer not exceeding $q$ always exceeds $q/2$.

The second delicate point is showing that a legal move always eliminates a new maximal element. If one merely states that every number has a maximal multiple, the conclusion does not follow. One must use legality. If all maximal multiples of $n$ had already been eliminated, then some previously chosen number would divide each of them. Since $n$ divides those same maximal elements, one of those earlier choices would force $n$ to be a divisor of a previously chosen number, contradicting that $n$ is legal.

The third delicate point is characterizing terminal positions. Having some numbers unavailable does not mean the game is over. The correct criterion is the presence of a noneliminated maximal element. Such an element is automatically legal, because any earlier chosen divisor would already eliminate it. Hence a position is terminal exactly when no maximal element survives.

Alternative Approaches

One can formulate the game directly in terms of the maximal elements $m>p/2$. Associate every number $n$ with the set of maximal elements divisible by $n$. Choosing $n$ removes one previously untouched maximal element from this family. The game then becomes equivalent to removing one token from a pile of $\lceil p/2\rceil$ indistinguishable tokens at each move. The winner is determined solely by the parity of the number of tokens.

Another approach uses induction on the number of maximal elements remaining. If $t$ maximal elements survive, at least one legal move exists; every legal move reduces $t$ by exactly one. Hence positions with even $t$ are winning for the previous player and positions with odd $t$ are winning for the next player. Starting from $t=\lceil p/2\rceil$ immediately yields the same result. The direct counting argument in the main solution is preferable because it identifies explicitly why every play has the same fixed length.