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 ???
reneb
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
Oui ... puis 3 et 13 ... mais et après comment trouver 4 et 12 ???
reneb
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
Bernard-maths
Re salut !
Je ne comprends pas pourquoi tu retires 4 et 12, sur quels critères ???
reneb
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.
reneb
re,
On continue a exploiter la grille. Je trie la colone passant par le centre pour s'assurer que les boules légères sont dans le haut de la grille, les lourdes dans le bas.
7 6
5 8 10
9 11
Soit 1 recours à l'appareil à classer.
19+1=20
on retir de la grille les 2 billes de gauche (5,7) et la bille du haut(5,7,6) on les trie => 5,6,7. Sur la rigole- solution, on place 5,6,7,à droite de la 4?
pareil, symétriquement au centre: => (10,11,9) " " " " => 9,10,11 " " " 9,10,11 à gauche de 12?
On rajoute au centre le 8
20+2=22
On a la rigole résultats: 1,2,3,4?,5,6,7?, 8? ,9?,10,11,12?,13,,14,15
Derniers recours à la machine: les boules 4?,5,6?, 10,11,12?, et 7?,8?,9?
et c'est terminé
22+3=25
c'est long l'explication.
Cette méthode est à toutes épreuves.
J'en ai pondu un programme python qui restitue à 100 % le classement des 15 boules en tous points identiques (sauf par leur poids qui est inique) en 25 recours à l'appareil.
A bientôt.
R.
Bernard-maths
Merci renéb !
Il faut que je cmprenne bien les proximités spatiales ...
Bonne nuit ... ne nuit pas.
Bernard-maths
bridgslam
Bonjour,
Déjà pour un nombre de boules très réduit par rapport aux 15 de départ, disons 5, le minimum de passages en machine pour les trier est de 4, alors que la minoration théorique (mais simple ) vaut 3 (plus petit exposant de 3! pour que la puissance soit au moins égal à 5! = 120 ).
Je ne serai donc pas surpris que pour qu'un algorithme fonctionne pour 15 boules, on soit largement au-dessus de 16.
Bonne soirée