USAMO Problemlösung
Ich hatte hier um einen Hinweis gebeten https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416Ich hatte es einmal mit Induktion versucht, aber ich dachte, es würde nicht funktionieren, also habe ich es verlassen, aber nachdem ich @lulus Kommentar gesehen hatte, beschloss ich, es noch einmal zu versuchen. Bitte überprüfen Sie, ob meine Lösung korrekt ist.
[USAMO 2003] Man beweise, dass es für jede positive ganze Zahl n eine durch diese teilbare n-stellige Zahl gibt $5^n$ Alle Ziffern sind ungerade.
MEINE LÖSUNG: Als erstes habe ich einige kleine Fälle überprüft und festgestellt, dass wir die Zahl mit (n + 1) Ziffern generieren können, die die Eigenschaft erfüllen, indem wir eine Zahl an die Vorderseite hinzufügen, d. H. Hinzufügen von b 10$^n$ auf die Zahl mit n Ziffern.
Wir werden mit der Induktion fortfahren. P (n) bedeutet, dass es eine durch diese teilbare n-stellige Zahl gibt $5^n$ Alle Ziffern sind ungerade.
P (1) ist wahr als 5 | 5.
Sei P (k) wahr, dh. lass 5$^k$ | $a_ka_{k-1}...a_1$ mit $a_i$ $\neq$ 2l für i $\in$ {1,2 ... k}.
Ich werde versuchen, dies durch Hinzufügen zu beweisen $ b \cdot 10^k $ mit $ b \in {1,3,5,7,9} $. wir können eine Zahl haben, die durch teilbar ist$5^{k+1}$.
Also wollen wir 5$^{k+1}$ $|$ $ b \cdot 10^k $ + $a_ka_{k-1}...a_1$. -> Gl.1
Lassen $a_ka_{k-1}...a_1$ = $5^km $
Also aus Gl. 1, Eingabe$a_ka_{k-1}...a_1$ = $5^km $ werden wir bekommen
5$^{k+1}$ $|$ $ b \cdot 10^k $ + $5^k$m, dann durch geteilt durch $5^k$ , wir brauchen
5 $|$ $2^k \cdot b + m$
wie $ b \in {1,3,5,7,9} $ , $\equiv$ 0,1,2,3,4 (mod 5)
Also jetzt m $\equiv$ 0,1,2,3,4 (mod 5), sei m $\equiv$ r (mod 5),
Wir brauchen $2^k \cdot b + r =0 (mod 5)$
jetzt,$2^k \equiv$ 1,2,3,4 (mod 5)
so akribisch durch jeden Fall möglicher Werte von $2^k$ und m (mod 5) (es gibt 16 Fälle) beweisen wir, dass wir a finden können $ b \in {1,3,5,7,9} $ so dass 5 $|$ $2^k \cdot b + m$ .
Dies ist das erste Mal, dass ich so viel in Latex geschrieben habe. Es tut mir leid, wenn es einen Fehler gibt.
Wenn Sie ein Grader von 7 wären, wie viele Punkte würden Sie mir geben?
Antworten
Ich glaube nicht, dass math.se-Antworten darauf eingehen können, wie sie es markieren würden, aber ich kann Ihnen einen saubereren Weg zum Schreiben von Antworten empfehlen, da Ihre Ideen richtig sind, sie aber algebraische Klarheit und Klarheit in Bezug auf Modulo-Arithmetik vertragen könnten. (Wenn Sie behaupten, dass wir, wenn wir etwas tun, irgendwann ein bestimmtes Ergebnis erzielen, versuchen Sie, dies als Existenzsatz zu bezeichnen, der entweder offensichtlich, bekannt oder in Ihrer Arbeit bewiesen ist.) Das heißt:
Wir behaupten eine Sequenz $a_n$ von $n$-stellige Zahlen in der Basis $10$, alle Ziffern ungerade, erfüllt $5^n|a_n,\,10^n|a_{n+1}-a_n$. Insbesondere schreiben$a_n=5^nb_n,\,a_{n+1}=a_n+10^nc_n$, damit $b_1=1$ (da $a_1=5$) und$$5^{n+1}b_{n+1}=a_{n+1}=c_n10^n+5^nb_n\iff5b_{n+1}=c_n2^n+b_n,$$es reicht also zu wählen $c_n\in\{1,\,3,\,5,\,7,\,9\}$ mit $5|c_n2^n+b_n$. Diese Wahl ist möglich, weil diese$5$ Auswahl der $c_n$ jedes erreicht eine andere Rückstandsklasse Modulo $5$ (da $5\nmid k2^n$ zum $k\in\{2,\,4,\,6,\,8\}$) und genau das erreicht man $5|c_n2^n+b_n$.
Da ist ein $\,x\in\Bbb Z\,$ mit $\,5\mid 2^k x - m\!\iff\! \bmod 5\!:\ 2^k x \equiv m\,$ hat eine Wurzel $\,x.\,$ Durch 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$$
und wir können eine Wurzel wählen $\,x\in \{1, 3, 5, 7, 9\}\,$ da ist es ein https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems $\!\bmod 5;\,$ Alternative: $ $ wenn $\,0\le x < 5\,$ ist auch dann noch $\,x':= x\!+\!5\,$ ist ungerade $< 10,\,$ und $\,x'$ bleibt eine Wurzel von $\,x'\equiv x\pmod{\!5}$.