Vous vous promenez en pleine fête foraine quand tout à coup un modeste stand attire votre attention. Un disque est peint sur le comptoir en bois, et l’escroc l’animateur le recouvre minutieusement avec des disques en métal, sous l’œil attentif des spectateurs. « A vous de jouer maintenant ! »
Règles du jeu :
Vous disposez de plusieurs disques en métal (5 ou 6 selon la variante) et vous devez les placez de façon à recouvrir entièrement le disque peint sur le plateau devant vous.
Attention : une fois un disque posé, il est interdit de le déplacer.
Ce jeu est une application du problème mathématique suivant :
Comment couvrir le plus grand disque possible avec un nombre minimum de disques ?
Allons-y petit à petit. Supposons que notre disque à couvrir (en rouge) ait un rayon . Cherchons le rayon minimum
pour pouvoir recouvrir ce disque à l’aide de
autres disques.
Commençons avec un seul disque :
Ce cas est trivial : on ne peut recouvrir qu’un disque identique, donc
- Avec 2 disques :
La aussi, on ne peut recouvrir qu’un disque identique à nos deux autres disques:
- Avec 3 disques :
Dans ce cas on peut recouvrir notre disque en utilisant des disques de rayon :
- Avec 4 disques :
Les disques C1, C2, C3 et C4 ont un rayon :
- Avec 5 disques :
Si on place les 5 disques de manière symétrique, alors leur rayon vaut :
avec le nombre d’or.
Néanmoins on peut améliorer ce résultat en plaçant les disques différemment.
Nous obtenons un rayon
Donc
- Avec 6 disques :
Là aussi, en plaçant les disques symétriquement en forme de rosace, on obtient un résultat moins bon qu’en plaçant les disques comme la figure à droite.
La partie théorique est maintenant finie (pour les détails des calculs, voir les liens en fin d’article), passons à la pratique.
J’ai codé un petit programme java pour s’entrainer, la variante est celle avec 5 disques.
Dans ce programme, le rayon des petits disques vaut , il est donc « relativement » facile de recouvrir 100% du disque rouge avec un peu d’entrainement ! Cliquez pour placer un disque.
Sources / En savoir plus
- Comment couvrir le plus grand disque avec un nombre minimum de disques
- Disques à couvrir
- The Cover The Spot Carnival Game
- Disk covering problem
- Five disks challenge
- Cover The Spot Secrets
