The numbers $1,2,\cdots,2021$ are arranged in a circle. For any $1 \le i \le 2021$, if $i,i+1,i+2$ are three consecutive numbers in some order such that $i+1$ is not in the middle, then $i$ is said to be a good number. Indices are taken mod $2021$. What is the maximum possible number of good numbers? CSJL
Problem
Source: IMOC 2021 C1
Tags: combinatorics, IMOC
CrazyInMath
13.08.2021 11:50
I did not get 7 on C1 during the camp, but I can solve it now. Here's the solution (close to the official solution) Arrange the number like this: 1,3,2,4,6,5,7,9,8,...,2020,2019,2021 This way, everything but 2021 and the multiple of 3 are good numbers. We go on by proving there could not be 3 adjacent numbers that are good. Proof: let n, n+1, and n+2 are all good numbers, then it must arrange in one of the four ways. 1. n, n+2, n+1 In this case, n+3 must be next to n+1, and n+2 would not be a good number, leading to a paradox. 2. n+2, n, n+1 In this case, n+1 isn't a good number (cause it's not next to n+2 and n+3 is not in between), causing a paradox. 3. n+1, n, n+2 In this case, n+1 isn't a good number (reason same as above), causing a paradox. 4. n+1, n+2, n In this case, n+2 can't be a good number (same as the first case) So, we're done proving that there couldn't be 3 adjacent good numbers. This way, we know all multiple of 3 won't be a good number, so we couldn't do better than the arrangement shown before, which would have 1346 good numbers. (I forgot to eliminate the number 2021 during the camp, and I got a 5 ) (sorry for my bad grammar and not putting LaTeX)
mathematics2004
25.08.2021 13:44
I get the same answer, but I don't quite follow your solution. You have proved that no $3$ consecutive good numbers. If we replace $2021$ by $n$, the proof goes like: If $n \equiv 0 \pmod 3$, we can group numbers into triples, so there are at most $\tfrac{2n}{3}$ good numbers. If $n \equiv 1 \pmod 3$, we can first find a bad number, then group the remaining $n-1$ numbers into triples, so there are at most $\tfrac{2(n-1)}{3}$ good numbers. But for $n \equiv 2 \pmod 3$ ( $2021$ is the case), I don't think you can say $\tfrac{2(n-2)}{3}$ directly. My solution involves messy (but not hard) local analysis on the structure of numbers if $2$ out of $3$ consecutive numbers are good. I would post it if needed.
primesarespecial
09.09.2021 17:50
By doing the casework as #1 did, we show that there can be atmost $2$ good numbers within three consecutive numbers. To handle $2021$,we see by this logic that since $1,2$ are good ,it can't be good. Thus we get that the number of good numbers $\le 2* 673$. Now,we show the straightforward construction $1 , 3 ,2, 4 , 6, 5, 7...2020 , 2019, 2021$. hence,the maximum number of good numbers is $1346$.
Number1048576
10.09.2023 13:30
We claim that the answer is $2 \times 673 = 1346$. For the construction, do $2020,1,2021,2,4,3,5,7,6,\cdots,2018,2019$, which can easily be checked to work.
Call a set of three consecutive numbers in the circle containing $i$ and not having the middle number in the middle an $i$-good set.
Now, note that if $1 \le i \le 2019$, then $i,i+1,i+2$ contains a number which is $0 \pmod 3$. However, given $i$, there are three sets of consecutive numbers containing $i$. Two of these sets contain $i-1$ or $i+1$, so if there were three $i$-good sets, then $i-1$ and $i+1$ would have to go directly to the left and right of $i$, which would make $\{i-1,i,i+1\}$ not $i$-good. Therefore, there are at most two $i$-good sets for each $i$.
If there are no good sets not containing a multiple of $3$, then we are done, as there are $673$ multiples of $3$ less than or equal to $2021$ implying that there are less than or equal to $673 \times 2$ good numbers.
Note that the possible good sets not containing a multiple of three contain two numbers either $1 \bmod 3$ or $2 \bmod 3$. WLOG one of them is $2 \bmod 3$. The possible such sets are $1,2021,2$ and $2,2021,1$. Note that every good set contains a number which is $2 \pmod 3$, so since both of these sets contain one twice every other good set has to contain one exactly once. WLOG the set is $2,2021,1$ (the same argument will work for the other set).
Now, $2$ needs to be part of another good set, and the only such possible one is $3,4,2$. Then $5$ has to be part of two good sets, so one of thse sets must contain $4$, so the only way we can place $5$ now is like $5,3,4,2,2021,1$. Then the only way we can place $6$ and $7$ is like
$6,7,5,3,4,2,2021,1$, and we can now repeat the same argument for $8$,$11$ and so on, until we get to $2018$. But we can't place numbers like $2018,2020,2019$, as the $1$ is in front of the $2020$, so we are done.