pour ma part je suis resté, il me semble, dans l'esprit de l'énoncé de départ.
je veux dire dans une démarche de questions/réponses, et pas à compter les bits.
ps : 7 est assez facilement démontrable, je ne sais pas d'où sort le fait que l'on vagabonderait entre 6 et 9.
( cette question étant d'ailleurs posée comme subsidiaire par le primo-posteur )
Bonjour, en effet les questions ne doovent pas dépendre des réponses précédentes, cela explique le nombre minimal de questions, et il ne faut pas s'interdire d'associer 1 à la réponse oui et 0 à la réponse non.
OK, merci pour cette précision non présente dans l'énoncé ( l'emploi du mot interactivité me semble du coup assez incongru )
j'ajuste mes 3 dernières questions.
Cdt
du coup, je vais tout réécrire en bits.
Cliquez pour afficher
est ce à moi que tu écris ? ce n'est pas ma résolution mais celle que Juzo attend.Envoyé par ansset
D'ailleurs Mediat nous l'a dit et je me suis quand même entêté avec l'interactivité, c'est à dire notamment des questions posées en fonction des réponses reçues.
Cliquez pour afficher
Dernière modification par Médiat ; 01/07/2016 à 10h39. Motif: Fautes de frappe
Juste désolé pour ma mauvaise orthographe sur mon message précédent, je fais toujours la confusion entre byte et bit.
Salut,
Cliquez pour afficher
Bonjour
Merci Juzo de bien vouloir préciser les conditions limites des questions et des réponses et éviter de sortir chaque fois avec une nouvelle condition.
Je pose la question 1
Q1 = Est-ce que Nb est supérieur ou égale à 8 ?
Puis je pose la question 2
Q2 = Est-ce que Nb est strictement inférieure à 7 ?
Si la réponse à la question 2 est la même que celle à la question 1 alors le sujet a menti, il ne va donc plus mentir.
Si la réponse à la question 2 est différente que celle à la question 1 alors le sujet n’a pas menti, on élimine donc la moitié des nombres et il nous reste 8 nombres (exemple de 8 à 15)
Je continue, en reprenant les questions Q1 et Q2 avec les nombres 12 et 11 (à la place de 8 et 7)
……
bonjour
une erreur dans mon message précédent
Au lieu de strictement inférieure à 7 il faut mettre inférieur ou égale à 7
Bonjour Iharmed,
en intéractif avec ce schéma, c'est une suite de 2 ( fois la même question ), puis un 3 , puis des 1
3111 -> 6 questions
2311 -> 7 questions
2231 -> 8 questions
2223 -> 9 questions
@mike:
je pense que si y on ne pense pas de suite en terme de bits, on ne s'en sort pas.
( sans connaître évidemment )
en effet ! mais je trouve le problème intéractif sympa aussi , surtout si on pouvait finir par conclure que 7 questions fixes à résultat binaires fournissent les 4 bits d'origine même si l'un des 7 bits est faux.
On pourrait aussi se demander si l'hypothèse d' "une erreur au plus tous les 7 bits" est réaliste sachant
- que s'il y a une erreur au bit b, il y a autant de chances d'en avoir au bit b+1 et ce jusqu'à la fin du message
- que quand il y a des erreurs, elles surviennent souvent en rafales à causes communes indéterminées
Cliquez pour afficher
je ne comprend pas, c'est dans l'énoncé ... ou pas, non ?
pour le reste, oui, à voir en interactif.
mais vu l'imprécision au départ, et le manque du moindre indice, cette énigme ( pourtant intéressante ) n'a pas eu d'effet "ludique" attendu chez moi.
donc, pas envie de m'y remettre.
Je trouve que c'est une bonne idée d'avoir tenté d'en faire une énigme. Beaucoup de ces codes provenaient d'idées trouvées parmi des problèmes de jeux mathématiques. Il y a surement des tas d'autres d'idées à redécouvrir par hasard ...
Le format des questions compte comme nous l'avons vu dans les dernières énigmes. On devrait s'arranger pour lever les ambiguités en 2 / 3 posts aux débuts des fils.
Mais dès le complément de Médiat, nous pouvions deviner qu'il s'agissait d'encodage fixe. Mais si de plus, la solution intéractive n'a au mieux qu'une solution homologue de la fixe, c'est bingo pour Juzo. Pour le savoir, il y a un peu de boulot ... Il ne faut pas abandonner la partie.
au temps pour moi, car je ne l'ai pas lu ainsi. ( pas percuté ), d'autant que juzo n'est quasiment pas intervenu, lui....
peut être fallait il le savoir pour l'"intuiter."
Bonjour, je pensais avoir donneé suffisamment d'indications, je ne voulais pas vous orienter sur une méthode. Dans l'esprit où j'ai posé l'énoncé, toute solution juste était bonne à prendre. Il était intéressant de voir les stratégies qui émergeaient.
Il manquait l'idée de l'interactivité mais je pensais qu'elle s'éliminerait toute seule.
J'aurais dû vous préciser aussi que j'étais très occupé, déménagement et recherche d'appart, mais je devrais être un peu plus dispo les prochains jours !
Désolé pour le désagrément ansset, je ne vois pas quels indices j'aurais pu vous donner. Mon téléphone n'affiche pas les spoilers, je reprendrai rapidement un ordinateur pour regarder vos propositions !
rappel:
le mess succint de Mediat.
"auto-correctif" évoque justement pour moi l'idée d'interaction , c-a-d de question n+1 liée aux réponses précédentes.
suite et 1ère intervention de Juzo, après de nombreuses tentatives de propositions.
que cela soit intéractif ou pas, l'énigme reste un nb minimal de question.
donc l'énoncé n'induisait pas du tout une non interactivité par principe.
de fait, ne pas s'interdire en l'espèce correspond d'avantage à "vivement conseillé".
car je suggère à qcq d'écrire la solution sans passer par les bits , et sans extrême lourdeur dans la formulation des questions.
@Juzo :
ne manquez pas la mienne ( sous spoiler ) , je voudrais la soumettre comme corrigé type pour les olympiades, si bien sûr vous êtes d'accord.
ps : tentez un "répondre avec citation"
bonjour mike ;
laquelle ?
déjà postée ou en attente ?
merci pour ta réponse MP
@juzo:
peux tu m'envoyer LA réponse par MP ou "Spoilée" , stp.
avec les 7 questions en bloc.
et une réponse à ma précédente.
si possible avec traduction en langage qui n'utilise pas un codage en base 2 "indispensable" et surtout sans programmation.
merci par avance.
Salut à vous, merci pour votre patience, j'ai enfin un ordi sous la main
Vous trouverez toute la solution détaillée ici, avec en bonus des questions supplémentaires : http://agreg.org/Textes/527.pdf
Et en spoiler la partie qui nous intéresse le plus :
Cliquez pour afficher
A noter ce passage sur l'interactivité :
"La problématique des codes correcteurs d’erreurs est la suivante : un expéditeur A envoie un message m à B ; durant la transmission de ce message, des erreurs se produisent éventuellement, et B reçoit un message m qui comporte peut-être des erreurs. Il s’agit de trouver comment faire pour que B,
1) d’une part détecte l’existence d’erreurs,
2) d’autre part, si elles ne sont pas trop nombreuses, sache les corriger. Dans certains cas, lorsqu’il est rapide de réexpédier le message,
1) suffit. Néanmoins, dans d’autres cas, 2) s’avère indispensable : par exemple, si A est une fusée intersidérale qui envoie une photographie d’une météorite, et s’il faut par une semaine pour que cette photographie atteigne B, à savoir la Terre, on ne pourra pas demander à la fusée de reprendre la même photographie de la météorite - qui sera bien loin de la fusée quinze jours après. Le même cas de figure se produit pour un disque compact commercial : s’il possède quelques défauts, il est plus rentable d’avoir un procédé pour corriger les erreurs que de devoir le racheter."
J'ai été un peu malhonnête de ne pas vous parler tout de suite de code auto-correcteur, ni d'interactivité. Je pensais que la seule solution permettant de résoudre le problème à tous les coups en 7 questions ne serait pas interactive.
Et enfin, pour être totalement clair, j'avais à peine le niveau suffisant pour savoir que l'énigme vous intéresserait et la solution vous conviendrait.
Voilà voilà
Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne voient pas.
Je suppose que vous n'avez pas encore posté cette réponse, ou je suis passé à côté.
J'attends votre réponse, et vos commentaires à celle que j'ai postée.
A bientôt
Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne voient pas.
sérieurement ? tout était déjà dit , j'ai simplement fait une proposition de renforcement des communications en # 43 ... J'espère que ça n'a déçu personne !
Je n'ai pas répondu car je connaissais le code et ai très vite réuni la littérature le concernant. Ce n'était plus du jeu !
Oui, bien sûr, votre réponse est opimale quoiqu'il soit parfois économe de demander directement la valeur d'un bit en mode intéractif ( longueur de la question )
L'intéractivité dans ce contexte implique qu'une question peut être choisie ou construite en fonction des réponses reçues auparavant et donc que l'émetteur peut apprendre des infos sur le récepteur alors qu'il n'en est rien dans la version qui est optimale en nombre de questions/réponses. Pas d'intétactivité => questions fixes et réponses pré-fournies avec le message de base.
Je suis sûr aussi que vous avez raison.
Mais j'aimerais bien savoir/comprendre/définir en général, à quelles conditons une solution non intéractive peut ne pas être optimale.
NB: Il y a des relations entre ce problème généralisé et le problème de recouvrement ( autre fil forum math ).
Moi je me serais plutôt demander si l'on ne peut pas montrer que la solution optimale est toujours une solution non interactive. D'instinct je dirai qu'on ne peut pas tester plusieurs choses en mêmes temps en étant interactif (je sais, ça reste vague)
Bizarrement ça me fait penser à une énigme de mon prof de maths que j'avais résolu au lycée : on dispose de douze boules dont l'une est plus lourde ou plus légère que les autres. En trois pesée avec une balance à plateaux, on doit déterminer quelle est cette boule, est si elle est plus lourde ou plus légère que les autres.
J'avais trouvé la solution en me disant que je ne pouvais pas faire de la dichotomie toute bête. Je dois quand même préciser que ma solution était interactive !
Je peux créer un nouveau fil pour cette énigme si ça vous intéresse
Dernière modification par Juzo ; 04/07/2016 à 20h38.
Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne voient pas.
il y a des énigmes sans solution avec des questions fixes. Mais le premier problème à résoudre c'est trouver un modèle pour les énigmes ! je ne sais pas s'il y a eu des travaux spécialisés.
Je connais l'énigme des 12 boules, il me semble même l'avoir croisée dans ce même forum ...
ben, étant parti sur une interactivité, j'ai bien trouvé une solution en 7 questions qui tenait compte des réponses précédentes.
un graphe à partir de la 5.
les 4 premières servant simplement à couvrir tout le spectre.
elle est parti à la poubelle quand il a été dit que cela n'était pas conforme à l'énigme.
Oui, s'il existe une solution interactive avec 7 questions maximum celle-ci est conforme à ma première formulation de l'énigme. Je serais d'ailleurs très intéressé de la lire si vous avez le courage de la réécrire.
L'énigme des douze boules est aussi une énigme où il faut trouver un élément différent des autres avec une information supplémentaire (plus lourd ou plus léger), et un système binaire (la balance à plateau) pour faire des tests. Si quelqu'un veut faire quelque chose de ça
A noter aussi qu'il s'en fallait de peu que la solution que j'ai publié fonctionne pour n'importe quel ensemble de 16 nombres, s'il n'y avait pas eu la question 4)Cliquez pour afficher
Une solution à ça ? Utiliser l'indice du nombre dans l'ordre croissant de la liste par exemple ? :"la position du nombre dans la liste rangée par ordre croissant est-elle paire ?"
Si une erreur lors de l'émission d'un bit est très très rare, alors une double erreur lors de l'émission de 7 bits est extrêmement rare, et le risque devient acceptable. On peut supposer raisonnablement qu'il y aura au plus une erreur lors de l'émission de 7 bits.
Dernière modification par Juzo ; 04/07/2016 à 23h31.
Les fleurs du cerisier rêvent en blanc les fruits qu'elles ne voient pas.
bonjour
la démarche la plus proche est celle du message #39.
la première question est la même : Q1 = Est-ce que Nb est supérieur ou égale à 8 ?
on n'y a prêté attention !!
@Juzo:
Cliquez pour afficher
moi si, cette logique n'aboutie pas.
fais un graphe et tu verras qu'il te faut plus de 7 questions , lié au fait que tu ne sais pas avec certitude s'il a menti et ou. ( combinatoire )
