Maths Olympiad Prep

Library / /273 of 377

Number theory Difficulty 5.4 AIME, harder Prove it United States

Problem:
A positive integer nn is called "flippant" if nn does not end in 00 (when written in decimal notation) and, moreover, nn and the number obtained by reversing the digits of nn are both divisible by 77. How many flippant integers are there between 1010 and 10001000?

Solution

Solution:
We use the notation "|" to mean "divides."

There is only one flippant 2-digit number, namely 7777. Indeed, if 10a+b10a + b is flippant (where a,ba, b are integers 11-99), then 710a+b7 \mid 10a + b and 710b+a7 \mid 10b + a. Thus,
73(10a+b)(10b+a)=29a7b=a+7(4ab) 7 \mid 3(10a + b) - (10b + a) = 29a - 7b = a + 7(4a - b)
so that 7a7 \mid a, and similarly 7b7 \mid b, so we'd better have a=b=7a = b = 7.

There are 1616 flippant 3-digit numbers. First consider the 1212 palindromic ones (ones where the hundreds and units digits are the same): 161,252,343,434,525,595,616,686,707,777,868161, 252, 343, 434, 525, 595, 616, 686, 707, 777, 868, and 959959.

Now consider the general case: suppose 100a+10b+c100a + 10b + c is flippant, where a,b,ca, b, c are integers 11-99. Then 7100a+10b+c7 \mid 100a + 10b + c and 7100c+10b+a7 \mid 100c + 10b + a, so 7(100a+10b+c)(100c+10b+a)=99(ac)7 \mid (100a + 10b + c) - (100c + 10b + a) = 99(a - c), and so 7ac7 \mid a - c. In order for this not to result in a palindromic integer, we must have ac=±7a - c = \pm 7 and, moreover, both 100a+10b+a100a + 10b + a and 100c+10b+c100c + 10b + c must be palindromic flippant integers. Consulting our list above, we find 44 more flippant integers: 168,259,861168, 259, 861, and 952952.

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

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.