Research Topics 2018-2019

  • 1. Terrier de marmottes
    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.
    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.
    Comment construire un terrier pour la famille de marmottes suivantes M1(6 réveilles), M2(4), M3(4), M4(1) et M5(3).

    2. L'équilibre
    Déterminer les positions d'équilibre d'un oeuf (en deux dimensions) ou d'une partie de parabole.

    3. Courbes parallèles
    Le bord extérieur de la route du circuit automobile (ou d’athlétisme) de MeJ à la forme ci-contre. On doit réaliser le marquage de la route intérieur ainsi que la ligne centrale sachant que la route doit toujours faire 10 m de large (c'est-à-dire que tout point du bord de la route intérieur doit être à 10 m du bord de la route extérieur). La bande centrale doit être à égale distance des deux bords.

    4. Le squelette
    Le biologiste, Harry Blum a introduit un nouvel outil pour aider à caractériser la forme des individus d'une même espèce et distinguer les espèces les unes des autres. Le squelette d'une forme S, noté MA(S), est défini par l'ensemble des centres des boules maximales contenue dans S.
    Que peut-on dire de la forme des squelettes ? Peut-on retrouver une forme pour un squelette donné?

    5. Construction d'une géométrie de la couleur
    Les couleurs sont codées par trois entiers de 0 à 255 qui correspondent au « niveau » de Rouge, Vert et Bleu. Par exemple la couleur (234;14;132) est formée de 234 de rouge, 14 de vert et 132 de bleu.
    Il existe plusieurs transformations possibles de ces couleurs. Par exemple NG, qui à chaque triplet de code couleur associe le triplet (m;m;m) où m est la partie entière de la moyenne des valeurs du triplet.
    (234;14;132) -> NG -> (126;126;126) car m=E({234+14+132}/3)=E(126,67)=126
    Un autre exemple de transformation : NB qui a un triplet associe (0;0;0) si la moyenne est <128 et sinon (255;255;255).
    Construire un espace pour modéliser les couleurs et déterminer tous les points qui ont la même image par NG ou par NB.

    6. "Don't cross the streams"
    There's something very important I forgot to tell you ! Don't cross the streams. . . It would be bad. . . Try to imagine all life as you know it stopping instantaneously and every molecule in your body exploding at the speed of light.
    Dr. Egon Spengler

    Les chasseurs de fantômes Ghostbusters utilisent des rayons pour neutraliser les fantômes. Comme l'indique la citation ci-dessus, il est primordial que ces rayons ne se croisent jamais. Imaginons dix fantômes chassés par dix Ghostbusters. Ces derniers peuvent-ils se répartir les fantômes afin que chacun tire sur un fantôme sans qu'aucun rayon ne se croise ? Peut-on trouver une méthode pour construire la solution par ordinateur?
    Peut-on toujours relier chacun des dix chasseurs a son fantôme sans qu'aucun des segments ne se croisent ?

    7. Les tresses
    7.1 Démêlage de tresses
    Une tresse consiste en n fils disposés verticalement qui s'entremêlent en divers croisements et sont attachés en haut et en bas. Si on peut retirer tous les croisements d'une tresse sans couper de fil ni bouger leurs extrémités, on dira que la tresse est triviale. Ci-contre, on voit deux tresses a trois brins, à gauche une triviale et à droite une non-triviale:
    Les tresses borroméennes.
    Existe-t-il des tresses non-triviales telles que si on ôte n'importe lequel de ses brins (par exemple si on le coupe) alors la tresse devient triviale ?
    Les anti-tresses.
    Est-il possible de coller sous une tresse une autre tresse telle que la tresse obtenue soit triviale ?

    8. Des cadenas et des lettres
    Un concret problème de combinatoire.
    On veut concevoir un cadenas à barrillet le plus sûr possible ! Mais les utilisateurs sont paresseux, et il utilise des mots communs de langue anglaise comme code d’ouverture.
    Comment doit-on choisir le nombre de barillets, le nombre de lettre par barillets et les lettres à inscrire sur chacun pour maximiser le nombre de combinaison et ainsi rendre la tâche d'un voleur plus difficile ?