|
Petits problèmes | |
| page précédente | Nicolas Markey |
|
|
Petits problèmes | |
| page précédente | Nicolas Markey |
Le fiancé de Suleima, orfèbvre arithméticien, prépare dans son atelier une bague pour sa bien-aimée. Il a en effet promis, comme preuve de son amour, de lui offrir chaque mois une bague en or différente, incrustée d'émeraudes, de saphirs ou de rubis. Chaque bague a dix pierres précieuse, régulièrement réparties, et se distingue des autres uniquement par l'ordonnancement des pierres qu'elle comporte. Pendant combien de temps Suleima pourra-t-elle être rassurée sur l'amour que lui voue son futur mari ?
Nous allons voir que se problème est un cas particulier d'un problème plus général, à savoir le dénombrement des mots circulaires, et peut se résoudre en faisant appel à la fonction de Möbius. Ce problème de combinatoire sur les mots circulaires est traité dans [B] et c'est sa présentation que nous allons suivre. Pour ce qui concerne la fonction de Möbius, on pourra également se reporter à [NQ].
[B] Claude Berge, Principes de combinatoire, Dunod,
1968.
[NQ] Patrice Naudin et Claude Quitté, Algorithmique
algébrique, Masson, 1992.
On se donne un certain nombre de couvertures carrées. La surface totale des couvertures vaut 4. Montrer que les couvertures peuvent recouvrir le carré unité.
Soit G=(V,E) un graphe connexe fini non orienté, et tel que E ne contienne pas de boucle d'un état sur lui-même. Sur chaque sommet de ce graphe, on dispose un certain nombre de jetons (et on nomme « configuration » du graphe une disposition de ces jetons).
Une « partie » est une suite de configurations, partant d'une configuration initiale, et telle que le passage d'une configuration à la suivante est régi par le principe suivant :
Il est clair qu'une partie peut être finie (intuitivement, s'il n'y a pas beaucoup de jetons) ou infinie (intuitivement, s'il y a beaucoup de jetons). Le nombre total de jetons est donc constant sur une partie. Notons le j. Notons également n le cardinal de V et m celui de E. Montrer que si une partie est infinie, alors toutes les parties commençant par la même configuration initiale sont infinies. Montrer qu'une partie est infinie si, et seulement si, elle fait intervenir tous les sommets. Montrer les équivalence suivantes :
| j > 2m-n | si, et seulement si, | toutes les parties sont infinies, quelle que soit la configuration initiale |
| j < m | si, et seulement si, | toutes les parties sont finies, quelle que soit la configuration initiale. |