Solution aux problèmes USAMO

Question

J'avais demandé un indice ici https://math.stackexchange.com/questions/3918416/usamo-problem-hint?noredirect=1#comment8081183_3918416J'avais essayé l'induction une fois mais je pensais que cela ne fonctionnait pas alors je l'ai laissé, mais après avoir vu le commentaire de @lulu, j'ai décidé de recommencer. Veuillez voir si ma solution est correcte.

[USAMO 2003] Montrer que pour tout entier positif n il existe un nombre à n chiffres divisible par $5^n$ dont tous les chiffres sont impairs.

MA SOLUTION: Donc, tout d'abord, j'ai vérifié quelques petits cas et j'ai pensé que nous pourrions générer le nombre avec (n + 1) chiffres satisfaisant la propriété en ajoutant un nombre à l'avant, c'est-à-dire. ajout de b 10$^n$ au nombre à n chiffres.

Nous allons procéder par récurrence, soit P (n) signifie qu'il existe un nombre à n chiffres divisible par $5^n$ dont tous les chiffres sont impairs.

P (1) est vrai comme 5 | 5.

Soit P (k) vrai, ie. laisser 5$^k$ | $a_ka_{k-1}...a_1$ avec $a_i$ $\neq$ 2l pour i $\in$ {1,2 ... k}.

Je vais essayer de le prouver en ajoutant $ b \cdot 10^k $ avec $ b \in {1,3,5,7,9} $. on peut avoir un nombre divisible par$5^{k+1}$.

Alors on veut 5$^{k+1}$ $|$ $ b \cdot 10^k $ + $a_ka_{k-1}...a_1$. -> éq.1

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

Donc à partir de l'eq. 1, entrée$a_ka_{k-1}...a_1$ = $5^km $ , nous allons obtenir

5$^{k+1}$ $|$ $ b \cdot 10^k $ + $5^k$m, puis en divisant par $5^k$ , nous avons besoin

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

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

Alors maintenant m $\equiv$ 0,1,2,3,4 (mod 5), soit m $\equiv$ r (mod 5),

Nous avons besoin $2^k \cdot b + r =0 (mod 5)$

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

si minutieusement en passant par chaque cas de valeurs possibles de $2^k$ et m (mod 5) (il y a 16 cas), nous prouvons que nous pouvons trouver un $ b \in {1,3,5,7,9} $ tel que 5 $|$ $2^k \cdot b + m$ .

C'est la première fois que j'écris autant en latex, donc je suis désolé s'il y a une erreur.

Si vous étiez évaluateur, sur 7, combien de points me donneriez-vous?

Answer 1

Je ne pense pas que les réponses math.se puissent expliquer comment elles le marqueraient, mais je peux vous conseiller sur une manière plus propre d'écrire des réponses, car vos idées sont justes, mais elles pourraient le faire avec une clarté algébrique et une clarté concernant l'arithmétique modulo. (Si vous vous retrouvez à prétendre que si nous faisons quelque chose, nous obtenons finalement un résultat particulier, essayez de l'énoncer comme un théorème d'existence qui est soit évident, bien connu ou prouvé dans votre travail.) À savoir:

Nous revendiquons une séquence $a_n$ de $n$-numéros en base $10$, tous les chiffres sont impairs, satisfait $5^n|a_n,\,10^n|a_{n+1}-a_n$. En particulier écrire$a_n=5^nb_n,\,a_{n+1}=a_n+10^nc_n$, donc $b_1=1$ (car $a_1=5$) et$$5^{n+1}b_{n+1}=a_{n+1}=c_n10^n+5^nb_n\iff5b_{n+1}=c_n2^n+b_n,$$il suffit donc de choisir $c_n\in\{1,\,3,\,5,\,7,\,9\}$ avec $5|c_n2^n+b_n$. Ce choix est possible car ces$5$ choix du $c_n$ chacun atteint une classe de résidus différente modulo $5$ (car $5\nmid k2^n$ pour $k\in\{2,\,4,\,6,\,8\}$), et exactement on obtient $5|c_n2^n+b_n$.

Answer 2

Il y a un $\,x\in\Bbb Z\,$ avec $\,5\mid 2^k x - m\!\iff\! \bmod 5\!:\ 2^k x \equiv m\,$ a une racine $\,x.\,$ Par 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$$

et nous pouvons choisir une racine $\,x\in \{1, 3, 5, 7, 9\}\,$ puisque c'est un https://en.wikipedia.org/wiki/Modular_arithmetic#Residue_systems $\!\bmod 5;\,$ alternativement: $ $ si $\,0\le x < 5\,$ est même alors $\,x':= x\!+\!5\,$ est impair $< 10,\,$ et $\,x'$ reste une racine par $\,x'\equiv x\pmod{\!5}$.