Question : Peut-on colorier cette figure, ou un polygone en deux couleurs seulement sans jamais obtenir deux zones de même couleur qui se touchent ?
Hé bien oui, on peut.
Voici le résultat :
Mais comment fait-on et comment peut-on être sûr de réussir ?
La démonstration est
Ça signifie qu'il suffit de démontrer que c'est possible au début (étape 0). Puis que si c'est vrai à une étape n, c'est vrai à la suivante (n+1). Par conséquent, comme c'est vrai en 0, c'est vrai en 1, 2, 3, etc...
Pour notre dessin, on démarre en enlevant tous les traits sauf un. On peut peindre un côté en bleu et l'autre en rouge, c'est vrai à l'étape 0 :
Ensuite on se place à une étape et on ajoute un trait. Il suffit alors d'inverser les couleurs d'un côté du nouveau trait pour vérifier la théorie :
Voici les étapes qui ont permis de réaliser le remplissage du motif :
J'aurais dit récurrente plutôt que récursive, non ?
RépondreSupprimerDésolé, mes années d'algorithmie ont pourri mon vocabulaire.
RépondreSupprimerSur la même idée, il me semblait qu'on avait fait un article sur le théorème des quatre couleurs, mais j'arrive pas à le retrouver...
RépondreSupprimerAh, je me rappelle des théories sur la banane et la bière mais les quatre couleurs, ça ne me dit rien.
RépondreSupprimer