//-------------------------------------------------------------------
// 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;
}