Maths Olympiad Prep

Track / Stage 6 / 130 of 400 #1130 of 1964

Problem 1130

National olympiad, first round
Combinatorics Difficulty 6.2 Prove it

Example 1n(4)1 \quad n(\geqslant 4) plates contain a total of at least 4 candies. Selecting one candy from each of any two plates and placing them into another plate is called one operation. Can all the candies be concentrated into one plate after a finite number of operations? Prove your conclusion.
(1994 9th China Olympiad Problem)

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution One (Adjustment Method) First, prove that all candies can be concentrated in 2 or 3 plates after a finite number of operations.

In fact, if the number of plates with candies is no less than 3, take any 3 of them, denoted as A,B,CA, B, C, and assume that A,B,CA, B, C contain a,b,c(0<b>c0a, b, c (0 < b > c \geqslant 0 respectively. This can be divided into the following two cases:
(1) If a=c+2a=c+2, then b=c+1b=c+1, since a+b+c=3c+34a+b+c=3c+3 \geqslant 4, so c1c \geqslant 1. Thus, the following steps can be performed to concentrate all candies in one plate after a finite number of operations:
(c+2,c+1,c,0)(c+1,c,c,2)(c,c+2,c,1)(c1,c+2,c+2,0)c+2+ (c+2, c+1, c, 0) \rightarrow(c+1, c, c, 2) \rightarrow(c, c+2, c, 1) \rightarrow(c-1, c+2, c+2,0) \rightarrow{ }^{c+2}+
(3c+3,0,0,0)\rightarrow(3c+3,0,0,0).
(2) If a>c+2a>c+2, then first perform the following operation on plates A,B,CA, B, C:
(a,b,c)(a1,b1,c+2) (a, b, c) \rightarrow(a-1, b-1, c+2) \text{. }

Since a>b>ca>b>c and a>c+2a>c+2, it follows that a1>b1c,a1(c+3)1=c+2a-1>b-1 \geqslant c, a-1 \geqslant(c+3)-1=c+2, so after adjustment, the maximum number of candies in the three plates decreases by 1, while the minimum number does not decrease. Therefore, after a finite number of adjustments, it can be reduced to the case where the number of candies in two plates is equal or to the aforementioned case (1). Thus, according to the previous proof, all candies can be concentrated in one plate after a finite number of operations.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.