Ponder This Challenge - July 2013 - Octahedronial dice

Ponder This Challenge:

When you roll three octahedron (eight sided) dice with the sides numbered 1, 4, 16, 64, 256, 1024, 4096, 16384, there are 120 different sums which can be produced. The maximal value, in this example, is 16384.

Find the eight positive integers that could number a octahedral die and minimize the maximum value of the eight faces, while still resulting in 120 possible sums when three of the dice are rolled.

Update 7/5: Many of you gave a solution of 219, which is not optimal; hint: don't be greedy.

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 are sorry to disappoint those of you who expected to see an elegant solution, but we don't know of one for this version of the Golomb ruler problem.
  If you find one - please send it to us and we'll publish it.
  There are many ways to solve this month's challenge - mostly just using computerized calculations to search for possible solutions.
  The only (up to a symmetrical) solution is 1, 3, 6, 35, 75, 108, 121, 130.
  Many of you solved a greedy version of the problem (see sequence A096772 in The On-Line Encyclopedia of Integer Sequences) and got the wrong solution: 1, 2, 5, 14, 33, 72, 125, 219.

  Some of you solved the more general problems for sets of nine and ten integers:
  1, 2, 18, 27, 128, 139, 186, 205, 209
  1, 7, 11, 35, 112, 131, 235, 268, 299, 310
  John Tromp also submitted his solution to the OEIS as sequence A227358. Thank you, John, for sharing your results and for holding the publication till the end of the month.

Solvers

• Hugo Pfoertner (06/30/2013 08:23 AM EDT)
• Florian Fischer (06/30/2013 02:41 PM EDT)
• Antoine Comeau (06/30/2013 09:36 PM EDT)
• Don Dodson (07/01/2013 05:00 AM EDT)
• Rogerio Ponce da Silva (07/01/2013 11:08 AM EDT)
• Arthur Vause (07/01/2013 11:02 AM EDT)
• Hakan Summakoglu (07/01/2013 01:29 PM EDT)
• Alan Murray (07/01/2013 03:55 PM EDT)
• David Friedman (07/01/2013 04:03 PM EDT)
• Rob Sessions (07/01/2013 08:28 PM EDT)
• Todd Will (07/01/2013 08:55 PM EDT)
• Shirish Chinchalkar (07/02/2013 06:10 AM EDT)
• Joseph DeVincentis (07/02/2013 06:24 AM EDT)
• János Kramár (07/02/2013 07:47 AM EDT)
• Armin Krauss (07/02/2013 08:18 AM EDT)
• David Greer (07/02/2013 02:10 PM EDT)
• Reiner Martin (07/02/2013 02:17 PM EDT)
• Hubert Kahlert (07/02/2013 03:03 PM EDT)
• Dezhi Zhao (07/02/2013 04:36 PM EDT)
• Peter Gerritson (07/02/2013 08:08 PM EDT)
• Álvaro Begué (07/02/2013 09:25 PM EDT)
• Vladimir Sedach (07/02/2013 11:55 PM EDT)
• Liubing Yu (07/03/2013 12:36 AM EDT)
• Radu-Alexandru Todor & Andreas Razen (07/03/2013 04:56 AM EDT)
• John Tromp (07/03/2013 08:39 AM EDT)
• Peter Holdsworth (07/03/2013 08:59 AM EDT)
• Stéphane Higueret (07/03/2013 09:16 AM EDT)
• Philippe Fondanaiche (07/03/2013 11:13 AM EDT)
• Michael Leung & Benjamin Greenlay (07/03/2013 11:20 AM EDT)
• Ed Pegg Jr (07/03/2013 01:37 PM EDT)
• I. J. Kennedy (07/03/2013 02:11 PM EDT)
• Duane Bailey (07/03/2013 03:16 PM EDT)
• Darin Yu (07/03/2013 03:28 PM EDT)
• Franza Cavalcante Jr (07/03/2013 06:51 PM EDT)
• Henry Liu (07/03/2013 08:23 PM EDT)
• Eric Harley (07/03/2013 08:39 PM EDT)
• Wanxin Yuan (07/04/2013 01:10 AM EDT)
• Leandro Araújo (07/04/2013 02:27 AM EDT)
• Andreas Stiller (07/04/2013 11:05 AM EDT)
• José Eduardo Gaboardi de Carvalho (07/04/2013 12:00 PM EDT)
• Harald Bögeholz (07/05/2013 09:53 AM EDT)
• Rami Pear (07/06/2013 04:48 AM EDT)
• Frank Mullin (07/06/2013 02:05 PM EDT)
• Daniel Bitin (07/06/2013 04:19 PM EDT)
• Ted Alper (07/07/2013 04:03 AM EDT)
• Antonio García Astudillo (07/07/2013 04:47 AM EDT)
• Tilmann Steinberg (07/07/2013 04:59 AM EDT)
• Tony Harrison (07/07/2013 02:47 PM EDT)
• Olivier Mercier (07/07/2013 09:02 AM EDT)
• Dieter Beckerle (07/07/2013 11:07 AM EDT)
• Yiting Ying (07/07/2013 07:52 PM EDT)
• Cameron Byer (07/08/2013 06:42 AM EDT)
• Dan Ismailescu (07/08/2013 07:14 AM EDT)
• Mark Pervovskiy (07/08/2013 01:50 PM EDT)
• Rob Pratt (07/08/2013 09:52 PM EDT)
• Kai Wang (07/08/2013 11:32 PM EDT)
• Paul Shaw & Philippe Laborie (07/09/2013 02:02 AM EDT)
• Amos Guler (07/09/2013 11:35 AM EDT)
• Steven Lu (07/09/2013 12:40 PM EDT)
• Graham Hemsley (07/09/2013 01:14 PM EDT)
• Marco Bellocchi (07/09/2013 06:13 PM EDT)
• Dan Dima (07/09/2013 11:03 PM EDT)
• Clive Tong (07/10/2013 01:19 AM EDT)
• Matthew Gara (07/10/2013 12:37 PM EDT)
• James Wilcox (07/10/2013 03:36 PM EDT)
• Renato Negrinho (07/10/2013 03:57 PM EDT)
• Alex Fleischer (07/10/2013 04:47 PM EDT)
• Anoop Ghanwani (07/10/2013 08:36 PM EDT)
• Mathias Schenker (07/11/2013 03:13 AM EDT)
• Reichel Lorenz (07/11/2013 04:22 AM EDT)
• Javier Rodriguez (07/11/2013 05:32 AM EDT)
• Houston Putman (07/11/2013 07:38 AM EDT)
• Tom Harley (07/11/2013 09:06 AM EDT)
• Alok Menghrajani (07/11/2013 03:09 PM EDT)
• Albert Stadler (07/11/2013 05:53 PM EDT)
• Sunil Srivastava (07/11/2013 11:40 PM EDT)
• Ian Barnard (07/12/2013 03:54 AM EDT)
• Matej Kollar (07/12/2013 06:24 AM EDT)
• Phil Benamy (07/12/2013 09:47 AM EDT)
• Klaus Nagel (07/12/2013 01:05 PM EDT)
• Ted Gault (07/13/2013 12:52 AM EDT)
• Christian Burnham (07/13/2013 01:09 PM EDT)
• Zhuo Wang & Congyun Gu (07/15/2013 09:35 AM EDT)
• Jan Fricke (07/15/2013 01:28 PM EDT)
• Ayas (07/15/2013 05:33 PM EDT)
• Mark Stuckel (07/16/2013 01:20 AM EDT)
• (07/16/2013 01:20 AM EDT)
• Kevin Bauer (07/16/2013 03:42 PM EDT)
• Jens Voss (07/17/2013 01:00 AM EDT)
• Juha Saukkola (07/17/2013 02:53 PM EDT)
• Chris Shannon (07/18/2013 03:06 AM EDT)
• Seong Woo Hong (07/18/2013 08:53 AM EDT)
• Adrian Orzepowski (07/18/2013 12:58 PM EDT)
• Joe Clark (07/18/2013 05:53 PM EDT)
• Andrea Andenna (07/19/2013 02:28 AM EDT)
• Ivan Pechenezhskiy (07/19/2013 07:22 AM EDT)
• Qiu Charlie (07/19/2013 07:33 AM EDT)
• Yuanming Yu (07/19/2013 11:00 AM EDT)
• Bernard Widynski (07/19/2013 11:39 PM EDT)
• Charlie Qiu (07/20/2013 09:38 AM EDT)
• Kan Shen (07/21/2013 03:52 PM EDT)
• Shouky Dan & Tamir Ganor (07/23/2013 03:17 AM EDT)
• Jeffrey Thompson (07/23/2013 06:55 AM EDT)
• Meng Shen (07/24/2013 07:20 AM EDT)
• Michael Lim (07/24/2013 09:11 PM EDT)
• Maris Van Sprang (07/25/2013 03:37 AM EDT)
• Evert van Dijken (07/26/2013 03:52 AM EDT))
• Peter Ross (07/27/2013 11:05 AM EDT)
• David McKee (07/27/2013 11:57 AM EDT)
• Paul Harmon (07/27/2013 05:49 PM EDT)
• Trung Dinh (07/28/2013 02:09 PM EDT)
• Balakrishnan Varadarajan (07/28/2013 04:27 PM EDT)
• Nyles Heise (07/28/2013 09:56 PM EDT)
• Kirill Ignatiev (07/29/2013 12:42 AM EDT)
• Vitor Miguel (07/29/2013 04:09 AM EDT)
• Nagendra Gulu (07/29/2013 12:32 PM EDT)
• Lieke de Rooij (07/29/2013 01:43 PM EDT)
• Alex Wagner (07/30/2013 04:04 AM EDT)
• Joseph Berman (07/30/2013 02:18 PM EDT)
• Stefano Soccio (07/30/2013 04:10 PM EDT)
• Tobias Heineke (07/30/2013 04:22 PM EDT)
• n (07/30/2013 04:22 PM EDT)
• Peter Holthe Hansen & Thomas Buron Glinsk (07/30/2013 04:32 PM EDT)
• Gyorgy Gyomai (07/31/2013 12:15 PM EDT)
• Eric Rosenthal (07/31/2013 02:30 PM EDT)