The Challenge: Three lunch boxes are labeled HH, HC, and CC. One of them contains two ham sandwiches, another one ham sandwich and one cheese sandwich, and the last one two cheese sandwiches. Unfortunately, the labels are all wrong: the HH box does not contain the two ham sandwiches, etc. You must straighten out the labels; that is, you must correctly identify the contents of each lunch box, but you must do it as cheaply as possible. You may open a lunch box and look at one sandwich in that box for a fee of $1. You would pay another $1 if you decide to look at the other sandwich in that box. You would pay another $1 to look at one sandwich in another box. You see the labels and you know they are all wrong. Of course, you can correctly identify the contents of the boxes for $6 if you look at every sandwich. How cheaply can you identify them all? Describe your process; what box would you pick first? What would you do next? How are you sure you know the correct contents of each box when you are done?
Solution by Arnav Moudgil, Grosse Point North High School
The answer is $1. By paying $1, we get to see one sandwich in one of the boxes. Since all of the boxes are mislabeled, we only need to see a sandwich from the HC box. If it is a ham sandwich, then the HC box must contain two ham sandwiches; if it’s cheese, then the HC box must contain two cheese sandwiches. Let’s assume, without loss of generality, that we found a ham sandwich in HC. Then we know that the HC box contains two ham sandwiches since it can’t contain one ham sandwich and one cheese sandwich. One of the remaining boxes, either CC or HH, must contain the two cheese sandwiches. Since it can’t be the box labeled CC, we deduce that the two cheese sandwiches are in the box marked HH. This leaves only the ham sandwich and cheese sandwich to be found in the CC box.
Had we found a cheese sandwich in the HC box originally, then the HC box would have two cheese sandwiches, the boxed marked CC would have two ham sandwiches, and the box marked HH would have the ham sandwich and cheese sandwich.
Also solved by: David Chamberlain, Edward Kennedy, Andrew Pape (Saginaw Heritage H.S.); Brittan Farmer (Rockford H.S.); Madhu Josyola, David Zhang (Ann Arbor Huron H.S.); Troy Howley, Mei Ling Liu (Saginaw Arts & Sciences Academy); Christine Miller (Holland H. S.); Chris Mohnke (St. Johns H.S.); Matt Moran (Monroe H.S.); McLain Pray (Charlotte H. S.); Eileen Chiu, Shiv Madan, Carolin Pezeshki, Marie Tominna, Lea Wojciechowski , Narendra Vempati, Howard Wu (Troy Athens H.S.); Kaitlin Gallup, Garrett Kerndt (Traverse City Central H.S.); Doug Dobney, Chad Griffor, Chris Hamilton, Justin Holle, Micah Jelinek, Colin Kerves, Andrew Northrop, Gary Patterson II, Emily Pedrotti, Lindsey Russell, A.J. Setter, Adam VanDeusen, Stacey Williams (Marysville H.S.); Tammam Alwan, Michelle Atto, Peter Keros, Ankit Singla, Ranjit Sood, Brittany Turner, Wendy Xiao (Andover High School); Cara Hosler (Dundee H.S.).