Earlier today I set you the following two puzzles:
1) Why is every even digit palindrome divisible by 11? (An even digit palindrome is a palindromic number that contains an even number of digits, like 1221, or 678876.)
Solution
There are different ways to solve this one. My method is perhaps the least technical, but feel free to post other methods below the line.
Let’s take a six digit palindrome, and call it ABCCBA. We can rephrase this as
(100001)A + (10010)B + (1100)C
which reduces further to
(100001)A + (1001)10B + (11)100C
This number will be divisible by 11 if each term is divisible by 11. If we can show that 100001, 1001 and 11 are all divisible by 11 we are done. But rather than use a calculator, let’s find the pattern.
11: that’s obviously divisible by 11.
1001: if we subtract 11 from 1001 we get 990, which is 9 x 110 = 9 x 10 x 11. And if 990 is divisible by 11, so is 1001
100001: if we subtract 11 from 100001 we get 99990, which is (9 x 11000) + (9 x 110) = (9 x 11 x 1000) + (9 x 11 x 10). Both terms are divisible by 11, so 99990 is, which means that 10001 is.
Spot the pattern? Any number of the form 100…001 where there are an even number of zeros between the 1s is divisible by 11. If this is the case, not only is our six-digit palindrome divisible by 11, but every even digit palindrome is, since we will be able to convert, as above, all even digit palindromes into a sum of terms, such that each term is a multiple of a number of the form 100…001, with even number of zeros.
2) More than 100 people live in a village. Prove there are 11 people living in the village for whom the sum of their ages is divisible by 11.
Solution
The property of 11 that is relevant here is the fact that the sum of numbers from 1 to 10 is divisible by 11.
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
We’ll get to why this is important in a moment.
There are at least 101 people in the village. Divide each age by 11, and make a note of all the remainders. Allocate each villager into one of 11 groups based on the their remainders. Everyone with remainder 0 is in one group, everyone with remainder 1 is in another group, everyone with remainder 2 is in another group, and so on.
It might be the case that one group has 11 or more people in it. But if no group has 11 or more people in it, then every group must have at least one person in it. (Since if no group has 11 members, all groups must have at most ten members. You cannot fit 101 people into ten groups with a maximum of ten members, since there are 101 candidates for only 10 x 10 = 100 spaces. There will always be at least one left over, in the eleventh group.)
If one group has 11 or more people in it, take 11 people from that group. The sum of their ages will be divisible by 11.
If every group has one person in it, then take a person from each group. Their remainders will add up to 55, which is divisible by 11. The sum of their ages must therefore also be divisible by 11.
I hope you enjoyed today’s puzzles. I’ll be back in two weeks.
I set a puzzle here every two weeks on a Monday. I’m always on the look-out for great puzzles. If you would like to suggest one, email me.
Sources for today’s puzzles:
1) Suggested by Angayar Pavanasam, of the National Institute of Technology, Trichy, India.
2) Adapted from Half A Century of Pythagoras Magazine, edited by Alex van den Brandhof, Jan Guichelaar and Arnout Jaspers.
