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

Profil challenge

Classement : 13/54254

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


Voir le profil
« #90 le: 27 Février 2017 à 14:11:59 »

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

Profil challenge

Classement : 16/54254

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


Voir le profil WWW
« #91 le: 27 Février 2017 à 14:26:58 »

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

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
the lsd
Administrateur

Profil challenge

Classement : 189/54254

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

poulping for fun & profit


Voir le profil WWW
« #92 le: 27 Février 2017 à 15:08:40 »

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

Newbie Contest Staff :
The lsd - Th3_l5D (IRC)
Statut :
Administrateur
Citation :
Cartésien désabusé : je pense, donc je suis, mais je m'en fous !
pixis
Administrateur

Profil challenge

Classement : 16/54254

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


Voir le profil WWW
« #93 le: 27 Février 2017 à 15:19:22 »

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

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

Profil challenge

Classement : 13/54254

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


Voir le profil
« #94 le: 27 Février 2017 à 17:19:29 »

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

Classement : 17017/54254

Néophyte
*
Hors ligne Hors ligne
Messages: 3


Voir le profil
« #95 le: 28 Février 2017 à 16:28:54 »

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

Profil challenge

Classement : 16/54254

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


Voir le profil WWW
« #96 le: 28 Février 2017 à 18:27:24 »

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

Newbie Contest Staff :
Pixis
Statut :
Administrateur
Blog :
hackndo
clement2B
Profil challenge

Classement : 17017/54254

Néophyte
*
Hors ligne Hors ligne
Messages: 3


Voir le profil
« #97 le: 28 Février 2017 à 22:12:50 »

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

Profil challenge

Classement : 13/54254

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


Voir le profil
« #98 le: 01 Mars 2017 à 01:02:31 »

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

Classement : 17017/54254

Néophyte
*
Hors ligne Hors ligne
Messages: 3


Voir le profil
« #99 le: 01 Mars 2017 à 02:26:12 »

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

Profil challenge

Classement : 16/54254

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


Voir le profil WWW
« #100 le: 01 Mars 2017 à 08:47:29 »

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

Edit : Je pensais ... Il manque la fin, en fait
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
« #101 le: 01 Mars 2017 à 20:53:29 »

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.
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
« #102 le: 02 Mars 2017 à 04:53:42 »

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

Profil challenge

Classement : 16/54254

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


Voir le profil WWW
« #103 le: 02 Mars 2017 à 08:11:41 »

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

Citation
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 F223 (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 F223, 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 F223, 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.
Journalisée

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

Profil challenge

Classement : 13/54254

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


Voir le profil
« #104 le: 02 Mars 2017 à 12:49:42 »

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).
« Dernière édition: 02 Mars 2017 à 14:36:20 par BAAL » Journalisée
Pages: 1 ... 5 6 [7] 8 9 ... 11
  Imprimer  
 
Aller à: