Casse-tête : Oranges

Vael · 15 juin 2009

bpn j'ai pas passé beaucoup de temps aujourd'hui sur ce probleme mais j'ai fais cherché quelque solutions en vain (ou en vein ou en vin....quoi que la je doute ) ( je dois pas etre doué pour les oranges ).

bref j'arrive toujours au même stade 4 orange en une pésée et on sait si elle est +/- lourde !

je dois pas m'y prendre correctement !

j'ai donc dessider de bouder jusqu'a demain ou je serais peut etre plus inspiré

Toutiet · 15 juin 2009

T'inquiète, je connais le problème
Trouver une orange parmi 8 dont 1 sur 4 est plus lourde ou 1 sur les 4 autres est plus légère

n'est pas plus difficile que d'en trouver 1 plus légère ou plus lourde parmi 4.

Avoue que trouver 1 orange plus légère ou plus lourde parmi 8 (et dire si c'est en plus ou en moins), n'est pas du tout de la même difficulté que si elles ne sont que 4 , c'est évident.

waskol · 15 juin 2009

Bon, parce que Toutiet est perplexe, je lui démontre le coup des 9 oranges en 2 pesées :

1) tu fais 3 tas A, B et C (3 oranges chacun)

2) 1ere pesée tu pèses A et B

--> Si l'orange plus légère et dans A ou B, ça se voit, si la balance est à l'équilibre, elle est donc dans C. Tu prends les 3 oranges du tas "léger" ainsi identifié...

3) Du coup, tu te retrouves avec 3 oranges, tu en prends deux au hasard sur les trois

4) 2ème pesée : tu les compares sur la balance.

--> Si la balance penche, l'orange la plus légère est vite trouvée, si la balance est à l'équilibre, c'est que l'orange laissée de côté était l'orange à trouver.

Tu vois, ça fait 9 oranges... et en 2 pesées

Sur ce principe "récursif" ou tu divises par groupe de trois, tu peux trouver l'orange la plus légère (ou la plus lourde) :

parmi 27 en 3 pesées

parmi 81 en 4 pesées

parmi 243 en 5 pesées

etc...

laurent-eos · 15 juin 2009

tu separes en deux tas, tu les peses et tu gardes le groupe le plus lourd ou leger selon

sur les 6 restantes; tu refait deux gourpes que tu repeses; et tu gardes de nouveau le groupe le plus lourd ou leger

sur les 3 restantes tu en pese deux au hasard, mettant de coté une orange.

et là deux posibilités :

- soit tu tombes directement sur l'orange à trouver et comme tu sait deja si elle est plus lourde ou legere d'aprés les 2 pesées precedentes

- soit les deux oranges ont le meme poids et c'est celle mis de coté qui est celle à trouver

voila j'ai bon ?????

waskol · 15 juin 2009

voila j'ai bon ?????

bah ouais, facile maintenant que j'ai défriché un peu :be:

Ouuuuiiiiii, je sais, :chuisundieu:

:vivemoa: :merci:

mais faut pas le répeter, sinon, j'ai des concurrents qui vont se radiner sur ce fil de discussion (ex : syncopatte,...)

Toutiet · 15 juin 2009

waskol, et d'autres...

C'est incroyable : je vais finir par croire que vous ne savez pas lire un énoncé :mad: ...!

"J'ai 12 oranges, toutes identiques d'aspect et de poids, sauf une qui a un poids différent des autres. Je dispose d'une balance de Roberval et, en trois pesées maximum, j'aimerais trouver la "fautive" et savoir si elle pèse plus ou moins que les autres".

Vous n'avez donc pas (encore) donné la solution

waskol · 15 juin 2009

Non, mais je ne vais pas donner la solution non plus, sinon, c'est pas de jeu ! J'ai pas envie de casser ton challenge : j'arrive et connais déjà la réponse... pas cool... :chaine:

Si j'en trouve une parmi 27 en 3 pesées, tu penses bien que ce n'est pas une pauvre douzaine qui va me faire peur ! :rolleyes:

C'est bien que chacun se creuse un peu les méninges, non ?

M'enfin, si tu y tiens vraiment, j'ai plusieurs solutions sous le coude...

On peu commencer par 3 tas de 4 oranges (1 pesée) puis 2x 2 oranges (2 pesées maxi), ou 2 fois 2 tas (2 pesées maxi) puis ça fini avec 3 oranges (1 pesée suffit alors), etc...

oups ! j'en ai déjà trop dis !

Beloube · 15 juin 2009

Si j'en trouve une parmi 27 en 3 pesées, tu penses bien que ce n'est pas une pauvre douzaine qui va me faire peur !

Moi aussi je savais faire ça... Mais on savait que l'orange cherchée était soit plus lourde, soit plus légère du fait que lorsque les pesées différaient, on savait avec quel tas continuer... :-/

Or ici, à la première pesée, s'il y a déséquilibre, quel tas choisir sans effectuer une deuxième pesée ?????????

:?:

j'vois pô !

EDIT : Toutiet, tu dis "3 pesées maxi"... tu peux faire en moins (même sur un cas particulier) ?

Tex murphy · 15 juin 2009

T'inquiète, je connais le problème
Trouver une orange parmi 8 dont 1 sur 4 est plus lourde ou 1 sur les 4 autres est plus légère

n'est pas plus difficile que d'en trouver 1 plus légère ou plus lourde parmi 4.

Avoue que trouver 1 orange plus légère ou plus lourde parmi 8 (et dire si c'est en plus ou en moins), n'est pas du tout de la même difficulté que si elles ne sont que 4 , c'est évident.

As-tu lu attentivement ma phrase ?

Je compare les 8 possibilités A+,B+,C+,D+,E-,F-,G-,H-

et les 8 possibilités A+,A-,B+,B-,C+,C-,D+,D-

Et moi non plus je ne donnerai pas la réponse que je connais, na!

Toutiet · 15 juin 2009

waskol,

tu fanfaronnes , mais j'attends toujours ta réponse en clair (ou en MP si tu veux laisser leur chance aux autres) puisque tu prétends connaître la solution au problème tel que posé et rappelé ci-dessus (post 36)...

Toutiet · 15 juin 2009

Moi aussi je savais faire ça... Mais on savait que l'orange cherchée était soit plus lourde, soit plus légère du fait que lorsque les pesées différaient, on savait avec quel tas continuer...

Or ici, à la première pesée, s'il y a déséquilibre, quel tas choisir sans effectuer une deuxième pesée ?????????

j'vois pô !

EDIT : Toutiet, tu dis "3 pesées maxi"... tu peux faire en moins (même sur un cas particulier) ?

Non. Le challenge est de répondre à la question en trois pesées maximum (et non pas 16, 17, 18 ...!)

waskol · 15 juin 2009

waskol,
tu fanfaronnes , mais j'attends toujours ta réponse en clair (ou en MP si tu veux laisser leur chance aux autres) puisque tu prétends connaître la solution au problème tel que posé et rappelé ci-dessus (post 36)...

Je veux bien, mais tu as désactivé ton mp : on ne peut pas t'en envoyer. :be:

Penses-tu, j'ai essayé !!

waskol · 15 juin 2009

On fait trois tas : (1 2 3 4) (5 6 7 8) (9 10 11 12).

Je mets un signe = derrière le chiffre quand on à déjà déterminé qu'une orange n'est pas l'intruse

A) Pesée 1 : On pèse (1 2 3 4) et (5 6 7 8)

--> si la balance s'équilibre alors l'intruse est dans (9 10 11 12), aller en B1

--> sinon, la balance penche, aller en B2

B1) Pesée 2 : remplacer 1= 2= 3= par 9 10 11,

donc on pèse (9 10 11 4=) et (5= 6= 7= 8=) (edit : remarquez, on peut aussi se passer de 4= et 5= !)

--> si la balance s'équilibre alors, l'orange n°12 est l'intruse, aller en C1

--> sinon l'intruse est dans (9, 10, 11), et on sait du même coup si elle est + ou - lourde, aller en C2

C1) Pesée 3 : on pèse (12) et (1=) pour savoir si elle est plus lourde ou plus légère. CQFD n°1

C2) Pesée 3 : On pèse (9) et (10)

(rappel : on sait déjà si l'intruse est + ou - lourde)

--> Si la balance s'équilibre, l'intruse est la 11. CQFD n°2

--> Sinon, on a déterminé que l'intruse était la 9 ou 10 selon que l'on sait que c'est la plus lourde ou la plus légère. CDFD n°3

B2) Pesée 2 : L'intruse est dans (1 2 3 4 5 6 7 8).

On remplace 1 2 3 par 9= 10= 11=, et on permute 4 par 5.

On pèse donc (9= 10= 11= 5) et (4 6 7 8)

--> Si la balance s'équilibre , l'intruse est dans (1 2 3), et on sait du même coup si elle est + ou - lourde (ça penchait de quel côté en A, hein ?), aller en C3

--> Sinon la balance penche comme en A, aller en C4

--> Sinon, la balance a penché dans le sens inverse de A, 4 ou 5 est donc l'intruse, aller en C5

C3) Pesée 3 : On pèse (1) et (2)

(rappel : on sait déjà si l'intruse est + ou - lourde)

--> Si la balance s'équilibre, l'intruse est la 3. CQFD n°4

--> Sinon, on a déterminé que l'intruse était la 1 ou 2 selon que l'on sait que c'est la plus lourde ou la plus légère. CDFD n°5

C4) Pesée 3 :

La balance a penché comme en A, et puisque 9= 10= 11= ont la même masse, on sait que l'intruse est dans (6 7 8),

hé oui, l'inversion de la 4 et de la 5 n'a rien changé donc (masse de 4)=(masse de 5) !!!

et on sait si elle est + ou - lourde que les autres. Ca a penché côté (5= 6 7 8) ou non ?

On pèse donc (6) et (7)

--> Si la balance s'équilibre, 8 est l'intruse. CQFD n°6

--> Sinon l'intruse est déterminée par la pesée, soit la 6, soit la 7. CQFD n°7

C5)Pesée 3 : La balance a penché dans le sens inverse de A, 4 ou 5 est donc l'intruse.

On pèse (4) avec (9=) , par exemple

--> si il y a équilibre la 5 est l'intruse

et on sait d'après la pesée en A, si la balance à penché côté (1= 2= 3= 4=) ou (5 6= 7= 8=) ! CQFD n°8

--> sinon, la balance a penché, la 4 est l'intruse, et du même coup on sait si elle est + ou - lourde que la 9= CQFD n°9

3 pesées, pas une de plus, pas une de moins, mais ça nécessite un marqueur pour numéroter les oranges

trop long à écrire ce genre de solution :be:

Non, non, je ne fanfaronnais pas par hasard, déjà vu dans un Jeux&Stratégie il y a fort longtemps, j'étais fan... :wub:

Il y avait vraiment des problêmes costauds dans ce mag

Beloube · 16 juin 2009

:b:

Très bon...

Respect :-_-:

Toutiet · 16 juin 2009

Bravo waskol. C'est exactement ça. Ce n'était pas évident à écrire !

Tex murphy · 16 juin 2009

Autre présentation de la solution;

Le principe est qu'il suffit de peser 2/3 des objets à chaque fois car le résultat d'une pesée donne aussi des indications sur les objets non pesés.

Quand la première est en déséquilibre, pour la 2ème pesée comme 8 n'est pas divisble par 3 on ajoute un objet de poids normal.

Je nomme les objets de A à L

Les signes \|/ indiquent dans quel sens penche l'aiguille de la balance.


ABCD \ EFGH   ABCD lourd ou EFGH léger
   ABE \ CDI  AB lourd
      A \ B	A lourd
      A | B	Impossible
      A / B	B lourd
   ABE | CDI  FGH léger
      F \ G	G léger
      F | G	H léger
      F / G	F léger
   ABE / CDI  CD lourd ou E léger
      C \ D	C lourd
      C | D	E léger
      C / D	D lourd
ABCD | EFGH   Parmi IJKL
   IJK \ ABC  IJK lourd
      I \ K	I lourd
      I | K	J lourd
      I / K	K lourd
   IJK | ABC  L différent
      L \ A	L lourd
      L | A	Impossible (aucun objet n'est différent des autres)
      L / A	L léger
   IJK / ABC  IJK léger
      I \ K	K léger
      I | K	J léger
      I / K	I léger
ABCD / EFGH   ABCD léger ou EFGH lourd
   ABE \ CDI  CD léger ou E lourd
      C \ D	D léger
      C | D	E lourd
      C / D	C léger
   ABE | CDI  FGH lourd
      F \ G	F lourd
      F | G	H lourd
      F / G	G lourd
   ABE / CDI  AB léger
      A \ B	B léger
      A | B	Impossible
      A / B	A léger[/Code]

On peut noter qu'on peut rajouter dans l'énoncé la possibilité qu'il n'y a pas d'objet de poids différent,

car on est capable de le déterminer aussi. (Cas actuellement impossible du milieu)

On peut noter aussi que la solution est symétrique par rapport à cette ligne

simplement en remplaçant léger par lourd et vice-versa.

-----------------------------------------------------------------------------------

Maintenant une méthode générale de résolution pour 12*3^N objets en 3+N pesées.

Elle est un peu difficile à suivre sans prendre des exemples au fur et à mesure

[Color=blue]

Martin Gardner a donné une jolie solution à ce problème.

Supposez que vous avez le droit à P pesées. Écrivez les 3^P chaînes

possibles de longueur P ayant pour caractères " 0 ", " 1 " et " 2 ".

Éliminez les 3 chaînes comportant uniquement un caractère répété

P fois.

Pour chaque chaîne, trouvez le premier caractère différent du

caractère le précédant. Considérez ce couple de caractères. Si ce

couple n'est pas 01, 12 ou 20, éliminez cette chaîne. En d'autres

termes, seules les chaînes de la forme 0*01.*, 1*12.* ou 2*20.*

(expressions rationnelles) sont acceptées.

Il doit vous rester (3^P-3)/2 chaînes. C'est le nombre de pièces

que vous pouvez contrôler en P pesées.

Associez donc chaque pièce à une chaîne de P caractères.

Effectuez P pesées comme suit:

Pour la pesée I, mettez d'un côté toutes les pièces ayant un 0

dans la chaîne en position I, et mettez de l'autre côté toutes

les pièces ayant un 2 dans la chaîne en position I.

Si le côté avec les 0 en position I est plus lourd, écrivez un 0.

Si c'est l'autre côté qui est plus lourd, écrivez un 2. Sinon,

écrivez un 1.

Après P pesées, vous avez écrit une chaîne de P caractères. Si votre

chaîne correspond à une des pièces, alors c'est cette pièce qui est

contrefaite, et elle est plus lourde. Sinon, changez chaque 2 en 0

et chaque 0 en 2 dans votre chaîne. Votre chaîne correspondra alors

à l'une des pièces, et cette pièce est plus légère que les autres.

Notez que si vous devez seulement identifier la pièce contrefaite,

mais pas déterminer si elle est plus lourde ou plus légère, vous

pouvez contrôler (3^P-3)/2+1 pièces. Étiquetez la pièce

supplémentaire par la chaîne contenant uniquement des 1, et utilisez

la méthode ci-dessus.

Notez aussi que vous pouvez contrôler (3^P-3)/2+1 pièces si vous

devez déterminer si la pièce contrefaite est plus lourde ou plus

légère, pourvu que vous ayez une pièce de référence, dont vous savez

qu'elle a le poids correct. Vous faites ceci en étiquetant la pièce

supplémentaire par la chaîne contenant uniquement des 2. Cette

pièce est placée toujours du même côté, et ce plateau contient une

pièce de plus que l'autre. Alors, placez la pièce de référence de

l'autre côté, à chaque pesée.

Il est très facile de prouver que ceci marche, une fois que vous

avez remarqué que la méthode de construction des chaînes assure

qu'à chaque position, 1/3 des chaînes ont un 0, 1/3 ont un 1, et 1/3

ont un 2, et que si une chaîne est dans la liste, alors celle

obtenue en remplaçant chaque 0 par un 2 et chaque 2 par un 0 n'y est

pas.

Si vous savez déjà que la pièce contrefaite est plus lourde (ou plus

légère), vous pouvez contrôler 3^P pièces. Avec P pesées, il ne peut

y avoir que 3^P combinaisons d'équilibre, plateau de gauche plus

lourd et plateau de droite plus lourd.

L'algorithme est dans ce cas:

Partagez les pièces en 3 groupes de même taille... A, B et C. Pesez

A avec B. Si un plateau tombe, il contient la pièce lourde, sinon

cette pièce est dans le groupe C. Si la taille de votre groupe est 1

vous avez trouvé la pièce, sinon faites une recurrence sur le groupe

contenant la pièce lourde.

[/Color]

Toutiet · 23 août 2009

Waskol, tu dis :

"Si j'en trouve une parmi 27 en 3 pesées,..."

En disant cela, tu te places dans le cas de Tex Murphy ou l'on suppose que l'on sait d'avance si la pièce est plus lourde ou moins lourde, N pesées permettant mathématiquement de trouver la pièce fautive paarmi 3^N pièces :

"Si vous savez déjà que la pièce contrefaite est plus lourde (ou plus

légère), vous pouvez contrôler 3^P pièces. Avec P pesées, il ne peut

y avoir que 3^P combinaisons d'équilibre..."

J'attends donc toujours ta démonstration pour trouver 1 orange parmi 27, en me précisant si elle est différente des autres en plus ou en moins... .

waskol · 11 septembre 2009

Toutiet, tu chipotes.

Bon, j'ai une solution qui va te plaire :

tu prends les 27 oranges, tu les laches toutes de la même hauteur, sol dur en dessous.

SOit, il y en a une plus abimée que les autres par terre (Plus de dégats=>plus d'énergie cynétique à l'impact=>masse plus importante => c'était logiquement la plus lourde !), à conntrario , si il y en a une moins abimée que les autres, c'était la plus légère.

0 pesées :be:

david.d · 14 septembre 2009

excellent un peu comme "J'ai un superbe baromètre pour

vous si vous me dites quelle est la hauteur de l'immeuble" (de la legende "urbaine" sur un échange entre Niels Bohr et Ernest Rutherford) http://labocharlemagne.free.fr/documents/Barom%E8tre%20de%20Bohr.pdf

David

Connexion

Casse-tête : Oranges

Messages recommandés

Vael

Toutiet

waskol

laurent-eos

waskol

Toutiet

waskol

Beloube

Tex murphy

Toutiet

Toutiet

waskol

waskol

Beloube

Toutiet

Tex murphy

Toutiet

waskol

david.d

Archivé

En ligne récemment 0 membre est en ligne

Annonces

Aider Webastro

Webastro

Forums

Constellia

Noctua

Communauté

Grenier

Ephémérides

Activité

Information importante