Permutations and Combinations Puzzle: Cube with Equal Faces
Source: Asked to me by Sumit Yadav
Problem:
Is it possible to label the edges of a cube using the numbers 1 through 12, in such a way that the sums of the numbers on any two faces of the cube are equal?
Update: (19-07-2012)
Solution posted by Rakesh Roy (SAP Labs, Bangalore) and Praveen Reddy Vaka (Mechanical Engg IITM Alumnus 2006, CSE IIT Kanpur Alumnus 2011) in comments!
Solution posted by Rakesh Roy (SAP Labs, Bangalore) and Praveen Reddy Vaka (Mechanical Engg IITM Alumnus 2006, CSE IIT Kanpur Alumnus 2011) in comments!
Yes, it is possible to label the edges of a cube using the numbers 1 through 12, such that the sums of the numbers on any two faces of the cube are equal. The sum of the numbers is 26. Let a,b,c,d,e,f,g,h,i,j,k,l be the edges of the cube. a-b-c-d(clockwise, facing towards the viewer)represents one face with h-e-f-g(clockwise) as the face exactly opposite to it. Similarly, c-i-f-j and a-l-h-k is another pair of opposite faces. Top face is b-l-e-i and bottom is d-k-g-j. The values a to l are as follows:
ReplyDeletea= 5; b=11; c=9; d=1; e=2; f=8; g= 12; h= 4; i= 3; j=6; k=7; and l=10.
Let us say label the edges of the cube as follows. a,b,c,d for the edges facing us a',b',c',d' for the edges edges exactly opposite. Label the other four edges e1,e2,e3,e4. Now we need the following conditions satisfied a+b+c+d = a'+b'+c'+d' = a+a'+e1+e2 = b+b'+e2+e3 = c+c'+e3+e4 = d+d'+e4+e1 and each of the numbers 1 to 12 is used exactly once.
ReplyDeleteWe don't solve this explicitly the conditions directly map to a well known problem. This is exactly equivalent to finding the solution of the following magic star https://picasaweb.google.com/116877570854616166367/GOAL?authkey=Gv1sRgCNi_rbHy-5jdLg#5751571488108842450 such that sum along each line is equal and each number from 1 to 12 appear exactly once. It is easy to prove that each sum has to be exactly 26 and based on this we can construct a solution by hand. There are several possible solutions one of them is listed by Rakesh. If needed all the solutions can be listed by a program based on a simple back tracking algorithm. Anyone interested in programming can even try to code the solution for http://www.spoj.pl/problems/GCPC11D
Thanks for the solution Rakesh and Praveen. Special thanks to Praveen for taking the pain to draw the image. That was really useful.
ReplyDeleteFrom Bob's Blog:
This is a very old puzzle, first proposed by Henry E. Dudeney and catalogued by Donald E. Knuth with the entry:
A star puzzle: Magic 6-star of {1,2,…,12} with sums 26
Volume 50, (1915), page 210, puzzle number X261.
This can be considered a problem in 12 unknowns with only 6 equations (the 6 straight lines making up the figure). There are therefore apparently 6 degrees of freedom. A straight-forward approach would be to choose A, B, C, D, F and G, (E must be equal to 26 – B – C – D, of course) and then calculate the other letters from the obvious relations. This would appear to give 12 x 11 x 10 x 9 x 8 x 7 solutions (12 choices for A, 11 for B etc) or 665,280 in all.
Unfortunately, many of these choices give values which are less than 1 or greater than 12 for some letters E or H – L. When these are eliminated, there are still many illegal combinations left where some numbers are duplicated. Finally the number of solutions is whittled down to 960 (double counting the symmetric stars).
I am sure the backtracking algorithm would be more efficient.
ReplyDeleteA simple all permutation search would also give all the solutions. Code can be found here:
http://www.reocities.com/oosterwal/computer/combinations.html
This comment has been removed by a blog administrator.
ReplyDeleteWe can remap 1,2 ... 12 to the numbers -11, -9, -7, ... -1, 1, 3, ... 11 as sums of the faces of cube remain equal.
ReplyDeleteNow, we can easily see from symmetry that each face should have 2 negative numbers and corresponding 2 positives which translates to a sum of 26 in the original numbers.
Trying different combinations we can get the values {11, -11, -3, 3} for the front face starting from top edge counter-clockwise, {-9, -1, +1, +9} for the back face starting from top edge counter-clockwise and {5, 7, -5, -7} for the side edges counter-clockwise from top-left.
Remapping gives {12, 1, 5, 8}, {2, 6, 7, 11} and {9, 10, 4, 3}