mercredi 26 octobre 2011

Deux couleurs

Ce sont les vacances, pour ne pas s'endormir, une petite incursion mathématique.

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 ?
La réponse dans la suite.
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 récursive récurrente. Si vous avez été jusqu'en 5ème, vous devez déjà avoir entendu ce mot.
Ç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 :

4 commentaires:

  1. J'aurais dit récurrente plutôt que récursive, non ?

    RépondreSupprimer
  2. Désolé, mes années d'algorithmie ont pourri mon vocabulaire.

    RépondreSupprimer
  3. Sur 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épondreSupprimer
  4. Ah, je me rappelle des théories sur la banane et la bière mais les quatre couleurs, ça ne me dit rien.

    RépondreSupprimer