Track / Stage 5 / 82 of 400 #682 of 2000

Problem 682

AIME late

Combinatorics Difficulty 5.2 Find the answer

1. Each of the 4 colors has 6 pencils. Each of the six children received 4 pencils. For what smallest $k$ can we always choose $k$ children and decorate their pencils so that we have at least one in each color?

Your answer

Official solution

1. Let's denote colors by numbers from 1 to 4. If the distribution of pencils among children is

$(1,1,1,1), \quad(2,2,2,2), \quad(3,3,3,3), \quad(1,1,4,4), \quad(2,2,4,4), \quad(3,3,4,4)$

each child has only one of the colors $1,2,3$ , so we need at least three children.

On the other hand, $k=3$ is sufficient: at least one child has pencils in two colors, and we will find the remaining two colors among the other two children.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.