Stand Dominos... A. Combien y a-t-il de domino boîte de dominos ? B. Et si on u

Stand Dominos... A. Combien y a-t-il de domino boîte de dominos ? B. Et si on utilisait jusqu'à 9 p au lieu de 6 ? C. Et 45 points ? Qui est-ce ? Une introduction aux codes correcteurs d’erreurs Sur une feuille sont dessinés des personnages, qui se distinguent selon 4 éléments, qu’ils possèdent ou non : des lunettes, une moustache, un chapeau, des cheveux. Tous les per- sonnages sont différents (par exemple, il ne peut pas y en avoir deux avec des lunettes, pas de moustache ni de chapeau et des cheveux). Un joueur choisit secrètement un des personnages. L’autre joueur doit deviner duquel il s’agit en posant des questions, auxquelles l’autre ne peut répondre que par « oui » ou « non », du type « a-t-il des cheveux ? ». Tous les personnages possibles sont dessinés dans le jeu. 1. Combien de personnages y a-t-il ? 24 = 16. Les puissances ne sont vues qu’en quatrième, au niveau jaune on dira 2 × 2 × 2 × 2. 2. Combien faut-il poser de questions pour être sûr de pouvoir trouver ? On pose autant de questions qu’il y a de critères, soit 4 questions. 3. On rajoute maintenant des éléments sur certains de ces personnages : boucle d’oreille, barbe, nœud papillon. Combien de questions faut-il poser pour être sûr de pouvoir trouver ? Cela ne change rien... toujours les 4 mêmes questions ! On joue à ce jeu avec les éléments supplémentaires et en rajoutant la règle suivante : le joueur qui a choisi le personnage secret a le droit de mentir au plus une fois en répondant aux questions. Ces questions sont, dans l’ordre : (1) A-t-il des lunettes ? (2) A-t-il une moustache ? (3) A-t-il un chapeau ? (4) A-t-il des cheveux ? (5) A-t-il des boucles d’oreille ? (6) A-t-il une barbe ? (7) A-t-il un nœud papillon ? On peut lancer une partie sur l’ordinateur (jeu.html, à ouvrir de préférence avec Firefox, éventuelle- ment Chrome, éviter Internet explorer et Safari). Il y a aussi un jeu de cartes (plus grandes) qu’on peut utiliser si les dessins sur l’écran sont trop petits ou pour jouer sans ordinateur. On représente un personnage par un élément de F2 7 : (x1, . . . , x7) avec xi = 1 si la réponse à la question i est « oui », 0 sinon. Les personnages représentés dans le jeu sont les 16 éléments du F2- espace vectoriel engendré par (1, 0, 0, 0, 1, 1, 0), (0, 1, 0, 0, 1, 0, 1), (0, 0, 1, 0, 0, 1, 1) et (0, 0, 0, 1, 1, 1, 1). 4. Quel est le nombre minimal de différences entre deux personnages distincts du jeu ? Il y en a 3. On ne va pas demander de vérifier tous les couples de personnages mais l’admettre. Ce qui est important c’est plutôt de comprendre la question suivante. 5. Pourquoi cela permet-il de deviner le personnage secret, même si le joueur a menti une fois ? Quand on ment à une question, on décrit un personnage (fictif) qui a une seul différence avec le personnage qu’on avait choisi. Et ce personnage fictif a au moins 2 différences avec les 15 autres personnages du jeu. Remarque : si deux personnages du jeu ne présentaient que 2 différences, on pourrait en mentant une fois décrire un personnage qui n’aurait qu’une différence avec ces deux personnages, et on n’aurait aucun moyen de savoir quel était le bon. Le niveau jaune s’arrête là mais si l’enfant a envie de continuer, on peut lui proposer la mé- thode de codage d’un personnage avec des 0 et des 1 présentée dans le niveau orange. On peut également expliquer que les données informatiques sont formées de 0 et de 1 et que lors d’une communication il peut y avoir des erreurs (comme quand on joue au téléphone arabe) qu’on aimerait pouvoir corriger, tout comme on a su trouver un mensonge dans notre jeu. Voyons maintenant comment jouer à ce jeu avec mensonge, sans l’aide de l’ordina- teur ! On représente chaque personnage par une suite de sept chiffres, 0 ou 1. Le troisième personnage, celui qui a des lunettes, pas de moustache, un chapeau, des cheveux, pas de boucle d’oreille, une barbe, pas de nœud papillon, sera ainsi représenté par 1011010. On code les réponses du joueur aux questions de la même façon, par exemple si j’ai choisi le personnage numéro 3 et que je mens à la question « a-t-il des boucles d’oreille ? », ma réponse sera 1011110. Remarque : Le code correspondant à une carte est inscrit au dos de la carte. On reçoit une réponse. Pour savoir si elle est correcte ou mensongère, on va calculer trois nombres, les « syndromes » qui valent chacun 0 ou 1. s1 : on garde un chiffre sur deux □□□□on en fait la somme. s1 vaut 0 si la somme est paire, 1 si elle est impaire. s2 : □□□□, on fait la somme, s2 vaut 0 si elle est paire, 1 si elle est impaire. s3 : □□□□ (que les quatre derniers chiffres), on fait la somme, s3 vaut 0 si elle est paire, 1 si elle est impaire. Exemple : Si la réponse obtenue est 0011110, on a s1 = 0, s2 = 1, s3 = 1. Notons H la matrice suivante, à coeffcients dans F2 : H =     1 0 1 0 1 0 1 0 1 1 0 1 1 0 0 0 0 1 1 1 1    . Si la réponse obtenue est x = (x1, . . . , x7), les syndromes associés sont donnés par le produit matriciel Hx. 6. Le joueur répond sans mensonge. Calculer, pour chaque personnage, s1, s2 et s3. Répartir la tâche dans le groupe, chacun en calcule 1 ou 2 ! Dans tous les cas, on trouve s1 = s2 = s3 = 0. En effet, le sous-espace vectoriel des (codes des) personnages du jeu est exactement le noyau de H (on a construit H pour cela). 7. Que valent s1, s2 et s3 si on ment à la première question et pas aux autres ? Il va être important de réussir à faire comprendre que la réponse à cette question ne dépend pas du personnage choisi. Pour le calcul de s1, on regarde □□□□. On a vu que si on ne mentait pas, s1 valait 0. Si on ment à la première question, on change la valeur du premier bit (0 si c’était 1, 1 si c’était 0) et pas des autres, et s1 vaut donc 1. Pour le calcul de s2, □□□□. Si on ne ment pas, s2 vaut 0. Si on ment à la première question, on change la valeur du premier bit (0 si c’était 1, 1 si c’était 0) et pas des autres, ce qui ne change pas s2 qui vaut toujours 0. Pour s3, comme pour s2, une modification du premier bit ne change rien, on a toujours s3 = 0. Explication en termes d’algèbre linéaire (sauf avec un expert, on évite bien entendu de parler de cette explication) : si le personnage choisi est m ∈F7 2 et qu’on ment à la question i, le personnage fictif décrit est m + ei où ei désigne le i-ième vecteur de la base canonique. Le syndrome obtenu est donc H(m+ei) = Hm+Hei = Hei qui est égal à la i-ième colonne de H. En particulier, si on ment à la première question, s1 = 1, s2 = 0, s3 = 0. 8. Et si on ment seulement à la cinquième question ? Dans ce cas, (s1, s2, s3) est égal à la cinquième colonne de H. On peut donner une explication du même type qu’à la question précédente, pour trouver s1 = 1, s2 = 1 et s3 = 1. 9. Comment le tableau ci-dessous permet-il de découvrir facilement à quelle question le joueur a menti ? On calcule les syndromes. S’ils ne valent pas tous 0, on regarde le numéro de la colonne corres- pondant, il donne le numéro de la question à laquelle on a menti. Si les syndromes sont tous les trois nuls, le joueur n’a pas menti. On a construit une sorte de détecteur de mensonge ! 1 2 3 4 5 6 7 s1 1 0 1 0 1 0 1 s2 0 1 1 0 1 1 0 s3 0 0 0 1 1 1 1 Le principe sur lequel repose ce jeu est en fait à la base d’applications très utiles, pour transmettre ou stocker des données. Disons que les données transmises sont des paquets de 0 et de 1. Lors de la transmission, que ce soit par ondes radio, par câble ou autre, des erreurs sont susceptibles de se produire et le message reçu n’est plus parfaitement conforme à celui qui a été envoyé (les erreurs jouent le rôle des mensonges de notre jeu). uploads/Litterature/ fiche-animateur-qui.pdf

Tags
littérature personnage a-t-il joueur question personnages
Documents similaires
  • 22
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager