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 $c$. If some chair adjacent to $c$ is already occupied, the same host orders one guest on such chair to stand up (if both chairs adjacent to $c$ 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 $k$ chairs are occupied. Determine the largest $k$ for which Ann can reach the goal, regardless of Bob's play.
Problem
Source: IZhO 2021 P5
Tags: combinatorics
Nersik.883
09.01.2021 23:05
So this is harder than p6
BlackFlower
09.01.2021 23:18
Nersik.883 wrote: So this is harder than p6 yes bro
Kaishin
09.01.2021 23:23
Ann places a person. Call the seat Ann's person sits on $c_0=0$, the seat to the right of it $c_1=1$ and so on. Then look at the seat modulo $3$. If Ann places a person on a seat not congruent to $0$ mod $3$, Bob can place a person next to that person, and make it congruent to $0$ mod $3$. If Ann places it on a seat congruent to $0$ mod $3$, Bob does the same. After all seats congruent to $0$ mod $3$ are occupied, it's Bob's turn. Anywhere he places his person, creates an empty triplet of seats. Ann places her person in the middle. Now if the seat congruent to $1$ mod $3$ is $c_m$, Bob can choose place his person on $c_{m+3}$, and now any move Ann makes can be reversed. We end up at $\frac{99}{3}+1$.
elcinmusazade
10.01.2021 11:38
@above are you sure ?Because you started from 0 and last seat will be 98 and then you will find that answer is 33.
L567
10.01.2021 12:00
redacted
alexiaslexia
15.01.2021 10:15
$\boxed{\text{Answer=}\, 34}$ Here is a problem where creates anxiety on the solver upon reaching the border of $32,33$ and $34$. Call the players Alice and Bob. $\rule{25cm}{1pt}$ In any moment, call two occupied chairs adjacent if one can travel between these two chairs without passing through another occupied chair. Define their distance to be the number of movements that is needed to do so. (For a diagram see attachment) Identify a configuration of chairs and guests as the set of its distances. Call that position to be $\textit{pure}$ if all those distances is divisible by $3$. Define it to be $\textit{impure}$ if it is not pure, and further define to be $\textit{inadjacently impure}$ of $\textit{I-impure}$ if there are two distances in that configuration which is not divisible by $3$, and they are not located beside each other. To simplify matters (which I didn't do in my original Solution), say a distance (distance can refer to the number, or the two chairs forming it) to be pure if it is divisible by $3$. Again, a distance is impure if it is not pure. A bit more briefing on game moments: call a moment $\textit{before}$ Bob's turn if at that moment, it is Bob's turn and he has yet to make a move, and call a moment $\textit{after}$ Bob's turn if Bob has made his move, and it is now $\textit{before}$ Alice's turn. $\color{green} \rule{25cm}{1pt}$ $\color{green} \textbf{Bob's strategy.}$ We will prove that $k \leq 34$. First we Claim the following: $\textbf{Lemma 1.}$ While the number of occupied chairs before Bob's turn is at most $32$, Bob an keep the position to be pure. $\textbf{Proof 1.}$ Done inductively. Let there still exists at most $32$ occupied chairs before Bob's turn, then it's obvious that before Bob's previous turn, there is at most $32$ chairs too. So, before Alice's last move, Bob has given Alice a pure position. At Alice's turn, she can move a person to a chair beside him (all guests are assumed to be male) or put one person between (inside) a pure distance. Since in this case, it's totally okay for Bob to play passive (his goal is to not increase the number of chairs, anyway) Bob can move the person back in the first case. In the second case, if Alice somehow made the position impure, the position $\textbf{cannot}$ be I-impure, as Alice can only change one pure distance into two impure distances which are beside each other. Bob then can proceed to move the person with two impure distances around him to a chair beside him. $\color{magenta} \textbf{The sneaky part}$ of this Section is the fact that Alice can play along to keep the position pure, and, as we can see in Alice's part later, Alice can give a pure configuration to Bob, forcing Bob to leave his comfort zone of always keeping it pure. For the time being, given that Bob was given a pure position with at most 32 chairs, Bob can add a chair to it in the middle of some distance of at least $6$ to keep the position pure (See diagram in the fourth page of the attachment.) $\blacksquare$ $\color{green} \rule{25cm}{2pt}$ Here, we aren't done yet. When the inevitable happens, that is somehow Alice can give Bob a 33-configuration, or Bob give a 33-configuration to Alice (one of these $\textbf{must}$ happen eventually), how could Bob guarantee his position? Here we actually need another Lemma: but to simplify it, say that after Bob's turn all distances are at most $3$. Then Bob can maintain his position. The proof is simple; since in Alice's immediate turn she cannot move add a guest, she can only move a guest to a chair beside him. Bob then can move back the guest (See $\color{green} \textbf{Extra Notes}$ for more details.) The first 33-config to appear is before Alice's turn. This configuration must be pure, since at Bob's previous turn with exactly $32$ chairs, he must have added a chair and keep the position pure. Basically, this meant that before Alice's particular turn, or after Bob's particular turn, all distances are at most $3$. Then Bob can keep $k \leq 33$. The first 33-config to appear is before Bob's turn. Bob then move an arbitrary person to a chair beside him, and brace for impact. Now Alice has three choices. She can move back the person Bob just moved. Then Bob repeats his action. She moves another person to a chair beside him. Then Bob moves back the person Alice has moved. She makes the distance $(2,2,2,3,\ldots,3)$. Bob then makes the position $(3,1,2,3,\ldots,3)$ or whatever he wants, as long as all distances are at most $3$. Then Bob can secure his objective to keep $k$ below $34$ here, due to the Lemma we just introduced. $\blacksquare$ $\color{red} \rule{25cm}{2pt}$ $\color{red} \textbf{Alice's strategy.}$ The Main Claim is that Alice can give Bob a 33-configuration which is pure or I-impure. (Also a bit hard to write up.) The best way I'd describe her strategy is to intentionally make mistakes which change a pure configuration to an impure one (and notice that she cannot directly make it I-impure.) At his moves, Bob roughly has two choices: not add any guests and fix Alice's mistake, keeping the number of occupied chairs constant; or adding any guest at all. The first case is easily elaborated, the main difficulty here is to construct a strategy for Alice once Bob has worsen the configuration. $\color{blue} \textbf{First Case.}$ Bob has given Alice pure 32-configuration. This happens when he fixes all of Alice's mistakes; Bob must move a person to a chair beside him. Here Alice gives back a 33-pure configuration to Bob. Bob then has no choice but to move a person to a chair beside him. This makes the distance equal to $(4,2,3,\ldots,3)$. Alice then can add a person in the middle of the $4-$distance and ensure $k \geq 34$. $\color{blue} \textbf{Second Case.}$ Instead of Alice making intentional mistakes, say that at some point she has received an intentional mistake from Bob. This means that before Alice's turn, the position is impure. Here we conjure another Lemma similar to Lemma 1: when the number of occupied chairs is 32, we Claim that Alice has total control over the configuration. $\color{magenta} \rule{25cm}{2pt}$ $\color{magenta} \textbf{Lemma 2.}$ While the number of occupied chairs before Alice's turn is at most $32$, and Bob has given Alice an impure configuration in some moment of time, Alice can add one chair and give an I-impure position to Bob. $\color{magenta} \textbf{Proof 2.}$ By PHP, since the sum of all distances is constant $(99)$, there exists a distance of size $4$ or more. If the distance is not 5-length-ed, Alice can always split it into two impure ones --- provided that there is another impure distance somewhere, there are at least 3 impure distances; so the configuration Alice gives Bob must be I-impure. If the distance is length-5, however, Alice would have to look at the distance in its left and in its right. If the impure distance is in its left, Alice will create a distance of length 3 between the left distance and another distance of length $2$. The same happens when the right distance is impure, Alice can just mirror her way of doing it. Similar to $\textbf{Lemma 1}$, Bob can only change at most two adjacent distances. So as long as Alice gives Bob an I-impure position, Bob cannot change it into a pure configuration. So, Alice can force this cycle to keep going. $\blacksquare$ $\blacksquare$ $\color{magenta} \rule{25cm}{1pt}$ So, as long as the number of chairs is at most $32$, Alice can always add a person, and give I-impure configurations to Bob. Once this number reaches $33$, if Bob is the first person to receive a 33-configuration, at his best, he can keep $k = 33$ and give an impure configuration to Alice. Alice then can win by choosing a distance of 4-length or more and simply add a person inside it. The same happens when Alice is the first person to receive a 33-configuration. $\blacksquare$ $\blacksquare$ $\blacksquare$
Experimenting for small cases, it perplexed me for a bit that when $n = 2$, Bob can force $k = 2$ but when $n = 3$, Alice can force $k = 4$. At first, Bob's strategy seemed obvious: just put guests on chairs with equal residue mod $3$. However, after Bob's first move, Alice can mess around and make the position impure, in some way. In other cases, Alice can play along with Bob and turn Bob's pure strategy back against him.
By this point, you should be convinced that $3$ is the golden number/invariant in this question, and this automatically ensures $k \geq 33$. Roughly, this is due to the fact that a host cannot add guests between chairs of distance $1$ or $2$ (and configurations with a lot of 3-distances seemed optimal). On the other hand, a host can (almost) freely add guests between chairs of distance $4$. So, 3 is a good border.
Label the chairs $1,2,\ldots,3n$, and in most of this Motivation I will put more emphasis on the cases $n = 3$, with $n = 4$ only functioning as an example. The case $n = 3$ itself is already quite deep, and will save us a lot of trouble when we consider it in depth.
$\rule{25cm}{1pt}$
Say Alice's first move is to put a guest in chair number 1. Bob has two choices: stall and keep $k = 1$ or add a random guest somewhere. Since Bob's interest is to force $k = 3$, that is, to give the equillibrium to Alice, it's in his best interests to make the set of distances be divisible by $3$. So assume Bob puts a guest in chair number 4 (for now.)
Here on, Alice already has three choices. First, she can move a person to a chair beside him, and make the configuration impure. Here, Bob can cheat his way and return the guest back, kind of hinting Alice to think of something more creative (a.k.a. add one guest, to finish the game quicker.) So Alice can put a guest in chair number 6 or 7 (8 is just a symmetry of putting a guest in chair number 6.)
So, here we get that Alice best plays along with Bob to create lots of 3-distances towards the end of the game, to instead give the equillibrium to Bob. In this case, Alice can force $k = 4$. The question is, can she do more?
The answer, is thankfully, no. Here after some more playing around, if Alice messes around and put a guest in a different class modulo 3, Bob can put him back to his rightful place; and keep the position pure. Assuming all positions with a few chairs are all pure, Alice just cannot do much, except for forcing Bob to accept an equillibrium before his turn. This relaxes the equillibrium by a bit, and then Bob can keep his cool and maintain $k = 34$.
$\rule{25cm}{1pt}$
The problem, more or less, is when Bob decided to stall in his first move, or when he explicitly makes a calculated mistake (of putting a guest in chair 3, for example.)
If Bob stalls, since a mistake shakes Bob's standings for a bit, Alice can force Bob to fix hers by putting a guest in such positions. This clarifies both players' roles: Bob can worsen Alice's mistake by not fixing it. If Bob doesn't stall an explicitly makes a mistake, his blatantly direct chaotic move catches Alice off-guard and forces her to act on the fly: she's given an already impure position to work with.
Here, a final observation that a host can only modify two adjacent distances finally helps, and whenever Alice gives an inadjacent impure position to Bob, there's no way for Bob to fix it in one go.
\[\begin{tabular}{p{12cm}}
$\rule{4cm}{0.5pt} \hspace{1cm} \blacksquare \hspace{1cm} \rule{4cm}{0.5pt}$ \\
\end{tabular} \\ \]Example: Alice chooses chair 1, and Bob chooses chair 4. If Alice picks chair 11, Bob can either pick chair 12 (which is a totally dumb move), pick chair 10 and risks Alice giving the equillibrium to him, or pick a completely far chair such as 9,8,7 or 6.
We can see that Alice can guarantee $k = 5$ for all of these cases.
When the game is altered a bit: Alice chooses chair 2, Bob chooses chair 1, and Alice chooses chair 11. Let Bob try to be a bit adventurous and picks chair 11. Alice then can tighten the position by moving the guest 11 to 12, which is a good move (and won't happen in an optimized game), so let's assume Alice picks the chair 9,8,7, or 6 (due to her expansionist goal.)
These four remaining choices gives interesting insights to Alice's possible moves and strategies.
If Alice picks chair 9 or 6, Bob has a lot of 2-distances he must work with, and he can't do much in such an onslaught. Especially, when Alice picks chair 6, the 2-distances are so far apart that they can't be fixed in one move. When Alice puts a chair in number 7, Bob can secure $k = 4$ by picking the tenth chair, so that the guest in the eleventh chair moves toward it. If Alice puts a chair in number 8, Bob is stuck with a weird predicament: the distance set is $(2,3,4,3)$. It seemed that there's no way out of it --- but its distance set is almost identical to when Alice picks chair 7, isn't it?
How is this so? The first time I thought about this, it seemed that the 4-distance between chair 4 and 8 will stay --- if Bob moves the guest in chair 8 to 7, the 4-gap will move towards 7 to 11, and Alice can place a guest in chair 9. However, when Bob gets the position $(1,4,7,11)$, Bob can easily fix that since the pair of chairs with impure distances (4,2) are located besides each other, and the position $(1,4,8,11)$ have impure distances which are not beside each other.
Attachments:
2INA11-3-6.pdf (327kb)
2INA11-7-10.pdf (468kb)
guas
15.01.2021 14:19
Nersik.883 wrote: So this is harder than p6 Oh, come on, average grade 1,9 against 0,43 for P6. The effect is purely psychological: there were many people who thought they have solved P5 and found they have not. On the other hand, those who thought they have solved P6 were mostly right.
GorgonMathDota
15.01.2021 15:37
guas wrote: Nersik.883 wrote: So this is harder than p6 Oh, come on, average grade 1,9 against 0,43 for P6. The effect is purely psychological: there were many people who thought they have solved P5 and found they have not. On the other hand, those who thought they have solved P6 were mostly right. They gave a lot more partials for 5 than for 6. For p6, it's either you got it or you miss it, while you can make a lot of progress in P5, that's why its average is higher. I think most of my friends who participate also agree that p5 is harder since it's not easy to write it down in the paper.
guas
15.01.2021 16:40
GorgonMathDota wrote: They gave a lot more partials for 5 than for 6. For p6, it's either you got it or you miss it, while you can make a lot of progress in P5, that's why its average is higher. I think most of my friends who participate also agree that p5 is harder since it's not easy to write it down in the paper. 58 7s on P5 against 15 on P6. Very ordinary pleasant combinatorics, only you have to be careful. And writing down is an (or perhaps THE) important part of mathematical profession.
lazizbek42
13.02.2022 09:27
I don't think it's possible to write a complete solution in 4.5 hours, even if you solve this problem, and you have to catch up with the rest of the problems.