Maths Olympiad Prep

Library / /411 of 520

Number theory Difficulty 5.7 AIME, harder Prove it

9. (14 points) Given tN+,t0,1(mod9)t \in \mathbf{N}_{+}, t \neq 0,1(\bmod 9). Arrange all tt-digit numbers from 1111\underbrace{11 \cdots 1}_{1 \uparrow} to 999t\underbrace{99 \cdots 9}_{t} in any order into a single number, denoted as AA. Prove that AA is not a perfect square.

Solution

9. It is known that the number of tt-digit numbers is
m=8889(t1) (numbers).  m=\underbrace{88 \cdots 89}_{(t-1) \uparrow} \text { (numbers). }

Let the mm tt-digit numbers in AA be ama_{m}, am1,,a1a_{m-1}, \cdots, a_{1}, i.e.,
A=i=1mai×10t(i1). A=\sum_{i=1}^{m} a_{i} \times 10^{t(i-1)} .

Thus, Ai=1mai(mod9)A \equiv \sum_{i=1}^{m} a_{i}(\bmod 9).
Let tr(mod9)(2r8)t \equiv r(\bmod 9)(2 \leqslant r \leqslant 8). Then
m=8889(t1)8(t1)+9m=\underbrace{88 \cdots 89}_{(t-1) \uparrow} \equiv 8(t-1)+9
10r(mod9)\equiv 10-r(\bmod 9).
Since i=kk+8i=9(2k+8)20(mod9)\sum_{i=k}^{k+8} i=\frac{9(2 k+8)}{2} \equiv 0(\bmod 9), we have
Ai=091(999ii)i=091(9i)=j=r9jA \equiv \sum_{i=0}^{9-1}(\underset{i \uparrow}{99 \cdots 9}-i) \equiv \sum_{i=0}^{9-1}(9-i)=\sum_{j=r}^{9} j
=(10r)(9+r)2=r(1r)2(mod9)=\frac{(10-r)(9+r)}{2}=\frac{r(1-r)}{2}(\bmod 9).
When r=2,5,8r=2,5,8, A1(mod9)A \equiv-1(\bmod 9);
When r=3,7r=3,7, A3(mod9)A \equiv-3(\bmod 9);
When r=4,6r=4,6, A3(mod9)A \equiv 3(\bmod 9).
If A3A \equiv 3 or 3(mod9)-3(\bmod 9), then AA is a multiple of 3, but not a multiple of 9; if A1(mod9)A \equiv-1(\bmod 9), then A1(mod3)A \equiv-1(\bmod 3), but n20n^{2} \equiv 0 or 1(mod3)1(\bmod 3).
Thus, AA is not a perfect square.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.