Maths Olympiad Prep

Library / /1210 of 1394

Combinatorics Difficulty 5.8 AIME, harder Prove it United States

Problem:

Ben has 16 balls labeled 11, 22, 33, \ldots, 1616, as well as 4 indistinguishable boxes. Two balls are neighbors if their labels differ by 11. Compute the number of ways for him to put 4 balls in each box such that each ball is in the same box as at least one of its neighbors. (The order in which the balls are placed does not matter.)

Solution

Solution:

Each box must either contain a single group of four consecutive balls (e.g. 55, 66, 77, 88) or two groups of two consecutive balls (e.g. 55, 66, 99, 1010). Since all groups have even lengths, this means that 11 and 22 are in the same group, 33 and 44 are in the same group, and so on. We can think of each of these 88 pairs of balls as an individual unit, so the answer is equal to the number of ways to put 88 objects in 44 indistinguishable boxes, where each box has 22 objects without any additional restrictions. The number of ways to do this is
8!244!=105 \frac{8!}{2^{4}\cdot 4!} = \boxed{105}

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.