USAMO समस्या समाधान
मैंने यहां इशारा करने के लिए कहा था https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416मैंने एक बार इंडक्शन की कोशिश की थी, लेकिन मुझे लगा कि यह काम नहीं करेगा इसलिए मैंने इसे छोड़ दिया, लेकिन @lulu की टिप्पणी देखने के बाद, मैंने इसे फिर से देने का फैसला किया। कृपया देखें कि मेरा समाधान सही है या नहीं।
[यूएसओएमओ २००३] साबित करें कि प्रत्येक सकारात्मक पूर्णांक के लिए n द्वारा एक n-अंकीय संख्या मौजूद है $5^n$ जिनके सभी अंक विषम हैं।
मेरा समाधान: तो पहली बात, मैंने कुछ छोटे मामलों की जाँच की और सोचा कि हम (n + 1) अंकों के साथ संख्या उत्पन्न कर सकते हैं, जो संपत्ति को एक संख्या में जोड़कर संतुष्ट करता है, यानी। बी 10 जोड़ना$^n$ एन अंकों के साथ संख्या के लिए।
हम इंडक्शन के साथ आगे बढ़ेंगे, P (n) का अर्थ है कि एक n-अंकीय संख्या विभाज्य है $5^n$ जिनके सभी अंक विषम हैं।
P (1) 5 के रूप में सत्य है। 5 |
P (k) सत्य है, अर्थात। चलो 5$^k$ | $a_ka_{k-1}...a_1$ साथ में $a_i$ $\neq$ आई के लिए 2 एल $\in$ {1,2 ... के}।
मैं जोड़कर साबित करने की कोशिश करूंगा $ 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$मी, तब से होकर विभाजित $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$ आर (मॉड 5),
ज़रुरत है $2^k \cdot b + r =0 (mod 5)$
अभी,$2^k \equiv$ 1,2,3,4 (मॉड 5)
इसलिए हर संभव मूल्यों के प्रत्येक मामले से गुजरने वाला श्रमसाध्य $2^k$ और एम (मॉड 5) (16 मामले हैं), हम साबित करते हैं कि हम एक खोज सकते हैं $ b \in {1,3,5,7,9} $ ऐसे कि ५ $|$ $2^k \cdot b + m$ ।
यह पहली बार है जब मैंने लेटेक्स में इतना कुछ लिखा है, इसलिए अगर कोई गलती हुई तो मुझे खेद है।
यदि आप 7 से बाहर एक ग्रेडर थे, तो आप मुझे कितने अंक देंगे?
जवाब
मुझे नहीं लगता कि math.se उत्तर पता कर सकते हैं कि वे इसे कैसे चिह्नित करेंगे, लेकिन मैं जवाब लिखने के लिए एक साफ तरीके से सलाह दे सकता हूं, क्योंकि आपके विचार सही हैं, लेकिन वे बीजीय स्पष्टता और मॉडुलो अंकगणित के बारे में स्पष्टता के साथ कर सकते हैं। (यदि आप खुद को यह दावा करते हुए पाते हैं कि यदि हम कुछ करते हैं तो हमें अंततः एक विशेष परिणाम मिलता है, इसे एक अस्तित्व प्रमेय के रूप में बताने का प्रयास करें जो आपके काम के भीतर या तो स्पष्ट, प्रसिद्ध या सिद्ध हो।)
हम कुछ अनुक्रम का दावा करते हैं $a_n$ का $n$आधार में -digit संख्या $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$ प्रत्येक एक अलग अवशेष वर्ग modulo प्राप्त करते हैं $5$ (चूंकि $5\nmid k2^n$ के लिये $k\in\{2,\,4,\,6,\,8\}$), और वास्तव में एक प्राप्त होता है $5|c_n2^n+b_n$।
वहां एक है $\,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}$।