Forum de mathématiques - Bibm@th.net

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

A faire perdre la boule à totomn !!!

Salut,

trouvé sur le net (merci à Ch. R)  : 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 ?

Dernière modification par freddy (02-01-2012 20:42:28)

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : A faire perdre la boule à totomn !!!

Bonjour,

Voila qui va compléter les algorithmes de tri présentés dans le forum programmation...
Suspense : Les comparaisons ternaires vont-elles l'emporter sur les comparaisons binaires ?

Cordialement

nerosson

Membre actif

Inscription : 21-03-2009

Messages : 1 658

Re : A faire perdre la boule à totomn !!!

Salut à tous,

Le cancre de service à l'appareil.

J'ai trouvé une solution. Elle n'est surement pas la meilleure. Elle a seulement le mérite de fonctionner. Elle implique un nombre de consultations qui peut varier (en fonction de la chance) entre 13 et 91.

Question subsidiaire : comment ai-je trouvé ces deux nombres ?

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Salut,

au pire, j'en ai 49, donc on doit pouvoir faire mieux.

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

salut
c'est possible avec au plus 27 classements  .

Dernière modification par amatheur (03-01-2012 21:24:08)

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Re,

tu nous montrerais comment tu fais, stp ?

Merci.

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

SALUT

▼solution

 
je vais procéder de la manière suivante: avec 5 challenges, je classe les boules en 5 groupes de trois, que je numérote de 1 à 5.
je prend la boule de poids moyen du groupe 2 et je la test avec les deux plus lourdes boules  du G1, si elle arrive seconde alors avec deux autres tests je peux classer les 2 autres boules du G2, sinon si elle est  la plus ou la moins lourde , je pourrais encore placer les 2 autre boules avec seulement 2 autres testes maximum, au total j' arriverai à former un groupe de 6 classés selon leurs poids avec 3 testes ( en plus des 5 de départ).

je continue à procéder ainsi avec le groupe 3, je testerai sa boule moyenne avec la troisième et le quatrième boules du groupe de 6 que je viens de former(G1+G2), et au pire des cas, je pourrai placer les trois boules du G3 avec 5 tests; j'aurais ainsi un groupe de neuf, de la même manière je continue à ajouter les boules du groupe 4 puis 5 en commençant toujours par tester leurs boules de poids moyen avec les boules de poids "médian" des groupes de 9 (respectivement de 12) , ainsi je pourrai placer les boules du G4 EN 7 tests et aussi les boules du G5 en 7 tests maximum aussi. au total,j'utiliserai au plus 27 tests

Dernière modification par amatheur (04-01-2012 01:55:04)

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : A faire perdre la boule à totomn !!!

Bonjour,

Pour le fun,  48 opérations maximum.

A mon avis je suis sur la même piste que Freddy (55-6) mais je me passe de la dernière => 49-1=48.

Je cherche encore si "peux mieux faire ".

A+-*/

---

Qui trouve, cherche.

jpp

Membre

Inscription : 31-12-2010

Messages : 1 105

Re : A faire perdre la boule à totomn !!!

bonsoir.

▼une solution

pour classer n boules il y a n! façons possibles   et comme on compare 3 boules à chaque fois , à la p^ème pesée , on doit  avoir 3^p solutions possibles . et si 3^p > n! , p  doit alors etre suffisant pour
ordonner les n boules .

ex.  n = 4  -->  p = 3  car  3³> 4!     27> 24

ex.  n = 5  -->  p = 5  car  3⁵> 5!     243 > 120

ex.  n = 6  -->  p = 6  car   3⁶> 6!    729 > 720

  alors  si 3^p> n!    [tex]\ln{(3^p)}> \ln{(n!)}[/tex]  -->  [tex]p > \frac{\ln{(n!)}}{\ln{3}}[/tex]

donc si n=15  en comparant méthodiquement  [tex] p > \frac{\ln{(15!)}}{\ln{3}}[/tex] [tex]  --> p> 25.395[/tex]

avec 26 pesées on doit toujours etre en mesure d'ordonner les 15 boules.

on a comparé les 3 premières boules  : on obtient  1-2-3  , en amenant  4 et 5 pour les comparer à  2 , au pire on a 4-2-5  et il faut 2 autres pesées  qui totaliseront 5    le classement se trouve etre  1-4-2-3-5 par exemple
ensuite  je compare  6 et 7 avec la boule médiane 2  : au pire on me rend  6-2-7 ;  cela me donne 8 pesées...

  et  [tex]8 >\frac{\ln{(7!)}}{\ln{3}} [/tex]

on peux sans doute aller comme ça jusqu'au bout.

Dernière modification par jpp (06-01-2012 01:05:39)

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

salut
@ JPP, cela fait 2 jours que je cherche une solution générale au problème, c'est l’inégalité qui me manquait, je n'y avais pas du tout pensé, BRAVO!

Dernière modification par amatheur (06-01-2012 02:00:28)

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

jpp

Membre

Inscription : 31-12-2010

Messages : 1 105

Re : A faire perdre la boule à totomn !!!

Salut .

@amatheur , rassures toi , avec ma méthode j'ai le meme nombre que toi , je n'ai pas réussi , pour l'instant à descendre en dessous , parce que la formule donne p=5  pour 5 boules alors que 4 à l'air de suffir dans le pire des cas.

donc on est en droit de penser que pour certains nombres , il faudrait arrondir au deuxième entier supérieur.

ou alors il y aurait peut-etre une stratégie plus subtile encore. je vais donc continuer à chercher.

                                                                                    à plus.

jpp

Membre

Inscription : 31-12-2010

Messages : 1 105

Re : A faire perdre la boule à totomn !!!

bonjour.

je crois que j'ai fait une erreur avec les permutations

▼parce que

15! = 1307674368000  , mais lorsque l'on compare 3 boules on divise par 6 et non par 3 le nombre de permutations . si bien que lorsque je compare  1-2-3 , 4-5-6 , 7-8-9 , 10-11-12 , 13-14-15 , il ne me reste
plus que [tex]\frac{15!}{3!^5} = 168168000[/tex]permutations possibles

donc la formule générale serait plutot   [tex] p > \frac{\ln15!}{ln6}--->  p>15.57 ---> p = 16[/tex]

en 5 pesées j'obtiens 5 triplets ordonnés et je les notes dans l'ordre comme ci dessus .
après je compare  1 , 4 , 7  -->  j'obtiens par exemple  1 - 7 - 4

         je compare aussi  1 , 10 , 13 --> j'obtiens par exemple  10 - 1 - 13

  si je compare  7 , 13 & 4    je sais déjà que 7 est avant 4  . je vais donc remplacer 7 par 8 et comparer 13 , 8 , 4
  j'obtiens par exemple  13 - 8 - 4
  je peux  écrire provisoirement  10 , 11 , 12 , 1 , 2 , 3 , 7 , 13 , 14 , 15 , 8 , 9 , 4 , 5 , 6   après  8 pesées.

ainsi  le 9 doit suivre le 8 et rester à sa droite.
après je peux comparer les secondes boules de 3 triplets  , par exemple  11 , 2 , 14   en sachant que  12 , 3 & 15
doivent rester respectivement à droite de chacune d'elle. et j'obtiens par exemple  11 - 2 -14

je peux écrire alors 10 , 1 , 11 , 12 , 2 , 3 , 7 , 13 , 14 , 15 , 8 , 9 , 4 , 5 , 6   après  9 pesées.

pour l'instant j'ai 9 triplets ordonnés:
               1-2-3 , 4-5-6 , 7-8-9 , 10-11-12 , 13-14-15 , 1-7-4 , 10-1-13 , 13-8-4  et enfin 11-2-14  que je retrouve dans mon ordonnancement . il me faut trouver un dixième triplet qui soit encore libre de ses 6 permutations afin de diviser par 6 le nombre de permutations qu'il me reste. je pense que  12 , 3 , 7 peut convenir , j'obtiens 12-7-3.
qui me donne un nouveau classement :

              10 , 1 , 11 , 12 , 2 , 7 , 3 , 13 , 14 , 15 , 8 , 9 , 4 , 5 , 6    après  10 pesées  il ne doit me rester que :

[tex]\frac{15!}{3!^{10}} \approx 21627[/tex] permutations possibles.

le triplet 15 , 9 & 3 a encore ses 6  permutations possibles  , j'obtiens par exemple  9 - 3 -15

ce qui me donne :  10 , 1 , 11 , 12 , 2 , 7 , 13 , 14 , 8 , 9 , 3 , 15 , 4 , 5 , 6    et je n'ai plus que 3605 permutations après 11 pesées.

je ne sais pas si je me suis placé dans le pire des cas  , car apparemment il me reste à ordonner 1, 11   ;  12,2   ;
7 , 13   ;  14 , 8    &  15 , 4  .   alors en 6 pesées car 15 a encore une liberté :

1 , 11 , 12 ( 12 est après 11)  ,  12 , 2 , 7 ( 7 est après 12)  ,   7,13,14 ( 14 est après 13)  ,  14,8,9 ( 9 est après 8)

  15 , 4 , 5   et  15 , 5 , 6 car  15 peut encore etre intercalé entre 5 & 6  ou se trouver dernier

j'obtiens par exemple  11-1-12  ;  2-12-7  ;  13-7-14  ;   8-14-9  ;   4-5-15   ; 5-15-6   .  ce qui me donne:

                      10 - 11 - 1 - 2 - 12 - 13 - 7 - 8 - 14 - 9 - 3 - 4 - 5 - 15 - 6   après 17 pesées .

mais on peut sans doute faire mieux

(...)

Dernière modification par jpp (07-01-2012 21:44:25)

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

SALUT

▼solution

 
je vais procéder de la manière suivante: avec 5 challenges, je classe les boules en 5 groupes de trois, que je numérote de 1 à 5.
je prend la boule de poids moyen du groupe 2 et je la test avec les deux plus lourdes boules  du G1, si elle arrive seconde alors avec deux autres tests je peux classer les 2 autres boules du G2, sinon si elle est  la plus ou la moins lourde , je pourrais encore placer les 2 autre boules avec seulement 2 autres testes maximum, au total j' arriverai à former un groupe de 6 classés selon leurs poids avec 3 testes ( en plus des 5 de départ).

je continue à procéder ainsi avec le groupe 3, je testerai sa boule moyenne avec la troisième et le quatrième boules du groupe de 6 que je viens de former(G1+G2), et au pire des cas, je pourrai placer les trois boules du G3 avec 5 tests; j'aurais ainsi un groupe de neuf, de la même manière je continue à ajouter les boules du groupe 4 puis 5 en commençant toujours par tester leurs boules de poids moyen avec les boules de poids "médian" des groupes de 9 (respectivement de 12) , ainsi je pourrai placer les boules du G4 EN 7 tests et aussi les boules du G5 en 7 tests maximum aussi. au total,j'utiliserai au plus 27 tests

Salut,
je cherche toujours une méthode optimale, et je me sers de la suite ci après comme test.
15 14 13 12 ... 3 2 1

J'ai testé ta méthode (qui est un classement par insertion). Après insertion des 4 premiers groupes et  sauf erreur, j'en suis déjà à 25 tests, et le dernier groupe nécessite bien plus de 2 tests.

J'espère m'être trompé ... ,, sinon il faut encore chercher. Sorry

PS : je fais comme toi pour la première série de classement, ensuite j'essaie d'utiliser d'autres techniques.

Dernière modification par freddy (08-01-2012 03:05:13)

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

bonjour.
@jpp; c'est moi qui va finir par perdre la boule!! je n'ai rien pigé dans ta dernière papinade! j'avoue aussi que mon analyse combinatoire commence sérieusement à se faire vieille ' même nersosson pourrait se vanter d’être plus jeune qu'elle", et qu'elle a besoin d'un bon rafraichissement, donc à moi les urnes!
A+

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : A faire perdre la boule à totomn !!!

Bonjour,

Je trouve une façon de classer les 15 boules après 33 passages dans la trieuse et quelques manipulations intermédiaires.

▼33 tris

Trois groupes de 5 boules.
Quatre tris pour classer 5 boules:                     4 * 3 = 12

Je les alignes en trois tas de 5 boules.

Je trie chaque colonne de la plus légère à la plus lourde.            =5

Je retire la boule haut gauche qui est la plus légère de toutes et la place à l’extrême gauche de la « rigole  solution » .
Je retire la boule droite bas qui est la plus lourde et la place à l’extrême droite de la « rigole  solution » ..
Je décale le premier tas de 2 colonnes vers la gauche.
Je décale le troisième tas de 2 colonnes vers la droite.

O          O              O              O

            O              O              O              O             O

                                              O                   O              O              O

Je trie les trois diagonales (à partir de la deuxième boule premier tas) de la plus légère à la plus lourde.
                                        =3

Je prends les 5 boules à gauche des trois boules verticales et les trie par ordre croissant.
                                        =4
J'enlève les 3 premières boules (qui sont déjà triées par ordre croissant) et les pose à droite de la plus légère sur la « rigole solution ».
Je prends les 5 boules à droite des trois boules verticales et les trie par ordre croissant.
                                        =4
J'enlève les 3 dernières boules (qui sont déjà triées par ordre croissant) et les pose à gauche de la plus lourde sur la « rigole solution »..

Les deux boules à gauche des trois boules verticales sont jointes à celle-ci et triées et placée à la suite des boules de droite sur la « rigole solution ». .
                                        =4
Les trois boules restantes sont triées complète l'ensemble des 15 boules ainsi triées.
                                        =1

                                TOTAL:    =33

J'ai essayé les configurations les plus originales (par ordre croissant ou décroissant verticalement, horizontalement) et ça marche.
Maintenant démontrer la logique sous-tendue...  Bof bof!

A+-*/

---

Qui trouve, cherche.

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

salut

▼rectification

je viens de réaliser que l'on pourrait placer les boules du G4 en 6 tests seulement, ce qui ramène la totale à 26 tests

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

re

▼petite amélioration

après avoir construit les trois groupes de 5, au lieu d'ajouter les boules les une après les autres,  je vais prendre trois groupes, je compare les plus lourdes, les moyennes et les plus légères entre elles en trois tests, puis avec 4 autres tests  au maximum, j’ordonne la totalité des 9 boules , ainsi je forme le groupe de 9 avec 7 tests " au lieu de 8 précédemment, pour le reste des boules, je continue comme avant. ce qui ramène la totale à 25 tests.   

Dernière modification par amatheur (08-01-2012 20:19:32)

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : A faire perdre la boule à totomn !!!

Bonsoir,

@ amatheur:

Je prends connaissance de ta démarche:

je vais procéder de la manière suivante: avec 5 challenges, je classe les boules en 5 groupes de trois, que je numérote de 1 à 5.
je prend la boule de poids moyen du groupe 2 et je la test avec les deux plus lourdes boules  du G1, si elle arrive seconde alors avec deux autres tests je peux classer les 2 autres boules du G2, sinon si elle est  la plus ou la moins lourde , je pourrais encore placer les 2 autre boules avec seulement 2 autres testes maximum, au total j' arriverai à former un groupe de 6 classés selon leurs poids avec 3 testes ( en plus des 5 de départ).

J'ai du mal à te suivre; pourrais-tu éclairer ma lanterne?

Mettons qu'on numérote les boules selon leur poids
Voici un premier classement en 5 groupes de trois boules:

    1        2        9
   
    3        4        13

    5        8        12

    6        10        15

    7        11        14

Je prends la boule « 10 » du groupe 2
Je la teste avec les boules « 11 et 14 » du groupe 1.

Après triage:

    10        11        14

Comment fais-tu pour qu'en 2 tests tu puisses placer les boules « 6 et 15 » et arriver à ceci ?

    6        7        10        11        14        15

J'ai essayé mais vainement.

A+-*/

Dernière modification par karlun (08-01-2012 21:09:09)

---

Qui trouve, cherche.

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

salut
eh bein tu compare la 11, la 14 et la 15 puis 6 la 7 et la 10 dans un autre test. ok!

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : A faire perdre la boule à totomn !!!

re,

Eh oui !!!

Evidemment dit comme cela...:-)

Merci.

A+-*/

---

Qui trouve, cherche.

amatheur

Membre

Inscription : 03-10-2011

Messages : 299

Re : A faire perdre la boule à totomn !!!

salut
@karlun, au fait je viens de revérifier l'algorithme de formation du groupe de 6, et  je me suis aperçu que certaines configurations ont besoin de 4 tests, donc tu avais raison, je dois revoir toute la méthode en détail!
A+

Dernière modification par amatheur (08-01-2012 21:48:17)

---

J'aimais les fées et les princesses,
Qu'on me disait n'exister pas..

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Bonjour,

Je trouve une façon de classer les 15 boules après 33 passages dans la trieuse et quelques manipulations intermédiaires.

▼33 tris

Trois groupes de 5 boules.
Quatre tris pour classer 5 boules:                     4 * 3 = 12

Je les alignes en trois tas de 5 boules.

Je trie chaque colonne de la plus légère à la plus lourde.            =5

Je retire la boule haut gauche qui est la plus légère de toutes et la place à l’extrême gauche de la « rigole  solution » .
Je retire la boule droite bas qui est la plus lourde et la place à l’extrême droite de la « rigole  solution » ..
Je décale le premier tas de 2 colonnes vers la gauche.
Je décale le troisième tas de 2 colonnes vers la droite.

O          O              O              O

            O              O              O              O             O

                                              O                   O              O              O

Je trie les trois diagonales (à partir de la deuxième boule premier tas) de la plus légère à la plus lourde.
                                        =3

Je prends les 5 boules à gauche des trois boules verticales et les trie par ordre croissant.
                                        =4
J'enlève les 3 premières boules (qui sont déjà triées par ordre croissant) et les pose à droite de la plus légère sur la « rigole solution ».
Je prends les 5 boules à droite des trois boules verticales et les trie par ordre croissant.
                                        =4
J'enlève les 3 dernières boules (qui sont déjà triées par ordre croissant) et les pose à gauche de la plus lourde sur la « rigole solution »..

Les deux boules à gauche des trois boules verticales sont jointes à celle-ci et triées et placée à la suite des boules de droite sur la « rigole solution ». .
                                        =4
Les trois boules restantes sont triées complète l'ensemble des 15 boules ainsi triées.
                                        =1

                                TOTAL:    =33

J'ai essayé les configurations les plus originales (par ordre croissant ou décroissant verticalement, horizontalement) et ça marche.
Maintenant démontrer la logique sous-tendue...  Bof bof!

A+-*/

Salut et chapeau, je pense que c'est parfait.

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

Re,

mais on devrait pouvoir faire un peu mieux !

---

De la considération des obstacles vient l’échec, des moyens, la réussite.

karlun

Membre

Inscription : 05-05-2010

Messages : 216

Re : A faire perdre la boule à totomn !!!

Bonsoir,

J'y ai pensé également pendant la journée.

J'ai regardé ce soir et....

▼31 tris

Au lieu de "Les deux boules à gauche des trois boules verticales sont jointes à celle-ci et triées..." on se contente de trier les trois boules verticales (la plus légère en haut) ensuite les deux boules à gauche sont jointes à la plus légère des trois verticales et triées idem pour les deux boules de droite jointe à la plus lourde des verticales.

On économise ainsi 2 tris.

Dernière modification par karlun (09-01-2012 23:44:34)

---

Qui trouve, cherche.

freddy

Membre chevronné

Lieu : Paris

Inscription : 27-03-2009

Messages : 7 457

Re : A faire perdre la boule à totomn !!!

try again !

---

De la considération des obstacles vient l’échec, des moyens, la réussite.