//------------------------------------------------------------------- // enigma1354.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Sound Idea" by Bob Walker, New Scientist, 20 August 2005, page 51. // // A wind chime, with 10 chimes of lengths 1 cm to 10 cm, placed // uniform distances apart around the circumference of a round // disk so they are "balanced perfectly." The 10 lengths of the // chimes in this sequence form an 11-digit number. What's the // smallest possible number for balanced chimes? // // This number obviously begins with 10, and the next digit ideally // is 1. Where we go from there depends on what balances. // // The weight of each chime is proportional to its length, so the // total weight of the chimes is 55 whatevers. // // Although I can't demonstrate this mathematically, it seems likely // that we want a situation where any line through the center of the // disk divides the weights into 27 on one side and 28 on another. If // we imagine this dividing line as rotating around the center of the // disk, we see that any chime of weight n should be balanced on // the opposite side by a weight of n+1 or n-1. If a chime of // weight n is balanced on the opposite by n+1, then the chime // adjancent to n (m, say) must be balanced with m-1. // // So, the 10 chime must be opposite the 9 chime. Here's a view of // the disk where the plus size indicates the center: // // 10 + 9 // // If the 1 chime is adjacent to the 10, then 2 must be adjacent to 9: // // 2 // 10 + 9 // 1 // // The chime opposite 10 is 10-1. The chime opposite the 1 is 1+1. // The next chime after the 1 (n, say) has to be opposite n-1. // Aiming for the lowest possible number, the next chime has to be 4 // and the opposite chime is 4-1: // // 3 // 2 // 10 + 9 // 1 // 4 // // The next one can be 5, opposite 5+1: // // 6 3 // 2 // 10 + 9 // 1 // 4 5 // // And then 8, opposite 8-1: // // 6 3 // 7 2 // 10 + 9 // 1 8 // 4 5 // // So, any dividing line through the center splits the chimes into 27 // on one side and 28 on another. As that line is rotated around the // center and passes each opposite pair, the weight shifts on one side // from 27 to 28, and on the other from 28 to 27. // // The answer, I conclude, is the number 10,145,892,367. // // But I'm not happy with this at all because I'm not sure how to // verify that this configuration is actually "balanced perfectly" // without getting down and dirty calculating the center of gravity. // // It is easy to calculate a center of gravity between two weights. // A Weight w1 at point (x1, y1) and a weight w2 at (x2, y2) is // equivalent to weight (w1 + w2) at the center of gravity at the // point (x,y) where: // // x = (x1 * w1 + x2 * w2) / (w1 + w2) // y = (y1 * w1 + y2 * w2) / (w1 + w2) // // A center of gravity among 10 points can be calculated similarly as // a series of pairs. Any two weights are equivalent to the combined // weight at the center of gravity. // // The code shown below loops through all the possible configurations // of chimes and calculates a center of gravity. If that center of // gravity coincides with the center of the disk, then the configuration // is balanced. //--------------------------------------------------------------------- #include #include // Define Pi and a Point structure. #define Pi acos(-1) typedef struct { double X, Y; } Point; int main(void) { int Chimes, ChimesTest, i, DigitTaken[10], Weight; Point Center, HangPoint[10]; // HangPoint are the coordinates of each chime based on a unit circle // where the origin is the center of the disk. for (i = 0; i < 10; i++) { HangPoint[i].X = cos(i * 2 * Pi / 10); HangPoint[i].Y = sin(i * 2 * Pi / 10); } // Loop through the possible orders of the nine chimes after chime "10". for (Chimes = 123456789; Chimes <= 987654321; Chimes++) { // Initialize the DigitTaken array for (i = 0; i < 10; i++) DigitTaken[i] = 0; // Store the Chimes value for mangling. ChimesTest = Chimes; // Loop through the 9 digits of Chimes. // We want to prevent digits of zero, and all the // digits need to be unique. for (i = 0; i < 9; i++) { // Get the least significant digit. int LastDigit = ChimesTest % 10; // If it's zero, we're not interested in that Chimes value. if (LastDigit == 0) break; // If the digit was already present, ditto. if (DigitTaken[LastDigit] > 0) break; // Mark the digit as taken. ++DigitTaken[LastDigit]; // Prepare for the next digit. ChimesTest /= 10; } // Check if the loop was completed successfully. if (i < 9) continue; // Initialize Center of gravity and Weight with Chime "10". Center = HangPoint[0]; Weight = 10; // Store the Chimes value for mangling again. ChimesTest = Chimes; // Loop through the 9 digits of Chimes. // We want to calculate a new center of gravity and total weight. for (i = 0; i < 9; i++) { int ChimeWeight = ChimesTest % 10; Point ChimePoint = HangPoint[9 - i]; // could also be [i + 1] // Calculate the new center of gravity based on weighted averages. Center.X = (Weight * Center.X + ChimeWeight * ChimePoint.X) / (Weight + ChimeWeight); Center.Y = (Weight * Center.Y + ChimeWeight * ChimePoint.Y) / (Weight + ChimeWeight); Weight += ChimeWeight; // Prepare for the next digit. ChimesTest /= 10; } // Check if the center of gravity is close to the origin. if (fabs(Center.X) < 0.000001 && fabs(Center.Y) < 0.000001) { printf("10,%i Center = (%20.17f, %20.17f)\n", Chimes, Center.X, Center.Y); } // For all printed configurations, the centers of gravity are as close // to the origin as the precision of IEEE double-precision allows. // The smallest number is the solution to the problem. } return 0; }