Ponder This Challenge - November 2011 - Volleyball tournament

Ponder This Challenge:

This month's puzzle spawned from a true story: Danny Arnon's solution for David Meiri's volleyball practice. Thank you both for the story.

Consider 9 teams playing volleyball on three courts simultaneously.

In each round, there are three teams on each court: two are playing against each other, while the third team is refereeing.

If the teams are numbered 1-9, you can represent the first round in the following manner:

1 2 (3)   4 5 (6)   7 8 (9)

On the first court, Team 1 plays against Team 2 while Team 3 referees; on the second court, Team 6 referees the play between Team 4 and Team 5, etc.

Here are the requirements for scheduling play:

(a) We need a 12-round schedule in which each team plays all eight other teams exactly once, and referees four times.
(b) After a team serves as referee, they should have at least two consecutive rounds of play before they have to referee again.

Can you make an ideal schedule that satisfies all our requirements?

If not, find a schedule that fulfils condition (a) and minimizes the number of times condition (b) is violated.

Please send your solutions as 12 lines of 9 digits each.

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

  First, we prove that no solution can exist without violating at least once either condition (a) or condition (b).

  If such a tournament takes place, it's easy to see that the same three teams will have to referee together, splitting the nine teams into three triplets.

  Let's call them groups A, B and C.

  Any game between a team from group B and a team from group C must take place when a group A team is refereeing.

  In each round when group A teams are refereeing, the number of BB games (i.e., both teams from the B group) is the same as the number of CC games.

  Therefore the number of BC games is odd (3-BB-CC). There are nine BC games and four A-refereeing rounds, but 9 cannot be expressed as a sum of four odd numbers, so that proves that we cannot fully fulfill conditions (a) and (b).

  Allowing for a single violation is enough. For example, the solution below fulfills condition (a) and violates (b) only once when team 7 referees in the 11th and 9th rounds.

  4 9 (1)   5 7 (2)   6 8 (3)
  1 7 (4)   2 8 (5)   3 9 (6)
  1 3 (7)   2 4 (8)   5 6 (9)
  6 9 (2)   7 8 (3)   4 5 (1)
  2 9 (5)   3 7 (6)   1 8 (4)
  2 5 (8)   3 6 (9)   1 4 (7)
  7 9 (3)   4 6 (1)   5 8 (2)
  3 8 (6)   1 9 (4)   2 7 (5)
  3 4 (9)   1 5 (7)   2 6 (8)
  4 8 (1)   5 9 (2)   6 7 (3)
  1 6 (4)   2 3 (5)   8 9 (7)
  1 2 (8)   3 5 (9)   4 7 (6)

Solvers

• Leif Jensen (11/01/2011 06:45 PM EDT)
• Peter de Rivaz (11/01/2011 07:23 PM EDT)
• Adam Daire (11/01/2011 07:42 PM EDT)
• Joseph DeVincentis (11/02/2011 10:24 AM EDT)
• Tom Sirgedas (11/02/2011 04:04 PM EDT)
• Chuck Carroll (11/02/2011 07:52 PM EDT)
• Radu-Alexandru Todor (11/02/2011 09:09 PM EDT)
• Frederik Kaster (11/03/2011 06:54 AM EDT)
• Gale Greenlee (11/03/2011 02:22 PM EDT)
• Liubing Yu (11/03/2011 06:09 PM EDT)
• Shilei Zang (11/03/2011 10:17 PM EDT)
• Oliver Hoepke (11/04/2011 07:16 PM EDT)
• Andreas Razen (11/05/2011 07:49 PM EDT)
• Jan Fricke (11/06/2011 07:21 AM EDT)
• Clive Tong (11/06/2011 10:15 AM EDT)
• Stanislav Grudnitskiy (11/06/2011 06:04 PM EDT)
• Andrew D Kidd (11/07/2011 03:09 PM EDT)
• Renato Fonseca (11/08/2011 12:09 AM EDT)
• Rob Pratt (11/08/2011 12:11 PM EDT)
• Donald T Dodson (11/08/2011 01:30 PM EDT)
• Adrian Neacsu (11/08/2011 05:09 PM EDT)
• Mathias Schenker (11/09/2011 06:30 AM EDT)
• Manoj vedvistara (11/09/2011 08:43 AM EDT)
• Mathew Davies (11/09/2011 08:45 AM EDT)
• Varun Ahluwalia (11/09/2011 12:26 AM EDT)
• Daniel Bitin (11/09/2011 03:09 PM EDT)
• Christopher Marks (11/09/2011 08:09 PM EDT)
• Serge Thill (11/10/2011 11:29 AM EDT)
• Katarzyna Wojdziak (11/10/2011 12:53 PM EDT)
• Ron Yu (11/11/2011 12:07 AM EDT)
• Anoop Ghanwani (11/11/2011 09:04 PM EDT)
• Fred Schalekamp (11/12/2011 11:39 AM EDT)
• William Heller (11/12/2011 03:17 PM EDT)
• David Friedman (11/13/2011 12:08 AM EDT)
• Stefan Kaaz (11/13/2011 07:08 AM EDT)
• Andrew Marrell (11/13/2011 03:43 PM EDT)
• Peter Gerritson (11/15/2011 01:08 PM EDT)
• Meninder Purewal (11/15/2011 08:30 PM EDT)
• Dan Dima (11/16/2011 06:43 PM EDT)
• Dominic Tipton (11/18/2011 09:39 PM EDT)
• Taketsuna Hisaji (11/19/2011 08:26 PM EDT)
• Ashutosh Mahajan (11/20/2011 11:47 PM EDT)
• Ananda Raidu (11/23/2011 11:06 AM EDT)
• Daniel König (11/23/2011 07:45 PM EDT)
• Bob Danani (11/24/2011 06:14 AM EDT)
• L. J Zigerell (11/26/2011 09:43 PM EDT)
• Antonio García Astudillo (11/28/2011 11:50 PM EDT)
• Panos Tsikogiannopoulos (11/29/2011 05:04 AM EDT)
• Dejan Stakic (11/29/2011 10:54 AM EDT)
• Vignesh Sethuraman (11/29/2011 05:48 PM EDT)
• Sergey Grishaev (11/30/2011 06:37 PM EDT)
• Mauro Bampo (11/30/2011 09:52 PM EDT)
• Franza Cavalcante Jr (12/01/2011 12:46 PM EDT)