Maths Olympiad Prep

Library / /501 of 520

Combinatorics Difficulty 6.4 National olympiad Prove it

We put 100 pebbles into 50 piles, with at least one in each. Prove that if no pile has more than 50 pebbles, then the piles can be divided into two groups such that each group has the same number of pebbles.

Solution

I. solution. If there are 2 pebbles in each pile, then the statement of the problem is obvious, since by collecting 25-25 piles into one group, there will be 50 pebbles in each group.

If there are piles with different numbers of elements, let a1,a2,a50a_{1}, a_{2} \ldots, a_{50} denote the number of pebbles in each pile, and assume, for example, that a1a2a_{1} \neq a_{2}.

Consider then the following 51 numbers:

a1,a2,a1+a2,a1+a2+a3,,a1+a2++a50 a_{1}, a_{2}, a_{1}+a_{2}, a_{1}+a_{2}+a_{3}, \ldots, a_{1}+a_{2}+\ldots+a_{50}

Among the above 51 numbers, there must be two, b1b_{1} and b2b_{2}, which give the same remainder when divided by 50. Since the listed numbers are different (a1a2a_{1} \neq a_{2} and ai>0a_{i}>0), and each of them is between 1 and 100, this is only possible if b1b2=50\left|b_{1}-b_{2}\right|=50. These two numbers are thus not a1a_{1} and a2a_{2}, since there is no number greater than 50 among the aia_{i}'s. However, the difference of any other two of the 51 listed numbers is the sum of different aia_{i}'s. If the sum of such numbers is 50, then by collecting the corresponding piles, the statement of the problem is satisfied for the resulting group - and thus for the group formed by the remaining ones.

II. solution. The problem is closely related to problem 2518 (see the solution in the 5-6th page of the January issue of this year). If we assign a weight to each pile, the mass of which is the number of pebbles in the pile measured in grams, then according to problem 2518, the statement is true for 51 weights instead of 50, and the method given there - placing the weights in the pans of a two-pan balance in decreasing order, in the left pan if the balance is even, otherwise in the lighter one - also results in the division of the total 100 grams of mass into two equal parts.

We will show that with this "balancing" method, the balance will also be in equilibrium at the end with 50 weights, which proves the existence of the desired division. In the proof, it can be assumed that the weights are not all equal, otherwise the statement is obvious.

The solution at that time was based on the fact that in the case of 51 weights, after placing the weights heavier than 1 gram, the difference between the pans did not exceed the total mass of the 1-gram weights. We call this the "1-gram condition". In the solution of problem 2518, we saw that if this is true, then the balance will be in equilibrium at the end of the "balancing" method. We will show that the 1-gram condition also holds in this case.

Let MM again denote the maximum of the masses involved, d1d_{1} the number of 1-gram, and d2d_{2} the number of 2-gram weights. Since the weights are not all equal, M>2M>2 and d1>0(d2=0d_{1}>0\left(d_{2}=0\right. is possible), so there are 501d150-1-d_{1} weights of at least 2 grams. Thus, for the sum of the masses, we get

100M+d1+2(49d1) 100 \geqq M+d_{1}+2\left(49-d_{1}\right)

from which

d1+2M d_{1}+2 \geqq M

follows.

If d2>0d_{2}>0, that is, there are 2-gram weights among the weights, then d1+2d1+2d2d_{1}+2 \leqq d_{1}+2 d_{2}, that is, the total mass of the 1 and 2-gram weights is at least as large as the maximum of the masses involved. Since the difference between the pans following the balancing method can never be greater than MM, the "2-gram" version of the 1-gram condition holds when d2>0d_{2}>0, that is, the difference EE between the pans after placing the weights heavier than 2 grams is at most the total mass of the weights not placed, d1+2d2d_{1}+2 d_{2}. We will show that in this case the 1-gram condition also holds.

Indeed, if the EE difference is greater than 2d22 d_{2}, then according to the method, all 2-gram weights will end up in the lighter pan, and in this case the difference between the pans will not be greater than d1d_{1}. If, however, EE is not greater than 2d22 d_{2}, then by placing the 2-gram weights according to the method, the difference between the pans will be 0, 1, or 2. In the first two cases, the 1-gram condition is true again because d1>0d_{1}>0. If, however, the difference is exactly 2, then since the total mass of the weights on the balance is even, d1d_{1} is also even (the total mass of the weights was 100) and thus d1>0d_{1}>0 implies d12d_{1} \geqq 2. Therefore, the 1-gram condition indeed holds when d2>0d_{2}>0.

If d2=0d_{2}=0, that is, there are no 2-gram weights, then (1) remains true if we replace the factor 2 on the right-hand side with 3 (then every weight heavier than 1 gram is at least 3 grams), from which we get after rearrangement

2d1M+47 2 d_{1} \geqq M+47

If here now Md1M \leqq d_{1}, then the 1-gram condition is clearly true. If M>d1M>d_{1}, then from (2) we get d1>47d_{1}>47, that is, M49M \geqq 49, which, together with M50M \leqq 50 and d2=0d_{2}=0, can only be if we have 48 1-gram, one 3-gram, and one 49-gram weight, in which case it can be seen that the 1-gram condition holds.

We have thus shown that the 1-gram condition holds in all cases, and this means that the balance will be in equilibrium at the end of the balancing method, so the desired division indeed exists.

Remarks. 1. The second solution is clearly not as elegant as the first. However, with some modification of its line of thought, a significantly stronger statement can be proven: if 35 weights each have an integer mass, none of the weights is heavier than 50 grams, and their total mass is 100 grams, then the weights can be divided into two groups of equal mass. (It seems hopeless to prove this statement with the method of the first solution.)

This lower bound for the number of weights is sharp. If 34 weights consist of 33 3-gram weights and one 1-gram weight, then no matter how we divide the weights into two groups, the mass of one will be divisible by 3, and the other will not, so they cannot be equal.

2. It is not true for fewer than 50 weights that the balancing method always produces a desired division. For example, if 49 weights consist of two 3-gram weights and 47 2-gram weights, then at the end of the method, the total mass of the weights in one pan will be 51 grams, and in the other 49 grams, although an equal division clearly exists (23+222=252=50)(2 \cdot 3+22 \cdot 2=25 \cdot 2=50).

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.