A faire perdre la boule à totomn !!!

jpp · 11-02-2012 15:07:12

salut.

je repare sur la matrice 5 lignes et 3 colonnes .

je teste les 5 lignes en 5 coups. après je teste les 3 colonnes en 3 fois 4 coups ---> total 17

ma boule la plus légère que j'appelle 1 est dans le coin supérieur gauche , et ma boule la plus lourde 15 est dans le coin inférieur droit.

18) je teste les 3 boules qui terminent chaque colonne et je sors la 14
19) je teste les trois boules qui commencent chacune des 3 colonnes et je sors la boule 2
je sors la 3 la 13 en 21 coups et il me reste les 9 boules centrales et je recommence avec une matrice 3 x 3

en 6 coups je place les 3 lignes et les 3 colonnes et je sors la 4 et la 12 au 27 eme coup

et à chaque coup jusqu'aux 3 dernieres je sors chacune d'elle. donc en 32 coups car je ne sais pas si les 3 dernieres

sont ordonnées après le 31ème coup. je pars sur 32.

finalement je viens de me rendre compte qu'après avoir sortie les boules 1 ,2 , 3 , 13 , 14 & 15 il me restait une colonne de 3 boules ordonnées . alors pour composer ma nouvelle matrice de 3 x 3 il me reste à coller 2 autres colonnes de 3 boules . donc après 21 tests je teste les 2 colonnes non ordonnées de ma matrice et les 3 lignes en 5 tests . ce qui me fait 26 tests qui me donne aussitot la boule 4 dans le coin supérieur gauche et la boule 12 dans le coin inférieur droit.

le test 27 me donne la 5 , le test 28 me donne la 11 , le test 29 me donne la 10 , le test 30 me donne la 6 et il me reste les 3 dernière boules à tester au test 31 pour ordonner les boules 7 , 8 & 9.

@Karlun Bravo !! and don't try again .

à plus.

Dernière modification par jpp (11-02-2012 17:34:27)

jpp · 12-02-2012 11:05:02

salut.

j'essaie une démo en 28 coups.

je donne le plan de ma matrice [tex]\begin{matrix}a&b&c\\d&e&f\\g&h&i\\j&k&l&\\m&n&o\end{matrix}[/tex]

je range pour avoir la plus légère en a et la plus lourde en o

en 5 coups j'ordonne mes 5 lignes. et en 3 fois 4 coups j'ordonne mes 3 colonnes.

ce qui me permet de sortir les boules 1 & 15 en 17 tests

Plusieurs remarques. 1°) ma boule 2 se situe obligatoirement en b ou en d

2°) ma boule 3 se situe obligatoirement en g , b , d ou c

3°) ma boule 14 se situe obligatoirement en l ou n

4°) ma boule13 se situe obligatoirement en m , n , l ou i

si je commence par les boules légères , alors je sors 3 boules parmi g,b,d & c et j'obtiens la boule 2
puis je recommence pour sortir la boules 3 . ce qui me donne 19 tests

Mais , à ce stade il me reste 2 boules plus lourdes qui sont ordonnées et je les compare en 2 tests aux boules

e & j et j'obtiens 4 boules ordonnées. après 21tests . je les place dans un coin.

Maintenant , symétriquement à la boule centrale h j'effectue les memes mouvements avec les boules lourdes,
en appliquant la meme logique. ce qui me fait 4 tests supplémentaires et porte le nombre à 25 tests.

Dans le camp des boules lourdes j'ai donc aussi 4 boules ordonnées
soit: 6 boules déjà sorties , 2 groupes de 4 boules ordonnées . Il ne me reste dans la matrice que ma boule centrale h

Une dernière remarque : dans la matrice , la boule centrale ne peut etre 5 < h < 11 de part l'ordonnancement de la matrice.
ce qui veut dire que dans mon groupe ordonné de 4 boules légères et mon groupe ordonné de 4 boules lourdes je peux sortir les boules 4 , 5 , 11 & 12

conclusion: après 25 tests , il me reste 2 paires de boules ordonnées + la boule centrale h . En 3 tests supplémentaires je dois pouvoir les ordonner. ce qui porte à 28 tests l'ordonnancement des 15 boules.

Si je n'ai pas fait d'erreur.
à plus.

Dernière modification par jpp (12-02-2012 12:00:35)

karlun · 12-02-2012 17:41:47

Bonsoir,

J'ai regardé ta solution jpp et elle me semble sans faille. Bravo !

Pourtant http://www.bibmath.net/forums/viewtopic … 942#p33942

Alors j'ai encore cherché et cherche encore; pffff!

A+-*/

jpp · 12-02-2012 19:45:44

re.

@karlun en faitje crois que la dernière phase ou il me reste les 5 boules 6 , 7 , 8 , 9 & 10 quelque soit la boule centrale je dois ordonner en 2coups seulement.

par exemple cette situation h = 10 et les couples ordonnés 6 , 8 & 7 , 9 alors j'ai juste à comparer la boule centrale avec la plus légère du groupe des boules légères et la plus lourde du groupe des boules lourdes et il me reste à comparer la boule centrale résultante avec les 2 autres.

ce qui me fait 27 tests au lieu de 28

freddy · 12-02-2012 20:53:00

Hallo,

ein wenig, zu viel !

jpp · 13-02-2012 09:49:08

SALUT.
en fait j'ai fait 2 memes erreurs avec 4 boules dont 2 ordonnées qui se rangent en 2 tests.

au final on a besoin de 25 tests .

à plus.

freddy · 13-02-2012 11:55:06

Salut,

comme on disait quand on était petit : "c'est chaud ! " ...

Dernière modification par freddy (13-02-2012 11:56:21)

amatheur · 13-02-2012 16:03:38

salut
bravo jpp, belle méthode.
@freddy, c'est combien le "god number" du problème?

jpp · 13-02-2012 18:04:49

re.

ce n'est pas fini , c'est moins encore . Il faut que je descendre à 24. je crois.

freddy · 13-02-2012 18:38:58

amatheur a écrit :

salut
bravo jpp, belle méthode.
@freddy, c'est combien le "god number" du problème?

Meiner Ansicht nach, drei und zwanzig !

amatheur · 13-02-2012 22:22:35

re
mes méninges partiront en fumée bien avant que je ne puisse l'atteindre!
Mais bon, "A chaque coffre sa clé,On les ouvrira tous".
A+

amatheur · 14-02-2012 01:57:10

re
en parcourant quelques articles sur les algorithmes de tri, ils font toujours remarquer que parfois, un usage combiner et astucieux de deux algorithmes différents pourrait faire mieux que chacun des algorithmes pris à lui seul, alors je me demande si on pourrait combiner deux ou plusieurs des méthodes utilisées jusqu'ici pour faire mieux!
@jpp+karlun; ça vous dit quelque chose?
@freddy; ton challenge m'a vraiment énervé, à cause de toi, it's no sleep land this night!

jpp · 14-02-2012 20:04:10

salut.

je cherche avec une matrice 3 x 3 ordonnée en 6 coups pour les lignes et les colonnes puis une ligne de 6 boules ordonnées en 7 coups .

mais tantot , je croyait bien tenir le bon bout , mais j'ai vite déchanté .

on peut remarquer quand meme qu'en 13 coups on a , soit la plus lourde , soit la plus légère . Mais ça c'est un choix.

donc je continue de cogiter sur cette méthode.

à plus.

jpp · 15-02-2012 13:51:59

salut à tous.

je reviens avec ma matrice 3 x 5
[tex]\begin{matrix}a&b&c\\d&e&f\\g&h&i\\j&k&l\\m&n&o\end{matrix}[/tex]

a) je commence par ordonner les 3 colonnes en 3 fois 4 coups. Ce qui donne 12 coups.

b) contrairement à ma dernière démo , je n'ordonne que les première & dernière lignes de façon à sortir les 2 boules extrèmes 1 & 15

donc en 14 coups j'ai sorti 2 boules.

c) ensuite je teste la diagonale g , e , c en remarquant :que b est plus légère que e & c
: que d est plus légère que e & g

d) je n'ai donc plus qu'à comparer b , d et la plus légère de ma diagonale g , e , cpour sortir les 2 boules 2 & 3 et il me reste un triplet ordonné avec 3 boules
parmi b , d , g , e & c

j'en suis donc à 16 coups .

e) j'applique la meme méthode par symétrie avec les boules lourdes . et en 18 coups j'ai sorti les 6 boules 1 , 2 , 3 , 13 , 14 & 15 et il me reste 9 boules à ordonner.

f) je me retrouve avec un second triplet ordonné parmi les 5 boules m , k , i , n & l
g) je teste la diagonale centrale j , h , f et j'obtiens mon 3^ème triplet ordonné

je me trouve donc avec une matrice 3 x 3 avec 3 colonnes ordonnées après 19 tests.

h) en 2 coups supplémentaires j'ordonne ma 1ere et ma 3eme ligne. et je sors les boules 4 & 11

i) meme méthode en testant ma diagonale au 21eme test et avec 2 tests de plus , je place toutes les boules dans l'ordre.en utilisant les remarque du d). donc 23tests

à plus

(....)

Dernière modification par jpp (15-02-2012 14:13:34)

amatheur · 15-02-2012 14:23:14

salut
@jpp: dans l'étape c tu affirmes que d est plus légère que e, je ne vois pas comment tu fais!

Dernière modification par amatheur (15-02-2012 14:25:45)

jpp · 15-02-2012 15:25:02

re.

autant pour moi je voulais dire : au pire la boule 3 est sur la diagonale g e cdonc elle va sortir.

je revois ma copie. il y a un blème.

Dernière modification par jpp (15-02-2012 15:45:05)

amatheur · 15-02-2012 19:49:53

salut
une deuxième remarque, si la boule 3 est le min(g,e,c) tu n'auras pas un triplet ordonné.
moi j aurais testé d; e; c puis selon les cas, d: b: g; même si dans le pire des cas, ça fait pareil que ta méthode.

jpp · 15-02-2012 20:37:15

re.

je modifie ma stratégie. pour 23 coups.
[tex]\begin{matrix}a&b&c\\d&e&f\\g&h&i\\j&k&l&\\m&n&o\end{matrix}[/tex]

a) j'ordonne partiellement ma première colonne en 3 coups mais en tirant vers le haut les boules légères c.a.d. qu'au second test , je compare la quatrième avec les 2 plus légères et au troisième test je compare la cinquième avec les 2 plus légères. 3 coups

b) j'ordonne entièrement la seconde colonne en 4 coups

c) symétriquement à la première colonne , j'ordonne partiellement ma troisième colonne en tirant vers le bas les boules lourdes. en 3 coups . TOTAL : 10 coups

d) je teste une par une mes 5 lignes en 5 coups ---> total = 15 coups je peux sortir les boules extrèmes

e) j'ordonne toujours ma diagonale g , e , c qui me donne mes boules 2 , 3 & 4 aux emplacements g , d , b que je teste à leur tour ---> total:17 coups

Une remarque: je sors mes 3 boules mais je conserve mon couplé ordonné en e , c

f) j'ordonne la diagonale m , k , i qui me donne mes boules 12 , 13 , 14 en n , l & i et que je teste à leur tour. ---> total : 19 coups

Une remarque: je sors mes 3 boules lourdes 12 , 13 & 14 mais je conserve mon couplé ordonné en m , k

g) j'ordonne ma diagonale centrale j , h , f total : 20 coups.

Il me reste 2 couplé ordonnés et un triplet central ordonné. e , c , j , h , f et m , k

h) en 3 coups je dois pouvoir les ordonner . pour cela je teste d'abord c , j , h puis les 2 plus lourdes de ce test avec m et pour finir , à nouveau les nouvelles boules centrales pour ordonner les boules 7 , 8 & 9

total:23 coups

j'ai tester plusieurs fois et ça a l'air de fonctionner . il y a meme des cas ou en 20 coups c'est règlé.

mais je vais poursuivre les expériences pour voir s'il n'y a pas une faille quelquepart.

en effet je ne peux sortir que 2 & 3 et 13 & 14 car 1,2,3 & 4 peuvent se situer sur la meme colonne.

à plus.

Dernière modification par jpp (15-02-2012 21:29:58)

amatheur · 17-02-2012 00:28:59

salut
@jpp: deux trucs m'échappent:
-étape d: comment arrives-tu à sortir les boules extrêmes alors que n'as pas totalement ordonné la première et la troisième colonnes?
-étape e: pourquoi ton raisonnement suppose que c est la boule la plus légère de la troisième colonne?
A+

Dernière modification par amatheur (17-02-2012 01:58:20)

jpp · 17-02-2012 07:19:37

salut à tous.

@amatheur. j'avais rajouté mes 2 dernières lignes parce que j'ai bien vu que la méthode n'était pas démontrée dans 100% des cas . t'inquiète , je continue à chercher et c'est pas une mince affaire. avec freddy , les transferts de boules , ça se règle pas en 5 mn . mais on l'aura un jour .. on l'aura . nous sommes des teignes. Et quand on est dessus...

à plus.

Dernière modification par jpp (17-02-2012 07:22:59)

amatheur · 18-02-2012 02:48:49

salut
absolument!

jpp · 18-02-2012 16:16:27

salut.

je me demande si on doit ranger les boules sur les lignes ou sur les colonnes ; à moins qu'il faille définir une liste de 23 triplets qui sera nécessaire et suffisante pour que quelque soit la position de chacune des 15 boules sur la matrice ou peut-etre sur une autre géomètrie comme le triangle ou le carré écorné 4 x 4 -1 , on obtienne un ordonnancement parfait des 15 boules .

Pour ça je pense à un truc que je vais exploiter. Je duplique ma matrice 3 x 5 et je l'éparpille façon puzzle comme ceci:

[tex]\begin{matrix}a&b&c&a&b&c&a&b&c\\d&e&f&d&e&f&d&e&f\\g&h&i&g&h&i&g&h&i\\j&k&l&j&k&l&j&k&l\\m&n&o&m&n&o&m&n&o\\a&b&c&a&b&c&a&b&c\\d&e&f&d&e&f&d&e&f\\g&H&i&g&H&i&g&h&i\\j&k&L&j&k&l&j&k&l\\M&n&o&m&n&o&m&n&o \end{matrix}[/tex]

à partir du point M je vais tracer toutes les droites passant par la plus proche des boules dans la matrice d'origine 3 x 5. ça me rappelle un autre problème récemment posé.

ces droites ont pour coefficients directeur [tex] 0 , \frac12 , 1 , \frac32 , 2 , 3 et 4[/tex]

à partir de ces droites je prend par exemple les boules L & H se situant sur la droite à coefficient directeur 0.5 .

je les teste et je suis une logique de placement comme : plus légère en haut ou à gauche et plus lourde au dessous ou à droite.
je vais donc chercher ces 23 triplets puis tester ensuite.
à plus.

(...)

amatheur · 28-02-2012 01:18:56

salut
@freddy, on commence sérieusement à s'ennuyer dans cette section, il n'y a plus de nouveaux problèmes, et jpp ne donne plus de ses nouvelles! j’espère que toi ou Fred nous donnerez prochainement un peu de fils à retordre.
A+

freddy · 02-04-2012 15:33:23

Salut,

bon, alors comment fait on en 23 pesées maxi ?

5 premières pesées permettent d'obtenir un classement du type :

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

Bien entendu, les numéros sont là pour aider à bien suivre le raisonnement. A chaque étape, on change les numéros implicites des boules pour maintenir le classement obtenu.

Ensuite, on a besoin de 4 étapes au plus pour classer les boules médianes, savoir les triplets (2,5,8) ; (5,11,14) ; (2,11,14) et (8,11 14).

En renumérotant correctement les boules, on sait qu'on a obtenu l'ordre suivant 2 < 5 < 8 < 11 < 14 et donc le classement partiel suivant : 1 < 2 < 5 < 8 < 11 < 14 < 15.

En faisant peser le triplet (1,2,4) on sait où va se ranger la boule 4 ; en faisant peser le tripler (12,14,15), on sait où se range la boule 12.

Total des pesées : 5+4+2 = 11.

En renumérotant implicitement, on a le classement partiel : 4 < 5 < 8 < 11 < 12 < 14 < 15

Pour savoir ou se range la boule 3, on soumet à la pesée le triplet 3, 8 et 14. Selon la réponse, une seconde et dernière pesée est nécessaire pour déterminer son poids comparatif.

En renumérotant le cas échéant, on a en particulier : 1 < 2 < 3 < 4 < 5 < 8 < 11 < 12. On peut alors, en deux pesées supplémentaires, ranger la boule 13, en commençant par la comparer aux boules n° 3 et n° 8 ci dessus.

Une seconde pesée permet de déterminer l'ordre partiel relatif suivant 3 < 8 < 11 < 12 < 13 < 14 < 15.

Ceci permet de positionner la boule n° 6 en deux étapes.

Ceci fait, on trouve en deux étapes supplémentaires le placement de la boules n° 10 dans le groupe (1,2,3,4,5,6,8,13), puis en deux étapes supplémentaires le placement de la boule n° 9 parmi le groupe (3,6,10,11,12,13,14,15) et on termine en deux dernières pesées la position de la boule n° 7 dans le groupe (1,2,3,4,5,6,10,13).

Total 11 + 12 = 23 pesées.

PS : je me suis fait un peu beaucoup aidé par ma petite famille !!!

totomm · 03-04-2012 11:13:11

Bonjour,

freddy a écrit :

En renumérotant correctement les boules, on sait qu'on a obtenu l'ordre suivant 2 < 5 < 8 < 11 < 14 et donc le classement partiel suivant : 1 < 2 < 5 < 8 < 11 < 14 < 15.

??? si les boules pèsent de 1g à 15g (pour différencier des positions de 1 à 15), la boule en 1 n'a pas changé de position et pouvait être 13g. en partant avec cet ordre : 13g, 14g, 15g, 1g,..., 12g.

il faudrait 2 pesées supplémentaires entre les plus légères de chacun des triplets précédents
pour être certain que la boule en 1 est plus légère que la plus légère de médianes

Pour avoir le classement partiel suivant : 1 < 2 < 5 < 8 < 11 < 14 < 15. il faudrait donc 5+4+2+2 = 13 pesées ?
Comment se fait alors le reste du classement ?

Cordialement

Forum de mathématiques - Bibm@th.net

#76 11-02-2012 15:07:12

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

#77 12-02-2012 11:05:02

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

#78 12-02-2012 17:41:47

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

#79 12-02-2012 19:45:44

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

#80 12-02-2012 20:53:00

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

#81 13-02-2012 09:49:08

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

#82 13-02-2012 11:55:06

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

#83 13-02-2012 16:03:38

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

#84 13-02-2012 18:04:49

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

#85 13-02-2012 18:38:58

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

#86 13-02-2012 22:22:35

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

#87 14-02-2012 01:57:10

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

#88 14-02-2012 20:04:10

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

#89 15-02-2012 13:51:59

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

#90 15-02-2012 14:23:14

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

#91 15-02-2012 15:25:02

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

#92 15-02-2012 19:49:53

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

#93 15-02-2012 20:37:15

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

#94 17-02-2012 00:28:59

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

#95 17-02-2012 07:19:37

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

#96 18-02-2012 02:48:49

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

#97 18-02-2012 16:16:27

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

#98 28-02-2012 01:18:56

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

#99 02-04-2012 15:33:23

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

#100 03-04-2012 11:13:11

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

Réponse rapide

Pied de page des forums