Library / CEMC Gauss (Grade 8) /525 of 525

CEMC Gauss (Grade 8), 2015

Number theory Difficulty 4.9 AIME Find the answer Canada

The alternating sum of the digits of 63 195 is $6-3+1-9+5=0$ . In general, the alternating sum of the digits of a positive integer is found by taking its leftmost digit, subtracting the next digit to the right, adding the next digit to the right, then subtracting, and so on. A positive integer is divisible by 11 exactly when the alternating sum of its digits is divisible by 11. For example, $63\,195$ is divisible by 11 since the alternating sum of its digits is equal to 0, and 0 is divisible by 11. Similarly, $92\,807$ is divisible by 11 since the alternating sum of its digits is 22, but $60\,432$ is not divisible by 11 since the alternating sum of its digits is 9. Lynne forms a 7-digit integer by arranging the digits $1,2,3,4,5,6,7$ in random order. What is the probability that the integer is divisible by 11?

Pick one

Solution

All 2-digit prime numbers are odd numbers, so to create a reversal pair, both digits of each prime must be odd (so that both the original number and its reversal are odd numbers).

We also note that the digit 5 cannot appear in either prime number of the reversal pair since any 2-digit number ending in 5 is not prime.

Combining these two facts together leaves only the following list of prime numbers from which to search for reversal pairs: $11, 13, 17, 19, 31, 37, 71, 73, 79,$ and 97.

This allows us to determine that the only reversal pairs are: 13 and 31, 17 and 71, 37 and 73, and 79 and 97.
(Note that the reversal of 11 does not produce a different prime number and the reversal of 19 is 91, which is not prime since $7\times13=91$ .)

Given a reversal pair, we must determine the prime numbers (different than each prime of the reversal pair) whose product with the reversal pair is a positive integer less than 10 000.

The product of the reversal pair 79 and 97 is $79\times97=7663$ .
Since the smallest prime number is 2 and $2\times7663=15\,326$ , which is greater than $10\,000$ , then the reversal pair 79 and 97 gives no possibilities that satisfy the given conditions.

We continue in this way, analyzing the other 3 reversal pairs, and summarize our results in the table below.

Prime Number	Product of the Prime Number with the Reversal Pair
13 and 31	17 and 71	37 and 73	79 and 97
2	$2\times13\times31=806$	$2\times17\times71=2414$	$2\times37\times73=5402$	greater than 10 000
3	$3\times13\times31=1209$	$3\times17\times71=3621$	$3\times37\times73=8103$
5	$5\times13\times31=2015$	$5\times17\times71=6035$	greater than 10 000
7	$7\times13\times31=2821$	$7\times17\times71=8449$
11	$11\times13\times31=4433$	greater than 10 000
13	can’t use 13 twice
17	$17\times13\times31=6851$
19	$19\times13\times31=7657$
23	$23\times13\times31=9269$
29	greater than 10 000
Total	8	4	2	0

In any column, once we obtain a product that is greater than 10 000, we may stop evaluating subsequent products since they use a larger prime number and thus will exceed the previous product.
In total, there are $8+4+2=14$ positive integers less than 10 000 which have the required property.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.