USAMO問題解決

Question

ここでヒントを求めていました https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416一度誘導を試したのですが、うまくいかないと思ってそのままにしましたが、@ luluのコメントを見て、またやってみることにしました。私の解決策が正しいかどうかを確認してください。

[USAMO 2003]すべての正の整数nに対して、で割り切れるn桁の数が存在することを証明します。 $5^n$ その数字はすべて奇数です。

私の解決策：最初に、いくつかの小さなケースをチェックし、その前に数字を追加することで、プロパティを満たす（n + 1）桁の数字を生成できると考えました。追加10 bを$^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$。-> eq.1

しましょう $a_ka_{k-1}...a_1$ = $5^km $

だから式から。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（mod 5）

だから今m $\equiv$ 0、1、2、3、4（mod 5）、m $\equiv$ r（mod 5）、

必要です $2^k \cdot b + r =0 (mod 5)$

今、$2^k \equiv$ 1,2,3,4（mod 5）

の可能な値のすべてのケースを丹念に調べます $2^k$ およびm（mod 5）（16のケースがあります）、私たちは見つけることができることを証明します $ b \in {1,3,5,7,9} $ そのような5 $|$ $2^k \cdot b + m$ 。

ラテックスでたくさん書いたのは初めてなので、間違いがあったらごめんなさい。

あなたが7年生のうち、あなたが私にいくつのポイントを与えますか？

Answer 1

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\}$）、そしてちょうど1つが達成します $5|c_n2^n+b_n$。

Answer 2

あります $\,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}$。