encore une petite colle

[shadoko]

Samish a la bonne réponse, mais il faudrait qu'il s'explique pour ses petits camarades...

[othar]

en attribuant par exemple une valeur 0 au bonnet rose,1 au vert,et 2 au jaune, on a un probleme de congruence de la "somme des bonnets" modulo 3 permettant d'en sauver 99 au moins.

Impresionnant, je crois que je n'aurais jamais penser à penser "congruence"!

mais je vois toujours pas la solution...
on n'utilise quand même pas le théorème chinois?

[Cyrano]

J'ai pas compris ce que la somme des bonnets modula permettrait de faire...
J'ai trouvé une solution sur internet :emb: pour deux couleurs...
Donc, ensuite...

je propose qu'on désinscrive Shadoko, ses trucs c'est pour nous bouffer du temps et que chez moi on me dise: "Mais c'est pas vrai que t'en es encore à ton histoire de bonnets?!"

En plus, moi, avec le manque de bol que j'ai, j'étais sauvé d'office: j'aurais eu un bonnet rose, alors... les autres, qu'ils se démmerdent...

[shadoko]

en attribuant par exemple une valeur 0 au bonnet rose,1 au vert,et 2 au jaune, on a un probleme de congruence de la "somme des bonnets" modulo 3 permettant d'en sauver 99 au moins.

Impresionnant, je crois que je n'aurais jamais penser à penser "congruence"!

mais je vois toujours pas la solution...
on n'utilise quand même pas le théorème chinois?

Non, non, ce n'est pas si chinois que ça.

Sinon, pour ceux qui ne comprennent rien à ce qui se dit là, j'expliquerai les choses en termes clairs dès que j'aurai le temps (si Samisch ne l'a pas fait...).

[shadoko]

Bon, pour bien comprendre la réponse, il faut d'abord apprendre à compter d'une manière un peu spéciale, mais facile.

On ne se sert que de 3 chiffres: 0, 1 et 2.

Quand on compte, "dans l'ordre", ça fait:

0,1,2,0,1,2,0,1,2, etc...

on "retombe" sur 0 après 2.

Ce qui est amusant, c'est qu'on peut quand-même faire des additions:

0+0=0
0+1=1
0+2=2
1+1=2

jusqu'ici, tout va bien, c'est comme d'habitude, mais

1+2=0 (et oui, parce qu'on retombe sur 0 après 2).
2+2=1
Cette dernière ligne est peut-être plus claire en décomposant le deuxième 2 en 1+1, c'est à dire:
2+2=2+(1+1)=(2+1)+1=0+1=1

Bon, une fois qu'on a compris les additions, on passe aux soustractions.
Il faut se rappeler d'un vieux truc.
D'habitude, faire 7-5, c'est comme faire 7+ (-5)
Donc, "soustraire" 5, c'est comme une addition, du moment qu'on sait ce qu'est le nombre -5. On cherche "l'opposé de 5".
Et -5, c'est le nombre tel que quand on fait 5+(-5), on trouve 0.

Ici, on va faire pareil. Quel est l'opposé de 0?
C'est facile, on cherche le nombre x tel que 0+x=0. On regarde dans toutes les additions qu'on a faites, et on trouve que c'est... 0. Donc, l'opposé de 0, c'est 0. Autrement dit,
-0=0

Quel est l'opposé de 1? C'est 2, puisque 2+1=0. Donc
-1=2

De même -2=1.

Voilà. Maintenant, on sait faire les soustractions:

1-1=1+(-1)=1+2=0

1-2=1+(-2)=1+1=2

Compris? Je les donne toutes pour qu'on puisse vérifier qu'on a compris:

1-0=1
1-1=0
1-2=2
2-0=0
2-1=1
2-2=0
0-0=0
0-1=2
0-2=1

Bon, maintenant, on pourrait apprendre à multiplier (facile) et à diviser (moins facile) par certains nombres. Mais on en a pas besoin pour l'énigme.

Dans le prochain message, j'explique l'énigme grâce à cette nouvelle manière de compter.

[othar]

je rajoute, pédagogie oblige :hinhin: , que cela revient à faire des additions, des soustractions en prenant les reste des divisions des nombres entiers (sans virgule) par 3:

le nombre 0 correspond aux nombres entiers qui sont des multiples de 3 (donc qui peuvent se mettre sous la forme 3p)

le nombre 1 correspond aux nombres entiers qui peuvent se mettre sous la forme 3p+1 (ex:1;4;7;10;-2;-5;-8, etc)

le nombre 2 correspond aux nombres entiers qui peuvent se mettre sous la forme 3p+2
(ex:2;5;8;-1;-4;-7,etc)

Par exemple, quand on multiplie un multiple de 3 par n'importe quoi, on obtient....
un multiple de 3 (cela revient ici à l'opération 0Xk=0 )

Pour l'anecdote, on obtient un ensemble (nommé Z/3Z) qui contient 3 éléments (0 1 et 2) qui a certaines propriétés interessantes (en particulier car 3 est un nombre premier).

[shadoko]

D'abord, il faut bien réfléchir à l'information dont dispose une personne au moment où elle doit parler:
-elle a entendu ce qu'on dit tous ceux qui sont derrière elle.
-elle voit tous ceux qui sont devant elle.

Donc en fait, elle sait pas mal de choses. S'il y avait une sorte de chose globale dont elle puisse déduire sa couleur en connaissant toutes les autres, ce serait facile... mais cette chose existe.

Si je vous donne plein de nombres, que vous les connaissez tous sauf 1, et que je vous donne la somme, c'est pas difficile de trouver celui qui manque. Il suffit de tous les soustraire à la somme, et c'est gagné. Et bien, c'est de ça dont on se sert pour l'énigme...

L'idée, c'est d'associer à chaque couleur un nombre (0, 1 et 2). Disons

vert=0
jaune=1
rose=2

Donc, maintenant, au lieu de dire: les prisonniers ont une couleur sur la tête, on fait comme si ils avaient un nombre sur la tête.

Le premier prisonnier à parler donne alors la somme de tous les nombres qu'il voit devant lui (donc des 99 nombres devant lui), avec notre nouvelle manière de compter. Il dit donc 0, 1 ou 2, selon que cette somme est 0, 1 ou 2. Tous les prisonniers ont bien entendu ce nombre, et le retiennent. On va l'appeler TOTAL pour se rappeler.

Le deuxième prisonnier voit tous les nombres devant lui (il y en a 98), il peut les soustraire au nombre TOTAL qu'il vient d'entendre. Ca lui donne donc son nombre. Il le dit.

Le troisième prisonnier voit tous les nombres qu'il y a devant lui (il y en a 97), il peut les soustraire au nombre TOTAL. Puis, il soustrait encore au résultat le nombre qu'à dit le deuxième. Il obtient encore son nombre. Il le dit.

Etc... chaque prisonnier soustrait de TOTAL tous les nombres qu'il voit devant lui, et tous ceux qu'il a déjà entendu à partir du deuxième qui a parlé.

Pour vérifier qu'on a compris, on peut se demander que diraient les prisonniers si les nombres sur leurs têtes étaient (en partant du dernier, donc le premier qui parle), et en supposant qu'ils ne sont que 5 prisonniers (ça ne change rien):

2,1,1,0,2

J'écris ce que prononcent dans l'ordre les prisonnier, et le calcul qu'ils font:

dernier:
1+1+0+2=1 donc TOTAL=1, et je dis "un" (et malheureusement, je suis mort).

ensuite:
TOTAL-(ce que je vois)=TOTAL-1-0-2=1-1-0-2=1, et je dis "un" (et je suis sauvé).

ensuite:
TOTAL-(ce que je vois)-(ce que j'ai entendu)=TOTAL -0-2 -1 =1-0-2-1=1,
je dis "un" (et je suis sauvé).

ensuite:
TOTAL-(ce que je vois)-(ce que j'ai entendu)=TOTAL -2 -1-1 =1-2-1-1=0,
je dis "zéro" (et je suis sauvé).

ensuite:
TOTAL-(ce que je vois, c'est à dire rien)-(ce que j'ai entendu)=TOTAL -1-1-0=2,
je dis "deux" (et je suis sauvé).

Tout le monde à pigé?

On peut noter qu'on peut poser la même question avec 1000 prisonniers, et 7 couleurs, par exemple, et en apprenant à compter "modulo 7" au lieu de "modulo 3", on peut sauver de même 999 prisonniers...

[othar]

moi je pense au premier qui se sacrifie pour tous les autres.... :(