Maths Olympiad Prep

Library / /2 of 2

Combinatorics Difficulty 7.6 National Olympiad, round 2 Prove it Zhautykov Olympiad

Problem:

On a party with 99 guests, hosts Ann and Bob play a game (the hosts are not regarded as guests). There are 99 chairs arranged in a circle; initially, all guests hang around those chairs. The hosts take turns alternately. By a turn, a host orders any standing guest to sit on an unoccupied chair cc. If some chair adjacent to cc is already occupied, the same host orders one guest on such chair to stand up (if both chairs adjacent to cc are occupied, the host chooses exactly one of them). All orders are carried out immediately. Ann makes the first move; her goal is to fulfill, after some move of hers, that at least kk chairs are occupied. Determine the largest kk for which Ann can reach the goal, regardless of Bob's play.

Solution

Solution:

Answer. k=34k=34.

Preliminary notes. Let FF denote the number of occupied chairs at the current position in the game. Notice that, on any turn, FF does not decrease. Thus, we need to determine the maximal value of FF Ann can guarantee after an arbitrary move (either hers or her opponent's).

Say that the situation in the game is stable if every unoccupied chair is adjacent to an occupied one. In a stable situation, we have F33F \geq 33, since at most 3F3F chairs are either occupied or adjacent to such. Moreover, the same argument shows that there is a unique (up to rotation) stable situation with F=33F=33, in which exactly every third chair is occupied; call such stable situation bad.

If the situation after Bob's move is stable, then Bob can act so as to preserve the current value of FF indefinitely. Namely, if AA puts some guest on chair aa, she must free some chair bb adjacent to aa. Then Bob merely puts a guest on bb and frees aa, returning to the same stable position.

On the other hand, if the situation after Bob's move is unstable, then Ann may increase FF in her turn by putting a guest on a chair having no adjacent occupied chairs.

Strategy for Ann, if k34k \leq 34. In short, Ann's strategy is to increase FF avoiding appearance of a bad situation after Bob's move (conversely, Ann creates a bad situation in her turn, if she can).

So, on each her turn, Ann takes an arbitrary turn increasing FF if there is no danger that Bob reaches a bad situation in the next turn (thus, Ann always avoids forcing any guest to stand up). The exceptional cases are listed below.

Case 1. After possible Ann's move (consisting in putting a guest on chair aa), we have F=32F=32, and Bob can reach a bad situation by putting a guest on some chair. This means that, after Ann's move, every third chair would be occupied, with one exception. But this means that, by her move, Ann could put a guest on a chair adjacent to aa, avoiding the danger.

Case 2. After possible Ann's move (by putting a guest on chair aa), we have F=33F=33, and Bob can reach a stable situation by putting a guest on some chair bb and freeing an adjacent chair cc. If a=ca=c, then Ann could put her guest on bb to create a stable situation after her turn; that enforces Bob to break stability in his turn. Otherwise, as in the previous case, Ann could put a guest on some chair adjacent to aa, still increasing the value of FF, but with no danger of bad situation arising.

So, acting as described, Ann increases the value of FF on each turn of hers whenever F33F \leq 33. Thus, she reaches F=34F=34 after some her turn.

Strategy for Bob, if k35k \geq 35. Split all chairs into 33 groups each consisting of three consecutive chairs, and number the groups by 1,2,,331,2, \ldots, 33 so that Ann's first turn uses a chair from group 1. In short, Bob's strategy is to ensure, after each his turn, that

()(*) In group 1, at most two chairs are occupied; in every other group, only the central chair may be occupied.

If ()(*) is satisfied after Bob's turn, then F34<kF \leq 34 < k; thus, property ()(*) ensures that Bob will not lose. It remains to show that Bob can always preserve ()(*) after any his turn. Clearly, he can do that at the first turn.

Suppose first that Ann, in her turn, puts a guest on chair aa and frees an adjacent chair bb, then Bob may revert her turn by putting a guest on chair bb and freeing chair aa.

Suppose now that Ann just puts a guest on some chair aa, and the chairs adjacent to aa are unoccupied. In particular, group 1 still contains at most two occupied chairs. If the obtained situation satisfies ()(*), then Bob just makes a turn by putting a guest into group 1 (preferably, on its central chair), and, possibly, removing another guest from that group. Otherwise, aa is a non-central chair in some group i2i \geq 2; in this case Bob puts a guest to the central chair in group ii and frees chair aa.

So Bob indeed can always preserve ()(*).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.