document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1201214>Question 1201214</A>: <I><SPAN STYLE=\"word-break: break-all;\"> Allison has 6 keys and 4 locks. Each lock can be locked by only one of the 6 keys, and each key can only open one of the 4 locks. What is the minimum number of times she must try to open a lock to guarantee that all 4 locks are opened? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #835495 by </B><A HREF=/tutors/aboutme.mpl?userid=greenestamps><B>greenestamps(13200)</B></A><img src=\"/images/stars/stars-13.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=greenestamps><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/cgi-bin/show-face.mpl?user=greenestamps><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=835495\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> <br><BR>\n" );
document.write( "Consider the worst case scenarios with two different strategies:<BR>\n" );
document.write( "Strategy 1: Pick a lock and find which key opens it<BR>\n" );
document.write( "Strategy 2: Pick a key and find which lock it opens<br><BR>\n" );
document.write( "Strategy 1....<br><BR>\n" );
document.write( "With lock #1, the worst case is it takes tries with all 6 keys to open it: 6 tries<BR>\n" );
document.write( "With lock #2, the worst case is it takes tries with all 5 remaining keys to open it: 5 tries<BR>\n" );
document.write( "With lock #3, the worst case is it takes tries with all 4 remaining keys to open it: 4 tries<BR>\n" );
document.write( "With lock #4, the worst case is it takes tries with all 3 remaining keys to open it: 3 tries<br><BR>\n" );
document.write( "Total number of tries to open all 4 locks with strategy 1: 6+5+4+3 = 18<br><BR>\n" );
document.write( "Strategy 2....<br><BR>\n" );
document.write( "With key 1, the worst case is that it doesn't open any of the 4 locks: 4 tries<BR>\n" );
document.write( "With key 2, the worst case is that it doesn't open any of the 4 locks: 4 tries<BR>\n" );
document.write( "With key 3, there are 4 locks still locked; the worst case is that it takes 4 tries to open one of the locks: 4 tries<BR>\n" );
document.write( "With key 4, there are 3 locks still locked; the worst case is that it takes 3 tries to open one of the locks: 3 tries<BR>\n" );
document.write( "With key 5, there are 2 locks still locked; the worst case is that it takes 2 tries to open one of the locks: 2 tries<BR>\n" );
document.write( "With key 6, there is only 1 lock still locked; the worst case (the only possibility) is that it takes 1 try to open the lock: 1 try<br><BR>\n" );
document.write( "Total number of tries to open all 4 locks with strategy 2: 4+4+4+3+2+1 = 18<br><BR>\n" );
document.write( "So with both strategies, the worst case is that it takes 18 tries to make sure all 4 locks are open.<br><BR>\n" );
document.write( "You can experiment with mixtures of these two strategies; you will find that in all cases the worst case is still that it takes 18 tries to make sure all 4 locks are open.<br><BR>\n" );
document.write( "ANSWER: A minimum of 18 tries is required to make sure all 4 locks are open.<br><BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );