Bonjour,
Entrant en prépa MPSI l'année prochaine, j'ai décidé de m'entrainer en maths pour la rentrée. Je suis alors tombé sur un exercice assez délicat venant du poly LLG. Voici l'énoncé:
"Soit S = {2^k*3^l ; (k,l) ∈ N^2}.
Montrer que tout élément de N* peut s’écrire s(1)+···+s(m) où m ∈ N*, où les s(i) sont dans S et où, pour tout couple (i,j) d’éléments distincts de {1,...,m}, s(i) ne divise pas s(j)."
Quelques pistes?
Merci d'avance
Il me semble avoir réussi à le prouver pour tout nombre pair mais je bloque pour les impairs. Je ne pense pas être sur la bonne piste. Voici ce que j'ai fait:
On raisonne par récurrence forte en supposant que P(i) avec i dans {1,2,...,n} est vraie.
Si n+1 est pair, alors n+1=2k, avec k dans N et k<n+1.
Or, par hypothèse de récurrence, k=s(1)+s(2)+...+s(m)
Donc, n+1=2s(1)+2s(2)+...+2s(m)
On peut montrer que pour tout (i,j) distincts dans N^2, 2s(i) ne divise pas 2s(j), sachant que s(i) ne divise pas s(j).
Ainsi, P(n+1) est vraie si n+1 est pair.
Le problème est que si n+1 est impair on ne peut pas faire le même raisonnement. En effet, n+1=2k+1, or il me semble que 1 divise tout nombre entier.
Reprenons ta récurrence forte et supposons l'hypothèse vraie pour 1, ..., n-1. On veut la montrer pour n.
Je te conseille pour cela de considérer m le plus grand entier tel que 2^m est plus petit que n et d'essayer de montrer que, si n - 2^m est divisible par 3, la propriété est vraie pour n.
Sinon... ça coince. Mais si n - 2^m n'est pas divisible par 3, tu peux montrer que n - 2^(m-1), lui, l'est... et ensuite...
Je ne sais pas si la preuve que je te suggère est la plus simple mais j'ai vérifié et a priori, elle marche !
