reneb
Bonjour,
C’est pas qu’une fois qu’elle se plante la « I.A. ».
Un petit problème de classement est posé à chatGPT.
Elle affirme pouvoir le résoudre. J’ai pris la peine de suivre, pas à pas, dans le détail ses algorithmes.
Souvent, à un moment, une erreur se glisse et le raisonnement ne peut plus être correct, le résultat, accompagné d’un message d’erreur, n’est pas celui prétendu avoir été atteint.
Ce problème (défi) a été proposé en 2012 par freddy en ces termes :
j'ai 15 boules parfaitement identiques, indiscernables ni au toucher, ni à la "soupesée".
Elles sont toutes d'un poids distinct.
J'ai à ma disposition un dispositif curieux : à chaque fois que je lui transmets trois boules, il me les rend classées dans l'ordre croissant de leur poids (mais sans indiquer leur valeur, oubli probable de son concepteur).
Combien de fois dois-je, au moins, avoir recours à ce dispositif pour ranger mes 15 boules de la plus légère à la plus lourde ?
https://www.bibmath.net/forums/viewtopic.php?id=5141
Un réponse définitive n'a pu encore être donnée.
Si ça vous dit...
R.
reneb
Bonjour,
Une conclusion de chatGPT après lui avoir soumi l'énoncé du problème :
"
? Conclusion
❌ Il est impossible de trier les 15 boules dans ce modèle.
Aucune stratégie, même avec un nombre illimité de tests, ne permet de déduire un ordre entre les boules,
car toute tentative d’observer ou mémoriser les identités échoue à cause de la perte d’identifiants dans les tris ternaires. "
Que, bien sûr, je conteste puisque j’arrive au résultat en 25 tests maximum.
Maîtriser la position dans l’espace !
R.
bridgslam
Bonjour,
Si le groupement en 5 séries de 3 est "miraculeux" ainsi que les choix pour 4 tests suivants, on s'en sort avec 9 tests, mais on doit compter sur un bol énorme dont la probabilité de réussite doit être très faible.
Bref il vaut mieux s'équiper avec une machine qui traite directement 15 boules :-).
Question difficile, je ne suis pas certain qu'elle recèle une réponse mathématiquement parlant.
Trouver un maximum OK, mais un minimum démontrable, j'ai un gros doute.
A.
reneb
Bonjour,
25 tests (maximum ) classent, sûrement, les 15 boules (dans tous les cas de figure) de la plus légère à la plus lourde.
Peut-être est-il encore possible de réduire le nombre de tests.
J’y travaille.
On arrive à 23 tests mais il y a des zones d’ombre et donc...
ChatGPT avance un calcul et conclu que 16 tests au minimum sont nécessaires. Elle ne tient pas toujours compte du fait que les boules sont indistinctes et qu’on ignore quels sont les mouvements des 3 boules à trier dans la machine (elles sortent classées et restent toutes semblables).
R
Michel-Coste
Bonjour,
Une minoration du nombre de tests suffisants dans tous les cas est relativement facile à obtenir :
Pour chaque test, il y a $3!=6$ réponses possibles.
Pour le rangement des boules, il y a $15!$ possibilités.
Il faut donc au moins 16 tests parce que 16 est le plus petit entier $n$ tel que $6^n \geq 15!$.
Ce genre de raisonnement est classique dans les problèmes de pesées. La réponse de ChatGPT vient sans doute de là.
reneb
Bonsoir,
La reponse de l'IA (16 tests) mise en œuvre platement sur le terrain est correcte sauf qu'elle ne prend pas en compte toutes les conditions de départ et notamment celle qui stipule que chaque boule est identique à toutes les autres et doit le rester. (Il n'est pas permis de les customiser).
Un grille 3X5 et un support linéaire assez long pour y ranger les 15 boules en ordre croissant sont indispensables
À +⁷
Michel-Coste
Je ne comprends pas ce que tu écris. Bien sûr que le problème permet de numéroter les boules de 1 à 15. Le problème est de trouver quelle permutation de {1,...,15} range les boules dans l'ordre croissant de poids, sachant qu'on peut ranger les boules quand on les prend 3 par 3.
reneb
Autrement dit,
Je voudrais une stratégie concrète, pas juste une borne théorique. Donc : quels gestes faire pour trier 15 boules indiscernables, qui n'ont aucune marque, et dont on ne peut rien dire sauf par le dispositif qui trie trois boules à la fois.
Combien, au minimum, faut-il de recours à ce dispositif pour trier les 15 boules ?
(25 recours pour ma part). Peut faire mieux?
A vos petits bouts de papiers, si ça vous dit.
R.
Bernard-maths
Bonjour à tous !
Je veux bien utiliser 15 boules de même couleur et de poids variant de 1 mg à la fois, ce qui fait 14 mg d'écart entre la + lourde et la - lourde ... donc indiscernables au sous-pesage.
Mais pour moi le nombre de pesées pour isoler la + lourde et la + légère, est de l'ordre de 14-15 ou 16 environ !
Et il en reste 13 à départager ...
Alors je ne vois pas du tout les 25 coups minimum ...
Donc j'attends plus de détails sur la méthode !
Bernard-maths
bridgslam
Bonjour
Si on a le droit de croire aux miracles, on peut espérer avec une probabilité quai nulle séparer les 15 billes en 5 groupes de poids consécutifs , que la machine ordonne avec 5 tris.
En croyant encore en sa bonne étoile, on groupe par 3 en prenant les deux plus lourdes d'un tas, et la plus légère d'un autre, à tester par la machine, youpi si ça marche , et on continue encore 3 fois... selon le même principe.
Si on a fait ces 4 tests dans l'ordre qu'il fallait (1 chance sur 24), cela fait donc 9 tests en tout.
D'accord , si le hasard fait vraiment bien les choses...
Mais pas impossible non plus.
Bernard-maths
@bridgslam !
Je suis d'accord, c'est un peu ça que je fais.
Mais 9 + le reste ... pour un mini de 25, je vais voir
B-m
Bernard-maths
D'accord, en 9 pesées on trouve la + lourde et la + légère. Reste les 13 autres ... on recommence ...
Bernard-maths
Alors en itérant "mon procédé", de tête, je trouve 35 à 37 pesées, pour ranger les 15 boules en ordre,
Ceci de façon certaine ! Alors 25 mini, c'est quoi ???
Bernard-maths
PS ; si vous insistez, je vous donnerai le détail ...?
bridgslam
Bonsoir,
@Bernard
Tu n'as pas saisi la manip, je pense:
Si le hasard a fait qu'elle a trié 5 triplets de 3 boules dont la masse est consécutive dans chaque triplet, 5 opérations), 4 opérations supplémentaires sous l'auspice des dieux aussi fait qu'on a pu déceler la boule la plus légère consécutive aux deux plus lourdes du triplet des plus légères , puis on recommence 3 fois de plus en se décalant d'un groupe à chaque fois: on a 23 chances sur 24 de se planter sur ces 4 opérations.
Ça fait neuf tris pour la machine en tout, à condition que le hasard nous ait aidé.
Je n'ai pas calculé la probabilité de réussite, mais elle est très faible.
La minoration de 16 concerne les tests sans aucun coup de pouce du hasard, en gros sans décision magique dans les choix des boules et les ordres dans les tests, donc avec une probabilité de 1.
La probabilité d'être aidé par le hasard à ce point (pour réussir en 9 coups) me fait dire que c'est comme si on avait opéré avec des informations supplémentaires, qui nous sort d'office du contexte du sujet.
La résolution idéale serait de déterminer, sans intervention favorable du hasard, un algorithme en 16 coups: on serait sûr que c'est le bon.
Mais je n'en ai pas trouvé présentement.
Bernard-maths
@bridgslam !
Justement je ne tiens pas compte du hasard : d'ailleurs comment le savoir ?
Je pense que ce que j'ai trouvé est juste, mais pas en 16 coups ... et mène à la solution ...
B-m
reneb
Bonsoir,
Bernard-maths a écritPS ; si vous insistez, je vous donnerai le détail ...?
Ben j'insiste, si tu veux bien, pour pouvoir suivre ton raisonnement avec les détails.
Je donne, caché, la première étape conduisant au tri de 15 boules en 25 recours.
On a une grille 5X3 et un rail, support linéaire pour 15 boules.
15 boules a répartir en 5 colonnes (C1,C2,C3,C4,C5) de 3 boules
Et donc, ainsi, former 3 lignes (L1,L2,L3) de 5 boules.
On glisse trois boules dans le dispositif « trieur ». Elles ressortent rangées par ordre croissant sans que l’on sache quelle boule a bougé et on les dépose dans la C1 (la plus légère en dessous.
Même opération pour les 12 autres boules déposées en ordre croissant dans les colonnes C2,C3,C4,C5.
Nous obtenons ainsi, 3 lignes (L1,L2,L3) de 5 boules
L1 est la ligne des boules légères.
Le tri des 5 boules d’une ligne se fait en 4 tris.
Les 5 boules ainsi classées de la plus légère(à gauche) à la plus lourde (à droite) forment la L1
Idem pour les boules des lignes L2 et L3.
Toutes les boules, indistinctes, sont réparties en ordre croissant sur les lignes et les colonnes.
Colonne:boule la plus légère en bas ; boule la plus lourde en haut.
Lignes : boule la plus légère à gauche ; boule la plus lourde à droite.
5+12=17 tris.
A bientôt.
R.
bridgslam
@Bernard !
On est donc d'accord.
Mais je voulais qu'il n'y ai pas d'ambiguïté dans mon propos, à savoir qu'on peut expliciter 9 opérations exactement menant à la réussite avec une probabilité très faible dans le choix miraculeux des triplets de boules et de l'ordre des tests ultérieurs.
Je ne pense pas, en se permettant donc une réussite non certaine, voire très douteuse , qu'on puisse descendre encore moins que 9.
On attend avec fébrilité ton procédé à 100%...
Au point où on en est:
- la minoration par 16 du nombre d'actions de la machine si l'on veut être sûr de réussir est indubitable: si un groupe au moins de 3 boules parmi les n du test sont ordonnés différemment par la machine , ils doivent correspondre à deux permutations différentes des 15 boules, d'où l'inégalité de Michel pour que n suffise.
- on cherche donc si un algorithme en 16 étapes existe, auquel cas ce sera effectivement le minimum.
L'ennui c'est que si on ne trouve pas, rien ne dit que ça n'existe pas: à double tranchant donc, si je puis dire.
- le nombre d'opérations minimum est 9 (sauf erreur ) si aucun objectif de réussite n'est imposé: dans ce cadre, au hasard de la procédure utilisée, on peut tomber ( si le hasard coopère au mieux ) sur la procédure que j'ai décrite.
Je ne vois pas moins de 9, mais je peux me tromper.
Peut-être quelqu'un fera-t-il mieux?
Bernard-maths
Salut les copains ! (connaissez-vous cette émission ?)
Le fait de trier les boules par 3 permet de créer la disposition des 5 colonnes et 3 lignes de renéb.
La plus légère des 15 se trouve dans un groupe de 3, et se retrouve donc dans la ligne du haut.
Pareil avec la plus lourde des 15, qui se retrouve dans la ligne du bas.
Mais c'est tout ce qu'on sait ! Ls 5 boules du haut ne sont pas forcément les 5 plus légères des 15.
Ni les 5 du bas les 5 plus lourdes des 15.
Isoler la plus légère : on pèse les 3 de gauche, on récupère la plus légère (des 3), qu'on repèse avec les 2 de droite, on a enfin la plus légère des 15 !
Isoler la plus lourde : même procédé avec les plus lourdes ...
Total étape 1= 5 + 2 + 2 = 9 pesées pour avoir la plus lourde et la plus légère des 15.
Il reste 13 boules, plusieurs approches peuvent se faire, en voici une, non comparée à d'autres ...
On a perdu les "identités" de tri de la 1ère étape, on recommence , 4 tris de 3 boules et il reste une orpheline !
Isoler la plus légère du haut : on pèse les 3 de gauche, pis les 2 plus légères avec la 4ème de droite, on a la plus légère des 4 du haut.
Isoler la plus lourde du bas : on procède même avec les plus lourdes.
On a finalement la plus légère des 4 du haut et la plus lourde des 4 du bas, qu'on pèse avec l'orpheline !
On a enfin la 2ème plus légère des 15 et l'avant dernière plus lourde. Il en reste 11 !
Total étape 2 = 4 + 2 + 2 + 1 = 9
On recommence, on a 3 colonnes de 3 et 2 orphelines.
On pèse les 3 du haut, on a la plus légère, on pèse les 3 du bas, on aa la plus lourde.
On pèse la plus légère et la plus lourde avec une orpheline, puis la plus légère et la plus lourde avec l'autre orpheline.
On a finalement la plus légère et laa plus lourde de 11 boules. Il en reste 9.
Total étape 3 = 3 + 1 + 1 + 1 + 1 = 7.
On recommence : 3 colonnes de 3 boules.
Les 3 du haut donnent la plus légère, ls 3 du bas lea plus lourde. Il reste 7 boules.
Total étape 4 = 3 + 1 + 1 = 5.
On recommence : 2 colonnes de 3 boules et une orpheline.
On pèse les 2 du haut avec la plus lourde des 15 !!! On a la plus légère ( et on garde la plus lourde !).
On pèse les 2 du bas avec la plus légère des 15 ! On a la plus lourde ...
On pèse la plus lourde et la plus légère avec l'orpheline ... on a la plus lourde et la plus légère des 7.
Total étape 4 = 2 + 1 + 1 = 4.
.
Il rest 5 boules ... puis il en restera 3 !
Je vous laisse chercher un peu la fin ???
Moi je trouve encore 3 puis 1 pesées.
En tout cela fait : 9 + 9 + 7 + 5 + 3 + 1 = 34 pesées.
Alors, à bientôt, Bernard-maths
reneb
Bonjour,
La méthode est correcte mais longue.
Bernard-maths a écrit
Total étape 1= 5 + 2 + 2 = 9 pesées pour avoir la plus lourde et la plus légère des 15.
Mais,on a perdu les "identités" de tri de la 1ère étape, on recommence...
Pour éviter de perdre les "identités" de tri de la 1ère étape, Un conseil?
Changer de méthode.
pourquoi pas classer les 5 boules du haut et les cinq boules du bas et dans la foulée celles du milieu?
A coup sûr la boule en haut de la première colonne ou à l'extrème gauche de la ligne du haut est la plus légère.
Par symétrie, on isole la boule la plus lourde.
Pour trier 5 boules il faut 4 appels à la machine.
Total étape 1= 5 + 3*4 = 17
Cette opération conserve les classements déjà effectués.
A bientôt
R.
Bernard-maths
Désolé ! Je ne comprends pas bien ... Si on tiré :
1 8 7 2 3 > 1 2 3 7 8
5 9 10 4 12 > 4 5 9 10 12
15 11 13 6 14 > 6 11 13 14 15
et après ???