USAMO 문제 해결
여기에 힌트를 요청했습니다 https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416한 번 귀납법을 시도했지만 작동하지 않을 것이라고 생각했기 때문에 떠났지만 @lulu의 의견을보고 다시 시도하기로 결정했습니다. 내 솔루션이 올바른지 확인하십시오.
[USAMO 2003] 모든 양의 정수 n에 대해 다음으로 나눌 수있는 n 자리 숫자가 있음을 증명하십시오. $5^n$ 모든 숫자가 홀수입니다.
내 솔루션 : 그래서 먼저 몇 가지 작은 경우를 확인하고 앞에 숫자를 추가하여 속성을 충족하는 (n + 1) 자리 숫자를 생성 할 수 있다고 생각했습니다. b 10 추가$^n$ n 자리 숫자로.
귀납법을 진행하겠습니다. P (n)은 다음으로 나눌 수있는 n 자리 숫자가 있음을 의미합니다. $5^n$ 모든 숫자가 홀수입니다.
P (1)은 5 | 5로 참입니다.
P (k)를 참이라고하자. 5하자$^k$ | $a_ka_{k-1}...a_1$ 와 $a_i$ $\neq$ 2l for i $\in$ {1,2 ... k}
나는 그것을 추가하여 증명하려고 시도 할 것입니다 $ b \cdot 10^k $ 와 $ b \in {1,3,5,7,9} $. 우리는 다음으로 나눌 수있는 숫자를 가질 수 있습니다.$5^{k+1}$.
그래서 우리는 5$^{k+1}$ $|$ $ b \cdot 10^k $ + $a_ka_{k-1}...a_1$. -> 식 1
허락하다 $a_ka_{k-1}...a_1$ = $5^km $
그래서 eq. 1, 입력$a_ka_{k-1}...a_1$ = $5^km $ , 우리는 얻을 것이다
5$^{k+1}$ $|$ $ b \cdot 10^k $ + $5^k$m, 다음으로 나누기 $5^k$ , 우리는
5 $|$ $2^k \cdot b + m$
같이 $ b \in {1,3,5,7,9} $ , $\equiv$ 0,1,2,3,4 (모드 5)
이제 m $\equiv$ 0,1,2,3,4 (mod 5), let m $\equiv$ r (모드 5),
우리는 필요합니다 $2^k \cdot b + r =0 (mod 5)$
지금,$2^k \equiv$ 1,2,3,4 (모드 5)
가능한 값의 모든 경우를 힘들게 살펴 봅니다. $2^k$ m (mod 5) (16 개의 경우가 있습니다), 우리는 $ b \in {1,3,5,7,9} $ 그런 5 $|$ $2^k \cdot b + m$ .
라텍스로 이렇게 많이 쓴 것은 이번이 처음이라 실수가 있으면 죄송합니다.
그레이 더라면 7 점 만점에 몇 점을 주겠습니까?
답변
나는 math.se 답변이 어떻게 표시되는지를 다룰 수 있다고 생각하지 않지만, 당신의 아이디어는 옳지 만 대 수학적 명확성과 모듈로 산술에 대한 명확성을 가지고 할 수 있기 때문에 답을 작성하는 더 깨끗한 방법에 대해 조언 할 수 있습니다. (우리가 무언가를하면 결국 특정 결과를 얻게된다고 주장하는 자신을 발견한다면, 이것을 당신의 작업 내에서 명백하고 잘 알려져 있거나 입증 된 존재 정리로 말하십시오.) 재치 :
우리는 어떤 순서를 주장합니다 $a_n$ 의 $n$-베이스의 숫자 $10$, 모든 자릿수 홀수, 만족 $5^n|a_n,\,10^n|a_{n+1}-a_n$. 특히 쓰기$a_n=5^nb_n,\,a_{n+1}=a_n+10^nc_n$, 그래서 $b_1=1$ (때문에 $a_1=5$) 및$$5^{n+1}b_{n+1}=a_{n+1}=c_n10^n+5^nb_n\iff5b_{n+1}=c_n2^n+b_n,$$그래서 선택하는 것으로 충분합니다 $c_n\in\{1,\,3,\,5,\,7,\,9\}$ 와 $5|c_n2^n+b_n$. 이 선택이 가능합니다.$5$ 의 선택 $c_n$ 각각 다른 잔기 클래스 모듈로 달성 $5$ (때문에 $5\nmid k2^n$ ...에 대한 $k\in\{2,\,4,\,6,\,8\}$), 정확히 하나는 $5|c_n2^n+b_n$.
이있다 $\,x\in\Bbb Z\,$ 와 $\,5\mid 2^k x - m\!\iff\! \bmod 5\!:\ 2^k x \equiv m\,$ 뿌리가있다 $\,x.\,$ 으로 https://math.stackexchange.com/a/3290965/242
$$\begin{align} \color{#c00}c\ x &\equiv \, d\!\!\pmod{\!\color{#0a0}n}\ \ \text{has a root}\ x\!\iff\! \gcd(\color{#c00}c,\,\color{#0a0}n)\mid d\\[.3em] {\rm thus}\ \ \color{#c00}{2^k} x&\equiv m\!\!\!\pmod{\!\color{#0a0}5}\ \ \text{has a root}\ x,\ \, {\rm by}\ \ \gcd(\color{#c00}{2^k},\color{#0a0}5)\!=\!1\end{align}\qquad$$
그리고 우리는 뿌리를 선택할 수 있습니다 $\,x\in \{1, 3, 5, 7, 9\}\,$ 그것은이기 때문에 https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems $\!\bmod 5;\,$ 또는 : $ $ 만약 $\,0\le x < 5\,$ 그때도 $\,x':= x\!+\!5\,$ 이상하다 $< 10,\,$ 과 $\,x'$ 뿌리로 남아있다 $\,x'\equiv x\pmod{\!5}$.