HMMT 二月 2025 · COMB 赛 · 第 3 题

HMMT February 2025 — COMB Round — Problem 3

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.)

解析

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.) Proposed by: Benjamin Shimabukuro Answer: 105 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. 8! The number of ways to do this is = 105 . 4 2 · 4!