Track / Stage 5 / 362 of 400 #962 of 1964

Problem 962

AIME late

Number theory Difficulty 5.8 Prove it

Let $k$ be a positive integer. Prove that there is a positive integer $N$ with the following properties:

(a) $N$ has $k$ digits, none of which is 0 .

(b) No matter how the digits of $N$ are rearranged, the resulting number is not divisible by 13 .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $N_{1}$ be the number consisting of $k$ ones. If $N_{1}$ is not divisible by 13 , it is the number $N$ we seek, since no matter how its digits are rearranged, it is still the same number.

If $N_{1}$ is divisible by 13 , consider $N_{1}+1$ , that is to say the number consisting of $k-1$ ones and one 2 . When the digits of this number are rearranged, the result has the form

$11 \cdots 121 \cdots 11=11 \cdots 111 \cdots 11+10 \cdots 00=N_{1}+10^{k}$

where $k \geq 0$ is an integer. This is not divisible by 13 since $N_{1}$ is divisible by 13 and $10^{k}$ is not.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.