Ponder This Challenge - July 2011 - School lunches

Ponder This Challenge:

There are 80 students in a school. Each of them eats fruit for dessert every day, and the available fruits are apples, bananas, and cherries.

Find a possible setting of desserts for 14 days such that for every set of three students, there exists at least one day in which they all ate different desserts.

Please supply your solution as a list of lines, in which each line is 80 characters long and contains the letters 'A', 'B' and 'C'.

Update: July 29th: Since this month's challenge was quite hard, we will keep it open for one more month.

Hint 1: The more days you have, the easier the problem gets. You may want to try to solve for 16 days instead of 14; and then optimize it.

Hint 2: Reducing the number of students simplifies the problem. For example, you can solve for 9 students in 4 days; furthermore - you can *prove* that one can not solve it in three days.

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

  We can solve the problem for 81 = 3^4 students using linear codes. Write each student as a 4-digit number in base 3, and let him eat the scalar multiplication of his number with the following constants:

  (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (0,0,1,1), (0,0,1,2), (1,1,0,0), (1,2,0,0), (0,1,0,1), (0,1,0,2), (1,0,1,0), (1,0,2,0), (1,1,1,1), (1,1,2,2)

  Click here to see the format we requested

  And click here to see another representation sent to us by Gale Greenlee.

  14 is the smallest number of days we found with a solution, yet we can prove a lower bound of 10. We leave this gap as an open question for our readers.

  This month James Dow Allen solved the unasked bonus question: Why did we ask for lines 80 characters in length when the solution lends itself to 81? Of course, we did it to make the solution a little less obvious, but also to honor the 80-character-wide IBM punched card.

  For more information see http://www.ibm.com/ibm100/us/en/icons/punchcar.

  Close [x]

  Here it is in the format we requested:

  ABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCABCAB

  AAABBBCCCAAABBBCCCAAABBBCCCAAABBBCCCAAABBBCCCAAABBBCCCAAABBBCCCAAABBBCCCAAABBBCC

  AAAAAAAAABBBBBBBBBCCCCCCCCCAAAAAAAAABBBBBBBBBCCCCCCCCCAAAAAAAAABBBBBBBBBCCCCCCCC

  AAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCC

  AAAAAAAAABBBBBBBBBCCCCCCCCCBBBBBBBBBCCCCCCCCCAAAAAAAAACCCCCCCCCAAAAAAAAABBBBBBBB

  AAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCAAAAAAAAABBBBBBBBBBBBBBBBBBCCCCCCCCCAAAAAAAA

  ABCBCACABABCBCACABABCBCACABABCBCACABABCBCACABABCBCACABABCBCACABABCBCACABABCBCACA

  ABCCABBCAABCCABBCAABCCABBCAABCCABBCAABCCABBCAABCCABBCAABCCABBCAABCCABBCAABCCABBC

  AAABBBCCCAAABBBCCCAAABBBCCCBBBCCCAAABBBCCCAAABBBCCCAAACCCAAABBBCCCAAABBBCCCAAABB

  AAABBBCCCAAABBBCCCAAABBBCCCCCCAAABBBCCCAAABBBCCCAAABBBBBBCCCAAABBBCCCAAABBBCCCAA

  ABCABCABCBCABCABCACABCABCABABCABCABCBCABCABCACABCABCABABCABCABCBCABCABCACABCABCA

  ABCABCABCCABCABCABBCABCABCAABCABCABCCABCABCABBCABCABCAABCABCABCCABCABCABBCABCABC

  ABCBCACABBCACABABCCABABCBCABCACABABCCABABCBCAABCBCACABCABABCBCAABCBCACABBCACABAB

  ABCBCACABCABABCBCABCACABABCCABABCBCABCACABABCABCBCACABBCACABABCABCBCACABCABABCBC

  Close [x]

  Representation sent to us by Gale Greenlee

Solvers

• James Dow Allen (07/01/2011 05:57 AM EDT)
• Leif Jensen (07/01/2011 06:52 PM EDT)
• Jan Fricke (07/02/2011 05:59 PM EDT)
• Motty Porat (07/03/2011 04:14 PM EDT)
• Shilei Zang (07/05/2011 11:11 PM EDT)
• Alan Murray (07/06/2011 10:41 PM EDT)
• János Kramár (07/07/2011 04:21 PM EDT)
• Naftali Peles (07/09/2011 11:37 PM EDT)
• Jason L (07/13/2011 12:53 PM EDT)
• Liubing Yu (07/13/2011 09:41 PM EDT)
• Michael Brand (07/16/2011 10:55 AM EDT)
• Luke Pebody (07/18/2011 12:16 PM EDT)
• Shlomo Hoory (07/20/2011 06:47 AM EDT)
• Prithu Tiwari (07/21/2011 06:13 PM EDT)
• Jan Braunisch (07/24/2011 12:36 PM EDT)
• Harald van Dijk (07/25/2011 06:06 PM EDT)
• Matt Dobrin (07/31/2011 01:30 PM EDT)
• Joseph DeVincentis (08/09/2011 05:11 PM EDT)
• Ilya Khivrich (08/10/2011 08:56 AM EDT)
• Clive Tong (08/12/2011 08:07 AM EDT)
• John Tromp (08/14/2011 11:48 PM EDT)
• Thomas Mack (08/20/2011 05:17 PM EDT)
• James Russell (08/23/2011 12:02 AM EDT)
• SriHariChandra (08/24/2011 02:18 PM EDT)
• Radu-Alexandru Todor (08/26/2011 12:28 PM EDT)
• Piet Orye (08/30/2011 06:14 PM EDT)