Ponder This Challenge - August 2013 - Letters on a 9D hypercube

Ponder This Challenge:

Put five-bit numbers on the vertices of a 9-dimensional hypercube such that, from any vertex, you can reach any number in no more than two moves along the edges of the hypercube.
Please provide the answer as a string of 512 characters using the following alphabet: ABCDEFGHIJKLMNOPQRSTUVWXYZ012345.
To clarify, here is a solution for the same problem with four-bit numbers on a 5-dimensional hypercube, where you can get to any number from any vertex by at most two moves along the edges:
"KLICHBEFMJAGPONDDNOPGAJMFEBHCILK"
This refers to:
Vertex Character(Value)
---------   ----------------
00000   K(10)
00001   L(11)
00010   I(8)
00011   C(2)
00100   H(7)
00101   B(1)
00110   E(4)
00111   F(5)
01000   M(12)
01001   J(9)
01010   A(0)
01011   G(6)
01100   P(15)
01101   O(14)
01110   N(13)
01111   D(3)
10000   D(3)
10001   N(13)
10010   O(14)
10011   P(15)
10100   G(6)
10101   A(0)
10110   J(9)
10111   M(12)
11000   F(5)
11001   E(4)
11010   B(1)
11011   H(7)
11100   C(2)
11101   I(8)
11110   L(11)
11111   K(10)

Each vertex of the five-dimensional hypercube is represented by five bits; this example uses only the first half of the alphabet: from A(0) to P(15).
Please wait for September with August's solution.

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

  To solve this month's challenge, you can try various types of searches, but a nice and elegant solution is to use the following linear matrix A:

  100001101
  010001011
  001000111
  000100001
  000010001

  and assign each nine-bit vertex v the five-bit value of the result of the matrix multiplication Av.
  It is easy to show that the first (v=0) vertex has all 32 types of neighbors. Lets call them v_0, v_1,..., v_31.
  From this follows that if we want to go from any vertex w of color c_1 to a neighbor of color c_2, all we need is to take the w xor v_{c_1 xor c_2} vertex.

  Don Dodson suggested a nice solution that not only contains the name and date but also the word "IBM" (look down and you'll find it vertically).

  PONDERTHISAUG2013BCFJKLXQVWMYZ45
  VQMWZY54B3FCKJXLSIUA2G10OPDNREHT
  FCB3XLKJMWVQ54ZYDNOPHTREUASI102G
  AUIS01G2NDPOTHERWMQV45YZCF3BLXJK
  45YZWMQVLXJKCF3B01G2AUISTHERNDPO
  HTREDNOP102GUASIXLKJFCB354ZYMWVQ
  2G10SIUAREHTOPDNZY54VQMWKJXLB3FC
  JKLX3BCFYZ45QVWMERTHPONDG201ISAU
  UASI102GDNOPHTREMWVQ54ZYFCB3XLKJ
  CF3BLXJKWMQV45YZNDPOTHERAUIS01G2
  QVWMYZ453BCFJKLXISAUG201PONDERTH
  OPDNREHTSIUA2G10B3FCKJXLVQMWZY54
  KJXLB3FCZY54VQMWREHTOPDN2G10SIUA
  G201ISAUERTHPONDYZ45QVWMJKLX3BCF
  THERNDPO01G2AUISLXJKCF3B45YZWMQV
  54ZYMWVQXLKJFCB3102GUASIHTREDNOP

  Matej Kollar wrote a nice game that displays the nine-dimens-dimensional cube and helps you color it.
  https://github.com/xkollar/PonderGameAugust2013

Solvers

• James Wilcox (08/01/2013 10:30 AM EDT)
• Zhuo Wang (08/01/2013 02:47 PM EDT)
• Christian Burnham (08/01/2013 05:07 PM EDT)
• Grahame Erskine (08/02/2013 09:38 AM EDT)
• Alexander Borg (08/02/2013 11:37 AM EDT)
• (08/02/2013 11:37 AM EDT)
• Andreas Stiller (08/02/2013 04:03 PM EDT)
• (08/02/2013 04:03 PM EDT)
• Andreas Razen (08/03/2013 10:31 AM EDT)
• Jan Fricke (08/03/2013 05:24 PM EDT)
• Jonathan Campbell (08/03/2013 08:17 PM EDT)
• Kenneth Arnold (08/04/2013 12:55 AM EDT)
• Tom Harley (08/04/2013 10:29 PM EDT)
• Bart De Vylder (08/05/2013 02:44 AM EDT)
• Ivan Pechenezhskiy (08/05/2013 06:39 AM EDT)
• Radu-Alexandru Todor (08/05/2013 11:40 AM EDT)
• Daniel Bitin (08/05/2013 02:59 PM EDT)
• Matt Gara (08/05/2013 03:51 PM EDT)
• Reiner Martin (08/05/2013 04:36 PM EDT)
• Masoud Alipour (08/05/2013 08:50 PM EDT)
• Kevin Bauer (08/05/2013 09:10 PM EDT)
• James Dow Allen (08/06/2013 09:40 PM EDT)
• Gergely Pataki (08/07/2013 04:06 PM EDT)
• Don Dodson (08/07/2013 11:40 AM EDT)
• Todd Will (08/08/2013 07:00 AM EDT)
• Zepeng Xie (08/08/2013 12:04 PM EDT)
• Richard Blankman (08/08/2013 04:21 PM EDT)
• Alex Wagner (08/08/2013 09:36 PM EDT)
• Duane Bailey (08/09/2013 10:17 AM EDT)
• Henry Liu (08/10/2013 10:48 AM EDT)
• Chad Barb (08/11/2013 02:05 AM EDT)
• John Tromp (08/11/2013 11:12 AM EDT)
• Joseph Berman (08/11/2013 08:31 PM EDT)
• Mark Pervovskiy (08/13/2013 06:24 PM EDT)
• Olivier Mercier (08/13/2013 10:29 PM EDT)
• Emanuele Natale (08/14/2013 01:59 PM EDT)
• Benjamin Phillabaum (08/14/2013 03:04 PM EDT)
• Harald Bögeholz (08/15/2013 02:33 PM EDT)
• Jason Levy (08/15/2013 07:52 AM EDT)
• Graham Hemsley (08/16/2013 05:22 AM EDT)
• Dieter Beckerle (08/16/2013 06:26 PM EDT)
• Ken Meehan (08/19/2013 09:43 PM EDT)
• David Greer (08/20/2013 11:40 AM EDT)
• Peter Holthe Hansen & Thomas Glinski (08/22/2013 03:32 PM EDT)
• Kan Shen (08/22/2013 10:14 PM EDT)
• Andrea Andenna (08/23/2013 03:11 AM EDT)
• Matej Kollar (08/23/2013 04:37 PM EDT)
• Fabio Michele Negroni (08/24/2013 06:34 AM EDT)
• Motty Porat (08/24/2013 03:25 PM EDT)
• Wenxun Huang (08/25/2013 03:27 AM EDT)
• Shirish Chinchalkar (08/25/2013 10:58 PM EDT)
• Balakrishnan Varadarajan (08/26/2013 09:56 AM EDT)
• Reichel Lorenz (08/28/2013 02:44 AM EDT)
• Tomek Czajka (08/28/2013 04:48 PM EDT)
• Alex Fleischer (08/29/2013 12:19 AM EDT)
• Javier Rodriguez (08/30/2013 04:17 AM EDT)
• Clive Tong (08/31/2013 10:00 AM EDT)
• Armin Krauss (08/31/2013 10:14 AM EDT)
• William Heller (08/31/2013 08:19 PM EDT)