June 2011 Brain Teaser Solution

When I divide it by 2, the remainder is 1. When I divide it by 3, the remainder is 2. When I divide it by 4, the remainder is 3. When I divide it by 5, the remainder is 4. When I divide it by 6, the remainder is 5. When I divide it by 7, the remainder is 6. When I divide it by 8, the remainder is 7. When I divide it by 9, the remainder is 8. When I divide it by 10, the remainder is 9. Find the smallest number that satisfies these conditions.

Since the remainder is always so close to the next multiple, the main idea is lowest common multiple so as George Polya, suggested solve a simpler problem.
Polya's Main Ideas in How to Solve It

Let's use just the first three criteria

When I divide it by 2, the remainder is 1.When I divide it by 3, the remainder is 2.When I divide it by 4, the remainder is 3. The number will be one less than the lowest common multiple of 2, 3 and 4 Counting by 2s 3s and 4s will yield 2 4 6 8 10 12 3 6 9 12 4 8 12  So 12 is the LCM -- notice that if we were to multiply 2 x 3 x 4, we would get 24 which is not the lowest common multiple.  The number is one less than this so 11 would be the number that satisfies all three criteria. With a longer list of numbers we might not want to write out all of the multiples.  In fact, for 2, 3 and 4, if we break them down to prime factors 2 is 2 and 3 is 3 but 4 is 2 x 2.  If we already have 2 and 3 we only need one more 2 to make a 4. So 2 x 3 x 2 will cover 2, 3, and 4 (2 x 2). So for all the way up to 10, we need the LCM of 2, 3, 4, 5, 6, 7, 8, 9, 10 For 2, 3, 4, 5 we need to add a 5 so 2 x 3 x 2 x 5 = 60 For 2, 3, 4, 5, 6, we already have a 6 because 2 x 3 = 6 so the LCM of 2, 3, 4, 5 ,6 is 60. For 2, 3, 4, 5, 6, 7 we need to add a 7 so 2 x 3 x 2 x 5 x 7 = 420 For 2, 3, 4, 5, 6, 7, 8, we need to add a 2 (8 is 2 x 2 x 2 and so far we only have two 2s) = 840 For 2, 3, 4, 5, 6, 7, 8, 9 we need to add a 3 (9 is 3 x 3 and so far we only have one 3) = 2520 For 2, 3, 4, 5, 6, 7, 8, 9 , 10 we already have a 10 because 2 x 5 = 10 so the LCM = 2520.

So the answer is 1 less than 2520: 2519