G2. Combinatoire - Dénombrements
|
Problème proposé par Jean Louis Legrand
Vous jouez avec 2011 cure-dents identiques, assimilés à des segments, que vous devez placer, à la verticale ou à l'horizontale, sur un plan (infini). Au tour 0, avant de jouer, il n'y a aucun cure-dent sur le plan. Au tour 1, vous placez un cure-dent à la verticale, n'importe où sur le plan. Ensuite, à chaque tour, vous devez placer le nombre maximum de cure-dents sur le plan, de façon que: - le milieu de chaque cure-dent soit situé à l'extrémité d'un cure-dent, et d'un seul, placé avant ce tour; - chaque cure-dent qui en touche un autre ne le fasse qu'à une extrémité (deux cure-dents ne doivent jamais se recouvrir sur une moitié). Par exemple, au tour 7, vous placez 12 cure-dents sur le plan pour obtenir la figure de 35 cure-dents suivante:
Q1 ***: Existe-t-il un tour qui donne une figure contenant exactement 2011 cure-dents? Si oui, déterminer le numéro de ce tour. Si non, préciser le numéro du tour qui donne le résultat le plus proche de 2011. Q2 *****: Combien y a-t-il de cure-dents à l’issue du tour n°2011?
Pierre Henri Palmade a résolu le problème en donnant pour réponse à Q1: 60-ième tour et en plaçant en réponse à Q2 : 2247339 cure-dents à l'issue du tour n° 2011. Paul Voyer a remarqué que ce problème a fait l'objet d'une analyse fouillée de la part de N.J.A. Sloane - le père fondateur de la célébre encyclopédie en ligne des séquences d'entiers (O.E.I.S)- et de deux autres mathématiciens américains sous le nom de Toothpick Sequence. On trouvera par ailleurs dans G266-Les cure-dents les liens avec l'OEIS.
|