Mon coup de coeur du jour - Page 3

Oui. Son exemple de partie est faux, mais le reste est bon. Modulo le fait d'avoir une mémoire infinie pour mémoriser tout le monde, et toutes les combinaisons de tout le monde, et un ordre sur ces combinaisons qui permet d'avoir un nombre de morts fini.

ça répond à ma question ^^

En gros, c'est totalement foireux.

PpHd (./61) :
Oui. Son exemple de partie est faux, mais le reste est bon. Modulo le fait d'avoir une mémoire infinie pour mémoriser tout le monde, et toutes les combinaisons de tout le monde, et un ordre sur ces combinaisons qui permet d'avoir un nombre de morts fini.

ben si l'affectation des chapeaux a été réalisée par une machine avec une mémoire bornée alors y a juste besoin d'une mémoire finie à peine plus grande que la borne pour être capable de retenir ce qu'il faut ^^
(mais ça reste totalement foireux )

Sally (./48) :
Et, euh, ils ont le droit d'utiliser l'axiome du choix pour se munir d'un bon ordre ? (et ça leur sert à quelque chose ?)

Oui l'axiome du choix est utilisable.
Mais non ils n'ont pas besoin d'être bien ordonnés. (si l'infini quelconque t'embête, ne considère que l'infini dénombrable)

PpHd (./49) :
Ils forment des groupes de 3 personnes. Puis une autre personne entre dans ce groupe si et seulement si ils ne sont pas toutes de la même couleur.

Zephyr (./50) :
vi j'ai pas du comprendre le problème, parceque je pensais aussi à qqchose d'assez simple dans le genre : deux personnes se pointent en face d'une 3eme qui leur dit "oui" ou "non" selon que leurs chapeaux sont de la même couleur ou non; en recommençant le processus autant de fois que nécessaire chaque personne se retrouve dans un groupe de gars qui ont des chapeaux de la même couleur que le sien

Ca équivaut à parler des couleurs.

Bon en fait on peut formuler plus simplement : une fois la stratégie élaborée, ils n'ont le droit de n'échanger strictement aucune autre information que regarder le chapeau des autres.

Zephyr (./50) :
[edit] mais je suppose que la solution au problème fait intervenir le fait qu'il n'y ait que 2 couleurs différentes et pas un nombre quelconque ?

En fait ça marche aussi avec N couleurs, voire même avec une infinité de couleurs, mais la stratégie, qui est déjà violente à la base, devient encore infiniment plus violente...


./56> Ok mais tu te casses beaucoup trop la tête, notamment ya aucun besoin d'ordonner. (voir la solution juste après)

On appelle G l'ensemble des gens au départ.

Une combinaison de chapeaux est une fonction f : G -> {bleu, rouge}.

On appelle C l'ensemble de toutes les combinaisons.

On dit que deux combinaisons f et g sont presque égales si f(x)=g(x) sauf pour un nombre fini de gens x. On note alors f~g.
~ est une relation d'équivalence sur C.

Pendant le meeting stratégique, on décide d'un représentant dans chaque classe d'équivalence (là on a besoin de l'axiome du choix).

Pendant le test, chaque personne x sait, en regardant les chapeaux des autres, dans quelle classe d'équivalence se trouve la combinaison tirée, et répond f(x) avec le représentant f qui a été choisi la veille. Par construction il n'y a qu'un nombre fini d'erreurs

Bon c'est ptet assez imbittable pour un non matheux (enfin Pollux a fait une chouette explication je trouve) mais j'ai trouvé ça trop joli que ce problème soit résoluble

PpHd (./61) :
Oui. Son exemple de partie est faux, mais le reste est bon. Modulo le fait d'avoir une mémoire infinie pour mémoriser tout le monde, et toutes les combinaisons de tout le monde, et un ordre sur ces combinaisons qui permet d'avoir un nombre de morts fini.

D'ailleurs il ne faut pas seulement avoir une mémoire infinie dénombrable pour tout le monde, mais une mémoire *indénombrable*, même si le nombre de personnes au départ est dénombrable. C'est 'achement funky quand on y pense.

Hippopotame (./65) :
Ca équivaut à parler des couleurs.

Là je ne suis pas d'accord. Il faut formuler correctement ton énoncé si tu veux une réponse adéquate.

Hippopotame (./65) :
Bon en fait on peut formuler plus simplement : une fois la stratégie élaborée, ils n'ont le droit de n'échanger strictement aucune autre information que regarder le chapeau des autres.

Fallait le dire dès le début.

Hippopotame (./65) :
j'ai trouvé ça trop joli que ce problème soit résoluble

C'est sûr. C'est une solution très praticable. M'enfin, ca reste joli

J'ai regardé la solution
M'enfin je ne voyais pas trop par où aller à part que je trouvais bien que ça sentait l'axiome du choix ^^ (qui décidément est toujours aussi puissant)

Pollux (./59) :
ben en fait on suppose par exemple que les gens ont un numéro unique (que tout le monde connaît, y compris eux), et du coup la situation n°4 devrait plutôt être "les gens qui ont un numéro pair ont un chapeau rouge, ceux avec un numéro impair ont un chapeau bleu" : ça permet à chacun de savoir sans ambiguïté s'il devrait dire bleu ou rouge

Mais.......si le choix de la couleur par les G.O. est complètement aléatoire ? Chaque personne donne une couleur au pif donc (ou tout le monde dit "rouge" ou "bleu", c'est pareil), non ? Donc y'a un nombre infini d'erreurs
C'est où que j'ai pas compris ?

Hippopotame (./65) :
D'ailleurs il ne faut pas seulement avoir une mémoire infinie dénombrable pour tout le monde, mais une mémoire *indénombrable*, même si le nombre de personnes au départ est dénombrable. C'est 'achement funky quand on y pense.

Rahhh, là j'ai vraiment rien compris

Titane (./68) :
Mais.......si le choix de la couleur par les G.O. est complètement aléatoire ? Chaque personne donne une couleur au pif donc (ou tout le monde dit "rouge" ou "bleu", c'est pareil), non ? Donc y'a un nombre infini d'erreurs

Non non on ne répond pas au hasard. *Toutes* les combinaisons de chapeau ont été abordées une à une lors de la réunion stratégique.

Rahhh, là j'ai vraiment rien compris

Tous les infinis ne se valent pas, ils y a plusieurs "tailles" d'infini. Le plus petit s'appelle l'infini dénombrable, c'est par exemple la taille de l'ensemble des nombres entiers, ou des nombres rationnels. C'est aussi la taille de ce que serait "un ordinateur avec une mémoire infinie" (machine de Turing).
Dans ce problème, pour retenir la stratégie à appliquer, les gens ont besoin d'avoir une mémoire strictement plus grande que l'infini dénombrable, ce qui est une condition extrêmement forte.

./68 > en fait les joueurs ont décidé a priori d'une stratégie du type : si la combinaison de chapeaux est telle combinaison à un nombre fini d'erreurs près, alors je réponds telle réponse. Donc ils ont un comportement complètement déterministe (ce qui est crucial). Ils ne répondent en aucun cas au hasard.
Et ils ont passé en revue toutes les possibilités sans exception ^^ c'est pour cela qu'ils ont besoin d'une mémoire infinie et même indénombrable.

Mais admettons que TOUS les chapeaux des autres concordent. Il y a deux scénarios qui rendent ça possibles : ça correspond pour tous les autres et j'ai un bleu ou ça correspond pour tous les autres et j'ai un rouge
Non ?

L'infini indénombrable il a pas une définition simple j'imagine

Titane (./71) :
Mais admettons que TOUS les chapeaux des autres concordent. Il y a deux scénarios qui rendent ça possibles : ça correspond pour tous les autres et j'ai un bleu ou ça correspond pour tous les autres et j'ai un rougeNon ?

Oui, et les deux font partie de la classe d'équivalence "tous les chapeaux sont bleus sauf un nombre finis d'entre eux", dont le représentant qu'ils ont choisi est par exemple "tous les chapeaux sont bleus sauf les chapeux n°4, 6, 256765, 5456546546354, et 55646546543213454735432130". Alors chacun répond bleu sauf 4, 6, 256765, 5456546546354, et 55646546543213454735432130, qui répondent rouge, et il y a entre 5 et 6 erreurs (selon que le chapeau du mec dont tu parles correspond ou non à la stratégie préconisée).

Titane (./71) :
L'infini indénombrable il a pas une définition simple j'imagine

Il n'y a pas qu'*un* infini indénombrable.

Un infini indénombrable, c'est n'importe quel infini autre que le plus petit d'entre eux, l'infini dénombrable. (donc en fait si la définition est simple ^^. Par contre un infini indénombrable est impossible à appréhender intuitivement, contrairement au dénombrable)

Hippopotame (./69) :
Dans ce problème, pour retenir la stratégie à appliquer, les gens ont besoin d'avoir une mémoire strictement plus grande que l'infini dénombrable, ce qui est une condition extrêmement forte.

Ah ! Parce que l'infini dénombrable est une condition faible

Oui, clairement !

Ca ne renvoie qu'à une machine de Turing, c'est tout bête.

euhhh si une demi-infinité d'entre eux a des chapeaux rouges, et les autres des chapeaux bleus ? ça veut dire qu'on a une infinité de chapeaux bleus et une infinité de chapeaux rouges et dans ce cas ils risquent fort de faire un nombre infini d'erreurs nan ?

Ben nan. Qu'il y ait tant ou tant de chapeau de telle ou telle couleur, ça ne change rien, le cas a été traité pendant la réunion

oui sauf que même en en ayant parlé, je vois pas comment faire forcément un nombre fini d'erreurs dans le cas où ni le nombre de chapeaux bleus ni le nombre de chapeaux rouge n'est dénombrable

./71 > comme a dit dualmoo, ces deux scénarios n'ont qu'un nombre fini de différences donc la même stratégie exactement est appliquée dans les deux cas.

En fait peut-être que tu comprendras plus facilement si on commence par considérer des cas simples ; moi par exemple quand j'ai lu le problème j'ai commencé par me demander si on ne pouvait pas distinguer des cas, et je me suis dit :
ben déjà, s'il n'y a qu'un nombre fini de chapeaux bleus, alors 1/ tout le monde le sait (parce que s'il y a un nombre fini de chapeaux bleus à part moi, alors si j'ai un chapeau bleu aussi ça n'en fait jamais qu'un de plus, donc le nombre reste fini), et 2/ chacun, étant au courant de cette situation, peut dire qu'il a un chapeau rouge, et le nombre d'erreurs sera fini puisque ce sera le nombre de chapeaux bleus.

Idem s'il n'y a qu'un nombre fini de chapeaux rouges.

(Donc en fait à la réflexion j'avais presque trouvé la méthode, mais bon j'ai pas pensé à continuer : après je me suis dit : bon, ben donc il reste le troisième cas, celui avec une infinité de chapeaux de chaque ^^.) Mais en fait le truc c'est de ne pas s'arrêter en si bon chemin et de continuer à distinguer des cas de la même façon, tous les cas possibles (ce qui fait une énorme infinité), genre : tous les bonshommes pairs ont un chapeau bleu et tous les bonshommes impairs en ont un rouge, sauf un nombre fini... ça marche exactement pareil, si on est dans cette situation tout le monde est en mesure de le constater, et donc chacun peut répondre "bleu" s'il est pair et "rouge" s'il est impair, et il n'y aura qu'un nombre fini d'erreurs.

./78 > ben qu'est-ce que ça change ? le truc c'est qu'il y a une quantité invraisemblablement énorme de cas à avoir préalablement distingués, mais si tu supposes qu'ils en sont capables, ça marche toujours...

dualmoo (./72) :

Titane (./71) :
Mais admettons que TOUS les chapeaux des autres concordent. Il y a deux scénarios qui rendent ça possibles : ça correspond pour tous les autres et j'ai un bleu ou ça correspond pour tous les autres et j'ai un rougeNon ?

Oui, et les deux font partie de la classe d'équivalence "tous les chapeaux sont bleus sauf un nombre finis d'entre eux", dont le représentant qu'ils ont choisi est par exemple "tous les chapeaux sont bleus sauf les chapeux n°4, 6, 256765, 5456546546354, et 55646546543213454735432130". Alors chacun répond bleu sauf 4, 6, 256765, 5456546546354, et 55646546543213454735432130, qui répondent rouge, et il y a entre 5 et 6 erreurs (selon que le chapeau du mec dont tu parles correspond ou non à la stratégie préconisée).

Quand je dis "ça correspond", je veux pas dire que tous les chapeaux ou presques sont bleus

J'ai besoin de comprendre donc je reprends

- TOUS les scénarios sont imaginés (ils ont résolu le problème de la mémoire infinie indénombrable toussa).
- Le jour J on se rend compte que tous les chapeaux ont été attribués au hasard (pas de n° pair toussa).
- Un individu i observe tous les chapeaux et compare leur distribution à celle des scénarios imaginés
- Il se trouve qu'il y a DEUX scénarios qui marchent :
* celui qui a la même distribution que celle qu'il voit avec lui en rouge
* celui qui a la même distribution que celle qu'il voit avec lui en bleu

Comment il choisit ?
Et son voisin ?
Et le voisin du voisin ?

Titane (./80) :
- TOUS les scénarios sont imaginés (ils ont résolu le problème de la mémoire infinie indénombrable toussa).

Oui.

Pendant la réunion stratégique, chaque combinaison X de chapeaux a été abordée. Il a été décidé une certaine réponse f(X) pour chaque combinaison X.

Avec les deux propriétés suivantes :
- Si X et Y ne diffèrent que d'un nombre fini de chapeaux, alors f(X)=f(Y)
- X et f(X) ne diffèrent que d'un nombre fini de chapeaux.

- Le jour J on se rend compte que tous les chapeaux ont été attribués au hasard (pas de n° pair toussa).
- Un individu i observe tous les chapeaux et compare leur distribution à celle des scénarios imaginés
- Il se trouve qu'il y a DEUX scénarios qui marchent :
* celui qui a la même distribution que celle qu'il voit avec lui en rouge * celui qui a la même distribution que celle qu'il voit avec lui en bleu

Exact.
Il y a deux possibilités de combinaisons de chapeaux, d'après ce qu'il peut observer. Appelons les X1 et X2.

Comment il choisit ?

Ben f(X1)=f(X2).

Donc il choisit cette combinaison là : f(X1), qui est aussi f(X2).

Et son voisin ?

Son voisin c'est analogue : De son propre point de vue, il y a deux combinaisons qui sont possibles : X3 et X4.

Comme X3 et X4 ne diffèrent que d'un chapeau, alors f(X3)=f(X4), et il choisit de répondre comme si c'était cette combinaison là, f(X3)=f(X4) qui avait été tirée.


MAIS remarque bien :
Tout le monde a la même combinaison f(X) en tête !
Parce que X1, X2, X3, et X4 ne diffèrent que d'au plus deux chapeaux, et donc f(X1)=f(X2)=f(X3)=f(X4).

Donc TOUT LE MONDE répond comme si c'était cette combinaison f(Xi) qui avait été tirée. Or, cette combinaison ne diffère de la combinaison réellement tirée que d'un nombre fini de chapeaux.

[EDIT : cross]

déjà première chose, il y a bcp plus de deux scénarios qui marchent : par "marcher" en fait on entend "il n'y a qu'un nombre fini de différences entre le scénario et la réalité"... donc par exemple il y aura les deux scénarios que tu mentionnes, mais aussi le scénario "qui a la même distribution que celle qu'il voit mais avec les chapeaux n°7, 4238, 748392748923 et 43985289048239 inversés et avec son propre chapeau [le n°714] en rouge", plus plein d'autres scénarios du même style ^^

et la clé pour savoir comment choisir, c'est que ces scénarios ont tous un numéro : on va choisir le premier de ces scénarios, i.e. celui avec le numéro le plus faible et du coup ça a très très peu de chances d'être l'un des deux scénarios que tu décris, i.e. que le scénario choisi corresponde exactement à ce qu'il voit sans aucune erreur visible ; c'est nettement plus probable qu'il y ait (par exemple) une 50aine de chapeaux qui chanegnt entre ce qu'il voit et le scénario qu'il choisit.

[EDIT : double cross ]

Ben ce choix a été préalablement effectué

Parce que ce qu'ils ont fait lors de la réunion c'est pas seulement d'imaginer tous les scénarios possibles ; ça c'est le 1/ en quelque sorte, mais ensuite :

2/ regrouper ces scénarios en classes, deux scénarios appartenant à la même classe s'ils ne diffèrent que par un nombre fini de chapeaux.
Ainsi par exemple l'ensemble des scénarios où il n'y a qu'un nombre fini de chapeaux bleus constitue une classe. L'ensemble de ceux où il n'y a qu'un nombre fini de chapeaux rouges en constitue une autre. Il y a une infinité (non dénombrable) de classes, mais elles sont bien définies : étant donnés deux scénarios, tu peux dire s'ils sont dans la même classe ou pas .

3/ Pour chacune de ces classes, ils se mettent d'accord sur *un scénario particulier* appartenant à cette classe. Par exemple dans la classe des scénarios avec un nombre finis de chapeaux bleus, on choisit LE scénario où il n'y a *aucun* chapeau bleu. (Mais on pourrait en choisir un autre, l'important c'est qu'ils se mettent d'accord pour en choisir un et un seul).


Ensuite, le jour J, chacun regarde dans quelle classe se trouve le scénario qu'il observe. Ça il le sait parce que le scénario où les autres sont comme il voit et lui est en rouge, et le scénario différent où les autres sont toujours comme il voit mais lui est en bleu ne diffèrent que par son chapeau à lui, ils ont donc un nombre fini de différences, ils sont donc dans la même classe. Il n'a donc pas besoin de savoir la couleur de son propre chapeau pour savoir dans quelle classe il est.
Donc là il se rappelle quel scénario particulier S avait été choisi d'un commun accord dans cette classe, et il indique la couleur qui lui est attribuée dans le scénario S.

Comme ils sont tous capables de constater qu'on est bien dans la classe de S et qu'ils s'étaient mis d'accord au 3/, l'ensemble de leurs réponses correspond exactement au scénario S. Comme le scénario effectif du jour J est dans la classe de S, on sait qu'il n'y a qu'un nombre fini de différences avec S, donc ils n'ont fait qu'un nombre fini d'erreurs. (Mais un nombre fini qui peut être arbitrairement grand, hein, peu importe qu'il y ait un nombre à 15 milliards de chiffres d'erreurs du moment qu'elles restent en nombre fini).

Ouais, au final il y a très peu de chances que la bonne solution soit donnée quoi

Je suis sincèrement (sérieusement) désolé mais ça ne marche toujours pas.

Ben f(X1)=f(X2).
Donc il choisit cette combinaison là : f(X1), qui est aussi f(X2).

Donc il dit rouge ou bleu ?

edit : bon donc j'ai dit n'importe quoi ^^

Titane > il dit ce qu'ils ont décidé lors de la réunion qu'il devait dire. Que ce soit rouge ou bleu dépend de ce qu'il voit...

Il y a très peu de chance que la solution exacte soit donnée, mais il y a 100% de chance que tous sauf un nombre fini aient raison, donc individuellement ils ont 100% de chance d'avoir juste. (bicross)

Mais il répond rouge ou bleu ?

Titane (./85) :

Ben f(X1)=f(X2).
Donc il choisit cette combinaison là : f(X1), qui est aussi f(X2).

Donc il dit rouge ou bleu ?

Appelons C cette combinaison de chapeaux f(X1)=f(X2).

Si dans C, son chapeau est bleu, alors il dit bleu, et s'il est rouge il dit rouge.

Sally (./86) :
Hum en fait à strictement parler j'aurais tendance à dire que non : quel que soit N, il y a presque sûrement plus de N erreurs, non ? ^^ donc c'est exactement aussi probable qu'il y en ait 0 et qu'il y en ait moins de 50 ou moins de 10^10^10^10

Non.
On ne peut pas faire de probabilité, parce que l'ensemble des représentants choisis, qui constituent la stratégie, n'est pas mesurable.


D'ailleurs il n'est pas possible que P(X<n)=0 pour tout n, parce que ça voudrait dire que les évènements {X<n} sont presque impossibles, et donc que leur réunion (dénombrable), qui est l'évènement certain, est presque impossible aussi :/

Concrètement, c'est utile dans quel domaine d'application ?