IMO 1962 Problem 1

Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 7m17s

Problem

Find the smallest natural number $n$ with the following properties:

(a) Its decimal representation ends in 6.

(b) If the final digit 6 is moved to the front, the resulting number is four times as large.

Exploration

Let $n$ be a natural number ending in 6 such that moving the 6 to the front produces a number four times as large. Denote the number of digits of $n$ by $k$, and let the number obtained by removing the last digit 6 be $m$, so $n = 10m + 6$. Moving the 6 to the front yields a number $6 \cdot 10^{k-1} + m$. The condition becomes

$6 \cdot 10^{k-1} + m = 4(10 m + 6) = 40 m + 24.$

This reduces to $6 \cdot 10^{k-1} - 24 = 39 m$, giving $m = \frac{6 \cdot 10^{k-1} - 24}{39} = \frac{2 \cdot 10^{k-1} - 8}{13}$. The task becomes finding the smallest integer $k$ such that $2 \cdot 10^{k-1} - 8$ is divisible by 13.

Checking modulo 13, $2 \cdot 10^{k-1} - 8 \equiv 0 \pmod{13}$, so $2 \cdot 10^{k-1} \equiv 8 \pmod{13}$, or $10^{k-1} \equiv 4 \pmod{13}$. The powers of 10 modulo 13 repeat with period 6: $10^1 \equiv 10$, $10^2 \equiv 9$, $10^3 \equiv 12$, $10^4 \equiv 3$, $10^5 \equiv 4$, $10^6 \equiv 1 \pmod{13}$. Hence $k-1 = 5$, so $k = 6$, giving $m = \frac{2 \cdot 10^5 - 8}{13} = \frac{199992}{13} = 15384$, and $n = 10 m + 6 = 153846$.

This matches the smallest solution and seems consistent with the divisibility condition.

Problem Understanding

The problem asks for the smallest natural number ending in 6 such that relocating the final 6 to the front multiplies the number by 4. This is a Type C problem because it requests the minimal element satisfying a given algebraic condition. The objects involved are integers, decimal representations, and digit manipulations. The core difficulty is translating the digit-shifting condition into an explicit equation in terms of the number of digits and solving a divisibility problem, ensuring integrality and minimality simultaneously.

Intuitively, the solution involves solving a modular congruence derived from the decimal representation and ensuring that the resulting number has the smallest number of digits. The minimal number is expected to have 6 digits, as smaller numbers fail the modular constraint.

Proof Architecture

Lemma 1: For a natural number $n$ ending in 6 with $k$ digits, moving the 6 to the front gives $6 \cdot 10^{k-1} + m$, where $m = \frac{n-6}{10}$. Proof: Direct manipulation of decimal expansions.

Lemma 2: The condition $6 \cdot 10^{k-1} + m = 4n$ reduces to $13 m = 2 \cdot 10^{k-1} - 8$. Proof: Algebraic simplification.

Lemma 3: $2 \cdot 10^{k-1} - 8$ is divisible by 13 if and only if $10^{k-1} \equiv 4 \pmod{13}$. Proof: Reduce modulo 13 and solve the linear congruence.

Lemma 4: The smallest positive integer $k$ satisfying $10^{k-1} \equiv 4 \pmod{13}$ is $k = 6$. Proof: Examine powers of 10 modulo 13.

Lemma 5: With $k = 6$, the corresponding $m$ is $15384$, giving $n = 153846$. Proof: Plug $k$ into the formula for $m$ and verify integrality.

The hardest step is Lemma 4 because it relies on computing and identifying the correct power modulo 13. The most likely to fail under scrutiny is the integrality check in Lemma 5.

Solution

Lemma 1: Let $n$ be a $k$-digit natural number ending in 6. Denote by $m$ the integer formed by removing the final digit, so $n = 10 m + 6$. Moving the 6 to the front produces the number $6 \cdot 10^{k-1} + m$ because multiplying the leading digit by $10^{k-1}$ accounts for its new position. ∎

Lemma 2: The condition that moving the 6 to the front yields four times the original number becomes $6 \cdot 10^{k-1} + m = 4(10 m + 6)$. Expanding the right-hand side gives $6 \cdot 10^{k-1} + m = 40 m + 24$. Subtract $m$ from both sides to obtain $6 \cdot 10^{k-1} = 39 m + 24$. Subtract 24 to obtain $6 \cdot 10^{k-1} - 24 = 39 m$. Factor 3: $3(2 \cdot 10^{k-1} - 8) = 3 \cdot 13 m$, hence $2 \cdot 10^{k-1} - 8 = 13 m$. ∎

Lemma 3: The integrality condition $m = \frac{2 \cdot 10^{k-1} - 8}{13}$ requires $2 \cdot 10^{k-1} - 8 \equiv 0 \pmod{13}$. Adding 8 and dividing by 2 modulo 13, we obtain $10^{k-1} \equiv 4 \pmod{13}$. ∎

Lemma 4: Compute powers of 10 modulo 13:

$10^1 \equiv 10, \quad 10^2 \equiv 9, \quad 10^3 \equiv 12, \quad 10^4 \equiv 3, \quad 10^5 \equiv 4, \quad 10^6 \equiv 1 \pmod{13}.$

The smallest exponent $k-1$ satisfying $10^{k-1} \equiv 4 \pmod{13}$ is $k-1 = 5$, hence $k = 6$. ∎

Lemma 5: With $k = 6$, we compute

$m = \frac{2 \cdot 10^5 - 8}{13} = \frac{200000 - 8}{13} = \frac{199992}{13}.$

Perform the division: $13 \cdot 15384 = 13 \cdot (15000 + 384) = 195000 + 4992 = 199992$, confirming integrality. Then $n = 10 m + 6 = 153840 + 6 = 153846$. Verify the condition: moving 6 to the front gives $6 \cdot 10^5 + 15384 = 600000 + 15384 = 615384$, which equals $4 n = 4 \cdot 153846 = 615384$. The condition holds. ∎

Hence the smallest natural number $n$ satisfying the given properties is

$\boxed{153846}.$

Verification of Key Steps

Lemma 4: Recompute powers modulo 13 independently. $10^1 \equiv 10$, $10^2 \equiv 9$, $10^3 \equiv 12$, $10^4 \equiv 3$, $10^5 \equiv 4$, $10^6 \equiv 1$. Correct. Exponent $k-1 = 5$ minimal.

Lemma 5: Independently check $m = (2 \cdot 10^5 - 8)/13 = (200000 - 8)/13 = 199992/13 = 15384$. Multiply $10 m + 6 = 153846$ and verify $4 n = 615384$ matches $6 \cdot 10^5 + m = 615384$. Confirmed. These steps cannot silently fail as each involves exact integer arithmetic.

Alternative Approaches

One alternative is to attempt a trial-and-error search among numbers ending with 6 and check the four-times property sequentially starting from the smallest possible numbers. This is inefficient due to exponential growth in digits and the rarity of satisfying numbers. Another approach is to use repeating decimal representations: set $n = 6 \cdot \frac{10^k - 1}{9}$ times some factor and solve a Diophantine equation, which eventually reduces to the same modular congruence. The modular approach is preferable because it directly encodes the digit manipulation into a linear congruence and allows precise determination of minimality.