All-Russian Olympiad Problem 3
There are
different pencils,
different colors, and
pencils of each color. They were given to
children in such a way that each got
pencils. What is the least number of children that you can randomly choose so that you can guarantee that you have pencils of all colors?This problem is part of
this set
.
The answer is 5.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The pencils can be represented as
0 0 0 0 0 0 , 1 1 1 1 1 1 , 2 2 2 2 2 2 , 3 3 3 3 3 3 .
Thus it can be seen that the most "unmixed" paring amongst the 6 children is:
( 0 0 0 0 ) , ( 0 0 1 1 ) , ( 1 1 1 1 ) , ( 2 2 2 2 ) , ( 2 2 3 3 ) , ( 3 3 3 3 ) .
In which the possible parings involves all four colours are:
( 0 0 0 0 ) , ( 1 1 1 1 ) , ( 2 2 2 2 ) , ( 3 3 3 3 ) ;
and with loss of generality, ( 0 0 1 1 ) , ( 1 1 1 1 ) , ( 2 2 2 2 ) , ( 2 2 3 3 ) , ( 3 3 3 3 ) .
Thus the minimum number of children chosen so that it can be guaranteed to have pencil of all colours is 5 .