Maths Olympiad Prep

Library / /229 of 462

Number theory Difficulty 5.8 AIME, harder Prove it Ireland

A positive integer nn is an anchor if every digit of nn (when written in base 10) is an odd number. Show that there exists an anchor nn such that the product mnm \cdot n is not an anchor for any anchor m>1m > 1.

Solutions — 4

Solution 1

Solution 1. One such integer is n=91n = 91. We show there is no anchor m>1m > 1 such that m×nm \times n is also an anchor for this value of nn. Let m>1m > 1 be an anchor. We consider separately the cases 3m93 \le m \le 9 and m11m \ge 11.
For small anchors mm, we have 3×91=2733 \times 91 = 273, 5×91=4555 \times 91 = 455, 7×91=6377 \times 91 = 637 and 9×91=8199 \times 91 = 819, none of which are anchors.

When m11m \ge 11, let the last two digits of mm be m1m_1 and m0m_0, with m0,m1{1,3,5,7,9}m_0, m_1 \in \{1, 3, 5, 7, 9\}. Then we can write (for some integer k0k \ge 0): m=100k+10m1+m0m = 100k + 10m_1 + m_0 so that:
91m=(90+1)(100k+10m1+m0)=100×(91k+9m1)+10(9m0+m1)+m0 \begin{aligned} 91m &= (90 + 1)(100k + 10m_1 + m_0) \\ &= 100 \times (91k + 9m_1) + 10(9m_0 + m_1) + m_0 \end{aligned}
The penultimate digit is then 9m0+m1(mod10)9m_0 + m_1 \pmod{10} which is even, and so 91m91m cannot be an anchor.

Solution 2

Solution 2. One such integer is n=99n = 99. We show there is no anchor m>1m > 1 such that m×nm \times n is also an anchor for this value of nn. Let m>1m > 1 be an anchor. We consider separately the cases 3m93 \le m \le 9 and m11m \ge 11.
For small anchors mm, we have 3×99=2973 \times 99 = 297, 5×99=4955 \times 99 = 495, 7×99=6937 \times 99 = 693 and 9×99=8919 \times 99 = 891, none of which are anchors.

When m11m \ge 11, let the last two digits of mm be m1m_1 and m0m_0, with m0,m1{1,3,5,7,9}m_0, m_1 \in \{1, 3, 5, 7, 9\}. Then we can write (for some integer k0k \ge 0): m=100k+10m1+m0m = 100k + 10m_1 + m_0 so that
99(100k+10m1+m0)(10m1+m0)10010m1m010(9m1)+(10m0)(mod100). \begin{aligned} 99(100k + 10m_1 + m_0) &\equiv -(10m_1 + m_0) \equiv 100 - 10m_1 - m_0 \\ &\equiv 10(9 - m_1) + (10 - m_0) \pmod{100}. \end{aligned}
This shows that the second last digit of 99m99m is equal to 9m19 - m_1, and this is even since m1m_1 is odd. Hence, 99m99m is not an anchor for any anchor m>1m > 1.

Solution 3

Solution 3. One such integer is n=911n = 911. We show there is no anchor m>1m > 1 such that m×nm \times n is also an anchor for this value of nn. The argument below applies to any n=91111>91n = 911 \dots 11 > 91.

First note that 9a9a, for any number 1<a<111 < a < 11, has two digits, the sum of which is divisible by 9 and smaller than 18, hence equal to 9. The units digit of 9a9a is odd if aa is odd, hence the leading digit is equal to the even number 9a9 - a. In particular, the leading digit of 911m911 \cdot m is even for m=3,5,7,9m = 3, 5, 7, 9, because there are no carries from the multiplications by 1.
If m>10m > 10 is an anchor, we have m10a+b(mod100)m \equiv 10a + b \pmod{100} with a,ba, b being odd digits. Hence 911m11(10a+b)10(a+b)+b(mod100)911m \equiv 11(10a + b) \equiv 10(a + b) + b \pmod{100} which means that the units digit of 911m911m is bb and the hundreds digit is equal to a+ba + b or a+b10a + b - 10, both of which are even.

Solution 4

Solution 4. It suffices to find a single anchor nn such that m×nm \times n is a non-anchor for all anchors m>1m > 1. There are many such nn. Here are some cases where n11(mod20)n \equiv 11 \pmod{20} with manual checks for m=3,5,7,9m = 3, 5, 7, 9:

m \ n91551911931951971991
3273165327332793285329132973
5455275545554655475548554955
7637385763776517665767976937
9819495981998379855987398919

Here are some cases with n19(mod20)n \equiv 19 \pmod{20}:
m \ n99339779919939959979999
32971017233727572817287729372997
54951695389545954695479548956895
76932373545364336573671368536993
98913051701182718451863188118991

It remains to check that the chosen value of nn produces non-anchors when multiplied by anchors m11m \ge 11. To prove this, we suppose more generally that either n11(mod20)n \equiv 11 \pmod{20} or n19(mod20)n \equiv 19 \pmod{20}. Since m11m \ge 11 is an anchor, mm has at least two digits and the last two digits are odd. Hence m{11,13,15,17,19}(mod20)m \in \{11, 13, 15, 17, 19\} \pmod{20}. Consider the multiplication table (mod 20):
m \ n1119
110109
130307
150505
170703
190901

In each case, the penultimate decimal digit is even so m×nm \times n is not an anchor. According to the remark above, we have tabulated all the solutions for n1000n \le 1000.

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.