//---------------------------------------------------------------------- // Enigma1340.c (c) 2005 by Charles Petzold (www.charlespetzold.com) // // "Stairs and Sums" from New Scientist, 14 May 2005, page 49. // // This problem involves a game in which a teddy bear is placed on // the top step of 9 numbered steps, where 9 is the top step. // The landing is 0. Teddy is pushed off the // top step and lands on a step below (steps 0 through 8). He is // then repeatedly pushed off the step he lands on until he // finally lands on step 0. The score for each game is the sum of // the steps Teddy lands on, including the one he started on. // // The probability of Teddy landing on any step below the one he's // pushed off is the same. // // This problem can be analyzed in a fairly straight-forward manner // without a computer program involved. // // For a game played on 1 step, Teddy goes from 1 to 0, and the // average score (Si, where i is the number of steps) is always 1: // // S1 = 1 // // For 2 steps, Teddy can go from 2 to 0, or from 2 to 1 with equal // probability. In the first case, the score is 2. In the second, the // score is 2 + S1. The average is: // // S2 = (2 + 2 + S1) / 2 // // or: // // S2 = 2 + (1/2)S1 // // For 3 steps, Teddy can go from 3 to 0, from 3 to 1, or 3 to 2 // with equal probability, for scores of 3, 3 + S1, and 3 + S2. // The average is: // // S3 = 3 + (1/3)(S1 + S2) // // or: // // S3 = 3 + (1/3)Sum(S1, S2) // // In general, // // Si = i + (1/i)Sum(S1 ... Si-1) // // The one that we're really interested in is: // // S9 = 9 + (1/9)(S1 + S2 + S3 + S4 + S5 + S6 + S7 + S8) // // or: // // S9 = 9 + (1/9)Sum(S1 ... S8) // // Let's rearrange a bit to extract S8 from the sum: // // S9 = 9 + (1/9)(S8 + Sum(S1 ... S7)) // // And substitute for S8: // // S9 = 9 + (1/9)(8 + (1/8)Sum(S1 ... S7) + Sum(S1 ... S7)) // // So: // // S9 = 9 + 8/9 + (1/8)Sum(S1 ... S7) // // This time extract S7 from the sum: // // S9 = 9 + 8/9 + (1/8)(S7 + Sum(S1 ... S6)) // // Substitute S7: // // S9 = 9 + 8/9 + (1/8)(7 + (1/7)Sum(S1 ... S6) + Sum(S1 ... S6)) // // So: // // S9 = 9 + 8/9 + 7/8 + (1/7)Sum(S1 ... S6) // // Keep doing this and eventually you'll get: // // S9 = 9 + 8/9 + 7/8 + 6/7 + 5/6 + 4/5 + 3/4 + 2/3 + 1/2 // // and that's about 15.17. // // The program uses two methods. The first is a recursive function, // and the second is a simulation. // //---------------------------------------------------------------------- #include #include // Returns the Average score for Teddy pushed off step number Step. double AverageScore(int Step) { int i; double Score = 0; if (Step == 0) return 0; for (i = 0; i < Step; i++) Score += Step + AverageScore(i); return Score / Step; } // Simulate the game Trials times and take the average. double RandomPushes(int Trials) { int i; double Total = 0; for (i = 0; i < Trials; i++) { int Step = 9, Score = 0; while (Step > 0) { Score += Step; Step = rand() % Step; } Total += Score; } return Total / Trials; } int main(void) { printf("Average score using recursive function: %f\n", AverageScore(9)); printf("Average score using 1,000,000 random kicks: %f\n", RandomPushes(1000000)); return 0; }