Maths Olympiad Prep

Library / /280 of 397

Combinatorics Difficulty 6.4 National Olympiad Prove it Taiwan

Given three positive integers KK, BB, WW, where B>W>1B > W > 1. There are two piles of balls: one pile has BB black balls; the other pile has WW white balls. They are divided according to the following method:

Operation: All piles are arranged in non-increasing order; if a black pile and a white pile have the same number, the white pile is placed first. Now select the first KK piles, if there are fewer than KK piles in total then select all of them. Then split each selected pile into two piles, and these two piles may differ in number of balls by at most one.

(For example: let K=4K = 4. Now there are four piles of black balls with 5,4,4,25, 4, 4, 2 balls respectively, and three piles of white balls with 8,4,28, 4, 2 balls respectively. So the order is (w8,b5,w4,b4,w2,b2)(w8, b5, w4, b4, w2, b2), where w8w8 denotes a white pile of 88 balls, b5b5 denotes a black pile of 55 balls. For the first four piles, perform the following split: (4,4),(3,2),(2,2),(2,2)(4, 4), (3, 2), (2, 2), (2, 2), so the new arrangement at the next stage is (w4,w4,b4,b3,w2,w2,w2,b2,b2,b2)(w4, w4, b4, b3, w2, w2, w2, b2, b2, b2)).

Repeat the "arrange-split" process continuously, until at the end of some operation there is a white ball forming a pile by itself. Prove that at this moment there must be a pile with at least two black balls.

Solution

Let the initial state be A0=(bB,wW)A_0 = (bB, wW), and let Ai1AiA_{i-1} \to A_i denote performing the ii-th "arrange-split" operation.
Following the operation pattern, until all piles consist of a single ball. We mark the following important stages:
AsA_s : the first time a pile of a single ball appears (whether black or white).
AtA_t : when the total number of piles exceeds KK; however it is possible that: when all piles are single balls the total is still no more than KK piles, in which case let t=t = \infty.
AfA_f : when all black balls are single-ball piles.
We only need to prove: the stopping moment required by the problem occurs at Af1A_{f-1} or earlier, that is, in Af1A_{f-1} there must be at least one pile of a single white ball.
Clearly, sfs \le f. (*) Also in Af1A_{f-1} the black balls must have some piles that are b2b2 (ranked among the first KK), and all others are b1b1.

When i<min{t,s}i < \min\{t, s\}, every pile in AiA_i is selected, and must be split into two (since there is no single-ball pile yet). Suppose at this point the maximum and minimum numbers of the black piles are MiM_i and mim_i respectively, and the maximum and minimum numbers of the white piles are NiN_i and nin_i respectively. For AiA_i, we have the following properties:
(1) The total number of black piles and the total number of white piles are both 2i2^i.
(2) MiNiM_i \ge N_i.
(3) minim_i \ge n_i.
All of these can be easily proved by induction.

Regarding the relative sizes of s,t,fs, t, f, there are two possible cases:

Case 1. [sts \le t or ft+1f \le t+1] In particular t=t = \infty belongs to this case. Suppose s=fs=f occurs. By the definition of ss, mi,ni2m_i, n_i \ge 2. By (*) we get Ms12M_{s-1} \le 2. So every pile has exactly two balls. But this contradicts B>WB > W together with property (1)! So it must be that sf1s \le f - 1.
The given condition [sts \le t or ft+1f \le t+1] combines into: sf1ts \le f - 1 \le t. Consider As1AsA_{s-1} \to A_s. Since every pile in As1A_{s-1} is selected and ms1ns1m_{s-1} \ge n_{s-1}, when splitting into AsA_s we have ms1(ms11,1)m_{s-1} \to (m_{s-1} - 1, 1), i.e., ms=1m_s = 1; simultaneously ns1(ns11,1)n_{s-1} \to (n_{s-1} - 1, 1), i.e., ns=1n_s = 1; that is, the single-ball black pile and the single-ball white pile first appear simultaneously at AsA_s. Since sf1s \le f - 1, the stopping moment required by the problem occurs at Af1A_{f-1} or earlier.

Case 2. [t+1st+1 \le s and t+2ft+2 \le f] At At1A_{t-1} the total number of piles is 2t2^t, so 2tK<2t+12^t \le K < 2^{t+1}, and at AtA_t the total number of piles is 2t+12^{t+1} (black and white each being 2t2^t). Perform step t+1t+1: AtAt+1A_t \to A_{t+1}, among the selected KK piles at most 2t2^t can be black piles, so At+1A_{t+1} has at least 2t+(K2t)=K2^t + (K - 2^t) = K white piles. Since the total number of white piles is non-decreasing, the number of white piles in Af1A_{f-1} is at least KK.

Finally, in Af1A_{f-1}, Mf1=2M_{f-1} = 2, and these b2b2 piles (at least one) are all split into (1,1)(1, 1) at step ff, so in Af1A_{f-1} at most K1K-1 white piles can be selected, meaning there is at least one white pile Ω\Omega that is not selected. This pile Ω\Omega has exactly one white ball, because if pile Ω\Omega had more than one white ball, then Ω\Omega should be ranked before the b2b2 piles, and thus it should have been selected, which is a contradiction! Therefore, in Af1A_{f-1} there must be at least one pile with a single white ball, which completes the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from zh; metadata (topic, difficulty) added by this project.