Problème des Cow-Boys

[Ben314]

L'énigme des "cows-boys" m'a fait penser à une autre.

L'énigme est en trois parties de dificulté croissante (1:complètement triviale ; 2:pas façile ; 3:je suis absolument pas sûr de la soluce...)

C'est toujours nos cow-boys prisoniers chez les indiens que l'on met en file indienne avec un chapeau sur la tête, ils ne voient que les chapeaux de ceux qui sont devant eux et il doivent savoir quel chapeau ils ont...
Le premier à parler est toujours le dernier de la file (qui voit tout les chapeaux sauf le sien)

Sauf que les règles ont un peu changé :

1) Tout le monde (enfin, tout les cow-boys) sait que les indiens ont, trés exactementl 18 chapeaux Rouges, 19 chapeaux Oranges ; 20 chapeaux Jaunes ; 21 chapeaux Verts et 22 chapeaux Bleus.

2) Tout ceux qui trouvent la couleur du chapeau qu'ils ont sur leur tête sont libèrés, mais si un seul d'entre eux ce trompe, ils sont absolument tous trucidés dans d'atroces soufrances.
Par contre ils ont le droit à un modeste "je ne sais pas quelle est la couleur de mon chapeau" qui leur permet de retourner peinard dans le camp des prisoniers.

Bien sûr, tout les cow-boys sont de trés fin logitiens et ne ratent aucune déductions possible (de plus ils savent qu'ils le sont...)

Le but est évidement dans chaque cas est de déterminer combien de cow-boys, au minimum, vont être libérés...

CAS 1) Il y a 100 cow-boys (fastochhhhhhhe)

CAS 2) Il y a 99 cow-boys (et évidement personne n'a la moindre idée de la couleur du chapeau non utilisé...)

CAS 3) Il y a 95 cow-boys (et toujours pas d'idée d'où ces foutus indiens cachent les chapeaux en rab...)

[LeJeu]

cool - j'y pensais hier soir

Peux tu confirmer

que chaque cow boy ne peut qu'énoncer qu'une couleur? ( que les précédents entendent)

si les autres peuvent ils être au courant d'un code genre ' si je dis "jaune" ca veut dire que je vois .." ou non..

[LeJeu]

je fais le fastoche !

"18 chapeaux Rouges, 19 chapeaux Oranges ; 20 chapeaux Jaunes ; 21 chapeaux Verts et 22 chapeaux Bleus." = 100 chapeaux

Le dernier voit 99 chapeaux et connait donc le sien
L'avant dernier voit 98...

Au suivant !

[ffpower]

Et aussi,si un gars hésite entre 2 couleurs, est ce que c est possible qu'il tente sa chance? ou il capitule forcément?

[Doraki]

A mon avis il capitule.
Aussi je pense que si il se trompe ne serait-ce que d'une syllabe dans "je ne sais pas quelle est la couleur de mon chapeau" ou si il essaye de faire son malin en chantant la phrase, tout le monde meurt.

[ffpower]

En admettant qu'un gars qui hésite abandonne forcément, parce que j'ai l'impression que ca va etre délicat de déduire des trucs sinon:
Dans le cas 2, le dernier voit tous les chapeaux sauf 2. Il ne peut se sauver que si ces 2 chapeaux sont de la même couleur. Auquel cas il énonce cette couleur et tous les autres cow boys auront toutes les infos pour se sauver reccurcivement. Sinon, il abandonne, l'avant dernier sait que ces 2 chapeaux ne sont pas de la même couleur, et ne peut alors se sauver que si son chapeau est de la meme couleur que l un de ces 2..En continuant ainsi, vu que ya que 5 couleurs, au pire ce sera le 95 ieme cow boy qui arrivera a deviner sa couleur, puis tous ceux devant lui. Donc au moins 95 sauvés..

[Ben314]

je fais le fastoche !
"18 chapeaux Rouges, 19 chapeaux Oranges ; 20 chapeaux Jaunes ; 21 chapeaux Verts et 22 chapeaux Bleus." = 100 chapeaux
Le dernier voit 99 chapeaux et connait donc le sien
L'avant dernier voit 98...

No problèmo...

A mon avis il capitule.
Aussi je pense que si il se trompe ne serait-ce que d'une syllabe dans "je ne sais pas quelle est la couleur de mon chapeau" ou si il essaye de faire son malin en chantant la phrase, tout le monde meurt.

Je confirme : tout les cow-boys pissent dans leur cullote du fait qu'il y a un bégue parmi eux... :zen:

Résumé : dés qu'un cow-boy n'est pas sûr à 100%, ils fait pas le mariole et prononcent mécaniquement "je-ne-sait-pas-de-quelle-couleur-est-mon-chapeau" d'un ton le plus neutre possible...

En admettant qu'un gars qui hésite abandonne forcément, parce que j'ai l'impression que ca va etre délicat de déduire des trucs sinon:
Dans le cas 2, le dernier voit tous les chapeaux sauf 2. Il ne peut se sauver que si ces 2 chapeaux sont de la même couleur. Auquel cas il énonce cette couleur et tous les autres cow boys auront toutes les infos pour se sauver reccurcivement OK. Sinon, il abandonne, l'avant dernier sait que ces 2 chapeaux ne sont pas de la même couleur, et ne peut alors se sauver que si son chapeau est de la meme couleur que l un de ces 2..En continuant ainsi, vu que ya que 5 couleurs, au pire ce sera le 95 ieme cow boy qui arrivera a deviner sa couleur OK (il me semble) puis tous ceux devant lui OK (il me semble) mais peut-être à détailler.... Donc au moins 95 sauvés..

P.S. Pour le 3) je suis absolument pas sûr de la réponse, déjà que pour la 2), j'ai failli reprendre ffpower en disant qu'au pire c'est le 94 ième vu qu'il sont 99... (mais je pense qu'il a raison)

[Doraki]

Le coup de "dès que quelqu'un devine la couleur de son chapeau alors tout le reste est sauvé" ça marche que si quelqu'un = cowboy 99 ou cowboy 95, si je ne m'abuse.

[Ben314]

Le coup de "dès que quelqu'un devine la couleur de son chapeau alors tout le reste est sauvé" ça marche que si quelqu'un = cowboy 99 ou cowboy 95, si je ne m'abuse.

Il me semblait aussi, mais perso, je métait dit qu'au pire, les cow boys pouvaient continuer à raisonner comme si ce cow-boy et son chapeau (dont tout le monde connait la couleur) étaient absent de l'énoncé dés le départ. Ce qui (il me semble) permet de conclure qu'il y en a au plus 4 qui ne trouvent pas (mais pas forcément parmi les 4 derniers)

P.S. Je rapelle que j'ai "inventé" l'énigme (il me semble me rappeller de la même avec 3 types et des chapeaux noirs et un blancs, mais je me rappelle plus l'énoncé exact...) Conclusion, pour les soluces, c'est pas du garanti sur facture...

[ffpower]

Exact Doraki, j avais pas fait gaffe a ca..Du coup l'affaire se corse déja..

Edit: Exact Ben..Du coup l'affaire se décorse ( mais ca prouve que j'étais qd même allé un peu vite en besogne..)

[Galax]

L'énigme des "cows-boys" m'a fait penser à une autre.

L'énigme est en trois parties de dificulté croissante (1:complètement triviale ; 2:pas façile ; 3:je suis absolument pas sûr de la soluce...)

C'est toujours nos cow-boys prisoniers chez les indiens que l'on met en file indienne avec un chapeau sur la tête, ils ne voient que les chapeaux de ceux qui sont devant eux et il doivent savoir quel chapeau ils ont...
Le premier à parler est toujours le dernier de la file (qui voit tout les chapeaux sauf le sien)

Sauf que les règles ont un peu changé :

1) Tout le monde (enfin, tout les cow-boys) sait que les indiens ont, trés exactementl 18 chapeaux Rouges, 19 chapeaux Oranges ; 20 chapeaux Jaunes ; 21 chapeaux Verts et 22 chapeaux Bleus.

2) Tout ceux qui trouvent la couleur du chapeau qu'ils ont sur leur tête sont libèrés, mais si un seul d'entre eux ce trompe, ils sont absolument tous trucidés dans d'atroces soufrances.
Par contre ils ont le droit à un modeste "je ne sais pas quelle est la couleur de mon chapeau" qui leur permet de retourner peinard dans le camp des prisoniers.

Bien sûr, tout les cow-boys sont de trés fin logitiens et ne ratent aucune déductions possible (de plus ils savent qu'ils le sont...)

Le but est évidement dans chaque cas (est) de déterminer combien de cow-boys, au minimum, vont être libérés...

CAS 1) Il y a 100 cow-boys (fastochhhhhhhe)

CAS 2) Il y a 99 cow-boys (et évidement personne n'a la moindre idée de la couleur du chapeau non utilisé...)

CAS 3) Il y a 95 cow-boys (et toujours pas d'idée d'où ces foutus indiens cachent les chapeaux en rab...)

Ben je sais que c'est un forum de maths, mais là tu charries un peu non ? :we:

[Dravadore]

Si je ne me trompe pas, il faut que quelqu'un ne "connaisse" pas au moins deux chapeaux de même couleur pour qu'il trouve la couleur de son chapeau (quelqu'un connaît un chapeau si il le voit ou si le cow-boy à qui il appartient a dit la couleur qu'il avait). Or, si il y a moins de 95 cow-boys sauvés, il y en aurait plus de 95 qui ne connaîtrait pas au moins six chapeaux parmi lesquels il y en a uniquement deux de la même couleur (uniquement car sinon un autre cow-boy aurait su sa couleur avant).Donc il y a au pire 95 cow-boys sauvés.

De même, dans le troisième cas, il y a au pire 75 cow-boys sauvés.
Plus généralement, pour cow-boys pas trop grands, il y a cow-boys sauvés.

[LeJeu]

Ben je sais que c'est un forum de maths, mais là tu charries un peu non ? :we:

Galax : puisque tu en parles :

Ben ne pouvant y répondre sans être de mauvaise foi (ça c'est la marchande de foie qui se dit ma foi c'est la dernière fois que je vends du foie dans la ville de Foix : fastoche) je m'y attelle ( alors là j'ai tout dans le même mot les deux t les deux l et l'accent... j'essaie de revenir à un mot connu : attelage, ca se lit bien, ca doit être ça , donc atteler c'est bon aussi, me voila donc à attele un fois conjugué, non sinon ça va se prononcer A TE LE , il faut que j'ajoute un accent; je cherche le sens il faut entendre AI, c'est donc attèle - et zut depuis que je suis à attele le correcteur orthographique n'est pas content, je regarde les propositions j'ai attèle et attelle - et zut j'aurais faux ? - j'ouvre un onglet et je cherche conjuguer atteler , grand bien me fasse ! j'avais tout faux, je corrige...)

J'ai appris l'orthographe du temps où l'on faisait des dictées avec un barème assez simple: moins quatre, moins deux, moins un suivant la faute . et ce qui devait arriver arriva, avec 37 points de pénalités ( sur 20 ça vaut zéro) je me suis fait tirer les oreilles.. ni une, ni deux je me suis vexé et attelé à la tâche, résultat moins 23: ca qui valait tout pareillement zéro... Grand moment d'incompréhension et désintérêt total par la suite pour la cause orthographique

Par contre depuis ce jour c'est sans problème que je manipule les inégalités et le sens en fonction du signe -37 23 ...

Ce n'est que bien plus tard que j'ai admis que c'était plus correct d'écrire sans faute. Tu ne peux pas savoir l'énergie que cela me demande ( d'essayer..)( c'est ce que je tente de t'expliquer dans mon premier paragraphe, ' et que je te conjugue au passé au futur, que je te remplace par le verve prendre, que je vérifie, et revérifie, les é les er , les on les ont, les se, les ce....) Et à chaque fois il en reste une grosse, énorme...

Si en plus mon attention se porte sur le contenu alors là c'est la kata totale...

LeJeu

[Ben314]

@Galax : désolé pour l'orthographe : je fait pas totalement exprés, mais j'y fait vraiment pas attention du tout...

@Dravadore : je ne suis pas sûr de totalement comprendre ton argument...
Je pense tout de même que ta formule finale est juste, (au moins lorsque n>82)

[boumba daboum]

Si je ne me trompe pas, il faut que quelqu'un ne "connaisse" pas au moins deux chapeaux de même couleur pour qu'il trouve la couleur de son chapeau (quelqu'un connaît un chapeau si il le voit ou si le cow-boy à qui il appartient a dit la couleur qu'il avait).

Il me semble comprendre ce qu'écrit Dravadore pour le cas 2 :

Cow-boy n° N : il ne voit pas le chapeau inutilisé, ni le sien. Si, d'après ce qu'il voit, les deux chapeaux qui manquent sont de la même couleur, il connait la couleur du sien.
En énonçant cette couleur, il est sauvé (et indique par là même à tout le monde la couleur du chapeau inutilisé, s'ils savent que c'est le dernier qui répond).

Sinon, (N-1) sait que les chapeaux qu'il ne connait pas hormis le sien (donc, celui de N et l'inutilisé) sont de deux couleurs différentes. Si d'après ce qu'il voit, il manque des chapeaux dans seulement deux couleurs, (1 d'une couleur, 2 de l'autre), il sait que le sien est de la couleur dont il manque deux exemplaires (mais n'indique pas la couleur du chapeau inutilisé, ni du dernier).

En règle générale, dès que quelqu'un voit qu'il manque deux chapeaux d'une couleur par rapport à ce qu'il a appris de ses successeurs dans la queue, c'est la couleur de son chapeau (sinon, son prédécesseur aurait vu le même manque et se serait attribué la couleur).

Dans ce cas, dès qu'une personne échoue, toute personne ayant un chapeau de même couleur verra deux manques et sera sauvée.
Tous les échecs correspondent à des couleurs différentes entre elles et différentes de la couleur réservée.

Donc, au plus quatre personnes échouent.

J'ai l'impression que le premier (depuis la fin) de chaque couleur différente de la couleur épargnée échoue, sauf si le dernier est de la couleur épargnée (et si on sait que c'est lui, dernier, qui énonce sa couleur), auquel cas tout le monde est sauvé.

Or, si il y a moins de 95 cow-boys sauvés, il y en aurait plus de 95 qui ...

pas plutôt 5 ou plus ?

Cas 3 :
S'il y a n cow-boys, il y a (100 - n) chapeaux en réserve.
Dès qu'un cow-boy constate qu'il manque (100-n+1) chapeaux dans une couleur par rapport à ce qu'il connait de ses prédécesseurs, c'est la couleur de son chapeau.
Il y a au plus (100-n) occurrences de chaque couleur, entre les échecs et la réserve... dans la limite du stock initial de chaque couleur.

La formule Dravadore doit convenir tant que le stock de chaque couleur est au moins n-1

Sinon ça devrait être au mieux :

Sauvés_au_pire=max(0,somme_sur_les_couleurs(min(stock_initial,n-100)))

mais je ne doute pas mal que les cow-boys soient toujours capables de déduire la couleur de leur chapeau dans les cas de stock insuffisant...

[Ben314]

Pour le cas 2), je pense que c'est bien ça, mais pour le cas 3, il y a des détails qui me manquent :

Dès qu'un cow-boy constate qu'il manque (100-n+1) chapeaux dans une couleur par rapport à ce qu'il connait de ses prédécesseurs, c'est la couleur de son chapeau.

Je pense que c'est juste, mais ça demanderait (à mon avis) un peu plus d'explications...

mais je ne doute pas mal que les cow-boys soient toujours capables de déduire la couleur de leur chapeau dans les cas de stock insuffisant...

Effectivement, si le nombre de chapeau manquant est supérieur (ou égal) au max des nombres de chapeau dans une couleur, il me semble que l'on est sûr que le dernier ne peut pas trouver son chapeau, ce qui signifie que, lorsqu'il dit "je ne sait pas", cela ne donne absolument pas la moindre informations aux suivants, et comme il connaissent encore moins de chapeaux que le dernier...

[boumba daboum]

Je pense que c'est juste, mais ça demanderait (à mon avis) un peu plus d'explications...

Dans le cas de l'exemple :

Si 95 constate qu'il manque 6 chapeaux de la même couleur, comme il y en a en tout 5 en réserve, c'est la couleur du sien.
Sinon, si 94 constate qu'il manque 6 chapeaux de la même couleur, comme ça n'était pas le cas pour 95, c'est la couleur de 94.
Et ainsi de suite.
Le premier à reconnaître son chapeau sera celui dont 5 chapeaux de même couleur sont en réserve ou non identifiés par un prédécesseur. Il constatera devant lui un manque de 6 dans sa couleur.
Pour le suivant dans la couleur, il suffira d'un manque de 5, puis de 4 et ainsi de suite.
Le premier à reconnaître son chapeau dans une autre couleur sera celui dont 5 chapeaux de même couleur sont en réserve ou non identifiés par un prédécesseur. Sinon, un prédécesseur qui n'a pas identifié son propre chapeau aurait fait la même constatation.

Réciproquement, dès que 5 chapeaux d'une couleur sont en réserve ou non identifiés par leur propriétaire, les porteur des suivants pourront déduire de la taille du manque qu'ils constatent que leur chapeau est de cette couleur.

[Ben314]

Ca me parrait plus clair (forcément, ... c'est plus long... :zen: ) sauf que dans ta rédaction, quand tu dit par exemple "...dans sa couleur..." ou "Pour le suivant dans la couleur", ça donne un peu l'impression qu'il savent déja quelle est leur couleurs...
Perso, j'aurais tendance à rédiger comme suit :
Chaque cow-boy regarde les couleurs "strictement devant lui", il en déduit celles "derrière lui + sur sa tête + non utilisées" puis il retranche les couleurs qui ont déjà été annoncés par un de ces prédécesseurs.
Si, aprés ce calcul, un des nombre vaut 6 (=nbre de chapeau inutilisé + 1) alors il sait que son chapeau est de la couleur correspondant à ce 6.
Si cette méthode est optimale , on peut parfaitement calculer le nombre qui vont trouver leur couleur (ç'est sans doute la formule que tu donne dans ton post d'hier.

Le truc qui me dérange, c'est que, si le dernier trouve ça couleur, la méthode ci dessus n'est clairement plus "optimale" vu qu'ils trouvent tous...
J'aurais tendance à en déduire que ce n'est pas tout le temps optimal (est-ce que, si l'avant dernier trouve sa couleur, on ne peut pas améliorer la méthode ?.)

[Doraki]

Dès que les chapeaux énoncés expliquent totalement la répartition de couleur des chapeaux inconnus, c'est fini.

Y'a le cas où les chapeaux sont comme ça :
(0 0 0 0 0) 0 .... <- (les 5 chapeaux inutilisés sont de couleur 0, et cowboy 95 a un chapeau de couleur 0)
ici, cowboy 95 déduit de ce qu'il voit que les 6 derniers chapeaux sont de couleur 0, en particulier le sien.

(0 0 0 0 0) 1 0 1 ..... <- cowboy 94 déduit de ce qu'il voit et de ce que dit cowboy 95, qu'il y a 6 chapeaux de couleur 0, dont le sien + un chapeau de couleur 1 dans les 7 chapeaux manquants,
cowboy 93 déduit qu'il y a 2 chapeaux encore inconnus de couleur 1, et c'est tout, donc il en déduit qu'il porte un chapeau de couleur 1, et ensuite, tout le monde sait tout.

(0 0 0 0 0) 1 0 2 1 ...
Ici, cowboy 93 ne peut rien déduire, et c'est seulement cowboy 92 qui peut annoncer aux autres qu'il porte un chapeau de couleur 1 et qu'il reste un chapeau de couleur indéterminée à trouver.

Y'a une sorte de course entre le nombre de couleurs de chapeaux manquants et le nombre de couleurs trouvées par les cowboys... et le nombre de chapeaux manquants d'une couleur qu'on doit voir pour pouvoir conclure que c'est la couleur de son chapeau n'est pas très clair non plus.

La pire situation apparaît quand on a 5*5 couleurs bien distribués avant de faire apparaître un 6ème chapequ d'une couleur. Après que les 20 cowboys déclarent qu'ils ne savent pas la couleur de leur chapeau, le reste sait qu'il y avait 5 chapeaux de chaque couleur et ils peuvent tous donner la couleur de leur chapeau.

[Dravadore]

Une autre façon d'optimiser est d'utiliser le nombre de chapeaux d'une même couleur.
Exemple : un seul cow-boy a dit "rouge" et un autre en voit 11 devant lui, il a donc obligatoirement le 18ème chapeau rouge.