Ponder This Challenge - September 1999 - Recognizing dishes

Ponder This Challenge:

Here's another food-related problem from Evan Morton.

Five people go to a Mesopotamian restaurant. Not being familiar with such food, they do not recognize any of the names for the dishes. Each orders one dish, not necessarily distinct. The waiter brings the dishes and places them in the middle, without saying which is which. At this point, they may be able to deduce some. For example, if two people ordered the same item, and everyone else ordered different dishes, then the item of which two copies arrive must be the one of which two were ordered.

They return to the restaurant two more times, following the same drill, though with different orders. After three meals, they have eaten all nine items on the menu, and can tell which is which.

What pattern of ordering fulfills this?

Show that the story couldn't be true if the number of items on the menu were ten instead of nine.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  At the first meal, order dishes A,B,B,C,D.

  At the second meal, order dishes D,E,E,F,G.

  At the third meal, order dishes G,H,H,I,A.

  Dish "A" is the only dish that appears at both the first and third meals; dish "B" is the only one that appears twice at the first meal; dish "C" is the only one that appears once at the first meal and never again; and so on.

  To show that ten dishes is impossible, assign each dish a triple of non-negative integers (x,y,z) if it is ordered x times at the first meal, y times at the second, and z times at the third. (x,y,z) cannot be (0,0,0) because of the stipulation that the diners have eaten all the items on the menu. The triples (x,y,z) corresponding to two different dishes must be different, or else the diners would never learn to distinguish those dishes. There are only three triples whose sum x+y+z is 1, namely (1,0,0), (0,1,0), and (0,0,1). There are only six triples whose sum x+y+z is 2, namely (2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), and (0,1,1).

  On the nine-dish menu, these nine patterns can be used, giving a total of 1+1+1+2+2+2+2+2+2=15=5*3 dishes ordered by the five diners at three meals. (In our solution they correspond to dishes C,F,I,B,E,H,D,A,G, respectively.) But on a ten-dish menu, an additional pattern must be used, so that the total number of dishes ordered must be at least 1+1+1+2+2+2+2+2+2+3=18, too much food for five diners in three meals.

Solvers

• Bruce Hoff (9.1.1999 @ 5:20 PM EST)
• Anthony Checkas (9.1.1999 @ 5:50 PM EST)
• Suresh B. Muppala (9.1.1999 @ 7:24 PM EST)
• Ashish Kadakia (9.1.1999 @ 8:10 PM EST)
• Sachin Desai (9.2.1999 @ 1:52 AM EST)
• Dan Peleg (9.2.1999 @ 3:24 AM EST)
• Stefan Verstraeten (9.2.1999 @ 5:59 AM EST)
• Manish C. Tayal (9.2.1999 @ 9:45 AM EST)
• Joseph DeVincentis (9.2.1999 @ 3:03 PM EST)
• Peter Hamilton (9.2.1999 @ 4:34 PM EST)
• Edward Lee, Santa Barbara (9.2.1999 @ 8:26 PM EST)
• Shanmugam Jaganathan (9.2.1999 @ 10:12 PM EST)
• Dieter Verhofstadt (9.3.1999 @ 6:30 AM EST)
• Ian Lovely (9.3.1999 @ 9:56 AM EST)
• Jonathan Sharp RBS (9.3.1999 @ 10:28 AM EST)
• Divakar Sarvabhowman (9.3.1999 @ 10:33 AM EST)
• Lei Kuang (9.3.1999 @ 12:00 PM EST)
• Trevor Strohman (9.3.1999 @ 2:23 PM EST)
• Tat Sang Fung (9.3.1999 @ 5:11 PM EST)
• Graham Waugh (9.4.1999 @ 7:28 AM EST)
• Aleksandar Basaric (9.4.1999 @ 5:18 PM EST)
• Paul Evans (9.4.1999 @ 11:53 PM EST)
• Dave Biggar (9.5.1999 @ 10:56 AM EST)
• Neal McBurnett (9.5.1999 @ 6:30 PM EST)
• Asher Walkover (9.5.1999 @ 9:54 PM EST)
• Peter Huesken (9.6.1999 @ 5:51 AM EST)
• Zuzana Gusparovicova (9.6.1999 @ 9:57 AM EST)
• Paul Gover (9.6.1999 @ 3:15 PM EST)
• James Chan (9.6.1999 @ 10:56 PM EST)
• Alamuru Krishna (9.7.1999 @ 1:14 AM EST)
• Shmuel M Spiegel (9.7.1999 @ 2:28 PM EST)
• Andrew Jones (9.7.1999 @ 2:55 PM EST)
• Imtiaz Hossain (9.7.1999 @ 4:05 PM EST)
• Mick Legare (9.7.1999 @ 11:26 AM EST)
• Chris Lusby-Taylor (9.8.1999 @ 12:42 PM EST)
• Saleem Ganiy (9.8.1999 @ 2:25 PM EST)
• Lorysa Meadowcroft (9.8.1999 @ 2:49 PM EST)
• Nathan Willett (9.8.1999 @ 3:12 PM EST)
• Madan Bysani (9.8.1999 @ 5:30 PM EST)
• Joseph Jacobs (9.8.1999 @ 6:22 PM EST)
• Andrew Bayly (9.8.1999 @ 6:36 PM EST)
• Philippe Fondanaiche (9.8.1999 @ 7:16 PM EST)
• Alan Nash (9.8.1999 @ 9:08 PM EST)
• Jens Oxlund (9.9.1999 @ 10:44 AM EST)
• Glen Hattrup (9.9.1999 @ 1:34 PM EST)
• Josh Scribner (9.9.1999 @ 4:57 PM EST)
• Rutger Vrijen (9.9.1999 @ 5:24 PM EST)
• Murray Baker (9.10.1999 @ 12:47 AM EST)
• Karin Cernik (9.10.1999 @ 11:06 AM EST)
• Chris Nokes (9.10.1999 @ 11:42 AM EST)
• Krishna Neelakanta (9.10.1999 @ 2:10 PM EST)
• David Ross (9.10.1999 @ 2:17 PM EST)
• Roddy May (9.10.1999 @ 3:25 PM EST)
• Trevor Green (9.10.1999 @ 5:15 PM EST)
• Gary Turner (9.10.1999 @ 5:26 PM EST)
• David Smith (9.10.1999 @ 5:42 PM EST)
• B Baskar (9.11.1999 @ 12:57 AM EST)
• Sunil Chandra (9.11.1999 @ 8:44 AM EST)
• Krishna Chaitanya H (9.11.1999 @ 10:15 AM EST)
• Kim Allen (9.12.1999 @ 8:38 PM EST)
• Amir Elad (9.13.1999 @ 4:57 AM EST)
• M.A. Freeman (9.13.1999 @ 11:46 AM EST)
• CJ Chang (9.13.1999 @ 1:08 PM EST)
• Karthik Gnanamurthy (9.13.1999 @ 2:10 PM EST)
• Suresh Gatti (9.13.1999 @ 7:35 PM EST)
• Chellaprabhu Andrew (9.13.1999 @ 10:57 PM EST)
• Brett Maune (9.15.1999 @ 12:58 AM EST)
• Michael Petter (9.15.1999 @ 1:02 AM EST)
• Eben Stewart (9.15.1999 @ 9:02 AM EST)
• Swapnesh Banerjee (9.15.1999 @ 2:59 PM EST)
• Joshua Zirbel (9.15.1999 @ 4:40 PM EST)
• Andrew Bozman (9.15.1999 @ 6:14 PM EST)
• Venkata Raghavan R.S. (9.16.1999 @ 4:37 AM EST)
• Erkan Ozmacun (9.16.1999 @ 9:06 AM EST)
• Ravi Srinivasan (9.16.1999 @ 10:36 AM EST)
• Alan Chan (9.16.1999 @ 11:17 AM EST)
• Bill Winters (9.16.1999 @ 11:17 PM EST)
• Johnny Colino (9.17.1999 @ 11:41 AM EST)
• Theresa Murdock (9.17.1999 @ 2:07 PM EST)
• Russell Logan (9.19.1999 @ 10:30 PM EST)
• Jimmy Hu (9.20.1999 @ 1:56 AM EST)
• Ludger Weber (9.20.1999 @ 6:19 AM EST)
• Jedidja Bourgeois (9.20.1999 @ 1:46 PM EST)
• Prashant Pogde (9.21.1999 @ 9:57 AM EST)
• Anil Ravi (9.21.1999 @ 10:34 AM EST)
• Alan Fung (9.21.1999 @ 1:05 PM EST)
• Tony Rivadeneyra (9.21.1999 @ 3:07 PM EST)
• Matt Watermann (9.22.1999 @ 12:18 AM EST)
• Bostjan Kuzman (9.22.1999 @ 12:48 PM EST)
• Pike Lawrence (9.22.1999 @ 4:33 PM EST)
• Mike Steigerwalt (9.23.1999 @ 9:35 AM EST)
• Simon Platinga (9.23.1999 @ 9:54 AM EST)
• Ronnie Cabrera (9.23.1999 @ 6:12 PM EST)
• Julie Baker (9.23.1999 @ 11:53 PM EST)
• Gururajan Krishnan (9.24.1999 @ 8:02 AM EST)
• Alison Sue (9.24.1999 @ 5:18 PM EST)
• Andy Willis (9.26.1999 @ 6:42 AM EST)
• John Bollinger (9.27.1999 @ 4:16 PM EST)
• Manikantan Srinivasan (9.27.1999 @ 6:21 PM EST)
• Mihai Cioc (9.28.1999 @ 11:40 AM EST)
• Sheeja Gangadharan (9.29.1999 @ 8:59 AM EST)
• Petr Broz (9.30.1999 @ 9:56 AM EST)
• Ronny Bjarnason (9.30.1999 @ 10:49 PM EST)