Souffrance, désespoir, que d'être dans un openSpace sans casque 
Je pense avoir compris qu'on ne parlait pas de mouton, mais j'ai pas la réponse.
moud t'on?
Ce n'est pas exactement la réponse que j'attendais, mais cariopes, c'est à toi !
Le café, où le moud t'on ?
Dans un moulin !
Désolé si elle est déjà passé, je me souviens plus trop, elle est plutôt connue mais toujours aussi intéressante :
Un homme se retrouve face à deux portes gardés par deux gardiens, une des portes le mèneras à la gloire, la richesse et le pouvoir, l'autre le conduiras dans les ténèbres et la mort. Il ne peux ouvrir une porte sans être condamné à s'y engager. Les gardiens connaissent les destin de chaque porte. Malheureusement un gardien ment toujours tandis que l'autre dis toujours la vérité.
Vous avez le droit de poser une et une seule question pour trouver la bonne porte !
Quelle est cette question?
Aaaaaaaaaah bah j'peux enfin ressortir mon xkcd 
Non, elle est pas sortie, mais elle est connue 
Et pour l'image de Javier, je l'ai vue dans mon livre d'ISN XD
Je me souviens avoir entendu cette énigme il y a longtemps, mais j'avais oublié la réponse, après réflexion j'ai trouvé ça :
Je me suis représenté le truc comme ceci :
On donne un nombre, un garde le multiplie par +1 (en disant vrai), et l'autre par -1 (en mentant), il faut donc multiplier les nombres des deux gardes pour être certain de la solution
Donc la réponse est :
"Que me dirait l'autre garde si je lui posais la question ?"
A toi la main Le Nain !
J'ai déjà vu cette manière de raisonner je la trouve géniale, ça dénote un sens de l’abstraction intéressant, pour vouloir directement se ramener à des équations mathématiques
Attention quand même. Si on pose cette question à l'un ou à l'autre des deux gardes, il nous indiquera le chemin à ne pas emprunter. N'allez pas vous faire avoir.
Alors je propose deux énigmes, la première qui est plus un problème que je n'ai pas su résoudre (donc je ne connais pas la réponse), la deuxième est une énigme plus classique pour ne pas briser le topic. Il suffit donc de trouver la réponse à la deuxième pour avoir la main, mais je pense que la première vous intéressera.
Je soumets la première à vos nobles méninges, je suis sûr qu'à nous tous on doit pouvoir faire quelque chose : Je suis invité chez des amis, et arrivés devant la porte de leur immeuble, je me trouve face à un digicode. Bien sûr, dans ma précipitation, je n'ai pas noté le code quand ils m'ont invité, et mon portable est déchargé. Je veux donc "hacker" le code, en testant tout simplement tous les codes possibles. Pour simplifier, disons que je me souviens qu'il y a 4 chiffres et aucune lettre. Bien sûr la solution logique qui vient est de tester comme ceci :
0000
0001
0002
…
9999
Mais pour que ça soit intéressant, il faut voir que le mécanisme de digicode ne se "reset" pas tous les 4 chiffres, par exemple si je teste 0012 puis 3400, et que le vrai code est 1234, la porte va s'ouvrir (j'aurais bien mis '1234' puisque j'aurais entré '00123400'). La première solution n'est donc pas la plus optimisée (certains codes sont testés plein de fois !).
Deux questions :
a) Existe-t-il une solution optimale où l'on testerait tous les codes qu'une et une seule fois ?
b) Comment peut-on "construire" une suite de chiffres la plus courte possible contenant tous les codes ? Je pense que les meilleurs d'entre nous en programmation auront certainement des idées intéressantes.
L'énigme plus classique maintenant : Le calife Al Nain va mourir, et écrit ses dernières volontés. Il veut que l'on donne toute sa fortune, ses palais, sa bateaux (tout ce qu'il possède en fait) aux pauvres et aux sans-logis, en gardant simplement son troupeau de chameaux, pour que celui-ci soit partagé entre ses trois fils. L'aîné doit hériter de la moitié du troupeau, le second doit en recevoir le tiers et le benjamin le neuvième. Al Nain meurt, et l'on exécute ses volontés. Seulement voilà, il a 17 chameaux (et ce serait dommage de couper un chameau en deux). Comment les partager entre ses fils ?
Pour ta première énigme :
C'est un problème cousin au code de Grey j'ai l'impression. Tu veux trouver une suite de 4 chiffres tel que
Sur papier j'ai peut-être une technique mais je ne suis pas sur du tout. Je tenterais une petite expérience de programmation peut-être.
Idée naïve :
A chaque préfixe de trois chiffres, on associe un compteur de
Je précise au sujet de la première énigme ce que j'ai déjà trouvé :
Pour simplifier à fond le problème j'ai fait un raisonnement où on n'a que 2 symboles possibles (le code n'est composé que de 0 et de 1). Ensuite j'ai demandé à un programme (python) de chercher une suite de chiffres contenant tous les codes possibles de longueur L en faisant varier L (pour que ce soit clair : dans le problème tel que je l'ai posé plus haut L = 4). Et j'ai constaté que quel que soit L, il existait toujours une suite de chiffre contenant tous les codes une et une seule fois. Mais c'est complètement empirique, je ne saurais pas le démontrer ! Et peut-être que ça ne marche qu'avec 2 symboles. En plus ça ne répond pas à la question b.
Idée pour la première énigme (pas sur que ça marche ou que ce soit optimal):
on écrit tous les nombres de 0000 a 9999. On relie entre eux les nombres qui ont 3 chiffres communs, l'un en début du nombre, l'autre a la fin (par exemple 2343 et 3435). On obtient un graphe, et on cherche un chemin eulérien, ie qui passe une seule fois par chaque nombre. On écrit alors la séquence obtenue sur ce chemin en éliminant a chaque fois les 3 chiffres doublons (dans l'exemple on obtient 23435). Après est ce que la théorie des graphes nous donne un outil pour trouver le nombre de chiffres optimal a la main, sans passer par une simulation info?)
Dans tous les cas on se frotte au problème suivante : montrer l'existence de la solution. Ok on a facilement un algorithme pour la calculer mais on a rien qui nous prouve l'existence de l'algorithme.
Peut-être qu'avec ta modélisation looping :
Si on montre que chaque nœud à autant d'arc sortant que d'arc entrant on peut montrer l'existence d'une telle solution.
Edit :
Bon si on construit le graphe de looping, c'est assez facile de démontrer qu'un chemin eulérien existe. Prenons un noeud au hasard
Pour la b :
Si on suit la modélisation par graphe : Il y a 10000 noeuds. A chaque noeud que l'on visite on ajoute un chiffre. Ce à quoi il faut rajouter les chiffres du noeud de départ. Donc si je ne me trompe pas ça fait 10003 chiffres. Si on divise par 4 ça fait 2500 codes à entrer plus trois chiffres.
Pour la b
Tout à fait, et on peut généraliser en nommant
La solution la moins bonne (du type 0000, 0001, 0002… 9999) est elle de taille
Pour les chameaux :
Même idée que pour les clopes (voir plus haut), on emprunte un chameau, on fais le partage et il reste un chameau, on le rend. Personne n'est lésé vu que tout le monde à eu plus que prévu. Je laisse la main à l'autre énigme.
Cariopes a trouvé !
Effectivement, c'est la même idée en un peu plus alambiqué.
J'ai un peu peur qu'on ne trouve pas la réponse à l'autre énigme donc je propose qu'on se donne 1 ou 2 jours pour trouver et si on n'a toujours pas de solution, cariopes ou qui voudra prendra la main.
EDIT : Il semblerait que ce soit en fait dans les règles mêmes du topic énoncées par Cirdo
Cariopes a trouvé !
Effectivement, c'est la même idée en un peu plus alambiqué.
J'ai un peu peur qu'on ne trouve pas la réponse à l'autre énigme donc je propose qu'on se donne 1 ou 2 jours pour trouver et si on n'a toujours pas de solution, cariopes ou qui voudra prendra la main.
En quoi la solution n'a pas été trouvé ?
Pour la a) c'est oui. Pour la b) Construire le graphe et faire un parcours eulérien
En quoi la solution n'a pas été trouvé ?
Au temps pour moi, étant mauvais connaisseur de la théorie des graphes, je n'avais pas compris que les solutions proposées résolvaient bien complètement l'énigme… Donc à toi la main !
J'espère que l'énigme n'a pas déjà été proposé.
Etant donné un carré, on vous demande de le paver avec des triangules tel que tous les angles de chaque triangule soient aiguës. Evidemment, les angles droits ne sont pas autorisés.
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
