document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1198918>Question 1198918</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Toni has 10 identical blue socks, 14 identical green socks, and 4 identical red socks in a drawer. she removes socks from the drawer one at a time at random without looking. The least number of socks that Toni needs to pull out to be sure of having 4 pairs of the same colour is<BR>\n" );
document.write( "a) 8 b) 15 c) 16 d) 19 e) 22 </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #832587 by </B><A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><B>math_tutor2020(3817)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=math_tutor2020><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/images/nopicture.jpg><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=832587\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <font color=black size=3><BR>\n" );
document.write( "B = blue<BR>\n" );
document.write( "G = green<BR>\n" );
document.write( "R = red\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "4 pairs = 4*2 = 8 individual socks<BR>\n" );
document.write( "Of course it's impossible to have 4 pairs of red, since Toni simply doesn't have enough red socks.<BR>\n" );
document.write( "Therefore, she'll either have 8 blue or 8 green.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The best case scenario is that Toni selects 8 blue socks in a row, or 8 green socks in a row. <BR>\n" );
document.write( "This would be the minimum number of selections needed.<BR>\n" );
document.write( "This is if she gets really lucky. \r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "But we cannot assume this incredible luck and instead have to consider the worst case scenario, so that we 100% guarantee getting those 4 matching pairs.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The worst case scenario is her selecting say a blue sock first, then green, then red. <BR>\n" );
document.write( "It would give the sequence: B, G, R.<BR>\n" );
document.write( "The order doesn't really matter. <BR>\n" );
document.write( "All that matters is that she doesn't have a matching pair yet.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The 4th selection changes that since she has no other colors to pick from. <BR>\n" );
document.write( "This 4th selection is guaranteed to be a match with a previous selection. <BR>\n" );
document.write( "Refer to the pigeonhole principle.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Let's say the 4th selection was red. <BR>\n" );
document.write( "Then let's say the 5th and 6th selections were also red. <BR>\n" );
document.write( "This means she has chosen all 4 red socks.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "But as I mentioned earlier, we ignore red since there aren't enough red socks to make 4 pairs that match.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "We have this sequence so far<BR>\n" );
document.write( "B, G, R<BR>\n" );
document.write( "R, R, R\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "For the 7th selection we could go for blue or green. <BR>\n" );
document.write( "Let's have the colors alternate to guarantee the worst case scenario. <BR>\n" );
document.write( "This delays a matched pair as much as possible.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "She has selected 1 blue sock so far.<BR>\n" );
document.write( "There are 10-1 = 9 blue socks left.<BR>\n" );
document.write( "She needs 8-1 = 7 more blue socks to have 4 pairs of blue.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "She has selected 1 green sock so far.<BR>\n" );
document.write( "There are 14-1 = 13 green socks left.<BR>\n" );
document.write( "She needs 8-1 = 7 more green socks to have 4 pairs of green.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "In short: she needs 7 more of either green or blue.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "The worst case scenario is that she selects 6 green and 6 blue in any order you want.<BR>\n" );
document.write( "That's an additional 6*2 = 12 socks on top of the 6 already chosen.<BR>\n" );
document.write( "There are a total of 6+12 = 18 socks selected so far.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "By the <font color=red>19</font><sup>th</sup> selection, she has 4 pairs of the same color (aka 8 socks of the same color). <BR>\n" );
document.write( "We don't have enough information to determine if the 4 matching pairs would be blue or green.\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Answer: <font color=red>19 (choice D)</font>\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Bonus question to think about: <BR>\n" );
document.write( "What is the least number of socks that Toni needs to select to guarantee 4 pairs of blue and 4 pairs of green?\r<BR>\n" );
document.write( "<BR>\n" );
document.write( "\n" );
document.write( "Edit: The tutor @greenestamps offers a more streamlined approach. And it makes sense to get the red socks out of the way first, which I didn't consider.<BR>\n" );
document.write( "</font> </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );