CombinatoricsDifficulty 5.8AIME, harderProve itUnited States
Problem:
Ben has 16 balls labeled 1, 2, 3, …, 16, as well as 4 indistinguishable boxes. Two balls are neighbors if their labels differ by 1. 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. 5, 6, 7, 8) or two groups of two consecutive balls (e.g. 5, 6, 9, 10). Since all groups have even lengths, this means that 1 and 2 are in the same group, 3 and 4 are in the same group, and so on. We can think of each of these 8 pairs of balls as an individual unit, so the answer is equal to the number of ways to put 8 objects in 4 indistinguishable boxes, where each box has 2 objects without any additional restrictions. The number of ways to do this is 24⋅4!8!=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.