Maths Olympiad Prep

Library / /8 of 8

Combinatorics Difficulty 4.6 AIME Prove it Japan

On each of 9 balls a distinct number chosen from 1 through 9 is marked. How many distinct ways of choosing some balls from this collection of 9 balls are there if the choice has to satisfy the following condition? Selecting no ball from the collection should be considered as 1 possibility.
Condition: By selecting suitably some balls from the chosen balls and putting them into a red box, and putting the remaining chosen balls into a blue box, we can make the difference of the numbers marked on any pair of balls in the same colored box to be 2 or less.

Solution

If no balls are selected, the condition is satisfied by agreement.

In all other cases, let us denote by MM and mm the maximum and the minimum number, respectively, among the numbers marked on the selected balls. When MmM - m is fixed, there are exactly 9(Mm)9 - (M - m) ways of choosing the pair (m,M)(m, M).

For each pair (m,M)(m, M) let us determine the number of possible ways of choosing balls to satisfy the given condition.

Case (i): Mm=0M - m = 0.
In this case, just 1 ball was selected and the condition is satisfied.

Case (ii): 1Mm51 \le M - m \le 5.
In this case, put the ball with the number mm into the red box, and if there are balls numbered m+1,m+2m + 1, m + 2 among the selected balls, put these also in the red box, and put the remaining selected balls into the blue box. Then, by the method of distribution it is clear that the difference of any pair of numbers on the balls in the red box does not exceed 2, and since all the balls put into the blue box have numbers greater than or equal to m+3m + 3 and less than or equal to MM and since M(m+3)2M - (m + 3) \le 2, the difference of any pair of numbers on the balls in the blue box also does not exceed 2. Thus, in Case (ii), any method of selecting the balls satisfies the condition, and thus the number of ways to select balls to satisfy the condition coincides with the number of ways of choosing some (may be none) balls from the group of balls numbered {m+1,m+2,,M1}\{m + 1, m + 2, \dots, M - 1\}, and this number is 2Mm12^{M-m-1}.

Case (iii): Mm6M - m \ge 6.
If all of the numbers on the selected balls belong to the set {m,m+1,m+2,M2,M1,M}\{m, m+1, m+2, M-2, M-1, M\}, then put those balls with numbers mm, or m+1m+1 or m+2m+2 into the red box and put all other selected balls into the blue box. Then it is easy to check that the distribution of the balls in the 2 boxes satisfies the requirement. If on the other hand, for some number xx different from any number in the set {m,m+1,m+2,M2,M1,M}\{m, m+1, m+2, M-2, M-1, M\}, the ball with that number xx is among the selected balls, then at least 2 among the balls numbered m,xm, x, MM have to be put into the same box, no matter how the distribution of the selected balls into the 2 boxes is carried out. But since each of the numbers xm,Mx,Mmx - m, M - x, M - m is 3\ge 3, there is no way of distributing selected balls into the 2 boxes to satisfy the requirement. So, in Case (iii) the number of ways of selecting balls to satisfy the requirement coincides with the number of choosing some (may be none) balls from those numbered {m+1,m+2,M2,M1}\{m+1, m+2, M-2, M-1\} and this number is 242^4.

Therefore, the total number of ways to select balls to satisfy the condition is:
1+9×1+8×20+7×21+6×22+5×23+4×24+3×24+2×24+1×24=256. 1+9 \times 1+8 \times 2^{0}+7 \times 2^{1}+6 \times 2^{2}+5 \times 2^{3}+4 \times 2^{4}+3 \times 2^{4}+2 \times 2^{4}+1 \times 2^{4}=256.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.