Maths Olympiad Prep

Library / /204 of 1394

Number theory Difficulty 4.9 AIME Find the answer United States

Problem:
Compute the 100th smallest positive multiple of 77 whose digits in base 1010 are all strictly less than 33.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Solution:
We construct an order-preserving bijection between positive multiples of 77 in base 1010 whose digits are all less than 33 and positive multiples of 77. For any multiple of 77 in base 1010 with digits all less than 33, interpret it as a base 33 number and convert it to a base 1010 decimal, which will be a multiple of 77. For example, 10221022 would map to 10223=35101022_3 = 35_{10}.

We first show that this is a valid mapping. Let ana1a0a_n \ldots a_1 a_0 be an arbitrary multiple of 77 (in base 1010) whose digits are all less than 33. This has a natural interpretation in base 33, and converting this interpretation to base 1010 gives
ana1a03=an3n++a131+a030an10n++a1101+a0100=ana1a0(mod7), a_n \ldots a_1 a_{0_3} = a_n \cdot 3^n + \cdots + a_1 \cdot 3^1 + a_0 \cdot 3^0 \equiv a_n \cdot 10^n + \cdots + a_1 \cdot 10^1 + a_0 \cdot 10^0 = a_n \ldots a_1 a_0 \pmod{7},
which is a multiple of 77.

This mapping is an injection because base conversion is an injection, and this mapping is also a surjection because for any multiple of 77 in base 1010, we can convert it to base 33 and interpret this number as a base 1010 decimal. (Reversing the above steps, we see the resulting decimal number is a multiple of 77.) Furthermore, for two positive multiples of 77 whose digits are less than 33, the larger one will have a larger base 33 representation, so this mapping is order-preserving.

Thus, this mapping is an order-preserving bijection between multiples of 77 in base 1010 with digits less than 33 and multiples of 77 in base 33. Therefore, the answer is the preimage of the 100th smallest positive multiple of 77, which is equal to 70010=2212213700_{10} = \boxed{221221}_{3}.

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.