Ponder This Challenge - May 2012 - Permutation scheduling

Ponder This Challenge:

This month's challenge is based on a puzzle by Barry Cipra, presented at the tenth Gathering for Gardner conference at Atlanta.

There are six sets of jobs. Each set is performed on a different server and each set contains jobs that take 1,2,3,...,10 minutes to run.

Obviously, all six sets would end up in 55 minutes.

Schedule all the sets such that if all six servers start together, on minute 0, a job would end on every minute from 1 to 54, and all six servers would end on minute 55 together.

Please supply the solution as six lines of ten numbers.

A solution for a smaller problem of four sets of six jobs ending every minute from 1 to 20 is:

2 1 5 4 6 3
1 3 6 4 5 2
5 2 4 6 3 1
6 3 4 2 1 5

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

  There are many solutions, some of which have quite a few interesting symmetries, like Joël Bleuse's solution (note the place of the 7-s):

    1    8    3    2    5    9    7  10    4    6
    2    5  10    9    7    1    6    4    8    3
    5    3    8    2    6    1    7  10    9    4
    4    9  10    7    1    6    2    8    3    5
    3    8    4    6    1    7    9  10    5    2
    6    4  10    7    9    5    2    3    8    1

  Matej Kollár even wrote a nice tool http://www.fi.muni.cz/~xkollar2/symmetry-helper-1/ and used it to find a nice symmetric solution.
  We think that for any even n>3, there is a solution for n permutations of 2n-2 elements, but we don't have a proof for it.

Solvers

• Anders Kaseorg (04/26/2012 08:28 PM EDT)
• Heiko Selber (04/27/2012 07:36 AM EDT)
• Andreas Stiller (04/27/2012 08:19 AM EDT)
• Daniel Bitin (04/27/2012 09:08 AM EDT)
• János Csorba (04/27/2012 09:14 AM EDT)
• Peter de Rivaz (04/27/2012 10:03 AM EDT)
• Serge Thill (04/27/2012 12:44 PM EDT)
• Simon Xu (04/27/2012 03:51 PM EDT)
• Adrian Orzepowski (04/27/2012 04:48 PM EDT)
• Deron Stewart (04/27/2012 10:51 PM EDT)
• Peter Gerritson (04/28/2012 11:19 AM EDT)
• Matej Kollár (04/28/2012 04:51 PM EDT)
• Mark Pervovskiy (04/28/2012 05:29 PM EDT)
• Radu-Alexandru Todor (04/28/2012 08:24 PM EDT)
• Paulo S. A. Sousa (04/29/2012 03:41 PM EDT)
• Don Dodson (04/29/2012 07:13 PM EDT)
• Harald Bögeholz (04/29/2012 07:25 PM EDT)
• Tom Sirgedas (04/30/2012 01:44 AM EDT)
• Øyvind Grotmol (04/30/2012 05:37 AM EDT)
• Ratul Das (04/30/2012 05:54 AM EDT)
• Shilei Zang (04/30/2012 09:55 AM EDT)
• Jérémie Bernier (04/30/2012 10:02 AM EDT)
• Joshua Small (04/30/2012 11:49 AM EDT)
• Marcos Donnantuoni (04/30/2012 02:18 PM EDT)
• Deane Stewart (04/30/2012 02:30 PM EDT)
• Josh Jordan (05/01/2012 02:55 AM EDT)
• Florian Fischer (05/01/2012 05:23 AM EDT)
• Albert Stadler (05/01/2012 09:17 AM EDT)
• Joseph DeVincentis (05/01/2012 01:50 PM EDT)
• Michael Sinko (05/01/2012 02:56 PM EDT)
• Masoud Alipour (05/01/2012 03:47 PM EDT)
• John Tromp (05/01/2012 05:38 PM EDT)
• Sergey Grishaev (05/01/2012 07:20 PM EDT)
• Armin Krauss (05/02/2012 03:54 AM EDT)
• Maris Van Sprang (05/02/2012 04:58 AM EDT)
• Katarzyna Wojdziak (05/02/2012 05:15 AM EDT)
• Chris Lewis (05/02/2012 10:38 AM EDT)
• Eden Hochbaum (05/02/2012 12:47 PM EDT)
• Mark Mammel (05/02/2012 01:58 PM EDT)
• Todd Will (05/02/2012 03:24 PM EDT)
• Naftali Peles (05/02/2012 07:34 PM EDT)
• Rob Pratt (05/03/2012 12:03 AM EDT)
• Dmitry Litvinenko (05/03/2012 04:05 AM EDT)
• Hakan Summakoglu (05/03/2012 06:06 AM EDT)
• Yurun Liu (05/03/2012 12:34 PM EDT)
• Joël Bleuse (05/03/2012 07:57 PM EDT)
• Alex Stangl (05/04/2012 12:14 AM EDT)
• Shelby Doolittle (05/04/2012 06:51 AM EDT)
• Jan Fricke (05/04/2012 03:23 PM EDT)
• Dan Ismailescu (05/04/2012 03:33 PM EDT)
• Cindy Traub (05/04/2012 05:50 PM EDT)
• Kellen Broemmelsiek (05/04/2012 07:46 PM EDT)
• Duane Bailey (05/04/2012 08:52 PM EDT)
• Fred Schalekamp (05/05/2012 04:58 AM EDT)
• Gary M. Gerken (05/06/2012 12:52 AM EDT)
• Hillel Lee Sing Chun (05/06/2012 05:49 AM EDT)
• Djinn Lu (05/06/2012 09:56 AM EDT)
• Wu Chengyuan (05/06/2012 10:35 AM EDT)
• Michael Rosola (05/06/2012 11:27 AM EDT)
• Scott Lee (05/06/2012 12:01 PM EDT)
• Kevin Sham (05/07/2012 01:07 PM EDT)
• Michael D. Moffitt (05/07/2012 01:53 PM EDT)
• Mark Dettinger (05/08/2012 07:30 AM EDT)
• Hugues Chabot (05/08/2012 02:15 PM EDT)
• Markus Boettle (05/08/2012 04:23 PM EDT)
• Balakrishnan Varadarajan (05/09/2012 02:51 AM EDT)
• Nicholas Wegman (05/09/2012 04:44 PM EDT)
• David Friedman (05/09/2012 06:52 PM EDT)
• Sergii Strelchuk (05/10/2012 08:09 AM EDT)
• Kurt Hectic (05/10/2012 10:57 AM EDT)
• Fabio Filatrella (05/10/2012 01:19 PM EDT)
• Taketsuna Hisaj (05/10/2012 05:55 PM EDT)
• i (05/10/2012 05:55 PM EDT)
• Christian Pape (05/10/2012 07:42 PM EDT)
• Anoop Ghanwani (05/10/2012 09:42 PM EDT)
• Thomas Fleming (05/10/2012 10:56 PM EDT)
• Chuck Carroll (05/10/2012 11:56 PM EDT)
• Michael Kokosenski (05/11/2012 12:08 AM EDT)
• Mathias Schenker (05/11/2012 09:06 AM EDT)
• Jonathan Namnath (05/11/2012 03:27 PM EDT)
• Motty Porat (05/11/2012 04:24 PM EDT)
• Henning F. Jensen (05/12/2012 04:35 PM EDT)
• Meninder Purewal (05/12/2012 10:00 PM EDT)
• Ferry Widigdo (05/13/2012 02:23 PM EDT)
• Denys Kopiychenko (05/14/2012 12:12 PM EDT)
• Stanislav Grudnitskiy (05/14/2012 02:20 PM EDT)
• Liubing Yu (05/14/2012 09:35 PM EDT)
• Jon Palin (05/15/2012 09:06 AM EDT)
• Chris St. John (05/15/2012 04:05 PM EDT)
• Hannes Schenck (05/16/2012 11:45 AM EDT)
• Andrew Leverentz (05/16/2012 12:57 AM EDT)
• Ayaskant Pani (05/16/2012 08:42 PM EDT)
• Vishaal Kapoor (05/16/2012 09:12 PM EDT)
• Soumen Dey (05/17/2012 11:06 AM EDT)
• Yasodhar (Pattu) Patnaik (05/17/2012 04:49 PM EDT)
• Annalisa Bravi (05/17/2012 08:29 PM EDT)
• Alexandru Drenea (05/18/2012 06:40 PM EDT)
• Hrushikesh Tilak (05/19/2012 12:01 AM EDT)
• Dario Serino (05/19/2012 07:28 PM EDT)
• Leandro Augusto de Araújo Silva (05/20/2012 02:56 AM EDT)
• Aliaksei Sanko (05/20/2012 10:51 AM EDT)
• Amy Hardesty (05/21/2012 05:34 PM EDT)
• Kay Bieri (05/08/2012 10:20 AM EDT)
• Anunay Kulshrestha (05/23/2012 12:46 AM EDT)
• Pramod Singh (05/23/2012 03:10 AM EDT)
• Pravin S. Gaikar (05/23/2012 06:35 AM EDT)
• Robert C. Sarvis (05/24/2012 02:42 AM EDT)
• Tero Patana (05/24/2012 09:14 PM EDT)
• Sandeep Repakula (05/26/2012 07:06 AM EDT)
• M. Zecevic (05/26/2012 08:20 AM EDT)
• Seth Troisi (05/27/2012 12:25 AM EDT)
• Ilya Khivrich (05/27/2012 12:52 PM EDT)
• Vitaly Ditman (05/27/2012 04:30 PM EDT)
• Piyush Sao (05/28/2012 01:22 AM EDT)
• Chris Kittlitz (05/28/2012 04:22 PM EDT)
• Don Ryan (05/29/2012 01:01 AM EDT)
• Luiz Friedrich (05/29/2012 06:09 AM EDT)
• Tor Myklebust (05/29/2012 05:08 PM EDT)
• Dan Dima (05/30/2012 07:42 AM EDT)
• William Heller (05/30/2012 09:02 AM EDT)
• Andrew Baine (05/30/2012 06:09 PM EDT)
• Jason Lee (05/30/2012 09:33 PM EDT)
• Stéphane Higueret (05/31/2012 09:20 AM EDT)
• Ignat Soroko (05/31/2012 12:21 PM EDT)
• Hari Sindhu (05/31/2012 11:34 AM EDT)
• Levon Haykazyan (05/31/2012 06:41 PM EDT)
• Jamie Jorgensen (05/31/2012 10:57 PM EDT)
• Sridivakar Inakonda (06/01/2012 12:06 AM EDT)
• Bhavaji Sravani (06/01/2012 12:22 AM EDT)