Maths Olympiad Prep

Library / /30 of 39

Combinatorics Difficulty 6.0 National Olympiad Find the answer Italy

Problem:

In Alice's drawer there are 30 socks of 5 colors: 6 white, 6 yellow, 6 red, 6 green and 6 light blue. Her mischievous little brother takes 10 black envelopes and puts into each envelope three socks (taken from the drawer) of three different colors. Now Alice has to go to Cesenatico and she must have in her suitcase at least three pairs of socks of three different colors (the two socks of each pair must be of the same color). How many envelopes must Alice take, at a minimum, to be sure of having all the socks she needs?

Pick one

Solution

Solution:

The answer is (C)\mathbf{(C)}. Note that, if Alice takes 3 envelopes, she cannot be sure of having the 3 pairs of socks she needs: for example the first envelope could contain a white sock, a yellow one and a red one, the second a white one, a yellow one and a green one, and the third a white one, a yellow one and a light blue one, and there would be only two well-matched pairs (a white one and a yellow one).

If Alice takes 4 envelopes, we see that in every case she finds the 3 pairs she needs. Let us call the three (distinct) colors of the socks present in the first envelope A,BA, B and CC; let us call DD and EE the two colors that do not appear in the first envelope. The second envelope must have at least one color in common with the first, say AA, of which we then have the pair. If it has no other colors in common, its colors are A,DA, D and EE, so with the third envelope we obtain the other two pairs (at least two socks are not AA and so they pair up with non-AA socks found previously). If the second envelope has at least one other color in common, say BB, we also have the pair of that color. It remains to find the third pair: observing that each of the 4 envelopes contains at least one sock of a color different from AA and from BB, among these socks there must be two of the same color (there are only 3 available colors, namely C,DC, D and EE) and then these socks will be the third pair. The minimum number of envelopes required is therefore 4.

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.