logo Homepage
+  NewbieContest
|-+  Général» Defouloir» Enigme du soir, Bonsoir !
Username:
Password:
Pages: 1 ... 8 9 [10] 11
  Imprimer  
Auteur Fil de discussion: Enigme du soir, Bonsoir !  (Lu 111502 fois)
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #135 le: 30 Avril 2017 à 23:50:00 »

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).
« Dernière édition: 30 Avril 2017 à 23:51:48 par harvey » Journalisée

L'entropie vient en mangeant.
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #136 le: 30 Avril 2017 à 23:54:18 »

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

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #137 le: 13 Mai 2017 à 22:10:59 »

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
« Dernière édition: 13 Mai 2017 à 22:14:21 par harvey » Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #138 le: 14 Mai 2017 à 20:29:53 »

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:

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

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #139 le: 15 Mai 2017 à 23:14:31 »

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.
Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #140 le: 19 Septembre 2017 à 03:47:31 »

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!
Journalisée
pixis
Administrateur

Profil challenge

Classement : 16/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 664


Voir le profil WWW
« #141 le: 19 Septembre 2017 à 16:45:16 »

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é.
Journalisée

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #142 le: 22 Septembre 2017 à 23:22:43 »


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
Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #143 le: 23 Septembre 2017 à 14:09:09 »

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é).
Journalisée
cssm
Profil challenge

Classement : 2382/54254

Néophyte
*
Hors ligne Hors ligne
Messages: 2


Voir le profil
« #144 le: 10 Février 2018 à 20:17:01 »

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/
Journalisée
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #145 le: 27 Décembre 2018 à 19:00:11 »

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 ?
Journalisée

L'entropie vient en mangeant.
BAAL

Profil challenge

Classement : 13/54254

Membre Héroïque
*****
Hors ligne Hors ligne
Messages: 532


Voir le profil
« #146 le: 30 Décembre 2018 à 00:52:59 »

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).
Journalisée
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #147 le: 30 Décembre 2018 à 18:57:53 »

https://oeis.org/A000031

Les solutions pour n=4 ou n=7 peuvent aider...
Journalisée

L'entropie vient en mangeant.
harvey

Profil challenge

Classement : 12/54254

Membre Senior
****
Hors ligne Hors ligne
Messages: 316


Voir le profil WWW
« #148 le: 24 Octobre 2019 à 13:58:57 »

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)
« Dernière édition: 25 Octobre 2019 à 12:42:55 par harvey » Journalisée

L'entropie vient en mangeant.
Touhead

Profil challenge

Classement : 89/54254

Néophyte
*
Hors ligne Hors ligne
Messages: 11


Voir le profil
« #149 le: 14 Novembre 2019 à 03:07:24 »

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...
Journalisée
Pages: 1 ... 8 9 [10] 11
  Imprimer  
 
Aller à: