Rozwiązanie problemu USAMO

Question

Poprosiłem o podpowiedź https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416Kiedyś próbowałem indukcji, ale myślałem, że to nie zadziała, więc zostawiłem ją, ale po zobaczeniu komentarza @lulu postanowiłem spróbować ponownie. Sprawdź, czy moje rozwiązanie jest poprawne.

[USAMO 2003] Udowodnij, że dla każdej dodatniej liczby całkowitej n istnieje liczba n-cyfrowa podzielna przez $5^n$ wszystkie cyfry są nieparzyste.

MOJE ROZWIĄZANIE: Po pierwsze, sprawdziłem kilka małych przypadków i doszedłem do wniosku, że możemy wygenerować liczbę z (n + 1) cyfr spełniającą właściwość, dodając liczbę na jej początku, tj. dodanie b 10$^n$ do numeru zawierającego n cyfr.

Będziemy kontynuować indukcję, niech P (n) oznacza, że ​​istnieje n-cyfrowa liczba podzielna przez $5^n$ wszystkie cyfry są nieparzyste.

P (1) jest prawdziwe jako 5 | 5.

Niech P (k) będzie prawdziwe, tj. niech 5$^k$ | $a_ka_{k-1}...a_1$ z $a_i$ $\neq$ 2l dla i $\in$ {1,2 ... k}.

Spróbuję to udowodnić, dodając $ b \cdot 10^k $ z $ b \in {1,3,5,7,9} $. możemy mieć liczbę, która jest podzielna przez$5^{k+1}$.

Więc chcemy 5$^{k+1}$ $|$ $ b \cdot 10^k $ + $a_ka_{k-1}...a_1$. -> równ. 1

Pozwolić $a_ka_{k-1}...a_1$ = $5^km $

Więc z równ. 1, wprowadzanie$a_ka_{k-1}...a_1$ = $5^km $ , dostaniemy

5$^{k+1}$ $|$ $ b \cdot 10^k $ + $5^k$m, a następnie dzieląc przez $5^k$ , potrzebujemy

5 $|$ $2^k \cdot b + m$

tak jak $ b \in {1,3,5,7,9} $ , $\equiv$ 0,1,2,3,4 (mod 5)

Więc teraz m $\equiv$ 0,1,2,3,4 (mod 5), niech m $\equiv$ r (mod 5),

Potrzebujemy $2^k \cdot b + r =0 (mod 5)$

teraz,$2^k \equiv$ 1,2,3,4 (mod 5)

tak skrupulatnie przechodząc przez każdy przypadek możliwych wartości $2^k$ im (mod 5) (jest 16 przypadków), udowadniamy, że możemy znaleźć plik $ b \in {1,3,5,7,9} $ takie, że 5 $|$ $2^k \cdot b + m$ .

To pierwszy raz, kiedy tak dużo napisałem w lateksie, więc przepraszam, jeśli jest jakiś błąd.

Gdybyś był oceniającym, na 7 punktów, ile dałbyś mi?

Answer 1

Nie sądzę, by w odpowiedziach w matm.se można było określić, jak by to oznaczyli, ale mogę doradzić bardziej przejrzysty sposób pisania odpowiedzi, ponieważ Twoje pomysły są słuszne, ale można je zastosować z przejrzystością algebraiczną i jasnością w zakresie arytmetyki modulo. (Jeśli okaże się, że twierdzisz, że jeśli coś zrobimy, w końcu osiągniemy określony wynik, spróbuj sformułować to jako twierdzenie o istnieniu, które jest albo oczywiste, dobrze znane, albo sprawdzone w twojej pracy).

Domagamy się jakiejś kolejności $a_n$ z $n$-cyfrowe liczby w bazie $10$, wszystkie cyfry są nieparzyste, spełnia $5^n|a_n,\,10^n|a_{n+1}-a_n$. W szczególności napisz$a_n=5^nb_n,\,a_{n+1}=a_n+10^nc_n$, więc $b_1=1$ (dlatego $a_1=5$) i$$5^{n+1}b_{n+1}=a_{n+1}=c_n10^n+5^nb_n\iff5b_{n+1}=c_n2^n+b_n,$$więc wystarczy wybrać $c_n\in\{1,\,3,\,5,\,7,\,9\}$ z $5|c_n2^n+b_n$. Ten wybór jest możliwy, ponieważ te$5$ wybory $c_n$ każdy osiąga inną klasę reszt modulo $5$ (dlatego $5\nmid k2^n$ dla $k\in\{2,\,4,\,6,\,8\}$) i dokładnie jeden z nich $5|c_n2^n+b_n$.

Answer 2

Tam jest $\,x\in\Bbb Z\,$ z $\,5\mid 2^k x - m\!\iff\! \bmod 5\!:\ 2^k x \equiv m\,$ ma korzeń $\,x.\,$ Przez 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$$

i możemy wybrać korzeń $\,x\in \{1, 3, 5, 7, 9\}\,$ ponieważ jest to https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems $\!\bmod 5;\,$ alternatywnie: $ $ Jeśli $\,0\le x < 5\,$ jest nawet wtedy $\,x':= x\!+\!5\,$ to jest dziwne $< 10,\,$ i $\,x'$ pozostaje rootem wg $\,x'\equiv x\pmod{\!5}$.