Maths Olympiad Prep

Library / /8 of 10

Number theory Difficulty 4.2 AIME Prove it North Macedonia

Find all nNn \in \mathbb{N} divisible by 1111, such that all numbers that can be obtained from nn by an arbitrary rearrangement of its digits are again divisible by 1111.

Најди ги сите nNn \in \mathbb{N} деливи со 1111, такви што сите броеви кои се добиваат со произволна прераспределба на цифрите на бројот nn повторно се деливи со 1111.

Solutions — 2

Solution 1

From the condition 11n11|n, the number nn must have at least two digits. Let n=akak1a0n = \overline{a_k a_{k-1} \dots a_0} where aia_i, 0ik0 \le i \le k are digits and ak0a_k \ne 0. From the former discussion we have k1k \ge 1.

We will show that all digits in the number nn are equal. Namely, from the condition of the exercise, the number n=akak1ai1aiai2a0n' = \overline{a_k a_{k-1} \dots a_{i-1} a_i a_{i-2} \dots a_0} (nn' is obtained from nn by exchanging the positions of the digits ai1a_{i-1} and aia_i) is also divisible by 1111. Therefore 11nn11|n-n', i.e. 1110i1(aiai1ai1ai)11|10^{i-1}(\overline{a_i a_{i-1}} - \overline{a_{i-1} a_i}) or 1110i19(aiai1)11|10^{i-1} \cdot 9(a_i - a_{i-1}), and hence ai=ai1a_i = a_{i-1}.

It follows that n=a1111k+1n = a \cdot \overline{11\dots11}_{k+1}. We easily check that 11n11|n if and only if kk is an odd number.

Solution 2

Од условот 11n11|n и бројот nn мора да е најмалку двоцифрен. Нека n=akak1...a0n = \overline{a_k a_{k-1}...a_0} каде aia_i, 0ik0 \le i \le k се цифри и ak0a_k \ne 0. Од претходната дискусија k1k \ge 1.

Ќе покажеме дека сите цифри во бројот nn се еднакви. Имено, од условот на задачата и бројот n=akak1ai1aiai2a0n' = a_k a_{k-1} \dots a_{i-1} a_i a_{i-2} \dots a_0 (nn' е добиен од nn со промена на местата на цифрите ai1a_{i-1} и aia_i) е делив со 1111. Значи 11nn11|n-n', т.е. 1110i1(aiai1ai1ai)11|10^{i-1}(a_i a_{i-1} - a_{i-1} a_i) или 1110i19(aiai1)11|10^{i-1} \cdot 9(a_i - a_{i-1}), па мора ai=ai1a_i = a_{i-1}.

Следува, n=a1a2ak+1n = a_1 \cdot a_2 \cdot \dots \cdot a_{k+1}. Лесно се проверува дека 11n11|n ако и само ако kk е непарен број.

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 and solution reproduced as published; topic and difficulty added by this site.