Exercice 2 — La tombola — Olympiades 2016 Bordeaux

Sujet

Pour une tombola, on a vendu tous les billets numérotés \(1,2,3, \ldots, n\) où \(n\) est un entier supérieur ou égal à 2016.
On détermine les numéros des billets gagnants de la façon suivante : on écrit de gauche à droite la liste des entiers de 1 à \(n\) sur un tableau puis on passe en revue cette liste dans l'ordre croissant en effaçant les entiers qui sont les triples des nombres non effacés. On obtient donc la liste dont les premiers nombres sont :

\[ 1,2,4,5,7,8,9,10,11,13,14,16,17,18, \ldots \]

On décide que les numéros effacés sont les gagnants. Les autres sont perdants.

Justifier que le numéro 100 est perdant. En déduire que 300 est gagnant.

Le numéro 2016 est-il perdant ou gagnant?
2. Démontrer que si le numéro \(a\) est perdant alors le numéro \(9 a\) l'est également.

Le numéro 729 est-il gagnant ou perdant?
Parmi les numéros qui sont des puissances de 3 , lesquels sont perdants?
3. On admet que l'algorithme suivant permet de répondre à la question «le nombre saisi correspond-il à un numéro gagnant?»

Saisir un entier n
Tant que N est divisible par 9
    Remplacer N par N/9
Fin de boucle Tant que
Si N est divisible par 3
    Afficher « Le numéro N est gagnant > 
Sinon
    Afficher « Le numéro N est perdant »

a) Faire fonctionner cet algorithme pour \(N=100, N=300, N=2016\).
b) Soit \(a\) un entier supérieur ou égal à 1 et \(b\) un nombre non divisible par 3 .

Qu'affiche l'algorithme lorsque l'on saisit le nombre \(N=3 b\) ?
On pourra distinguer deux cas selon la parité de a.
4. Démontrer qu'un numéro qui peut s'écrire comme produit de deux numéros perdants est perdant.
5. Dans cette question, on suppose que \(n=2016\).

Quel est le pourcentage de numéros gagnants ?
6. En réalité, on a dénombré 2016 numéros perdants.

Quelle est la plus petite valeur possible du nombre \(n\) de billets vendus?

100 est perdant car il n'est pas divisible par 3 et n'a donc pas été effacé.

300 est gagnant car il a été effacé puisque c'est le triple de 100 qui n'a pas été effacé.
\(2016=3 \times 672\) et \(672=3 \times 224\). Comme 224 n'est pas un multiple de 3 , il n'a pas été effacé, donc 672 a été effacé et 2016 n'a pas été effacé. 2016 est donc perdant.
2. Si \(a\) est perdant, \(a \mathrm{n}\) ?a pas été effacé donc \(3 a\) est effacé et \(9 a\) ne l'est pas donc \(9 a\) est perdant. \(729=9 \times 81\) et \(81=9 \times 9\). Comme 9 est perdant, 81 est perdant et 729 est perdant.
Plus généralement, les puissances de 3 qui correspondent à des numéros perdants sont les puissances de 9 , c'est-à-dire de la forme \(3^{a}\) : avec \(a\) pair.
3. a) Pour \(N=100\), pas d'entrée dans la boucle et \(N\) n'est pas divisible par 3 donc l'algorithme affiche «Le numéro \(N\) est perdant».
Pour \(N=300\), pas d'entrée dans la boucle et \(N\) est divisible par 3 donc l'algorithme affiche « Le numéro \(N\) est gagnant \(\gg\).
Pour \(N=2016\), en sortie de boucle \(N\) est égal à 224 et \(N\) n'est pas divisible par 3 donc l'algorithme affiche «Le numéro \(N\) est perdant».
b) Si \(a\) est pair, en sortie de boucle \(N\) est égal à \(b\) qui n'est pas divisible par 3 donc l'algorithme affiche «Le numéro \(N\) est perdant».
Si \(a\) est impair, en sortie de boucle \(N\) est égal à \(3 b\) qui est divisible par 3 donc l'algorithme affiche «Le numéro \(N\) est gagnant».
4. D'après 3 , les numéros perdants sont les nombres de la forme \(3 b\) où \(a\) est un entier naturel pair et \(b\) un entier naturel non divisible par 3.
Soient \(3^{a} b\) et \(3^{a^{\prime}} b^{\prime}\) deux numéros perdants c'est-à-dire tels que \(a\) et \(a^{\prime}\) sont des entiers naturels pairs et \(b\) et \(b^{\prime}\) sont des entiers naturels non divisibles par 3 .
Le produit \(p=3^{a} b \times 3^{a^{\prime}} b^{\prime}\) est égal à \(3^{A} B\) avec \(A=a+a^{\prime}\) et \(B=b+b^{\prime}\).
\(A\) est un entier naturel pair comme somme de deux entiers naturels pairs. \(B\) est un entier naturel qui n'est pas divisible par 3 puisque ni \(b\) ni \(n b^{\prime}\) le sont. Ainsi \(p\) est un numéro perdant.
5. Il y a \(25 \%\) de numéros gagnants.

Une démarche possible : on dénombre les entiers de la forme \(3^{a} b\) (où \(a\) est un entier naturel impair et \(b\) un entier naturel non divisible par 3) qui sont inférieurs ou égaux à 2016.
Les valeurs possibles de \(a\) sont \(1,3,5\).
Pour \(a=1\), on doit avoir \(b \leqslant 672\) et \(b\) non divisible par 3 . Comme il y a 224 multiples de 3 inférieurs ou égaux à \(672, b\) peut prendre \(672-224=448\) valeurs.
Pour \(a=3\), on doit avoir \(b \leqslant 74\) (car \(\frac{2016}{27} \approx 74,7\) ) et \(b\) non divisible par 3 . On en déduit que \(b\) peut prendre \(74-24=50\) valeurs.
Pour \(a=5\), on doit avoir \(b \leqslant 8\) et \(b\) non divisible par 3 . On en déduit que \(b\) peut prendre 6 valeurs.
6. La valeur minimale de 4 est 2689 .

Une démarche possible : compte tenu de la question 5 , on peut penser qu'il y a environ \(25 \%\) de gagnants donc les 2016 numéros perdants représentent environ les trois quarts des billets vendus. Ce qui donne environ 2688 billets vendus.

Pour \(n=2688\), le même raisonnement qu'en 5 donne 673 gagnants donc 2015 perdants.
Pour \(n=2689\), le numéro 2689 est perdant donc il y a 2016 perdants.