15 boules à classer

renéb · 03-09-2025 14:54:04

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.

renéb · 04-09-2025 08:47:18

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.

▼un indice?

R.

bridgslam · 04-09-2025 09:00:26

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.

Dernière modification par bridgslam (04-09-2025 09:02:09)

renéb · 04-09-2025 11:43:57

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 · 04-09-2025 17:47:28

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à.

renéb · 04-09-2025 19:11:16

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 indice?

À +⁷

Michel Coste · 04-09-2025 22:06:41

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.

Dernière modification par Michel Coste (05-09-2025 09:03:16)

renéb · 06-09-2025 12:41:33

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 · 06-09-2025 16:34:51

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

Dernière modification par Bernard-maths (06-09-2025 16:35:40)

bridgslam · 06-09-2025 17:02:01

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.

Dernière modification par bridgslam (06-09-2025 17:03:22)

Bernard-maths · 06-09-2025 17:15:17

@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 · 06-09-2025 17:24:24

D'accord, en 9 pesées on trouve la + lourde et la + légère. Reste les 13 autres ... on recommence ...

Bernard-maths · 06-09-2025 17:43:41

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 · 06-09-2025 19:26:17

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.

Dernière modification par bridgslam (06-09-2025 19:28:06)

Bernard-maths · 06-09-2025 19:30:21

@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

renéb · 06-09-2025 19:47:48

Bonsoir,

Bernard-maths a écrit :

PS ; 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.

▼ première étape

A bientôt.

R.

Dernière modification par renéb (06-09-2025 20:23:10)

bridgslam · 06-09-2025 20:06:46

@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?

Dernière modification par bridgslam (06-09-2025 23:14:40)

Bernard-maths · 07-09-2025 08:34:03

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

Dernière modification par Bernard-maths (07-09-2025 08:39:50)

renéb · 07-09-2025 11:55:18

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?

▼conseil

A bientôt

R.

Bernard-maths · 07-09-2025 13:10:37

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 ???

renéb · 07-09-2025 13:20:03

Salut,

Après on connait la boule la plus légère coin supérieur gauche (C1L3) et la plus lourde coin inférieur droit (C5L1).
Et en plus, la boule 2 est voisine de la boule la plus légère b1 idem b14 voisine de b15. (symétrie oblige.)

Bernard-maths · 07-09-2025 13:29:56

Oui ... puis 3 et 13 ... mais et après comment trouver 4 et 12 ???

renéb · 07-09-2025 13:44:13

Re!

On attaque le problème par les deux extrémités. Les opérations sont symétriques.

On les retire de la grille et les plaçons sur la rigole solution aux extrémités de celle-ci
1,…………..15
avec au voisinage de 1: 2et4
et au voisinage de 15: 12et14. Retirées de la grille mais pas encore posées sur la rigole
(Indispensable de les laisser libre de bouger avant les manipulations spatiales)
La grille mise à jour:
"" "" 3 7 8
"" 5 9 10 ""
6 11 13 "" ""
Rigole salution:

. 1,…………..15
2,4 12,14

Dernière modification par renéb (07-09-2025 13:47:02)

Bernard-maths · 07-09-2025 13:52:28

Re salut !

Je ne comprends pas pourquoi tu retires 4 et 12, sur quels critères ???

renéb · 07-09-2025 14:30:57

Re,

Parce qu'ils sont, spacialement, dans le voisinage de 1 (1 a 2 voisins) et symétriquement.
Pourquoi encore?
Parce qu'ils préparent ,en tant qu' élément de la future triade, le classement de trois boules au côté de 1 et symétriquement

On a 1,.......
Ont trie (2,4,?).
La troisième boule est sous nos yeux il suffit de la sortir:
Manipulation spatiale :
On bouge les trois boules de la ligne L1 de deux places vers la gauche.
On bouge les trois boules de la ligne L3 de deux places vers la droite.
On obtient:
3 7 8
5 9 10
6 11 13
On retire la 3 et la13
On les joints aux tris en attente:
(2,4,3) qui donne (2,3,4) en retenant que 4 reste mobile (d'où 4?)
et symétriquement

Sur la grille, à coup sûr: 1,2,3,4?.......12?,13,14,15
Soit 2 recours à l'appareil à classer.
17+2=19

Après?

A bientôt
R.

Dernière modification par renéb (07-09-2025 16:49:17)

Forum de mathématiques - Bibm@th.net

#1 03-09-2025 14:54:04

15 boules à classer

#2 04-09-2025 08:47:18

Re : 15 boules à classer

#3 04-09-2025 09:00:26

Re : 15 boules à classer

#4 04-09-2025 11:43:57

Re : 15 boules à classer

#5 04-09-2025 17:47:28

Re : 15 boules à classer

#6 04-09-2025 19:11:16

Re : 15 boules à classer

#7 04-09-2025 22:06:41

Re : 15 boules à classer

#8 06-09-2025 12:41:33

Re : 15 boules à classer

#9 06-09-2025 16:34:51

Re : 15 boules à classer

#10 06-09-2025 17:02:01

Re : 15 boules à classer

#11 06-09-2025 17:15:17

Re : 15 boules à classer

#12 06-09-2025 17:24:24

Re : 15 boules à classer

#13 06-09-2025 17:43:41

Re : 15 boules à classer

#14 06-09-2025 19:26:17

Re : 15 boules à classer

#15 06-09-2025 19:30:21

Re : 15 boules à classer

#16 06-09-2025 19:47:48

Re : 15 boules à classer

#17 06-09-2025 20:06:46

Re : 15 boules à classer

#18 07-09-2025 08:34:03

Re : 15 boules à classer

#19 07-09-2025 11:55:18

Re : 15 boules à classer

#20 07-09-2025 13:10:37

Re : 15 boules à classer

#21 07-09-2025 13:20:03

Re : 15 boules à classer

#22 07-09-2025 13:29:56

Re : 15 boules à classer

#23 07-09-2025 13:44:13

Re : 15 boules à classer

#24 07-09-2025 13:52:28

Re : 15 boules à classer

#25 07-09-2025 14:30:57

Re : 15 boules à classer

Réponse rapide

Pied de page des forums