[BAAL]

Je crois pouvoir faire 18. Y'a-t-il mieux? J'aimerais bien que quelqu'un d'autre réponde aussi, j'ai l'impression d'être le seul à chercher .

[pixis]

Il y a mieux, mais je suis curieux de connaître ton raisonnement pour 18. En effet, il y a beaucoup de raisonnements qui permettent de trouver 17, mais je n'en avais pas trouvé pour 18 !
PS : Harvey est aussi dessus

[the lsd]

Je crois pouvoir faire 18. Y'a-t-il mieux? J'aimerais bien que quelqu'un d'autre réponde aussi, j'ai l'impression d'être le seul à chercher .

J'ai cherché, j'ai trouvé 11 -_-
Après, je me suis dit qu'il y avait surement des notions de maths dans l'histoire. J'ai pris une couverture de survie et me suis mis en PLS durant 30 minutes.


Enjoy

The lsd

Edit : ouais, c'était bien 12, j'me suis loupé en comptant.

[pixis]

Je pense que tu as trouvé 12, plutôt (si tu refais ce que tu as fait, je pense).
Pour trouver 17, c'est très faisable, pas besoin de notions de maths.
Pour trouver plus, ça se corse (quoique je ne sais pas comment BAAL a trouvé 18)

[BAAL]

Ah non, j'ai trouvé 17=6*2+5, et j'ai un bit bonus, pas 18... 
Mais j'ai d'autres idées à essayer...

[clement2B]

Bonjour a vous
j'ai regardé j'ai aussi trouvé 12, pouvez vous dire comment vous trouvez 17, pour voir le cheminement svp ?

[pixis]

Il n'y a pas besoin de notion de maths compliquées pour trouver 17. C'est juste un peu de logique. Si vraiment tu ne trouves pas, je peux t'envoyer le raisonnement pour ce résultat.

En revanche, c'est un raisonnement bien différent qu'il faut adopter pour trouver la réponse (supérieure à 17), et qui demande de pousser la logique et les maths à un niveau au dessus

[clement2B]

dans ce cas, j'attend de voir le dis raisonnement     je prend les pop corn et j'attend

[BAAL]

Pour 17:
On a 1h30=5400 secondes.
ceil(log_2(5400))=12, on peut donc transmettre 12 bits d'information.

Le premier bit nous indique la majorité des questions 1,2,3:
1 veut dire qu'au moins 2 sont vraies, 0 veut dire qu'au moins 2 sont fausses. Ça donne 2/3 bonnes réponses guaranties.
On fait ça pour les 6 premiers triplets avec les 6 premiers bits, et on a 12/18 bonnes réponses guaranties.
Ensuite on utilise 1 bit par réponse pour arriver à 17/23, et il nous reste 1 bit bonus.

Je crois savoir comment faire pour avoir plus, mais pas le temps de m'y mettre... ça laisse du temps à quelqu'un d'autre de trouver entre temps .

[clement2B]

j'etait sur cette maniere de penser, j'avais trouvé 17 aussi en re regardant j'avais arrêté mon raisonnement en plein milieu en fait, par contre j'y suis revenu et pour trouver plus franchement je sais pas ce que vous faites dans la vie mais vous êtes pas la moitié de demeurés    je vais me couché, peut être aurais-je la reponse demain matin, ou une illumination dans la nuit 

[pixis]

Pour information, Harvey a trouvé, bravo à lui !

Edit : Je pensais ... Il manque la fin, en fait

[harvey]

Oui, enfin j'ai trouvé une manière de faire mieux que 17. Avec 7 questions, il suffit de 4 bits pour garantir 6 réponses. En appliquant le même système 3 fois, on obtient 18 réponses avec 12 bits. Je sais aussi prouver que la solution ne peut pas être supérieure à 20. Mais je ne sais pas encore comment atteindre 20 ni même si c'est possible (sauf si, peut-être, pixis m'a hinté là-dessus), et étendre le modèle jusque-là n'a pas l'air simple.

[BAAL]

La réponse est 20.

Je vous encourage à continuer à chercher. Il n’y a pas besoin de maths avancées du tout!
Voici ma méthode pour les n00bs qui ne trouveront pas seuls:

 
On a q questions et un message de m bits (q=23, m=12 dans notre cas).
On pourra donc générer 2^m messages différents, ce qui n’est pas assez pour représenter toutes les 2^q réponses possibles tant que m<q (12<23).

Cela dit, si on est prêt à tolérer e erreurs, on pourra utiliser le même message pour couvrir plusieurs réponses d’un coup.
Pour e erreurs, chaque réponse est couverte par sum{i=0 à e}{C(q, i)} messages différents.
Par exemple, pour q=4, la réponse 0000 est couverte par:
e=0 -> 0000 (total=C(4,0)=1)
e=1 -> 0000 1000 0100 0010 0001 (total=1+C(4,1)=5)
e=2 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 (total=5+C(4,2)=11)
e=3 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 1110 1101 1011 0111 (total=11+C(4,3)=15)
e=4 -> 0000 1000 0100 0010 0001 1100 1010 1001 0110 0011 0101 1110 1101 1011 0111 1111 (total=15+C(4,4)=16)
On s’attend bien sûr à retrouver 2^4=16 pour le cas e=4 (peu importe le message de 4 bits, on n’aura pas plus de 4 erreurs).

Vu la symétrie du problème, il est clair que ces messages sont distribués équitablement à travers les 2^q réponses possibles.
Du coup, pour chaque nombre d'erreurs e, il nous suffit de multiplier le nombre ci-dessus par le nombre de messages que nous pouvons utiliser (2^m),
pour savoir combien de messages on couvrera. Si ce nombre atteint ou dépasse 2^q, on peut garantir le nombre d’erreurs correspondant.
En d'autres mots, on peut supporter e erreurs si l’inégalité suivante est satisfaite:
sum{i=0 à e}{C(q, i)} * 2^m >= 2^q

(Points bonus si quelqu’un arrive à écrire tout ça sous la forme e = ... au lieu d’utiliser une inégalité et de tester les “e” un par un).

Dans l’exemple ci-dessus:
e=0 -> on a besoin de m=4
e=1 -> on a besoin de m=2
e=2 -> on a besoin de m=1
e=3 -> on a besoin de m=0

On peut d’ailleurs confirmer l’exemple de harvey: q=7 e=1 -> m=4
Maintenant pour la question initialement posée, on trouve: q=23 m=12 -> e=3
q-e = 20 questions garanties.

#micdrop

[pixis]

Bien joué BAAL. Pour l'aspect mathématique, effectivement il ne faut pas forcément de notions avancées pour trouver le problème (quoique, cf. mes remarques en noir), cependant les maths sous-jacentes qui permettent de généraliser le problème le sont un peu plus.

En fait, c'est ta phrase

Vu la symétrie du problème, il est clair que ces messages sont distribués équitablement à travers les 2^q réponses possibles.

que tu utilises pour simplifier le problème (non pas en tant qu'hypothèse, mais en tant que proposition qu'il n'y a pas besoin de démontrer), si j'ai bien compris. Harvey ne l'a pas prise en compte, et du coup avec ton raisonnement il considère que la réponse est <= 20

En effet, il cherche maintenant à prouver l'existence de ces 2^12 différentes informations qui permettent de couvrir tous les cas. Avec ton raisonnement, on montre qu'il ne peut pas y avoir plus de 20 réponses possibles au pire. Cependant, rien ne montre qu'il existe 2^12 solutions toutes distantes de 7 une à une.

Le problème peut être ramené à 4096 secondes (au lieu de 5400). Comme on a sum{i=0 à 3}{C(23, i)} = 2**11 (et que 2**11 * 2**12 = 2**23), pour que la réponse soit bien 20, il faut s'assurer qu'il y existe une partition de l'espace F₂²³ (dimension 23, avec des entiers modulo 2, donc 0 et 1) avec des boules de rayon 3 (au sens distance de hamming) qui sont dans un espace vectoriel de dimension 12, sous EV de F₂²³, donc comme dit plus haut, qu'il existe 2^12 solutions toutes distantes de 7 une à une.

Si une telle partition n'existe pas, ça veut dire que quoiqu'il arrive, des boules auront une intersection non vide, donc il y aura des solutions couvertes par deux informations, et d'autres pas couvertes.

Ce que tu as montré, finalement, c'est que si on prend des boules de rayon 2, alors quelque soit le centre des boules, 2^12 boules ne suffiront pas à décrire l'espace F₂²³, mais que des boules de rayon 3 peuvent potentiellement décrire cet espace. Il faudrait le montrer




J'espère que je suis clair, et que j'ai bien compris ton raisonnement, donc que mes remarques sont légitimes.

[BAAL]

Oui j'ai pris un raccourci, basé sur l’intuition (et quelques tests pour m'assurer que ça tenait debout). Je me doutais bien qu'une preuve plus rigoureuse serait reliée à Hamming.

Bravo donc à harvey pour avoir trouvé en premier! (au moins avec la même méthode que moi).