In how many ways can a pound (value 100 pence) be changed into some combination of 1, 2, 5, 10, 20 and 50 pence coins? There are more than 4000 possibilities. Lots of people have sent lists of some of the possibilities but nobody has cracked this one yet. Perhaps people were put off by the length of the question but it described how to solve the problem.
Solution to tough nut Small Change by John Lesieutre and Tony Cardell, both 14, both State College Area High School
The method we used to solve this problem was rather simple. The number of ways to make n pence out of 1 and 2 pence coins is (n/2)+1 is n is even and ((n+1)/2) if n is odd. This is given in the hint, and is also obvious. A calculator program was then written which checked all combinations of up to 2 fifty pence coins, up to 5 twenty pence coins, up to 10 ten pence coins, and up to 20 five pence coins, and then filled up the rest of the amount needed to reach 100 pence with every combination of 1 and 2 pence coins. There are a total of 3*6*11*21 (There can be 0 of a coin!)=4158 different combinations to try. For each combination, the program calculated the number of ways to finish the 100 pence using 1 and 2 pence coins, and added this number to a variable E. When all 4,158 combinations had been checked after 5 minutes and 15 seconds, E=4,562 and therefore this is the number of ways to make 1 pound out of 1, 2, 5, 10, 20, and 50 pence coins.