Olympiades académiques

apmep

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

4 pages

Français

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

A propos
Informations
Extrait

Description

Olympiades académiques - 2009 39 BESANÇON Exercice no 1 (Série S) Enoncé Promenade parmi les nombres On part du nombre 5 et on s'autorise à utiliser deux opérateurs : • L'opérateur (M) « multiplier par 2 » : n 7?? 2? n • L'opérateur (R) « retrancher 3 » : n 7?? 3? n. Un entier naturel N est dit admissible s'il est possible, en partant de 5 et en n'utilisant que les deux opérateurs ci-dessus, de parvenir en un certain nombre d'étapes au nombre N . Par exemple 25 est admissible par le chemin à cinq étapes : 5 M????? 10 R????? 7 M????? 14 M????? 28 R????? 25 On considérera par convention que 5 est admissible (chemin avec 0 étape) 1. Quels sont les entiers naturels admissibles en au plus 3 étapes ? 2. Montrer que 11, 13, 16 et 19 sont aussi admissibles. 3. Certains entiers naturels sont non admissibles : lesquels ? Justifier. 4. Montrer que 2 009 est admissible en présentant une méthode permettant de trouver le chemin menant de 5 à 2 009 (une telle méthode est aussi appelée algorithme). Eléments de solution 1. Les six nombres admissibles en trois étapes sont : le nombre 1 : 5 R????? 2 M????? 4 R????? 1 le nombre 8 : 5 R????? 2 M????? 4 M????? 8 le nombre 4 : 5 M????? 10 R????? 7 R????? 4 le nombre 14 : 5 M????? 10 R????? 7 M????? 14 le nombre 17 : 5 M????? 10 M????? 20 R????? 17 le nombre 40

equipe

coût minimal

tableau de score

chemin inverse

enoncé tableau des scores

olympiades académiques

algorithme de création de chemin

Sujets

Équipe

Informations

Publié par	apmep
Nombre de lectures	25
Langue	Français

Extrait

Olympiades acadÉmiques - 2009

BESANçON

o Exercice n1(SÉrie S)

Enoncè Promenade parmi les nombres On part du nombre 5 et on s’autorise Ā utiliser deux oprateurs : •L’oprateur (M) « multiplier par 2 » :n→−72×n •L’oprateur (R) « retrancher 3 » :n7−→3×n. Un entier naturelNest dit admissible s’il est possible, en partant de 5 et en n’utilisant que les deux oprateurs ci-dessus, de parvenir en un certain nombre d’tapes au nombreN. Par exemple 25 est admissible par le chemin Ā cinq tapes :

M RM M R 5−−−−→10−−−→7−−−−→14−−−−→28−−−→25 On considrera par convention que 5 est admissible (chemin avec 0 tape) 1. Quelssont les entiers naturels admissibles en au plus 3 tapes? 2. Montrerque 11, 13, 16 et 19 sont aussi admissibles. 3. Certainsentiers naturels sont non admissibles : lesquels? Justiﬁer. 4. Montrerque 2 009 est admissible en prsentant une mthode permettant de trouver le chemin menant de 5 Ā 2009 (une telle mthode est aussi appelealgorithme).

Elèments de solution 1.Les six nombres admissibles en trois tapes sont :

R M R le nombre 1 :5−−−→2−−−−→4−−−→1 R M M le nombre 8 :5−−−→2−−−−→4−−−−→8 M RR le nombre 4 :5−−−−→10−−−→7−−−→4 M RM le nombre 14 :5−−−−→10−−−→7−−−−→14 M M R le nombre 17 :5−−−−→10−−−−→20−−−→17 M M M le nombre 40 :5−−−−→10−−−−→20−−−−→40

Olympiades acadÉmiques - 2009

Le raisonnement prcdent laisse apparaitre aussi les nombres admissibles en 0 tapes (5), une tape (2; 10) et deux tapes (4; 7; 20). Les onze nombres admissibles en moins de 4 tapes sont donc : 1 - 2 - 4 - 5 - 7 - 8 - 10 - 14 - 17 - 20 - 40

2.Les deux chemins suivants donnent la rponse : R M M MR 5−−−→2−−−−→4−−−−→8−−−−→16−−−→13 M RM R M R 5−−−−→10−−−→7−−−−→14−−−→11−−−−→22−−−→19

3.Les nombres divisibles par trois ne sont pas accessibles car : ◦;5 n’est pas divisible par 3 ◦en multipliant par 2 un nombre non divisible par 3, on obtient un nombre non divisible par 3; ◦En retranchant 3 Ā un nombre non divisible par 3, on obtient un nombre non divisible par 3. Ainsi, partant d’un nombre non divisible par 3, on ne trouvera sur son chemin (et donc au ﬁnal) aucun nombre divisible par 3. 4.Un chemin menant de 5 Ā 2009 : R M M MM M M 5−−−→2−−−−→4−−−−→8−−−−→16−−−−→32−−−−→64−−−−→128 M R M R −−−−→256−−−→253−−−−→506−−−→503 M M R −−−−→1006−−−−→2012−−−→2009. Ce chemin a t trouv par l’algorithme ci-dessous : Algorithme de crÉation de chemin: On cre en fait le chemin inverse : en partant deN, on obtient un chemin qui mne Ā 5 de la manire suivante : FSinest divisible par 2, son prdcesseur (pre) estn/2. D L’oprateur est le rciproque de (M) :n−−−−→n/2 FSinon, son prdcesseur estn+ 3. A L’oprateur est le rciproque de (R) :n−−−→n+ 3. Ainsi, pour 2009, on obtient successivement :

2009 - 2012 - 1006 - 503 - 506 - 253 - .. . -16 - 8 - 4 - 2 - 5. ComplÉment 1 : justiﬁcation de cet algorithme Il est clair que le chemin inverse est bien constitu des seuls oprateurs autori-ss (M) et (R). n n+ 3n On montre que l’anctre de degr 2 (le « grand pre ») denest, ,ou + 4 22 3; on montre alors que tant quen >6, il est strictement infrieur Ān. Ainsi la suite des grands-pres successifs dcrot strictement, elle ne peut tre

Olympiades acadÉmiques - 2009

inﬁnie en restant suprieure Ā 6 et donc on atteint Ā un instant donn pour la premire fois une valeur strictement infrieure Ā 6. On montre que la valeur prcdente ne peut tre que 8 ou 10. D D A Si c’est 8, on ﬁnit le trajet par8−−−−→4−−−−→2−−−→5 D Si c’est 10, on ﬁnit le trajet par10−−−−→5. Ce qui montre que l’algorithme aboutit Ā 5 et donc le chemin inverse mne de 5 ĀN. ComplÉment 2 : caractÈre minimal de cet algorithme L’algorithme prcdent est original car : FLorsquenest impair, on n’a pas d’autre choix que lui ajouter 3. FLorsquen= 2v,nest pair, au lieu de le diviser par 2, on pourrait lui ajouter un certain nombre(q)de fois le nombre 3 puis seulement ensuite le diviser par 2 ( ce qui doit ncessairement arriver pour dcrotre). Mais ceci impose queqsoit pair pour pouvoir diviser par 2; ainsiq= 2r. 2v+ 3q2v+ 6r On arrive ainsi au nombre= =v+ 3r. 2 2 Mais dans l’algorithme choisi on peut arriver Ā ce mme nombre par une divi-sion par 2 etrajouts de 3. Ce que rsume le diagramme ci-dessous : D u= 2v−−−−→v   2rfois (A)rfois (A) y y D 2v+ 6r−−−−→v+ 3r En notant cule coÛt minimal pour aller deuĀ 5. cle coÛt minimal pour aller deuĀ 5 en commenÇant par l’oprateur (D) kle coÛt minimal pour aller deuĀ 5 en commenÇant par l’oprateur (A). on aura :c61 +r+cv+3r61 + 2r+cv+3r=k et doncc61 +r+cv+3r61 + 2r+cv+3r=k et[c=k]⇔[r= 0]. On a bien tabli l’algorithme minimal. ComplÉment 3 : nombre minimal d’Étapes En notant pourNnon divisible par 3 : ¡ ¢ k k •p= min{k∈N/2>Net 3 divise 2−N} p 2−N •b= 3 •cle nombre de chiﬀres en base 2 deb •ule nombre de 1 dans l’criture en base 2 deb.

Olympiades acadÉmiques - 2009

∗ pourN∈N− {1,4}avecNnon divisible par 3, la longueur du trajet minimal est •p+u−4sip−c= 2 •p+usip−c6= 2.

o Exercice n2 Enoncè Tableau des scores d’une poule de championnat On s’intresse aux tableaux de scores obtenus Ā l’issue d’une poule d’un championnat sportif. Dans une telle poule, chaque quipe rencontre chacune des autres; z;en cas de match nul on attribue 1 point Ā chaque quipe zsinon on attribue 3 points Ā l’quipe gagnante et 0 point Ā l’quipe perdante. Par exemple, si une poule comporte 3 quipes nommes A, B et C, on aura 3 matchs : A contre B, A contre C, B contre C. Si A perd ses deux matchs et que B gagne contre C, A totalisera 0 point, B 6 points et C 3 points. Le tableau de la poule sera dans ce cas le suivant : er 1 B6 e 2 C3 e 3 A0 Seule nous intresse ici la troisime colonne; nous la coderons630 . Attention, dans un tel codexyz, on aura toujoursx>y>z. Autre exemple : si les trois matchs donnent un rsultat nul, le code obtenu sera 222 . 1. Dans cette question, la poule comporte 3 quipes. Combien de codes possibles obtient-on? (on connat djĀ 630 et 222) Dans toute la suite, la poule comporte 4 quipes. 2. Sion sait qu’une quipe gagne tous ses matchs, combien de codes possibles peut-on obtenir? 3. Sion sait que le premier du groupe a totalis 4 points, combien de codes possibles peut-on obtenir?

Elèments de solution 1.On obtient facilement 7 codes possibles : 630, 611, 440, 431, 421, 333 et 222. 2.a)En fait, le premier a 9 points. Le reste de la poule revient Ā eﬀectuer