Example 10 [China 2010, Problem 5]
There are some (finite number of) cards placed at the points A1, A2, …, An and O, where n ≥ 3. We can perform one of the following operations in each step:
Show that if the total number of cards is at least n2+3n+1, we can make the number of cards at each vertex at least n + 1 after finitely many steps.
Solution : The total number of cards stays the same.
(a) if we balance out the cards at each Ai, then there won't be disproportionate cards at any one point.
(b) We can make each of the Ai's have 0, 1, or 2 cards.
(c) from observation b, we can have 1,2 or 3 cards from the stage where they have 0,1 or 2 cards, by applying operation 2.
(d) based on observation c, we can make each of the Ai's have 1, 2, or 3 cards. Suppose x of the Ai's have one card, y of the Ai's have 2 cards and z of the Ai's have 3 cards. The number of cards at O is (n2+3n+1)-(x+2y+3z) Since (x+y+z) = n, the latter component is <= 2n if x >= z and O will have n2+n+1 cards. Then all of Ai's will now have at least n+1 cards and O will have n2+n+1-n2 cards and we are done.
Based on observation d(), we can start with points on the perimeter having 1,2 or 3 cards and ends in a position having 1, 2 or 3 cards but the number of points having 3 cards is not more than those with 1 card. We can do this by ensuring that any two points having three cards has a point with one card in between.
We can do this by applying 1 on all consecutive 3's to transform the set (x,3, ... 3,y) to (x+1, 1, 2 ... 2, 1, y+1) and there are no adjacent 3's. Now suppose there are two 3's with only 2's in between them like (x,3,2,2, ... 2, 3, y). Then we can do operation 1) on the first 3 to covert its adjacent to 3 and then again to the next adjacent 3. This we can please repeat as long as there are no adjacent 3's.
There are some (finite number of) cards placed at the points A1, A2, …, An and O, where n ≥ 3. We can perform one of the following operations in each step:
(1) If there are more than 2 cards at some point Ai, we can remove 3 cards from this point and place one each at Ai-1, Ai+1 and O (here A0 = An and An+1 = A1)
(2) If there are at least n cards at O, we can remove n cards from O and place one each at A1, A2, …, An. Show that if the total number of cards is at least n2+3n+1, we can make the number of cards at each vertex at least n + 1 after finitely many steps.
Solution : The total number of cards stays the same.
(a) if we balance out the cards at each Ai, then there won't be disproportionate cards at any one point.
(b) We can make each of the Ai's have 0, 1, or 2 cards.
(c) from observation b, we can have 1,2 or 3 cards from the stage where they have 0,1 or 2 cards, by applying operation 2.
(d) based on observation c, we can make each of the Ai's have 1, 2, or 3 cards. Suppose x of the Ai's have one card, y of the Ai's have 2 cards and z of the Ai's have 3 cards. The number of cards at O is (n2+3n+1)-(x+2y+3z) Since (x+y+z) = n, the latter component is <= 2n if x >= z and O will have n2+n+1 cards. Then all of Ai's will now have at least n+1 cards and O will have n2+n+1-n2 cards and we are done.
Based on observation d(), we can start with points on the perimeter having 1,2 or 3 cards and ends in a position having 1, 2 or 3 cards but the number of points having 3 cards is not more than those with 1 card. We can do this by ensuring that any two points having three cards has a point with one card in between.
We can do this by applying 1 on all consecutive 3's to transform the set (x,3, ... 3,y) to (x+1, 1, 2 ... 2, 1, y+1) and there are no adjacent 3's. Now suppose there are two 3's with only 2's in between them like (x,3,2,2, ... 2, 3, y). Then we can do operation 1) on the first 3 to covert its adjacent to 3 and then again to the next adjacent 3. This we can please repeat as long as there are no adjacent 3's.
No comments:
Post a Comment