Ponder This Challenge - March 2012 - Balanced binary tree

Ponder This Challenge:

Arrange the numbers 1, 2, 3,..., 63 on the nodes of a balanced binary tree of height 6 such that each distance 1, 2, 3,..., 62 is realized on an edge; i.e., it is the difference of two vertices which are connected with an edge.

Please supply the answer as a list of 63 numbers from top to bottom, left to right.

For example, here is a solution of the same problem for a tree of height 3 realizing all distances of 1, 2 ,.., 6:

Provide your answers in regular text format. The above solution, for example, in regular text format would be 7, 1, 3, 6, 4, 5, 2.

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

  The question is about graceful labeling of balanced binary trees (see http://mathworld.wolfram.com/GracefulGraph.html).

  There are many ways to solve this problem: genetic algorithms; standard searching techniques; SAT solvers; etc.

  But there is also an analytic solution:

  Let n denote the tree height. In our case, n=6.

  Denote by h(i) the Hamming weight function and by l(i) the truncated log_2 function.

  The following function f computes as f(i) (for 1 <= i <= 2**n-1) the required answer:

  [-(-1)**(n-l(i)) * [int(l(i)/2)+2-h(i)+i*2**(n-l(i))]] mod (2**n)

  The output for n=6, in the format we asked for is as follows:

  63,1,32,62,47,31,16,2,9,17,24,33,40,48,55,61,58,54,51,46,43,39,36,30,27,23,20,15,12,8,5,3,4,6,7,10,11,13,14,18,19,21,22,25,26,28,29,34,35,37,38,41,42,44,45,49,50,52,53,56,57,59,60.

  One of the solvers asked us why all the solutions have an odd number at the root.

  There is an elegant simple proof for that. Can you find it?

Solvers

• Michael Brand (03/01/2012 06:51 PM EDT)
• János Csorba (03/01/2012 09:49 PM EDT)
• Radu-Alexandru Todor (03/01/2012 10:47 PM EDT)
• Thomas Mack (03/01/2012 11:09 PM EDT)
• Todd Will (03/02/2012 12:09 PM EDT)
• Sanjoy Das (03/03/2012 09:33 AM EDT)
• Motty Porat (03/03/2012 11:03 AM EDT)
• Stéphane Higueret (03/03/2012 02:22 PM EDT)
• Deane Stewart & Deron Stewart (03/03/2012 11:54 PM EDT)
• Gary M. Gerken (03/04/2012 03:33 AM EDT)
• Peter Gerritson (03/04/2012 12:41 PM EDT)
• Stancu Mihai (03/04/2012 06:07 PM EDT)
• Mark Mammel (03/05/2012 01:35 AM EDT)
• Liubing Yu (03/05/2012 02:04 PM EDT)
• Joseph DeVincentis (03/05/2012 06:26 PM EDT)
• Lu Wang (03/06/2012 01:21 PM EDT)
• Adam Daire (03/06/2012 04:23 PM EDT)
• Shilei Zang (03/07/2012 05:32 AM EDT)
• Albert Stadler (03/07/2012 09:56 AM EDT)
• Chris Lewis (03/07/2012 11:54 AM EDT)
• Don Dodson (03/07/2012 06:01 PM EDT)
• Luke Pebody (03/08/2012 09:38 AM EDT)
• Øyvind Grotmol (03/08/2012 11:31 AM EDT)
• Sergey Grishaev (03/08/2012 08:37 PM EDT)
• Andreas Stiller (03/08/2012 09:20 PM EDT)
• Jonathan Namnath (03/08/2012 10:32 PM EDT)
• Mark Pervovskiy (03/09/2012 09:00 AM EDT)
• Gergely Pataki (03/09/2012 09:45 AM EDT)
• Rob Pratt (03/09/2012 09:49 AM EDT)
• Peter & Jenny de Rivaz (03/09/2012 09:53 AM EDT)
• Matej Kollár (03/09/2012 12:22 PM EDT)
• Karl D'Souza (03/09/2012 01:18 PM EDT)
• Ondrej Zjevík & Jakub Gerlich (03/10/2012 10:00 AM EDT)
• Dejan Stakic (03/11/2012 10:21 AM EDT)
• Piotr Komisarski (03/11/2012 03:16 PM EDT)
• Katarzyna Wojdziak (03/11/2012 03:41 PM EDT)
• Serge Thill (03/12/2012 09:41 AM EDT)
• Michael D Moffitt (03/13/2012 06:10 PM EDT)
• Paulo S. A. Sousa (03/13/2012 06:39 PM EDT)
• Scott Desing (03/15/2012 05:02 PM EDT)
• Armin Krauss (03/16/2012 08:35 AM EDT)
• Minxi Jiang (03/19/2012 09:25 AM EDT)
• Renato Negrinho (03/20/2012 08:44 PM EDT)
• Clive Tong (03/21/2012 04:05 AM EDT)
• Michael Kokosenski (03/25/2012 06:50 PM EDT)
• Masoud Alipour (03/25/2012 12:25 PM EDT)
• Kumar Avijit (03/24/2012 08:18 PM EDT)
• Adrian Orzepowski (03/27/2012 05:36 PM EDT)
• Maciej Piróg (03/27/2012 07:06 PM EDT)
• Jamie Jorgensen & Jason Lee (03/27/2012 09:44 PM EDT)
• Daniil Agashiyev (03/29/2012 10:29 PM EDT)
• Lei Liu (03/30/2012 04:15 AM EDT)
• Michael Rosola (03/30/2012 10:19 AM EDT)
• Heiko Selber (03/30/2012 12:52 PM EDT)
• J. Eric Ivancich (03/31/2012 01:44 AM EDT)
• Denys Kopiychenko (03/31/2012 07:34 PM EDT)