Forum TI-Planet.org

L'épreuve de mathématiques du BAC S a suivi nombre de modes depuis bientôt 10 ans que je la suis.

Il y a eu la mode QCM (2004-2005), puis la mode ROC (2006), puis la mode "question ouverte"...

Nous sommes clairement aujourd'hui dans la mode algorithmique, d'une popularité sans précédent puisque s'étendant même au delà de la série S (séries ES, L et bientôt technologiques), et même au-delà du BAC!



En effet, un exercice d'algorithmique vient de tomber au Concours Général de Mathématiques 2013.
Le voici:


Nous nous devons donc d'aider Sisyphe, qui avance à partir de la case '0' avec un dé à 6 faces, et se doit d'atteindre ou dépasser 100 tout en évitant les nombres premiers.

Mais il n'y a que 25 nombres premiers inférieurs à 100 - un jeu d'enfant me direz-vous?
Approchons le problème de façon empirique à l'aide d'une petite simulation.
Voici un programme TI-Nspire qui renvoi le numéro de la case sur laquelle Sisyphe termine sa partie, c'est-à-dire:

• un nombre supérieur ou égal à 100 si il gagne
• un nombre premier inférieur à 100 si il perd

Comme vous voyez, j'ai effectué 8 parties et ai toujours perdu en atteignant un nombre premier inférieur à 100...

Mais peut-être est-ce de la malchance? Il faut simuler un grand nombre de parties pour que la fréquence d'apparition d'un événement tende vers sa probabilité.
Voici un autre programme TI-Nspire destiné à nous renvoyer la fréquence des parties gagnantes pour une simulation de n parties:

La probabilité de gagner la partie est effectivement très faible... Malgré plusieurs centaines ou milliers de parties simulées, la fréquence des parties gagnantes en souvent nulle ou très proche de zéro...



Les apparences sont donc trompeuses, et ce pauvre Sisyphe porte donc bien son nom, tel son homologue mythologique père d'Ulysse, qui fut damné à pousser un rocher jusqu'en haut d'une colline, ce rocher ayant une très forte probabilité de redégringoler alors immédiatement puisqu'il s'agit d'un équilibre instable (dérivée seconde du potentiel négative).




Bon, venons-en enfin aux questions qui nous intéressent.
Dans la 2ème partie, on étudie la loi de probabilité de variable aléatoire X, où X prend pour valeurs le numéro de la case en fin de partie (qu'elle soit gagnée ou perdue).

Les événements X=2 et X=3 sont aisément dénombrables via un arbre.
On code ici en rouge l'événement "atteindre un nombre premier inférieur à 100", ce qui met fin à la partie.


A partir de la case 0, on peut atteindre la case 2 en:

• sortant directement 2 (probabilité 1/6)
• sortant 1 puis 1 (probabilité 1/36)

Donc P(X=2)=7/36.

La case 2 étant interdite (nombre premier), les seules façons d'atteindre 3 sont en:

• sortant directement 3 (probabilité 1/6)
• sortant 1 puis 2 (case intermédiaire: 1 - probabilité 1/36)

Donc encore P(X=3)=7/36.

Les cases 2 et 3 étant interdites (nombres premiers), les seules façons d'atteindre 5 sont en:

• sortant directement 5 (probabilité 1/6)
• sortant 4 puis 1 (case intermédiaire: 4 - probabilité 1/36)
• sortant 1 puis 4 (case intermédiaire: 1 - probabilité 1/36)
• sortant 1 puis 3 puis 1 (cases intermédiaires: 1, 4 - probabilité 1/216)

Donc P(X=5)=49/216.

Les nombres 0, 1 et 4 étant des nombres non premiers ils ne peuvent achever une partie et on a donc de façon triviale P(X=0)=P(X=1)=P(X=4)=0.

On en déduit que P(X>=4)=1-P(X<4)=1-(P(X=0)+P(X=1)+P(X=2)+P(X=3))=11/18

Mais nous aurons bien évidemment beaucoup de mal à esquisser un arbre qui va plus loin...



La question nous demande donc en conséquence la production d'un algorithme permettant de déterminer P(X=k).
En utilisant les formules de probabilités d'événements successifs indépendants, on peut construire un algorithme récursif qui va parcourir l'arbre en profondeur, chaque nouvelle sous-branche correspondant à une multiplication par 1/6.

Nous allons utiliser pour cela sur TI-Nspire:

• une fonction testant si le noeud de l'arbre est un noeud arrêtant la partie
• une fonction pour initialiser la récursivité

Et il nous faut enfin la fonction récursive en tant que telle, qui à partir d'un noeud-parent se réappelle sur les 6 noeuds-fils (dé tiré entre 1 et 6) pour calculer les probabilités par multiplication par 1/6 et somme.
Cette fonction travaille donc branche par branche.
Elle renverra 0 si on termine la partie sans atteindre le nombre cherché, ce qui par produit annulera les chemins inutiles ici et permettra de ne considérer par somme que les 'bons' chemins.




Il ne s'agit probablement pas de l'algorithme le plus rapide, et une version itérative serait sans doute plus performante.
Mais je trouvais la version récursive plus naturelle à comprendre.

Dans tous les cas, il s'agit probablement d'un problème de complexité exponentielle, et quoi que l'on fasse l'algorithme explosera donc rapidement les capacités de toutes les machines actuelles.

Sur TI-Nspire notamment, en partant de P(X=0) on passe de calculs instantanés à des calculs de quelques secondes, puis quelques minutes, et enfin quelques heures sur P(X=29).

Tout juste peut-on conjecturer que la suite des P(X=k) non nuls semble décroissante à partir du rang 5 et tendre rapidement vers 0.

D'ici à ce qu'elle arrive à P(X=105), l'univers a certainement le temps de s'écrouler...



Edit: Pour une version itérative de l'algorithme, voir les commentaires de la news.



Rappelons que si les nombres premiers et plus généralement l'arithmétique, l'algorithmique et la programmation t'intéressent, nous tenons encore pour deux semaines un concours sur les nombres premiers-palindromes!




Liens:
Sujet du Concours Général de Mathématiques 2013
Document TI-Nspire support pour l'exercice 3

Jolis algorithmes...
J'ai bien peur malheureusement que peu de candidats aient pensé à la récursivité.

J'ai programmé sur Maple pour voir ce que ça donne, et avec l'option "remember", on arrive à des résultats très rapidement. Cela confirme qu'un algorithme itératif utilisant un tableau pour retenir les valeurs précédemment calculées serait bien plus rapide que l'algorithme récursif.

On peut en particulier calculer la valeur exacte de P(X>=100), soit :
220165609187884971313923019058879317936462947421492115 / 638324153542299148846280854514738362441007133779155746816

La valeur approchée correspondante est d'environ : 0.0003449

PS : J'ai rajouté le calcul de P(X>=4) qui avait été omis.

Merci.

On ne les habitue pas au lycée à écrire d'algorithmes récursifs, donc je pense aussi que les copies l'utilisant seront peu nombreuses.

L'algorithme itératif me semble beaucoup moins naturel et beaucoup plus complexe à établir si on reste dans l'optique d'un parcours d'arbre en profondeur ou même en largeur.


Mais après, peut-être peut-on avoir d'autres approches...

Pour info, j'ai aussi lancé 2 tests de la fonction "parties" pour n=1000000, toujours sur Maple, et Maple m'a répondu 33/10000, soit 0.00033 et 177/50000 soit 0.000354, ce qui sont 2 bonnes valeurs approchées de P(X>=100).
Il faut à peu près 2 minutes 30 à Maple pour calculer cela.

Par ailleurs, pour une autre approche, il y a peut-être moyen d'utiliser des matrices... mais je ne suis pas sûr que ça aide beaucoup.

Superbe article bien détaillé, c'est parfait pour les élèves, bravo

Pour les deux approches, je doute aussi qu'il y en aient eu beaucoup qui se sont mouillé dans le récursif, déjà que peu s'intéressent à l'algo tout court....

Mais après tout, c'est le concours général, les proportions changent peut etre
Bref, j'ai trouvé ce sujet déja bien plus intéressant que ceux du bac (normal ^^)

Voici un algorithme bien plus rapide que l'algorithme récursif de critor.

Le principe est simple : la probabilité de s'arrêter en N est nulle si N n'est pas premier. Sinon, il a fallu passer par une des 6 cases précédentes et avancer jusqu'en N au coup précédent. Dans ce cas, la probabilité de s'arrêter en N est égale à 1/6 fois la somme des probabilités de tomber sur l'une des cases précédentes et de continuer.

Il suffit alors de maintenir à jour une liste des probabilités de continuer après être tombé sur l'une des 6 cases précédentes. Mais ces probabilités s'obtiennent par les mêmes règles que précédemment, à l'exception près que cette fois, la proba de continuer est nulle lorsque le nombre est premier.

Voici ce que ça donne sur Nspire :

Code: Select all

Define probato(n)=
Func
local i,l,p
if isprime(n)
  return 0
l:={1,0,0,0,0,0}
for i,1,n
  p:=when(isprime(i),0,sum(l)/6)
  l:=shift(l)
  l[1]:=p
endfor
return sum(l)/6
EndFunc

Pour chaque i de 1 à n, et pour chaque k de 1 à 6, quand on entre dans la boucle "for", l[k] est la probabilité d'arriver en i-k et de continuer.

J'espère que c'est correct et compréhensible.

C'est une approche intéressante.

C'est quasiment ça oui. Corrigé sans doute une erreur de frappe en ligne 4:

Code: Select all

Define probato(n)=
Func
local i,l,p
if not isprime(n)
  return 0
l:={1,0,0,0,0,0}
for i,1,n
  p:=when(isprime(i),0,sum(l)/6)
  l:=shift(l)
  l[1]:=p
endfor
return sum(l)/6
EndFunc

Effectivement, faute de frappe... Merci d'avoir corrigé.

Le problème, maintenant, c'est qu'après quelques tests, je trouve des résultats différents des tiens pour quelques valeurs éparses !
En particulier, la valeur pour n=7 est différente...

Il doit y avoir un os quelque part.

Je suis en train de regarder ça oui.

Mais peut-être que c'est moi qui ai tort...

Nos algos sont d'accord pour n de 0 à 6, valeurs pour lesquelles on a l'arbre.
La 1ère différence est à n=7.

C'est meme la seule différence pour n allant de 0 à 23... ce qui est très troublant.