Lei Lei wrote: [China Mathematics Olympiads (National Round) 2010 Problem 5] There is a deck of cards placed at every points $A_1, A_2, \ldots , A_n$ and $O$, where $n \geq 3$. We can do one of the following two operations at each step: 1) If there are more than 2 cards at some points $A_i$, we can withdraw three cards from that deck and place one each at $A_{i-1}, A_{i+1}$ and $O$. (Here $A_0=A_n$ and $A_{n+1}=A_1$); 2) If there are more than or equal to $n$ cards at point $O$, we can withdraw $n$ cards from that deck and place one each at $A_1, A_2, \ldots , A_n$. Show that if the total number of cards is more than or equal to $n^2+3n+1$, we can make the number of cards at every points more than or equal to $n-1$ after finitely many steps. Maybe there's a translation error somewhere, but this seems quite simple and we derive a better lower bound. First note that the number of cards doesn't change by applying moves. Apply the following procedure: While there is some point $A_i$ with at least 3 cards, apply (1) to $A_i$. Applying (1) decreases the number of cards being not in deck $O$, which can't get negative, so this process terminates. At the end of this procedure, there are at most 2 cards at all $A_i$ points, so there are at least $n^2+3n+1-2n = n^2+n+1$ cards in $O$. Now apply (2) $n-1$ times, which leaves at least $n^2+n+1 - n(n-1) = 2n+1 \geq n-1$ cards in $O$ and brings $n-1$ new cards to every $A_i$.

There is a typo in the problem. The problem is to show one can take some moves to make at least $n+1$ cards at each point.

As r3d30m3j proved, we can ensure that at most two cards lie on each $A_i$. So there are at least $n^2+n+1$ cards at $O$. Now we do operation (2), so that each $A_i$ contains either 1, 2, or 3 cards. We do operation (1) repeatedly, such that we end up with a configuration where each $A_i$ contains exactly 1, 2, or 3 cards. Suppose we arrive at a point where we cannot do it anymore. Let $a,b,c$ be the numbers of points containing 1, 2, and 3 cards, respectively. We will prove that $a\ge c$. If there are consecutive 3's $(x,3,3,\ldots,3,y)$ ($x,y\ne3$), we can do operation (1) a few times and we get $(x+1,1,2,2,\ldots,2,1,y+1)$. Each point still contains 1, 2, or 3 cards, contradicting our assumption. So there are no consecutive 3's. Consider two points containing 3 cards, suppose each point between them contains exactly 2 cards, $(x,3,2,2,\ldots,2,3,y)$ ($x,y\ne3$). After doing operation (1) a few times, we get $(x+1,1,1,1,\ldots,1,y+1)$. Each point contains 1, 2, or 3 cards, contradicting our assumption. So a point between them contains exactly 1 card. Thus, there is no consecutive 3's, and between any two 3's there is a point containing 1 card. Hence $a\ge c$. Now the number of cards in $A_1,A_2,\ldots,A_n$ is $a+2b+3c\le 2a+2b+2c=2n$. So the number of cards at $O$ is at least $n^2+n+1$. Now we do operation (2) $n$ times, and we get the desired configuration.

hello could you johan show me where is the contradiction here ''If there are consecutive 3's (), we can do operation (1) a few times and we get . Each point still contains 1, 2, or 3 cards, contradicting our assumption. So there are no consecutive 3's. Consider two points containing 3 cards, suppose each point between them contains exactly 2 cards, (). After doing operation (1) a few times, we get . Each point contains 1, 2, or 3 cards, contradicting our assumption. So a point between them contains exactly 1 card.'' thank's for your attention enig..

It contradicts our assumption: Johan Gunardi wrote: We do operation (1) repeatedly, such that we end up with a configuration where each $A_i$ contains exactly 1, 2, or 3 cards. Suppose we arrive at a point where we cannot do it anymore.

okey.. I think that I understand u ; but if the supposition that u made in the begining is false? i think u should prove that's true

As we do (1) repeatedly, the number of cards keep decreasing. So we cannot do it forever, and there must be a point where we cannot do it anymore.

ok thank's

Refer to the first move as an "outer move" and the second move as a "inner move". If we perform an outer move on any $A_i$ with at least $3$ cards until we cannot (which must eventually occur, as each outer move increases the number of cards on $O$ which is bounded by $n^2+3n+1$), we are left with at most $2$ cards on $A_1,\ldots,A_n$. Suppose that there are $a$ indices $i$ such that $A_i$ has $0$ cards and $b$ indices $i$ such that $A_i$ has $2$ cards, so $n-a-b$ indices $i$ exist with $A_i$ having one card. Then it is evident that $n-a+b$ cards are present amongst $A_1,\ldots,A_n$, so there are $n^2+2n+1+(a-b)$ cards on $O$. If $a\geq b$, then we can make $n+1$ inner moves, leaving $n+1+(a-b)\geq n+1$ cards on $O$ and at least $n+1$ cards on each of $A_1,\ldots,A_n$, so we're done. If $a<b$, then make $n$ inner moves, which leaves $a$ indices $i$ with $A_i=n$ and $b$ indices $i$ with $A_i=n+2$. Suppose the $b$ indices are $x_1<\ldots<x_b$, and denote $x_{b+1}=x_1$. Then place $A_1,\ldots,A_n$ on a circle $\omega$ in that order, so split the circumference of $\omega$ into $b$ arcs of the form $A_{x_i}A_{x_{i+1}}$. Since $a<b$, by Pigeonhole there must exist some arc $A_{x_j}A_{x_{j+1}}$ that doesn't contain any point with $n$ cards on it. Thus, knowing that it must exist, we may pick the longest arc on $\omega$ which doesn't contain any point with $n$ cards in it, and whose endpoints are points with $n+2$ cards in it. As such, the points immediately "outside" of the arc contain at most $n+1$ cards. As $n \geq 3$, we may make an outer move on all of the points contained in this arc, which strictly increases the number of cards on $O$. Further, this procedure maintains the fact that there are either $n,n+1,n+2$ cards at $A_1,\ldots,A_n$, since The endpoints decrease by $2$, which brings them to $n$ The other points in the arc decrease by $1$, which brings them to $n$ or $n+1$ The points immediately outside the arc increase by $1$, which brings them to $n+1$ or $n+2$, and also strictly increases the number of points on $O$, i.e. strictly decreases $b-a$. Therefore we can repeat this process until we eventually arrive at values of $a,b$ with $b-a \leq 0$, or $a \geq b$, in which case we have already shown we can finish. $\blacksquare$ Remark: A cool problem. Initially one might be drawn to just picking the arc $A_{x_j}A_{x_{j+1}}$, as I did, but this fails if, say, $A_{x_j-1}$ also has $n+2$ cards on it, in which case we end up with a point that has $n+3$ cards. Fortunately, this is easy to fix.

Doing operation 1 repeatedly to any $A_i$ with $\geq3$ cards gives that when we can't do the operation anymore, that each $A_i$ has $k \in (1,2)$ cards. Then there are $\geq n^2+n+1$ cards at $O$. Doing operation 1 repeatedly such that there are $x$ $A_i$'s with $3$ cards, $y$ $A_i$'s with $2$ cards, and $z$ $A_i$'s with $1$ card. Then there are also no $A_i$'s with $0$ cards. Then let there be $k$ consecutive $A_i$'s with 3 cards. Then do operation 1 and it switches to adding 1 to the card before and after the string, and the string goes from $(3,3,...,3) \implies (1,2,2,...,2,1).$ This means that no consecutive $A_i$'s can exist with exactly 3 cards if the operation is optimal. WLOG with above, consider $2$ $3's$ and only consecutive $2$'s between them. Then repeating operation $1$ gives that the card before and after each $3$ will be added to $1$, and all the cards between these $2$ cards is $1$. This implies that $z \geq x$ which finishes, as total # of cards on the $A_i$'s is \[ z+2y+3x \leq 2(x+y+z) =2n \]which implies problem after doing operation $2n$ times.

I'd consider this "not that bad" for a 2010 p5 because it's a very straightforward algorithm. Do operation 1 until each point has 0,1,2 cards (except O). Now make everything get 1,2,3 by one of operation 2, which we know we can do since otherwise we would have at max $2n+n-1<n^2+3n+1$ cards in total. Suppose x points have 1 card, y have 2, z have 3. We want O to have n^2+n+1, since we could consequently do the operation 2 n times and each card gets 1 plus n. (motivation: try to get O to be bounded from below, by making all points small we make large O, and getting 1,2,3 helps us guarantee) O has at least $n^2+3n+1-x-2y-3z=n^2+3n+1-2n-z+x=n^2+n+1-z+x$, if $x\ge z$ we're done. So we make an algorithm that guarantees a point with 1 between every point with 3, from which it would be obvious there is at least a point with 1 per point of 3. If there are any consecutive 3s (a,3,...,3,b), apply operation 1 to increase O, which doesn't "hurt", and also we end up with (a+1,1,2,...,2,1,b+1), which "helps". Now suppose there are 3s and 2s in between (c,3,2,...,2,3,d). Applying only operation 1s here, ->(c+1,0,3,2,...,2,3,d)->(c+1,1,0,3,2,...,2,3,d)->...->(c+1,1,...,1,0,4,d)->(c+1,1,...,1,d+1), hence again $x\ge z$. This satisfies what we wanted. $\blacksquare$

Truly incoherent solution. Refer to the number of cards in the deck by the card name. Assume there are exactly $n^2 + 3n + 1$ cards. First, repeat the first operation until all $A_i$ are between $0$ and $2$. Claim: If $\sum_{i} A_i - nA \le n$ then the result holds. This is equivalent to $|A_i - A_j| \in \{0, 1\}$ for all $i$ and $j$. Proof. Apply the second operation until $A$ becomes $n + 1$ and finish. $\blacksquare$ Claim: If $\sum_{i} A_i - nA > n$, then we can specify a proper subset $S$ of the decks $A_i$ to apply the inverse of the first operation such that all cards are in $\{A + 1, A + 2, A + 3\}$. Proof. Repeatedly apply the inverse first operation to the decks with $A$ cards. Since each card only has $2$ neighbors only apply to each card at most once, so this must terminate in at most $n$ applications. Then the number of occurences of decks with $A$ initially is less than the number of occurences of $A + 2$. As such, there's a range of cards which have end points of $A + 2$ without any decks with $A$ cards, of which the operation is not applied to. $\blacksquare$ Then, if we apply the first operation to the decks in $\{A_1, A_2, \dots A_n \} \setminus S$, the monovariant $\sum_{i} A_i - nA$ decreases. However, since this is equivalent to applying the inverse of the second operation and then applying the inverse operation to $S$, this preserves the fact that $A_i \in \{A, A + 1, A + 2\}$. Eventually this is less than $n$, so then we can finish.

Short Idea First, make all the numbers at most 2 using (1). Second, you can make all of the numbers at least 1 and at most 3 by adding all of the numbers 1 by using (2). Third, if the number of 1's is more significant than the number of 3's, we can make $O$ at least $n^2+n+1$ and we can add all of the numbers $n+1$ and make all of the numbers at least $n+1$. Forth, if the number of 1's is smaller than the number of 3's, we can make a sequence that doesn't have adjacent 3's and has 1's between all of the 3's. This way we can make the number of 3's less than the number of 1's.

Call the first operation sharing and the second distributing. Share repeatedly until each point has at most two cards then distribute once. if we have consecutive threes have them all share so $(3,3,\dots,3)\mapsto +1,(1,2,\dots,2,1),+1$, where $+1$ denotes that the outer adjacent points are getting an additional card. Notice this still preserves nonzero points so we can assume there are no consecutive threes. Claim:If at any point the number of ones is at least the number of threes and there are no empty points, we are done. Proof. Notice the average number of cards in $A_i$ is at most $2$ so there are at least $n^2+n+1$ cards at $O$. Distribute $n$ times to win. $\blacksquare$ We will have a number of ``chains'' of twos/threes bordered by ones. If each chain contains at most one three, we are done as there are not more threes than ones. If a chain contains at least two threes, take two threes closest to each other share repeatedly to get the following: \[(3,2,2,\dots,3)\mapsto +1,(1,1,1,\dots,1,1),+1\]This cannot increase the number of threes (we are deleting two and creating at most two from the $+1$s) and it creates a ``block'' of three or more ones. Hence, our original chain is split into two chains. Notice we will always have only twos between threes in the same chain so we can repeat this process and since the number of ones increases while the number of threes stays the same, eventually the condition in our claim must be true. $\square$

The argument for this problem is quite natural. The first step is to consolidate all the cards at $O$. Consider a configuration of the deck in which the number of cards at $O$ is maximal. It follows that none of the points $A_i$ has more than $2$ cards, thus $O$ has at least $n^2+n+1$ cards. By redistributing the cards, we can guarantee that every vertex $A_i$ has at least $n+1$ cards. Now, consider a configuration where every point $A_i$ has at least $n+1$ cards, and the number of cards at $O$ is maximal. Notice that if any vertex $A_i$ has at least $n+4$ cards, then we can redistribute it, contradicting maximality. We can now make the following key observation: Claim. The number of cards labeled $n+3$ must be at most the number of cards labeled $n+1$. Proof. Arrange the $A_i$ in a circle, and assume otherwise. Notice that there must exist two cards labeled $n+3$ with no cards labeled $n+1$ between them. Then, by performing the operation on every card in that consecutive block (including the two cards on the borders), the condition is still maintained. Thus contradiction! $\blacksquare$ Thus it follows that the total number of cards among the $A_i$ is at most $n^2+2n$, so $O$ has at least $n+1$ cards too, which finishes.

Call the following operation $X$: Apply $(1)$ while there exists a deck with >= 3 cards. This process must terminate since the total number of cards in $A_i$ is decreasing strictly. We are left with all decks 0, 1 or 2. Perform $X$ once. Call the following operation $Y$: Apply $(2)$ once, so all decks are 1, 2, or 3, then perform $X$. Let $a$ be the number of 2's, before operation $Y$, then the sum $S= \sum A_i$ decreases by at least $a$ since each $(1)$ decreases it by 1. Unless $n = a$ (So all $A_i$ decks are 2, which can be finished easily by distributing the $O$ deck), this decreases the total sum until we reach $a = 0$. Then $S \leq n$, so $O \geq n^2 +2n + 1$, which can be distributed to all the points with at least $n+1$ per point.

skibisolved with NTguy

China 2010/5 If all cards are at $O$ then it’s obvious. Now take the config such that each $A_i$ has a at least $n+1$, such that the number of cards of $O$ is maximal, we clearly have that we don’t have $n+4$ as this will contradict maximality of $O$. We claim the number of $A_i$ with $n+1$ cards is more than or equal to $A_i$ with $n+3$ cards, which can be shown by showing that between any two points that has $n+3$ cards there is a point with $n+1$, and that there are no consecutive points with $n+3$ cards, hence we have that $A_i$ has at most $n^2+2n$ cards, hence $O$ has at least $n+1$.

Step 1: Make each $A_i$ have exactly 1, 2, or 3 cards. Notice that move 1 monotonically decreases the number of cards in $\bigcup A_i$, so we can apply it finitely many times until all $A_i$ has exactly 0, 1, or 2 cards, then apply move 2. Step 2: Suppose $a$, $b$, $c$ of the $n$ points have exactly 1, 2, 3 cards, respectively. We can get to a stage where $a \ge c$. It suffices to show we have no consecutive 3s and at least one 1 between each pair of 3s. We're done if we have this; otherwise we can perform the two moves, which preserve the property that each $A_i$ has exactly 1, 2, or 3 cards at the end: (A) Consecutive 3s: Perform move 1 on each of the 3s in the block. (B) Only 2s between 3s: Perform move 1 on each of the 2s and 3s. Apply (A) each time we have consecutive 3s, and then move (B) until we get the desired. Again, monotonicity prevents this process from being infinite. Step 3: Apply move 2 exactly $n$ times to get the desired end state. It suffices to have at least $n^2+n+1$ cards at $O$, or at most $2n$ cards in $\bigcup A_i$, which holds as \[\left\lvert \bigcup A_i \right\rvert = a+2b+3c \leq 2a+2b+2c = 2n. \blacksquare\]

Nice problem one can see that while applying move 1 $\sum_{i} |A|_i $ get smaller by 1 so after a finite number of operations you will end with all of the $|A|$ being either $0$ $1$ or $2$ so $\sum_{i} |A|_i $ would be at most $2n$ thus but $|O|$ would be at least $n^2 +n +1$ so applying $move 2 $ finishes the problem. $\blacksquare$