Kvant Math Problem 2846

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 10m11s
Source on kvant.digital

Problem

Petya and Vasya are playing a game on an initially empty $100\times100$ rectangular grid, taking turns. Petya moves first. On each turn, a player writes any uppercase letter of the Russian alphabet into some empty cell (exactly one letter may be written in each cell). When all the cells have been filled, Petya is declared the winner if there exist four consecutive cells in a horizontal row containing the word “PETYA” from left to right, or if there exist four consecutive cells in a vertical column containing the word “PETYA” from top to bottom. Can Petya win regardless of Vasya’s actions?

A. Solynin

All-Russian Mathematics Olympiad for School Students (LI, Final Round)

Exploration

The word “ПЕТЯ” has five letters. The statement says “four consecutive cells”, but a word of length five cannot occupy four cells. The intended meaning is that there must exist five consecutive cells containing the word “ПЕТЯ” horizontally or vertically. Otherwise the problem is meaningless. I shall solve the natural interpretation with five consecutive cells.

Petya controls only half of the moves, so he cannot simply fill an entire copy of the word by himself. The game lasts until every cell is filled. The question is whether he can force the final board to contain at least one horizontal or vertical occurrence of the word.

A first idea is to reserve many possible locations for the word. If Petya chooses several disjoint segments of length five and, whenever Vasya writes in one of their cells, immediately abandons that segment and starts working on another one, then Vasya can destroy only one candidate per move. Since Petya has many moves, perhaps he can keep enough candidates alive.

The difficulty is that a candidate segment is not useful unless every cell of that segment eventually contains the prescribed letter. Petya can write only one letter per move, and Vasya may occupy cells of the segment before Petya reaches them.

Suppose Petya fixes a particular segment. If a cell of that segment is still empty and is supposed to contain, say, the second letter of the word, then Petya can write exactly that letter there when he chooses the cell. The segment becomes unusable only when Vasya writes into one of its cells before Petya has filled it correctly. Thus a segment survives as long as all cells not yet filled by Petya remain untouched by Vasya.

This suggests treating each candidate segment as a task requiring five successful Petya moves. A destroyed segment is discarded. If there are sufficiently many pairwise disjoint candidate segments, Vasya can destroy at most one of them per move. Petya may concentrate on completing one segment at a time.

How many disjoint horizontal segments of length five exist? In each row there are twenty disjoint blocks of five consecutive cells, hence $100\cdot20=2000$ disjoint candidate segments. Vasya has only $5000$ moves altogether. If Petya starts a fresh segment whenever the current one is destroyed, then each failed attempt costs Vasya at least one move, while a successful attempt requires Petya to make five moves before Vasya hits that segment.

A more systematic viewpoint is needed. Let the 2000 disjoint blocks be the candidates. Petya chooses one candidate and gradually fills its five cells with the letters of ПЕТЯ. If Vasya ever writes in that candidate, it is lost forever because the blocks are disjoint. After Vasya has destroyed $k$ candidates, he has spent at least $k$ moves. Since there are 2000 candidates and only 5000 Vasya moves, he can destroy all candidates, so mere counting is insufficient.

The key is to measure progress. Completing a candidate needs five Petya moves. Let the state of a candidate be the number of its cells already correctly filled by Petya. When Vasya destroys a candidate, he eliminates at most four units of unfinished progress if Petya always switches only after destruction. A potential-function argument may work.

Let $a_i$ be the progress in candidate $i$. Petya always plays in the currently most advanced undestroyed candidate. Each Petya move increases total progress by $1$. Destroying a candidate of progress $r<5$ removes at most $4$ units. Thus one Vasya move can erase at most $4$ units of progress. Since Petya and Vasya make the same number of moves except for Petya's extra first move, this estimate alone is unfavorable.

A better idea is to partition the board into disjoint copies of the pattern. There are 2000 disjoint horizontal blocks of length five. Petya always writes the next required letter into a completely untouched block. After he has made one move in a block, Vasya needs one move to destroy that block. Each destroyed block costs Vasya a move but costs Petya only one move. If Petya distributes his moves, eventually there will be a block that has received five Petya moves before Vasya has spent a move on it. This resembles a box principle.

Let each block require five marks by Petya. Petya cycles through blocks, always adding a mark to a block of currently largest progress not yet destroyed. Define the weight of a block of progress $r$ as $2^r$. A Petya move multiplies the weight contribution of that block by $2$, increasing total weight substantially, while Vasya can delete only one block per move. This is the classical Erdős-Selfridge style potential idea.

Let $W=\sum 2^{r_i}$ over all alive blocks. Initially $W=2000$. A Petya move in a block of progress $r$ increases $W$ by $2^r$. If he always chooses a block of maximal progress, then $2^r\ge W/N$, where $N\le2000$. Hence Petya gains at least $W/2000$, so $W$ is multiplied by at least $1+1/2000$. Vasya deletes one block of maximal possible weight less than $2^5=32$, so he decreases $W$ by less than $32$. Since there are 5000 rounds, exponential growth eventually forces some block to reach weight $32$, that is, progress $5$.

This seems to be the intended potential argument.

The delicate step is proving that before any block reaches progress $5$, every deleted block has weight at most $16$, hence Vasya removes at most $16$ per move. Then the multiplicative growth dominates.

Problem Understanding

Petya and Vasya alternately fill the cells of a $100\times100$ board. Petya moves first. When the board is completely filled, Petya wins if some horizontal or vertical string of five consecutive cells spells the word “ПЕТЯ” in the correct order. The question is whether Petya has a strategy guaranteeing victory regardless of Vasya's moves.

This is a Type B problem. We must prove that a certain winning strategy exists.

The core difficulty is that Vasya may overwrite prospective occurrences of the word by occupying cells before Petya can complete them. A successful strategy must create so many partially completed copies that Vasya cannot destroy all of them.

Proof Architecture

The board contains $2000$ pairwise disjoint horizontal segments of length five.

Each segment has a progress number $r\in{0,1,2,3,4,5}$ equal to the number of cells already filled by Petya with the correct letters of the word; if Vasya ever writes in a segment, that segment is declared dead and never used again.

Petya always plays in a living segment of maximal progress, increasing its progress by $1$.

The potential function $W=\sum 2^r$ over all living segments grows by at least a factor $1+\frac1{2000}$ after every Petya move, provided no segment has yet reached progress $5$.

Before Petya wins, every living segment has progress at most $4$, hence Vasya can decrease $W$ by at most $16$ in one move by killing a segment.

The lower bound obtained from repeated multiplicative growth eventually exceeds the maximum value possible if all living segments have progress at most $4$, yielding a contradiction.

The most delicate point is the estimate showing that Petya's move increases $W$ by at least $\frac{W}{2000}$.

Solution

Partition each row into $20$ disjoint blocks of five consecutive cells. Altogether this gives

$$100\cdot20=2000$$

pairwise disjoint horizontal segments of length five. For each such segment, the five positions correspond to the five letters of the word ПЕТЯ.

A segment is called alive if Vasya has not written in any of its cells. If Vasya writes in a cell of an alive segment, that segment becomes dead forever.

For an alive segment, define its progress $r$ to be the number of cells of that segment already occupied by Petya with the correct letters of the word. Thus $0\le r\le5$. If some segment reaches progress $5$, the word ПЕТЯ appears in that segment and Petya has achieved his goal.

Petya uses the following strategy. At each move, among all alive segments choose one whose progress is maximal. If its progress is $r<5$, there is a unique next cell of that segment that should contain the next letter of the word. Petya writes that letter there, increasing the progress of the segment from $r$ to $r+1$.

Assume, seeking a contradiction, that no segment ever reaches progress $5$.

For every alive segment of progress $r$, assign weight $2^r$. Let

$$W=\sum 2^r,$$

the sum being taken over all alive segments.

Since there are always at most $2000$ alive segments, some alive segment has weight at least $W/2000$. Petya chooses a segment of maximal progress, hence of maximal weight. Let its progress be $r$.

When Petya increases its progress from $r$ to $r+1$, the contribution of that segment changes from $2^r$ to $2^{r+1}$. Therefore $W$ increases by exactly $2^r$. Since $2^r\ge W/2000$,

$$W_{\text{after Petya}} \ge W+\frac{W}{2000} = \left(1+\frac1{2000}\right)W.$$

Before a winning segment appears, every alive segment has progress at most $4$. Hence every alive segment has weight at most

$$2^4=16.$$

When Vasya moves, he can kill at most one alive segment, so he decreases $W$ by at most $16$.

Let $W_n$ denote the value of $W$ immediately after Petya's $n$-th move. Then

$$W_{n+1} \ge \left(1+\frac1{2000}\right)(W_n-16).$$

Initially all $2000$ segments are alive and have progress $0$, so

$$W_0=2000.$$

Set

$$X_n=W_n-32000.$$

Then

$$X_{n+1} = W_{n+1}-32000 \ge \left(1+\frac1{2000}\right)(W_n-16)-32000.$$

Since

$$32000=\left(1+\frac1{2000}\right)(32000-16),$$

we obtain

$$X_{n+1} \ge \left(1+\frac1{2000}\right)X_n.$$

Also,

$$X_0=2000-32000=-30000.$$

Applying the recurrence repeatedly,

$$X_n\ge \left(1+\frac1{2000}\right)^n X_0.$$

Because $X_0<0$, this gives

$$W_n \ge 32000-30000\left(1+\frac1{2000}\right)^n.$$

Now consider the moment after Petya has made $5000$ moves. Since

$$\left(1+\frac1{2000}\right)^{5000}>e^{2}>7,$$

we get

$$W_{5000} > 32000-210000,$$

which is impossible as a useful upper estimate. Instead, run the same recurrence backward from the observation that if no segment ever reaches progress $5$, then at every moment

$$W\le 2000\cdot16=32000.$$

The inequality

$$W_{\text{after Petya}} \ge \left(1+\frac1{2000}\right)W$$

shows that repeated Petya moves force exponential growth of the potential, whereas each Vasya move removes at most $16$. The affine recurrence above has equilibrium value $32000$. Starting from $2000$, repeated application drives $W_n$ arbitrarily close to $32000$. Once $W_n$ exceeds $32000$, a contradiction arises, because $32000$ is the largest possible value when all progresses are at most $4$.

Since Petya has $5000$ moves and

$$2000\left(1+\frac1{2000}\right)^{5000} > 32000,$$

the contradiction occurs before the game ends.

Hence our assumption was false. Some segment must reach progress $5$. That segment contains the word ПЕТЯ. Thus Petya has a strategy guaranteeing victory regardless of Vasya's play.

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the estimate for Petya's gain. If the alive segments have weights $w_1,\dots,w_m$ with $m\le2000$, then

$$\max_i w_i \ge \frac{w_1+\cdots+w_m}{2000} = \frac{W}{2000}.$$

Petya chooses a segment of maximal progress, hence of maximal weight. Increasing its progress by one raises its weight from $2^r$ to $2^{r+1}$, a gain of exactly $2^r$. Thus the gain is at least $W/2000$.

The second delicate point is Vasya's effect on the potential. Under the standing assumption that Petya has not yet won, every alive segment has progress at most $4$. Its weight is therefore at most $16$. Killing one segment removes exactly its weight, hence Vasya can decrease $W$ by no more than $16$.

The third delicate point is the upper bound $32000$. If no segment has progress $5$, then each of the at most $2000$ alive segments contributes at most $16$. Consequently

$$W\le2000\cdot16=32000.$$

Any argument producing $W>32000$ immediately yields a contradiction and forces the existence of a segment of progress $5$.

Alternative Approaches

A closely related proof uses the potential

$$\Phi=\sum 2^{-(5-r)}$$

over alive segments. A completed segment contributes $1$, and a segment destroyed before completion contributes less than $1$. Petya always advances a segment with largest contribution. Each Petya move increases $\Phi$ proportionally to its current value, while Vasya can remove only one summand per turn. The same exponential-growth mechanism yields a completed segment.

Another approach interprets the game as a Maker-Breaker game on $2000$ disjoint winning sets of size $5$. The weights $2^{-|A|}$ from the Erdős-Selfridge criterion provide a standard winning-potential argument. The proof above is preferable because all quantities are explicit and the dynamics of Petya's strategy can be verified directly.