Olympiad Maths Prep

Track / Stage 7 / 73 of 300 #1473 of 2000

Problem 1473

National olympiad second round; IMO P1/P4
Number theory Difficulty 7.1 Find the answer

Let dd be a natural number. Given two natural numbers MM and NN with dd digits, MM is a friend of NN if and only if the dd numbers obtained substituting each one of the digits of MM by the digit of NN which is on the same position are all multiples of 77. Find all the values of dd for which the following condition is valid:
For any two numbers MM and NN with dd digits, MM is a friend of NN if and only if NN is a friend of MM.

Official solution

1. Define the problem and notation:
Let d d be a natural number. Given two natural numbers M M and N N with d d digits, M M is a friend of N N if and only if the d d numbers obtained by substituting each one of the digits of M M by the digit of N N which is in the same position are all multiples of 7 7 . We need to find all values of d d for which the following condition is valid: For any two numbers M M and N N with d d digits, M M is a friend of N N if and only if N N is a friend of M M .

2. **Express M M and N N in terms of their digits:**
Let M=k=0d1mk10k M = \sum_{k=0}^{d-1} m_k 10^k and N=k=0d1nk10k N = \sum_{k=0}^{d-1} n_k 10^k .

3. **Condition for M M to be a friend of N N :**
The statement that M M is a friend of N N is equivalent to:
M+10k(nkmk)0(mod7)for all 0kd1. M + 10^k (n_k - m_k) \equiv 0 \pmod{7} \quad \text{for all } 0 \leq k \leq d-1.

4. **Case 1: d≢2(mod7) d \not\equiv 2 \pmod{7} :**
- Assume M M is a friend of N N and vice versa.
- Summing all the equalities, we get:
dM+NM0(mod7)anddN+MN0(mod7). dM + N - M \equiv 0 \pmod{7} \quad \text{and} \quad dN + M - N \equiv 0 \pmod{7}.
- Subtracting these two congruences:
(d2)M(d2)N(mod7)    MN(mod7). (d-2)M \equiv (d-2)N \pmod{7} \implies M \equiv N \pmod{7}.
- Since M M and N N are congruent modulo 7, we can write:
M+10k(nkmk)0N+10k(mknk)M+10k(mknk)(mod7). M + 10^k (n_k - m_k) \equiv 0 \equiv N + 10^k (m_k - n_k) \equiv M + 10^k (m_k - n_k) \pmod{7}.
- This implies MN0(mod7) M \equiv N \equiv 0 \pmod{7} .
- However, there exist numbers M M and N N such that M M is a friend of N N and 7M 7 \nmid M . For example, take M=10d1 M = 10^{d-1} , nd1=7 n_{d-1} = 7 , and nk10dk(mod7) n_k \equiv -10^{d-k} \pmod{7} . If k<d1 k < d-1 , then:
M+10k(nkmk)=10d+10knk0(mod7), M + 10^k (n_k - m_k) = 10^d + 10^k n_k \equiv 0 \pmod{7},
and if k=d1 k = d-1 , then:
M+10k(nkmk)=7×10d10(mod7). M + 10^k (n_k - m_k) = 7 \times 10^{d-1} \equiv 0 \pmod{7}.
- This shows that N N is not necessarily a friend of M M , contradicting the condition.

5. **Case 2: d2(mod7) d \equiv 2 \pmod{7} :**
- Assume M M is a friend of N N .
- Summing the equalities M+10k(nkmk)0(mod7) M + 10^k (n_k - m_k) \equiv 0 \pmod{7} , we get:
dM+NM0(mod7)    2M+NMM+N(mod7)(since d2(mod7)). dM + N - M \equiv 0 \pmod{7} \implies 2M + N - M \equiv M + N \pmod{7} \quad \text{(since \( d \equiv 2 \pmod{7} \))}.
- This implies:
N+10k(mknk)M10k(nkmk)0(mod7), N + 10^k (m_k - n_k) \equiv -M - 10^k (n_k - m_k) \equiv 0 \pmod{7},
so N N is a friend of M M , as desired.

6. Conclusion:
The only values of d d for which the condition is valid are those such that d2(mod7) d \equiv 2 \pmod{7} .

The final answer is d2(mod7) \boxed{ d \equiv 2 \pmod{7} } .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.