1986 AHSME Problems/Problem 17
Problem
A drawer in a darkened room contains red socks,
green socks,
blue socks and
black socks.
A youngster selects socks one at a time from the drawer but is unable to see the color of the socks drawn.
What is the smallest number of socks that must be selected to guarantee that the selection contains at least
pairs?
(A pair of socks is two socks of the same color. No sock may be counted in more than one pair.)
Solution 1
~ e_power_pi_times_i
Suppose that you wish to draw one pair of socks from the drawer. Then you would pick socks (one of each kind, plus one). Notice that in the worst possible situation, you will continue to draw the same sock, until you get
pairs. This is because drawing the same sock results in a pair every
of that sock, whereas drawing another sock creates another pair. Thus the answer is
.
Solution 2
~ Levieee (formatted shalomkeshet)
We have to choose
of socks, i.e
socks
We choose socks in the worst possible scenario there will be
and
socks that are not paired, so we choose
more socks to this, but
can be the sum of
(like
)
This means there might be
and a few unpaired. If we choose
, it cannot be formed by summing
. Therefore,
must have
of socks in it. Note that
cannot happen because in the worst case scenario, we have
, and if
, then pulling out one more will leave us with
. However, the question demands
.
cannot happen either because if we pull out another sock it can be the same colour as the one we pulled out before, meaning it cannot be paired, but if we pull out another one and in the worst case scenario if the colour is same it still forms a pair with the last sock that we pulled out, therefore, the answer is
.
Solution 3
Since there are colors of socks, any selected set of socks could contain at most
unpaired socks. So a set of socks which contains
or fewer matched pairs could have at most
socks. This could happen if
red socks and
sock of each other color are selected. So the minimum number of socks needed to guarantee
matched pairs is
.
-j314andrews
Solution 4
Let ,
,
, and
be the number of red, green, blue, and black socks selected, respectively. Then the number of matched pairs of socks is
. Note that for any integer
,
if
is even and
if
is odd. So
. Thus if
, then
and
. That is, a set of socks containing
or fewer matched pairs contains at most
socks. Several equality cases exist, such as
. So the minimum number of socks needed to guarantee
matched pairs is
.
-j314andrews
See also
1986 AHSME (Problems • Answer Key • Resources) | ||
Preceded by Problem 16 |
Followed by Problem 18 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 | ||
All AHSME Problems and Solutions |
These problems are copyrighted © by the Mathematical Association of America, as part of the American Mathematics Competitions.