Example 1. A palindrome is a number which reads the same forward and backwards such as 1441 or 35253. Find the largest five-digit palindrome that is divisible by 101.
Example 2. Suppose, we have an urn with 1000 balls numbered from 1 to 1000. We choose 9 balls randomly from the urn (without replacement) and add the shown numbers. Determine the probability that the sum is even.
Solution 1. Suppose the palindrome abcba is a multiple of 101, where a, b and c are digits. Now 101 is a factor of 1010 and we have b × 1010 = b0b0.
Therefore, abcba – b × 1010 = abcba – b0b0 = a0c0a is a multiple 101.
Again, 10201 = 10100 + 101 = 101(100 + 1) is a multiple of 101 and hence a0c0a – a × 10201 = (c – 2a) 100 is also a multiple of 101.
Since 100 and 101 are relatively primes, 101 must divide (c – 2a).
But 18 ≤ c – 2a ≤ 9, and the only integer multiple of 101 in that range is zero.
Essentially c – 2a = 0, which means that the maximal value for the first digit of our palindrome is a = 4 and then c is 4.
We can choose b any way we like and its maximal value is 9, which gives 49894 as the largest five-digit palindrome that is divisible by 101.
Solution 2. First we will show that, if we choose 9 balls randomly then it is equally likely to get an even sum as an odd sum, i.e., the required probability in question is 1/2 .
Consider the 1000 balls in the given urn as 500 even-numbered balls painted white and 500 odd-numbered balls painted black.
The sum of the number on the 9 chosen balls will be odd exactly when we select an odd number of white balls and an even number of black balls.
Thus, we could select 1, 3, 5, 7 or 9 white balls to get an odd sum or 0, 2, 4, 6 or 8 white balls to get an even sum.
Clearly, since we begin with 500 balls of each colour, the probability of selecting k white balls with 9 – k black balls is equal to the probability of selecting k black balls with 9 – k white balls.
This shows that the probabilities of selecting 1, 3, 5, 7 or 9 white balls is equal to the probability of selecting 8, 6, 4, 2 or 0 white balls, respectively. Therefore, it is equally likely that our sum will be even or odd.