Library / /65 of 75

, 2003

Combinatorics Difficulty 6.2 National Olympiad Prove it Italy

Problem:

We want to give seven gift packages to seven children, one to each. We want to arrange things so that each package contains three different toys and so that, however two children are chosen, they receive at most one toy in common. What is the minimum number of distinct types of toys that it is necessary to use?

Solution

Solution:

The answer is $7$ . That it is possible to build seven packages with the required properties using seven types of toys is shown by the following grid, in which $A$ , $B$ , $C$ , $D$ , $E$ , $F$ and $G$ denote the types of toys and the columns give the composition of the packages.

$\mathrm{A}$	$\mathrm{A}$	$\mathrm{B}$	$\mathrm{C}$	$\mathrm{A}$	$\mathrm{B}$	$\mathrm{C}$
$\mathrm{B}$	$\mathrm{D}$	$\mathrm{D}$	$\mathrm{E}$	$\mathrm{F}$	$\mathrm{E}$	$\mathrm{D}$
$\mathrm{C}$	$\mathrm{E}$	$\mathrm{G}$	$\mathrm{G}$	$\mathrm{G}$	$\mathrm{F}$	$\mathrm{F}$

Moreover, six types of toys are not sufficient. We prove this fact by contradiction. Suppose that

A

B

C

D

E

and

F

are sufficient for seven packages. In total we have twenty-one toys, and therefore there exists a type of toy, say

A

, that appears in at least three distinct packages; the other toys that appear in these three packages are six (two times three) and they must all be of types distinct from one another and all different from

A

; we would then have seven distinct types of toys, that is, a contradiction.

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 translated into English from it; metadata (topic, difficulty) added by this project.