Competition problem — Combinatorics

Library / /3 of 73

Combinatorics Difficulty 7.4 National Olympiad, round 2 Prove it Turkey

$3m$ balls numbered $1, 1, 1, 2, 2, 2, 3, 3, 3, \dots, m, m, m$ are distributed into $8$ boxes so that any two boxes contain identical balls. Find the minimal possible value of $m$ .

Solution

If some box contains a ball numbered $i$ then at most two other boxes can also contain ball numbered $i$ . Therefore, each box must contain at least $4$ balls and consequently the total number of balls is at least $32$ . Thus, $m \ge 11$ . The example for $m = 11$ : $(1,2,3,4)$ , $(1,4,5,6)$ , $(1,7,8,9)$ , $(2,5,7,9)$ , $(2,6,8,10)$ , $(3,5,8,11)$ , $(3,6,9,10,11)$ , $(4,7,10,11)$ .

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.