USAMO problem çözümü

Question

Burada bir ipucu istemiştim https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416indüksiyonu bir kez denedim ama işe yaramayacağını düşündüm, bu yüzden bıraktım ama @lulu'nun yorumunu gördükten sonra tekrar denemeye karar verdim. Lütfen çözümümün doğru olup olmadığına bakın.

[USAMO 2003] Her n pozitif tamsayı için şuna bölünebilen n basamaklı bir sayı olduğunu kanıtlayın $5^n$ tüm rakamları tuhaf.

ÇÖZÜMÜM: İlk olarak, bazı küçük durumları kontrol ettim ve mülkün önüne bir sayı ekleyerek (n + 1) basamaklı bir sayı üretebileceğimizi düşündüm. ekleyerek b 10$^n$ n basamaklı sayıya.

Tümevarımla devam edeceğiz, P (n) ile bölünebilen n basamaklı bir sayı var demek olsun. $5^n$ tüm rakamları tuhaf.

P (1) 5 | 5 olarak doğrudur.

P (k) doğru olsun, yani. let 5$^k$ | $a_ka_{k-1}...a_1$ ile $a_i$ $\neq$ Ben için 2l $\in$ {1,2 ... k}.

Bunu ekleyerek kanıtlamaya çalışacağım $ b \cdot 10^k $ ile $ b \in {1,3,5,7,9} $. ile bölünebilen bir sayıya sahip olabiliriz$5^{k+1}$.

Yani 5 istiyoruz$^{k+1}$ $|$ $ b \cdot 10^k $ + $a_ka_{k-1}...a_1$. -> eq.1

İzin Vermek $a_ka_{k-1}...a_1$ = $5^km $

Yani eq. 1, giriş$a_ka_{k-1}...a_1$ = $5^km $ , alacağız

5$^{k+1}$ $|$ $ b \cdot 10^k $ + $5^k$m, sonra bölünerek $5^k$ , ihtiyacımız var

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

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

Öyleyse şimdi m $\equiv$ 0,1,2,3,4 (mod 5), let m $\equiv$ r (mod 5),

İhtiyacımız var $2^k \cdot b + r =0 (mod 5)$

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

Olası değerlerin her bir vakasını titizlikle incelemek $2^k$ ve m (mod 5) (16 vaka var), bulabileceğimizi kanıtlıyoruz $ b \in {1,3,5,7,9} $ öyle ki 5 $|$ $2^k \cdot b + m$ .

Lateksle ilk kez bu kadar çok yazıyorum, bu yüzden herhangi bir hata varsa özür dilerim.

Bir sınıf öğrencisi olsaydın, 7 üzerinden kaç puan verirdin?

Answer 1

Math.se cevaplarının onu nasıl işaretleyeceklerini ele alacağını sanmıyorum, ancak cevapları yazmanın daha net bir yolunu önerebilirim, çünkü fikirleriniz doğru ama cebirsel netlik ve modülo aritmetiğe ilişkin netlik ile yapabilirler. (Eğer bir şey yaparsak, sonunda belirli bir sonuç elde edeceğimizi iddia ederken kendinizi bulursanız, bunu apaçık, iyi bilinen veya çalışmanızda kanıtlanmış bir varoluş teoremi olarak ifade etmeye çalışın.)

Bir dizi talep ediyoruz $a_n$ nın-nin $n$Tabandaki basamaklı sayılar $10$, tüm rakamlar tuhaf, tatmin edici $5^n|a_n,\,10^n|a_{n+1}-a_n$. Özellikle yaz$a_n=5^nb_n,\,a_{n+1}=a_n+10^nc_n$, yani $b_1=1$ (Çünkü $a_1=5$) ve$$5^{n+1}b_{n+1}=a_{n+1}=c_n10^n+5^nb_n\iff5b_{n+1}=c_n2^n+b_n,$$bu yüzden seçmek yeterli $c_n\in\{1,\,3,\,5,\,7,\,9\}$ ile $5|c_n2^n+b_n$. Bu seçim mümkündür çünkü bunlar$5$ seçimleri $c_n$ her biri farklı bir kalıntı sınıfı modulo elde eder $5$ (Çünkü $5\nmid k2^n$ için $k\in\{2,\,4,\,6,\,8\}$) ve tam olarak biri $5|c_n2^n+b_n$.

Answer 2

Var $\,x\in\Bbb Z\,$ ile $\,5\mid 2^k x - m\!\iff\! \bmod 5\!:\ 2^k x \equiv m\,$ kökü var $\,x.\,$ Tarafından 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$$

ve bir kök seçebiliriz $\,x\in \{1, 3, 5, 7, 9\}\,$ olduğundan beri https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems $\!\bmod 5;\,$ alternatif olarak: $ $ Eğer $\,0\le x < 5\,$ o zaman bile $\,x':= x\!+\!5\,$ garip $< 10,\,$ ve $\,x'$ tarafından kök kalır $\,x'\equiv x\pmod{\!5}$.