Défi : nombre mystère et détection de mensonge

[Juzo]

Bonjour à tous,

Un sujet pense à un nombre entre 0 et 15. Vous devez poser sept question à celui-ci, qui peut répondre par oui ou par non, et peut mentir au plus une fois.
A l'issue des sept questions, vous devez être capable de dire si le sujet a menti, et dans ce cas à quelle question, et d'indiquer le nombre qu'il avait choisi.

Comment vous y prenez-vous ?

Question subsidiaire : Montrer qu'il fallait au moins sept questions.

Pensez aux spoilers pour vos réponses
-----

[Médiat]

Bonjour,

Très bonne énigme qui, pour les curieux est liée aux codes auto-correctifs ...

[ansset]

est ce que tout tpe de question est autorisé ?
par exemple.
-as tu déjà menti ? ( même s'il ment à cette dernière ) ou bien
-le chiffre appartient il à l'ensemble {0,2,4,6}
à titre d'exemple

[mike.p]

Salut,

est ce que les tests de relations supérieur sont autorisés ?

[A voir en vidéo sur Futura]

[ansset]

pour l'instant, je m'autorise toute question mathématique.
voilà ou j'en suis.

 Cliquez pour afficher

1)le nb est il pair ?
2)le nb est il <=7 ?
3)le nb app il à {0,3,4,7,8,11,12,15}?
( si la formulation n'est pas had-hoc , on peut la formaliser plus proprement )
4)le nb est il congru à 0 mod 3 ?
au final
-si pas de mensonge, rep=0
-si mensonge à la 1), rep=3
-si mensonge à la 2), rep=12
-si mensonge à la 3), rep=6
-si mensonge à la 4), rep=4

Et il me reste des questions.....
A suivre.

[ansset]

correction, je suis parti des réponses oui à chaque fois , ma réponse est donc loin d'être complête dans les arborescences.
j'ai omis toutes les symétries, mais on abouti à des cas uniques de manière similaire.
à tout à l'heure.

[ansset]

en fait ma segmentation n'est pas bonne. ( questions mal agencées pour une bonne discrimination )
mais je garde l'idée d'une démarche.
poser 4 questions dont l'ensemble amène 1 seul résultat, avec des résultats tous différents.
il y a 15 combinaisons OOOO,OOON,.... pour 16 solutions.
ceci au départ sans savoir si il y a eu mensonge ou pas.
resterait ensuite 3 questions pour déterminer si mensonge et à quelle question, ce qui ramène à la combinaison vraie qui est supposée ne donner qu'un seul résultat.

[Médiat]

Bonjour,

il y a 15 combinaisons OOOO,OOON,....

Il y en a bien 16 (=2^4)

[ansset]

oui, oui, désolé.
j'ai une bonne combinaison de questions maintenant. ( dans l'esprit de ma démarche )
me reste à finaliser.
a tout de suite.

[ansset]

résumé de ma première étape:

 Cliquez pour afficher

Q1) nb pair ?
Q2) <=7 ?
Q3) congru à 0 ou 3 mod(4)
Q4) congru à 0,1 ou 2 mod(7)
il n'y a qu'un résultat pour suite qcq de réponse parmi les combinaisons.
( qu'il y ait eu ou pas mensonge , ce qui n'était pas le cas avec mes questions précédentes ).
et tous les résultats sont possibles.
reste 3 questions pour déterminer si il y a eu mensonge qcq part et retrouver la combinaison réelle et donc à la fois le résultat et la réponse mensongère.

en espérant être dans une bonne direction.

[ansset]

pour la fin:
peut on poser une question autre que mathématique :
- m'as tu menti par exemple ?

la réponse induit fortement la nature de mes trois dernières questions.

[mike.p]

Salut,

c'est inutile de poser des questions compliquées

Mais la question "as tu menti ?" , sachant que X est l'inconnue et R ta proposition en cours, pourrait être simplement ( X == R ? )

A tout à l'heure

[ansset]

Salut,

c'est inutile de poser des questions compliquées

salut,
je ne sais pas ce que tu appelles "compliqué" ?
( parlais tu des premières questions ? )
il y a peut être une astuce subtile qui m'échappe !?
reste qu'il faut bien 7 questions.
et de mon coté, j'ai suivi une voie, et ta remarque me permet effectivement de formaliser simplement les dernières et de conclure.
Cdt

[ansset]

à écrire proprement quand même.
je veux dire que la question citée était un exemple.
pas encore structuré les 3 dernières, pas le temps....
Cdt

[Juzo]

Je n'avais pas vu vos messages ! Il vaut mieux éviter les questions du "type as-tu menti ? " dans la solution recherchée. En effet comme le disait Mediat la solution fonctionne aussi dans le cas où il ne s'agit pas de détecter un mensonge, mais une éventuelle erreur du sujet

[ansset]

OK, merci Juzo
et à la réflexion ( si je suis mon idée ) , je ne trouve pas les questions à priori simplistes, même les dernières, comme le sous entend peut être Mike.
par exemple, pour la 5ème, il peut aussi avoir une réponse fausse sans l'avoir eu avant.
ce qui complique un peu les choses.
au total, en fonction des réponses obtenues, il y a 5 solutions possibles mais que l'on connait.
je pense qu'il faut travailler les 3 dernières questions en fonction des cas possibles.

dis moi juste si je suis sur une voie qui aboutie ?
Cdt

[ansset]

ps : c'est ton énoncé qui parle de "mentir": anyway, cela revient au même : réponse erronée.

[mike.p]

je ne répondais qu'à la dernière question sans avoir lu le spoiler.

Pour la simplicité ou le format autorisé des questions, c'était juste un râle générâle pour les questions sans format dans l'énoncé ... Ici, ça va.

Si c'est un code non intéractif, ce sont donc des éléments de réponses pré-établis et donc , en effet, on ne peut demander si un résultat est juste, il faudrait à nouveau autant de questions. Ou bien ce serait un autre problème.

Ce qui est intéressant dans ce genre de questions, c'est la contrainte apportée par l'hypothèse de tant d'erreurs au maximum.

[ansset]

ben , une erreur max suffit bien comme ça
( au passage c'est 0 OU 1 ce qui est un facteur de plus )
il reste que même avec une bonne dichotomie au départ ( il y en a beaucoup de possible ), je reste bien ennuyé sur la fin.
il me faut trouver une forme de "rétroaction" à la 5 ème je pense.
( auto-adaptation dirait Médiat )
mais peut être faut il le faire avant......sachant que l'erreur peut se situer à "tous les étages".
donc d'une certaine manière activer un mode "contradiction possible" plus tôt.
mais 4 questions pour 16 résultats me semblaient un bon point de départ ( oui/non : 4²=16 )

[ansset]

du coup, ça m'amuse et m'excite en même temps, car normalement ce type de logique devrait résonner avec mes gènes d'Ingé..
même si le temps me manque aujourd'hui.
Cdt.

[mike.p]

Je ne peux par répondre pas parce que je connaissais déjà quand c'est un code.

Mais j'espérais que ce serait une variante intéractive avec des questions ne portant pas sur des bits. Il faut dans ce cas réarranger les questions pour ne jamais dépasser 7 ou ... utiliser le code non intéractif ( que la réponse finale nommera ).

[ansset]

je comprend,
si je continue ma logique,

 Cliquez pour afficher

en cas de non erreur aux 4 premières questions , il n'y a qu'une réponse possible.
en cas d'une erreur , il n'y a aussi qu'une réponse possible.
exemple:
une suite ONOO donne
5 si pas d'erreur
6 si erreur à la question 1
13 si erreur à la question 2
3 si erreur à la question 3
1 si erreur à la question 4

je propose :
Q5 : la réponse est elle 5?
si oui, alors il n'y a pas eu d'erreur , ou alors plus d'une ( impossible ), donc 5
si non, alors deux possibilités
-il y a eu une erreur avant et, il n'y en aura plus.
reste donc 2 questions pour trouver 1 nombre parmi 4 connus.
il me semble ( sans démo explicite ) qu'on peut affirmer que c'est tj possible.( 2²=4)
tout en déterminant à quelle question correspond la réponse erronée.

-il se trompe à cette question, et encore une fois ne se trompera plus et ne s'est jamais trompé avant.
et là, je ne trouve pas l'astuce éventuelle.

[lper]

Bonjour,

merci pour ce défi, j'ai une piste simple que je vous propose pour savoir si je suis sur la bonne voie :

 Cliquez pour afficher

par dichotomie en doublant les questions et si la réponse diffère alors on la repose une troisième fois pour avoir la bonne réponse.
Dans le cas ou on a le mensonge, il est inutile de doubler ensuite les questions.
La première question serait : est-ce que le nombre est inférieur ou égal à 7, ensuite à 3, à 1.
J'ai juste un problème à la fin si les réponses sont toujours bonnes, on arrive à 6 questions avec deux nombres restants et une seule question.

[mike.p]

Bonjour Iper, Ansset et tous

j'ai lu vos solutions

bien vu , vous avez donc compris qu'intéractivement, il faut 6 à 9 questions , mais ce serait un autre problème et seulement le début de sa solution. Relisez le fil au sujet des questions , du mensonge et de l'intéractivité. Ce qui trompe un peu, c'est qu'il faut montrer que 7 questions sont nécessaires, comme s'il avait été possible d'en poser moins ( ou plus d'ailleurs )

Je reformule la question : comment envoyer 4 informations binaires avec 7 bits de telle sorte que même si l'un d'entre eux est faux, les 4 vrais bits pourront être retrouvés.
Si on considère qu'un oracle répond aux questions, il faut faire comme s'il ne sait répondre qu'à des questions fixes posées à l'avance et que ses réponses font partie de l'envoi. Il n'est pas omniscient et n'a aucune idée de ce que vous avez reçu.

[fregoli]

Bonjour à tous,

 Cliquez pour afficher

En 4 question et s'il ne ment pas, on aurait la réponse:
A: Le nombre est-il supérieur à 7?
B: le nombre est-il supérieur à, soit 3 si réponse N, soit 11 si réponse O
C: idem avec 0, 3, etc... en fonction des deux premières réponses.
D: idem avec 0 (2,4,...) et on a découvert le nombre.

Problème: il peut avoir menti à une des réponses.

Donc après chaque question, lui poser la question: viens-tu de mentir?
S'il répond "Non", alors on continue sur le même algorithme,
S'il répond "Oui", alors on sait que la réponse précédente est fausse, et on change de branche de choix.
Il ne peut plus mentir, il n'y a donc plus de raison de poser cette question "as-tu menti" jusqu'à la fin.
Il y a donc au maximum 3x2 questions + 1 (cas ou il ne ment qu'à la dernière), soit 7

[lper]

Merci Mike.p, ça m'a permis de voir ces algorithmes de contrôle et notamment pour le calcul des CRC.
On est donc dans la recherche d'un polynôme ?

[mike.p]

Je ne voudrais pas polluer le fil , il faut voir avec Juzo et en tous les cas spoiler si ce n'est pas pour des généralités

[lper]

Oui, bien sûr, si un modo juge nécessaire de spoiler mon intervention, merci d'avance !

[ansset]

Si on considère qu'un oracle répond aux questions, il faut faire comme s'il ne sait répondre qu'à des questions fixes posées à l'avance et que ses réponses font partie de l'envoi. Il n'est pas omniscient et n'a aucune idée de ce que vous avez reçu.

qu'entends tu par "posées à l'avance".
cela sous entend-il qu'on ne peux ajuster les questions n+1 par rapport aux réponses précédentes.?
puisque tu parles d'interactivité.
cela n'était pas mentionné.

quand au reste, j'avais bien saisi,.....; MERCI !

ps : j'ai la solution ( enfin 1) mais le ton de ton message me refroidi un peu.

[ansset]

rappel de la démarche:

 Cliquez pour afficher

poser d'abord 4 questions qui forment ensemble la totalité des 16 combinaisons possibles ( OOOO,NOOO,ONOO,....,NNNN).
les fautes( erreur de réponses ) sont aussi identifiées en même temps.
par exemple pour les questions que j'ai imaginé )
5 correspond à la suite de réponses ONOO avec des réponses justes.
et s'il y a eu faute
- à la 1) : res 6
- à la 2) : res 13
- à la 3) : res 3
- à la 4) : res 1
reste à trouver les 3 dernières questions , sachant qu'il ne peut y avoir + d'une erreur dans les réponses.
ce que j'ai fait en fct de chaque réponse.

il semble que tu attends TA résolution qui semble plutôt de l'ordre informatique.
je suis profondément désolé d'avoir suivi une autre voie.
du coup, je garde cette fin pour moi, si elle est hors sujet.
merci.