15 boules à classer

renéb · 07-09-2025 17:57:50

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 · 07-09-2025 19:39:26

Merci renéb !

Il faut que je cmprenne bien les proximités spatiales ...

Bonne nuit ... ne nuit pas.

Bernard-maths

bridgslam · 07-09-2025 20:05:11

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

Ernst · 08-09-2025 13:54:49

renéb a écrit :

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.

Bonjour,

Absolument magnifique.

Allez hop, ta méthode (nombres de 11 à 25 pour ne pas confondre avec les indices) détaillée visuellement :
https://sites.google.com/view/ernst01/boules

Strictement aucun test, cases déplacées ou triées sans regard sur leur contenu, moi je dis chapeau !!!

Ernst · 08-09-2025 14:59:59

Argh, j'ai dû me tromper quelque part, il y a des mélanges pour lesquels ça ne marche pas :

15-16-23-21-12
24-18-20-14-11
25-22-19-17-13

Quand c'est terminé, le rail donne 11-12-14-13... donc pas top.

J'ai forcé cette grille histoire de vérifier :
https://sites.google.com/view/ernst01/boules1

J'ai dû me gourer dans les cases à trier. Le fait que je place par exemple en R 2-3-4 les boules en attente que tu tries à part et que tu places ensuite à cette même place, ou que je cherche directement les cases sans déplacer les lignes ne devrait pas changer grand chose, et même le fait de pouvoir vérifier avant/après ne m'a pas permis de trouver l'erreur...

(désolé)

renéb · 08-09-2025 15:24:13

Bonjour

Ernst a écrit :

... je cherche directement les cases sans déplacer les lignes ne devrait pas changer grand chose,
(désolé)

Le déplacement de lignes change le tris vertical.

La méthode décrite ci-dessus n'est pas tout à fait semblable.
Entre autres: le classement des colones: en bas la boule la plus légère et en haut, la plus lourde
des lignes, à gauche la boule la plus légère et à droite la plus lourde
Mais le principe est le même.

A bientôt

R.

renéb · 08-09-2025 17:54:39

'soir,

Zut.

15-16-23-21-12
24-18-20-14-11
25-22-19-17-13

La configuration ci-dessus nécessite plus de recours à l'appareil.

Prétentieux que j'étais.

Merci Ernst d'avoir relancé nos recherches du minimum de recours posible pour arriver à classer les 15 boules.

Au boulot.

R.

renéb · 08-09-2025 18:29:50

R'soir,

Avec 2 recours en plus ça semble rentrer dans l'ordre.
Je m'en vais les rajouter dans le programme python.

25+2=27

Il doit y avoir une mèthode plus rapide.

R.

Ernst · 08-09-2025 21:28:14

renéb a écrit :

Au boulot.

Bonsoir renéb,

Voilà une nouvelle approche en essayant de coller au mieux à tes explications. Honnêtement, ta méthode marche super bien, même si elle n’est pas parfaite, je suis toujours aussi admiratif pour quelque chose que j'ai été incapable d’approcher :

https://sites.google.com/view/ernst01/boules2

Suffit de relancer la session (F5 sur mon PC) pour avoir d’autres configurations. Il arrive que le rail final ne soit pas dans l’ordre, un point vert ou rouge permet de le voir plus vite. Un bouton ‘auto’ permet de trouver plus facilement les configurations qui résistent, histoire de décortiquer ce qui s’est passé et d’analyser le pourquoi du comment.

N’empêche, impressionné je reste, t’as vraiment mis le doigt sur quelque chose, y a sans doute pas grand-chose qui coince (mais je n’en ai aucune idée, je le dis tout de suite).

renéb · 09-09-2025 09:14:50

Bonjour,

Je confirme que l'ajout de deux recours à la trieuse donne le résultat attendu.
J'ai testé cela avec "python modifié "sur des dizaines de milliers d'exemples.
Je peux publier le programme python si vous voulez.

Je cherche une méthode plus economique en recours à l'appareil.

A bientôt.

Ernst · 09-09-2025 10:03:46

Bonjour,

Oui, dans le rail final les configurations qui résistent demandent encore deux tris. Je suis en train de regarder un truc, dans un premier temps ne pas trier la ligne centrale, on gagne quatre opérations, et quand on a dégagé les coins et qu'il ne reste plus que trois éléments dans cette ligne, alors on la trie, on perd donc une opération à ce moment-là, mais il nous reste un différentiel positif de trois opérations à utiliser plus tard. Par contre on se retrouve avec des éléments incongrus dans le rail, faut utiliser des tris pour les rapprocher de leur position finale, donc pas sûr qu'on y gagne quoi que ce soit...

yoshi · 09-09-2025 14:49:24

RE,

renéb a écrit :

Je peux publier le programme python si vous voulez.

Volontiers.
Merci d'avance.

@+

Bernard-maths · 09-09-2025 16:42:55

Bonsoir !

Pouvez-vous essayer les 5 premiers tirages donnant :

13 4 6 1 7
14 5 11 2 8
15 9 12 3 10

j'ai essayé de diminuer à 2 les numéros qui restent sur la même ligne ...

Merci de tester vos programmes !

B-m

Dernière modification par Bernard-maths (09-09-2025 16:44:05)

renéb · 09-09-2025 18:51:06

Bonsoir.

Je suis à l’étranger.
Pas de machine pour m’épauler.
Le code python dès mon retour.
Pour ce qui est de la question posée, je ne la comprends pas bien . Peut-être en d’autre termes?

À bientôt.
⁷
R.

Dernière modification par renéb (09-09-2025 21:56:06)

renéb · 12-09-2025 17:16:47

Bonjour,

Comme annoncé, voici le programme assurant (en un éclair) le classement de 15 boules parfaitement identiques si ce n'est leurs poids singuliers.
La pythonisation de ce défi se trouve dans la rubrique Programmation:
https://www.bibmath.net/forums/viewtopic.php?id=18002

Par ailleurs, je recherche une méthode moins gourmande en recours à l'appareil trieur.
J'ai une piste que je dois éprouver avec l'aide de python.

A bientôt.

R.

Bernard-maths · 12-09-2025 17:28:36

Bonsoir à tous !

Je ne peux pas charger ton programme ...

MAIS quelqu'un pourra-t-il essayer mon tirage proposé en #38, et me dire la réponse ???

Merci au kamikaze,

B-m

renéb · 13-09-2025 18:41:10

Bonsoir,

Il faut 4 appels à la trieuse pour classer 5 éléments.
Si je me contente de trois appels pour 5 éléments je diminue les recours à 27-3=24
Avec application j'ai pythonisé l'algorithme qui me travaille.
Python, en un éclair, balaie l'algorithme et arrive avec succès au résultat attendu.

Je regarde à faire mieux encore.

A bientôt.

R.

renéb · 13-09-2025 21:29:44

bonsoir,

j'ai osé soumettre aux machines la proposition de Bernard-maths:

13 4 6 1 7
14 5 11 2 8
15 9 12 3 10
...
Tout va bien pour le tri en 27.
Pour le tri en 24 ça coince.
Pas très robuste.
Peut-être en 25?
Merci pour la trouvaille.

J'y retourne.

R.

Bernard-maths · 14-09-2025 07:26:18

Bonjour !

Puisque vous parlez de tri spatial, j'ai essayé de donner un tirage des 5 premiers avec le minimum de numéros "obligatoires" par lignes, soit 1 ou 2, après les tris des lignes. Ainsi on a :

1 4 6 7 13
2 5 8 11 14
3 9 10 12 15

Je verrai si je trouve mieux ...

Mais bravo pour cet essai en 27, mon exemple montre qu'il faut améliorer la méthode ...

En tout cas, moi avec 34, ça marche ... (;-)

B-m

Ernst · 21-09-2025 21:12:16

Bonjour,

Ce petit casse-tête est quand même bien sympathique. Voici en Python une série de 27 triplets qu'on peut appliquer de façon aveugle et qui fait le taf quelle que soit la distribution des 15 valeurs initiales

# === Paramètres ===

N = 15

D_values = [2,11,9,12,3,14,5,8,4,13,6,15,7,10,1]  # 15 valeurs quelconques

S = [

    [1,8,15],[2,9,14],[3,7,13],[4,10,12],[5,11,15],

    [1,6,10],[7,9,11],[1,4,7],[2,5,8],[8,12,14],

    [10,13,15],[11,12,13],[6,9,11],[3,5,6],[6,8,10],

    [1,2,3],[13,14,15],[5,6,7],[3,4,5],[7,8,9],

    [9,10,11],[11,12,13],[5,6,7],[2,3,4],[7,8,9],

    [9,10,11],[3,11,12]

]

bar = [None] + D_values  # base 1

print(" "); print(f"===== N : {N} ====="); print(" ")

for step, (i, j, k) in enumerate(S, start=1):

    print(f"{bar[1:]} <= {[i,j,k]}")

    trio = sorted([bar[i], bar[j], bar[k]])

    bar[i], bar[j], bar[k] = trio

    print(f"{bar[1:]} ({step})"); print(" ")

print("Barrette finale :", bar[1:], f"en {len(S)} étapes."); print(" ")

On lui propose n’importe quelle liste, on lance la moulinette et hop, c'est trié en 27 passages.

Ernst · 21-09-2025 21:17:24

Explications :

En fait j’ai pas mal galéré avec ces histoires de lignes et de colonnes, cela ne me plaisait qu’à moitié. Moi je triais les lignes d’abord, ça marchait mieux, mais une fois la récupération des valeurs extrêmes qui se distribuent assez simplement, j’arrivais à un méchant potage avec les valeurs centrales, contrariant.

Je suis donc passé à une approche différente qui consiste à trier les boules directement dans la barrette. J’ai décidé d’un programme qui allait faire un truc tout simple :
- choisir un petit nombre de boules
- mélanger
- faire la liste de tous les triplets possibles
- tous les essayer
- choisir celui qui permet la meilleure amélioration
- l’appliquer à la barrette
- et recommencer avec cette nouvelle distribution

Émerveillement, ça range, et ça range super vite ! L’étape suivante a consisté à augmenter le nombre de boules (7, 8, 9, 10…) et à augmenter aussi le nombre de barrettes (5, 10, 50, 100, 500…). Bingo, ça marchait toujours. De plus en plus lentement certes, des solutions de plus en plus longues aussi, solutions parfois différentes selon les mélanges mais ça marchait, et je suis tombé sur cet enchaînement.

Pour le moment, cette configuration a résisté à des milliards et des milliards de tirages différents, mais il faut bien reconnaître que cela reste insignifiant par rapport aux 15 ! = 1307674368000 distributions possibles.

Ceci dit, le programme fait de l’optimisation bourrin. Il est incapable de garder des tris légèrement moins bons même si les suivants pourraient faire mieux. Et puis pour l’heuristique, que faut-il privilégier, les bonnes places ? Les rapprochements ? Les groupes adjacents faciles à permuter ?

renéb · 21-09-2025 23:15:15

Bonsoir,

Rappelons-nous l’énoncé :
.

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 ?

L’intéressant, c’est d’imaginer les manipulations concrètes à entreprendre pour réaliser le classement complet.

Ernst a écrit :

On lui propose n’importe quelle liste, on lance la moulinette et hop, c'est trié en 27 passages.

(Je crois qu’il y a un dernier passage qui est resté dans la machine).

- faire la liste de tous les triplets possibles
- tous les essayer
- choisir celui qui permet la meilleure amélioration.

Ton approche, je crois, nécessite plus de 27 recours. Pourrais-tu nous en donner un ordre de grandeur ?

Pour ma part, j’explore la distribution des boules réparties sous différents formats de grille ; j’ai remarqué que pour sept boules il suffisait de cinq recours à l’appareil.
Je cogite, ça m'amuse.

A bientôt.

R

jpp · 22-09-2025 09:14:08

Salut ,

Je pense que si j'ai le droit de marquer les boules , 21 tests suffisent.

renéb · 22-09-2025 10:09:37

Bonjour,

j'ai 15 boules parfaitement identiques, indiscernables ni au toucher, ni à la "soupesée".

et doivent le rester, pas le droit de les marquer. juste l'appareil intervient pour les départager:

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

R.

Ernst · 22-09-2025 11:17:43

renéb a écrit :

(Je crois qu’il y a un dernier passage qui est resté dans la machine).

Bonjour,

Mon programme permet de tester une stratégie d’échange pour un nombre de boules donné. La plupart du temps on obtient des résolutions plus rapides, là j’ai choisi une distribution particulière qui n’était toujours pas triée à la 26ème étape. Voici, en condensé, la sortie du programme :

15 valeurs distinctes aux indices 1..15 :

[2,11,9,12,3,14,5,8,4,13,6,15,7,10,1]

on échange [1,8,15] et on obtient

[1,11,9,12,3,14,5,2,4,13,6,15,7,10,8](1)

on échange [2,9,14] et on obtient

[1,4,9,12,3,14,5,2,10,13,6,15,7,11,8](2)

on échange [3,7,13] et on obtient

[1,4,5,12,3,14,7,2,10,13,6,15,9,11,8](3)

on échange [4,10,12] et on obtient

[1,4,5,12,3,14,7,2,10,13,6,15,9,11,8](4)

on échange [5,11,15] et on obtient

[1,4,5,12,3,14,7,2,10,13,6,15,9,11,8](5)

on échange [1,6,10] et on obtient

[1,4,5,12,3,13,7,2,10,14,6,15,9,11,8](6)

on échange [7,9,11] et on obtient

[1,4,5,12,3,13,6,2,7,14,10,15,9,11,8](7)

on échange [1,4,7] et on obtient

[1,4,5,6,3,13,12,2,7,14,10,15,9,11,8](8)

on échange [2,5,8] et on obtient

[1,2,5,6,3,13,12,4,7,14,10,15,9,11,8](9)

on échange [8,12,14] et on obtient

[1,2,5,6,3,13,12,4,7,14,10,11,9,15,8](10)

on échange [10,13,15] et on obtient

[1,2,5,6,3,13,12,4,7,8,10,11,9,15,14](11)

on échange [11,12,13] et on obtient

[1,2,5,6,3,13,12,4,7,8,9,10,11,15,14](12)

on échange [6,9,11] et on obtient

[1,2,5,6,3,7,12,4,9,8,13,10,11,15,14](13)

on échange [3,5,6] et on obtient

[1,2,3,6,5,7,12,4,9,8,13,10,11,15,14](14)

on échange [6,8,10] et on obtient

[1,2,3,6,5,4,12,7,9,8,13,10,11,15,14](15)

on échange [1,2,3] et on obtient

[1,2,3,6,5,4,12,7,9,8,13,10,11,15,14](16)

on échange [13,14,15] et on obtient

[1,2,3,6,5,4,12,7,9,8,13,10,11,14,15](17)

on échange [5,6,7] et on obtient

[1,2,3,6,4,5,12,7,9,8,13,10,11,14,15](18)

on échange [3,4,5] et on obtient

[1,2,3,4,6,5,12,7,9,8,13,10,11,14,15](19)

on échange [7,8,9] et on obtient

[1,2,3,4,6,5,7,9,12,8,13,10,11,14,15](20)

on échange [9,10,11] et on obtient

[1,2,3,4,6,5,7,9,8,12,13,10,11,14,15](21)

on échange [11,12,13] et on obtient

[1,2,3,4,6,5,7,9,8,12,10,11,13,14,15](22)

on échange [5,6,7] et on obtient

[1,2,3,4,5,6,7,9,8,12,10,11,13,14,15](23)

on échange [2,3,4] et on obtient

[1,2,3,4,5,6,7,9,8,12,10,11,13,14,15](24)

on échange [7,8,9] et on obtient

[1,2,3,4,5,6,7,8,9,12,10,11,13,14,15](25)

on échange [9,10,11] et on obtient

[1,2,3,4,5,6,7,8,9,10,12,11,13,14,15](26)

on échange [3,11,12] et on obtient

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15](27)

Barrette finale triée en 27 étapes.

Je ne vois pas trop où se perdrait un passage. Par ailleurs on peut bien sûr changer la distribution dans le programme histoire de tester du moment qu'elle contienne quinze valeurs numériques séparées par des virgules, perso je n'en ai pas trouvée une seule qui resistait à cette séquence.

Forum de mathématiques - Bibm@th.net

#26 07-09-2025 17:57:50

Re : 15 boules à classer

#27 07-09-2025 19:39:26

Re : 15 boules à classer

#28 07-09-2025 20:05:11

Re : 15 boules à classer

#29 08-09-2025 13:54:49

Re : 15 boules à classer

#30 08-09-2025 14:59:59

Re : 15 boules à classer

#31 08-09-2025 15:24:13

Re : 15 boules à classer

#32 08-09-2025 17:54:39

Re : 15 boules à classer

#33 08-09-2025 18:29:50

Re : 15 boules à classer

#34 08-09-2025 21:28:14

Re : 15 boules à classer

#35 09-09-2025 09:14:50

Re : 15 boules à classer

#36 09-09-2025 10:03:46

Re : 15 boules à classer

#37 09-09-2025 14:49:24

Re : 15 boules à classer

#38 09-09-2025 16:42:55

Re : 15 boules à classer

#39 09-09-2025 18:51:06

Re : 15 boules à classer

#40 12-09-2025 17:16:47

Re : 15 boules à classer

#41 12-09-2025 17:28:36

Re : 15 boules à classer

#42 13-09-2025 18:41:10

Re : 15 boules à classer

#43 13-09-2025 21:29:44

Re : 15 boules à classer

#44 14-09-2025 07:26:18

Re : 15 boules à classer

#45 21-09-2025 21:12:16

Re : 15 boules à classer

#46 21-09-2025 21:17:24

Re : 15 boules à classer

#47 21-09-2025 23:15:15

Re : 15 boules à classer

#48 22-09-2025 09:14:08

Re : 15 boules à classer

#49 22-09-2025 10:09:37

Re : 15 boules à classer

#50 22-09-2025 11:17:43

Re : 15 boules à classer

Réponse rapide

Pied de page des forums