วิธีแก้ปัญหา USAMO

Question

ฉันได้ขอคำใบ้ที่นี่ 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 สำหรับ 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 $

จาก 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)

ตอนนี้ม $\equiv$ 0,1,2,3,4 (สมัย 5) ให้ม $\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 คะแนนคุณจะให้ฉันกี่คะแนน?

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\}$) และหนึ่งเดียวที่ประสบความสำเร็จ $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}$.