About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
March 2012
<<February March April>>
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?
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com