[harvey]

puisque l'ensemble de prisonniers est indénombrable

L'ensemble des prisonniers est dénombrable (aleph-zéro). Autrement, ils ne pourraient pas tous répondre séquentiellement.

J'avais le même avis que toi: ça a vraiment l'air infaisable.
Le principe est de diviser l'ensemble des mondes possibles en classes, de telle sorte que
1. les prisonniers puissent constater dans quelle classe se trouve le monde réel
2. la "distance" entre deux mondes possibles d'une même classe soit finie
3. on puisse choisir un monde de référence au sein de chaque classe (l'axiome de choix sert à ça, entre autre)
À partir de là, je pense qu'il en faut peu pour trouver la solution (mais peut-être que ce que je raconte est imbitable).

[pixis]

Pour le moment, je suis d'accord avec les derniers mots de ton dernier post. Il faudra que je revienne dessus.

[harvey]

Alors si ça intéresse encore quelqu'un, voici la solution telle que je la comprends.



On considère que deux séquences de couleurs sont "semblables" si et seulement si le nombre de différences entre elles est fini. Cette relation est transitive: soient trois séquences A,B et C, le nombre de différences entre A et C est, au plus la somme du nombre de différence entre A et B et entre B et C  (et au moins l'écart entre ces deux nombres). C'est donc une relation d'équivalence, et on peut découper l'ensemble des séquences de couleurs possibles en sous-ensembles de séquences semblables (classes d'équivalence). Chaque classe contient une infinité (dénombrable) de séquences, et il y a une infinité (indénombrable) de classes.

Pour décider si une séquence S appartient à une classe C, il suffit de "compter" le nombre de différences entre S et une séquence quelconque de C. Si ce nombre est fini, S appartient bien à C. Pendant la préparation, les prisonniers s'entendent pour choisir une séquence dans chaque classe (c'est là qu'intervient l'axiome de choix, qui dit que c'est possible); appelons-les les représentantes. Puis pendant l'exercice, ils comparent la séquence réelle (appelons-la R) avec chacune des représentantes. Pour une et une seule d'entre elles (appelons-la Q), ils trouveront un nombre de différences fini. À partir de là, on procède comme dans le cas fini. Le premier prisonnier qui parle indique, en disant "noir" ou "blanc", si le nombre de différences qu'il voit entre R et Q est pair ou impair. Le suivant compare cette parité avec le nombre de différences qu'il voit, lui, entre R et Q. Si c'est la même, alors le bit qui correspond à sa position est le même que dans Q, sinon il est différent.

Alors évidemment, on ne peut pas *construire* les objets dont on parle, et il suffit que l'un des prisonniers se trompe pour tout foutre en l'air. Mais ce sont les hasards de la vie.



Voici la vidéo dans laquelle j'ai trouvé ce problème (tout ce qui est sur la chaîne est excellent):
https://www.youtube.com/watch?v=aDOP0XynAzA

[BAAL]

Moi ça m’intéresse toujours .

C’est juste que je pensais avoir trouvé une solution valable, et après avoir vu la solution, je crois que la mienne marche toujours. En fait c’est peut-être la même solution, juste formulée de manière bien moins élégante. Mais j’ai peut-être tort...

Je ne connaissais pas mathologer, j’ai regardé plusieurs vidéos maintenant, et j’aime beaucoup, merci pour la référence!

Par contre je connaissais une autre chaîne du genre: Numberphile. D’ailleurs, voici un problème que j’ai vu sur Numberphile, mais dont je n’ai pas encore regardé la solution (et je n’ai pas encore vraiment essayé résoudre). Je chercherai donc en même temps que vous:

Soient a et b deux entiers positifs. Prouvez que si (a²+b²) est divisible par (ab+1), alors (a²+b²)/(ab+1) est le carré d’un entier.

[harvey]

J'ai relu ta réponse. Si je comprends bien, le code associe à chaque séquence un bit 0 ou 1, avec la propriété que deux séquences ont un bit différent si elles ont un nombre impair de différences, et le même bit si ce nombre est pair. Ça revient effectivement au même. Je donnais aussi le même bit à toutes les représentantes, mais comme celles-ci sont choisies au hasard, je crois que ça ne change rien.

Je zyeute ton problème.

[BAAL]

Histoire de relancer cette conversation et de vous motiver, voici la vidéo où j’ai découvert le problème ci-dessus.
Ça vaut le coup de s’y mettre .

https://www.youtube.com/watch?v=Y30VF3cSIYQ

Bon j'avoue que c'était assez difficile.
Passons donc à l’épreuve suivante!

Voyez le jeu suivant:
http://www.web-games-online.com/peg-solitaire/index.php

Il existe en deux versions, française et anglaise.
Prenez le temps de jouer quelques parties, c’est fun!

Ce qui est intéressant c'est que dans la version française, si on commence avec le pion central manquant, il devient impossible de résoudre le problème.
Votre mission est de le prouver!

[pixis]

Ah je connais ce jeu, j'avais appris à le résoudre (version anglaise) ya loooongtemps, mais on a un cerveau étonnant et tous les automatismes sont revenus. Il faut que j'essaie la version française, pour me retrouver face à l'impossibilité de le résoudre avec en situation initiale la pièce centrale manquante, et comprendre l'impossibilité.

[harvey]

On associe des nombres aux cases comme ceci:
le centre vaut 0, et à chaque fois qu'on va vers le haut ou vers la droite on ajoute 1 modulo 3.
Inversement, on soustrait 1 mod 3 quand on va vers le bas ou la gauche.
Ça donne quelque chose comme ça:
   
        201
       01201
      1201201
      0120120
      2012012
       20120
        201

D'après la règle, pour qu'un pion arrive sur une case 0, il doit soit partir d'une case 2 et retirer un pion d'une case 1,
soit partir d'une case 1 et retirer un pion d'une case 2.
Si on compte le nombre de pions sur chaque type de case avant et après le coup, on obtient dans les deux cas ceci:

       0       1      2
avant: x       y      z
après: x+1     y-1    z-1

On voit que la parité des trois nombres change simultanément. S'il sont tous les trois pairs, ils deviennent tous impairs. Et s'ils sont tous impairs, ils deviennent tous pairs.
C'est aussi le cas avec les autres types de coups.
Or la position de départ avec le pion manquant au centre a 12 pions sur les cases 0, 12 sur les cases 1 et 12 sur les cases 2.
Elle ne peut pas être convertie en une position avec une seule valeur impaire.
Il est donc impossible de ne laisser qu'un seul pion.
.

Mais je ne sais pas prouver que l'autre version est solvable

[BAAL]

Pas mal du tout! bien joué harvey. C’est exactement la preuve que j’avais lu sur Wikipedia.
En fait je ne savais pas que c’était impossible et j’ai essayé de résoudre pendant plusieurs heures. Au final je suis allé voir la page du jeu sur Wikipedia pour m'inspirer et je me suis rendu compte que c’était impossible, en voyant une belle preuve comme la tienne.

Pour prouver que l’autre version est solvable, il te suffit de la résoudre . (Ça j’y suis arrivé).

[cssm]

Pour ceux qui ont de l'endurance en mode bien costaud, cette chasse au trésor sur le thème SF de Philip K Dick a l'air pas mal : http://chasse-au-tresor-pkd.com/

[harvey]

Pour la SIGSEVv1, Pixis a préparé un gâteau au chocolat et à la fraise.
Le gâteau est circulaire, la pâte au chocolat en dessous, et celle à la fraise au dessus.

Il partage le gâteau en 10, et invite les 10 premiers au challenge à le déguster dans l'espace VIP.

Mais l'un.e des 10 insiste pour avoir le chocolat au dessus ! Manque de bol, il n'y a qu'un seul plat et le seul outil pour retourner les parts est une pelle magique qui fait exactement 3/10 de la surface, et permet seulement de retourner 3 parts contigües. #logistique

Combien faut-il d'opérations de retournement pour avoir exactement une part avec le chocolat sur le dessus ?

Pendant qu'il réfléchit, les challengers cherchent le moyen de l'embêter le plus possible, parce que le chall avec les pirates qui se disputent le contrôle de la tireuse à bière était vraiment trop hardcore. Il cherchent donc combien de parts avec le chocolat au-dessus lui demander pour maximiser le nombre de retournements. Que vont-il trouver ?

[BAAL]

On se rend compte assez vite qu’il n’y a pas tant d’états uniques grâce aux symétries. J’ai donc fait un double-sided breadth-first-search à la main (cherchant à partir du début et de la fin en même temps afin de trouver une intersection plus tôt).

Mais c’est quand même long... il faudra au moins 6 coups. Et pour la deuxième question, on se rend compte assez facilement que la réponse sera soit 1 soit 10.

Je laisse tomber pour l’instant par manque de temps. Bonne chance aux autres! Quelques questions qui m’intriguent: Comment généraliser pour n’importe quel entier positif n et k (ici n=10 et k=3).

Y a-t-il une formule pour calculer le nombre d’états uniques (dépendant seulement de n). Par exemple, les états 0011000111 et 1110001100 sont les mêmes et ne devraient pas être comptés deux fois (les chaînes ci-dessus devraient être circulaires).

[harvey]

https://oeis.org/A000031

Les solutions pour n=4 ou n=7 peuvent aider...

[harvey]

Un instrument de musique est composé d'une bassine circulaire, d'un mât vertical central et de trois cordes identiques.
Les cordes sont tendues entre le sommet du mât et le bord de la bassine. Le pied du mât est au creux de la bassine.
Comment choisir les points de fixation des cordes à la bassine pour que les trois notes forment un accord majeur "parfait" (eg. Do-mi-sol) ?

(On suppose que la bassine ne se déforme pas, et que le mât est tenu droit par la tension des cordes)

[Touhead]

Pour le gateau de la SIGSEVv1, il existe une solution en 7 retournements relativement simple si on pense a utiliser les proprietes circulaire du gateau :
0 - 0000000000
1 - 1110000000
2 - 1111110000
3 - 1111111110
4 - 1111111001
5 - 1111100101
6 - 1100000101
7 - 0000000100

Pour la deuxieme question, il me semble que la reponse est 10 (il devrait etre impossible d'obtenir 10 sans passer par l'etat avec 1 part retournee).
Ou peut etre, the cake is a lie...