Principe :

Un groupe de marmottes décide de se creuser un nouveau terrier en vue de l'hiver qui arrive, mais cette année elles ont décidé de le faire de manière optimisée. Le problème de ces marmottes est qu'elles ont le sommeil léger, ce qui implique deux règles, plus une pour que la structure ne s'écroule pas :

1. A partir de l'entrée, ou à partir de l'extrêmité d'un couloir, on peut maximum creuser deux couloirs, sinon la structure risque de s'effondrer (et ça correspond à ce qu'on peut faire avec les couloirs du kit).
2. Il est impensable de faire dormir une marmotte à un croisement ou au milieu d'un couloir. Si on le faisait elle se ferait marcher dessus par d'autres marmottes habitant plus loin dans le terrier et cela ruinerait son hibernation. Les marmottes dorment donc uniquement au fond d'une galerie qui ne donne sur rien d'autre que sa salle.
3. Même le simple déplacement des marmottes et le bruit de leurs petites pattes génère des vibrations qui dérangent le groupe pendant leur sommeil (elles ont vraiment le sommeil léger !!) du coup, comme on sait combien de fois chacune va se réveiller et sortir du terrier pendant l'hiver, on va faire en sorte que la somme des déplacements des marmottes soit la plus petite possible.

Par exemple une marmotte qui se réveille 6 fois, si elle est à 4 couloirs de la sortie, devra parcourir 6 x 4 = 24 couloirs, aller et retour (mais pour avoir des chiffres moins gros on ne va compter que les allers). Si on la met à un couloir de la sortie, elle ne parcourra plus que 6 x 1 = 6 couloirs.

Le déroulé de l'activité est décrit ci-dessous.

• On donne un ensemble de marmottes + couloirs à chaque groupe de participants et on leur explique les règles, puis on les laisse expérimenter.
• On compare les résultats obtenus entre les différents groupes et on essaie d'expliquer comment faire le meilleur terrier possible, ou pourquoi tel terrier est moins optimisé que tel autre.
• En général les stratégies utilisées sont des tests et un peu de bon sens, mais les gens n'arrivent pas à donner un algorithme. On peut leur donner et les laisser expérimenter l'algorithme de Huffman :
  1. Prendre les deux marmottes qui se réveillent le moins souvent et les relier ensemble,
  2. noter sur le coude du couloir qui relie ces deux marmottes le nombre de réveils qu'elles ont à elles deux,
  3. recommencer les points 1 et 2 en considérant maintenant que les marmottes qu'on vient de relier ne sont plus qu'une seule marmotte, dont le nombre de réveils est le nombre noté sur le coude du couloir,
  4. continuer à répéter les deux premières étapes jusqu'à ce que l'on n'ait plus qu'un seul terrier qui relie toutes les marmottes.
  Et il se trouve que cet algorithme produit à coup sûr un terrier optimal
• Réfléchir sur l'unicité du terrier optimal (ce n'est pas le cas, on choisit parfois entre plus de deux marmottes (ou groupes de marmottes reliées) qui se réveillent le même nombre de fois)
• C'est le moment de retourner les terriers (doù l'utilité des scratchs) et de voir le côté informatique : ce ne sont plus des marmottes mais des lettres, des réveils dans l'hiver mais un nombre de fois que la lettre apparaît dans un texte, des couloirs mais le code binaire associé à chaque lettre

Pour l'explication informatique des contraintes, savoir comment compresser/décompresser un texte à l'aide d'un arbre de Huffman, voir la fiche explicative de la section liens.