Théorème des quatre couleurs

[Geckoo1337]

Bonjour à tous.
Je suis en train de travailler sur un jeu basé sur le Théorème des quatre couleurs. Je ne vous ferai pas l'insulte d'expliquer ce dont il s'agit. Je ne suis pas trop versé dans les mathématiques. Je suis juste développeur en C/C++ et je bute sur une éventuelle application logique d'un principe.

https://imgur.com/a/pbrMzJ7

Imaginons un rectangle quelconque divisé en plusieurs blocs distincts comme sur l'illustration du dessus. Existerait-il un moyen de connaître l'amplitude minimale possible entre les couleurs (ou plus simplement entre les aires), connaissant le nombre de blocs ? L'amplitude est basée sur la différence entre la couleur la plus présente et la couleur la moins présente - le but étant de réduire au maximum l'écart. Y aurait-il un moyen d'y parvenir ?

Je vous remercie pour l'aide que vous m'apporterez, et je vous souhaite le meilleur.

[lyceen95]

Les pourcentages qui sont calculés dans l'image, ce sont des pourcentages calculés sur la base des surfaces, et pas sur la base du nombre de cases de chaque couleur.
2 zones vertes et 5 zones oranges, et quasiment le même pourcentage à l'arrivée.

Ici, l'amplitude est 3.3% ( 26.7% - 23.3%)

Est-ce qu'on a la certitude à partir de n'importe quel découpage , de pouvoir trouver un découpage avec une amplitude inférieure à x%, x étant fixé à l'avance.
Non.
On peut toujours imaginer un découpage de notre rectangle avec un grand rectangle central, qui peut couvrir 90% de la surface où même plus, et plein de petit carrés pour faire le cadre autour du grand rectangle central.
Quel que soit le coloriage choisi, une des couleurs couvrira au moins 90% de la surface totale.
Et les 2 ou 3 autres couleurs se partageront les 10% restants.

Ta question, c'est donc : a partir d'une carte imposée, avec des frontières connues, comment trouver le coloriage qui donnera l'amplitude minimum, ou bien, un peu moins ambitieux, comment trouver l'amplitude minimum. Et on herchera le coloriage correspondant ensuite.
Je réfléchis tout haut.
On va commencer simple. Chacune des portions a une surface qui est un nombre entier. Imaginons que la surface totale soit de 123 carreaux.
Un chose est sûre, c'est que, au mieux, à l'arrivée, la solution sera 30+31+31+31, et donc au mieux, l'amplitude sera de 1/123.
Sans aucune certitude de trouver une solution qui donne ce resultat.

Si les nombres ne sont pas des entiers, ou si on a une centaine de petits rectangles pour une surface totale de 1234567, on a bien des nombres entiers ...on va dire avec ce raisonnement qu'on peut espèrer une amplitude de 1/1234567, mais dans les faits, il y a une probabilité très faible de réussir cela.

Combiner une centaine de nombres, pour faire 4 totaux aussi équilibrés que possible, sans la contrainte des couleurs, c'est un problème un petit peu plus facile que le problème que tu as. Mais dans un 2nd temps, tu vas devoir ajouter la contrainte des couleurs. Donc autant l'intégrer immédiatement.

Après, c'est de la combinatoire, ou plutôt de la programmation. Je pense qu'il n'y a pas de miracle. Il va falloir chercher tous les coloriages possibles, et voir lequel est le plus équilibré.
Quand je dis de chercher tous les coloriages possibles, on peut beaucoup optimiser.
Dès qu'on a trouvé un coloriage valide, on calcule l'amplitude pour ce coloriage. Admettons qu'on ait une amplitude de 10%
Dans ce cas, quand on recherche les autres coloriages valides, on colorie certaines cases, et dès qu'une couleur pèse plus de 32.5%, on est sûr que ce coloriage ne sera pas mieux que le coloriage déjà trouvé, et on peut abandonner les coloriages qui commencent avec les couleurs déjà placées.
Pourquoi 32.5% :
x=10%
f(x) = (1-x)/4+x = 0.325

[Geckoo1337]

Impressionnante explication lyceen95 - une synthèse bien plus compréhensible que ma première analyse. Je pense que je vais "laisser faire" la machine afin de trouver l'amplitude minimale - une espèce de brute force basée sur l'algorithme du théorème. Je pensais à tort qu'il y avait une espèce de correspondance, mais ton énoncé est clair. Néanmoins, dans l'absolu, ne peut-on pas dire d'emblée que l'amplitude minimum correspond au rapport de l'aire minimale des portions quant à la surface totale ? Par exemple, dans l'image précédente, je ne parviens pas à faire mieux que 1.6%. Merci à toi.

[lyceen95]

ne peut-on pas dire d'emblée que l'amplitude minimum correspond au rapport de l'aire minimale des portions quant à la surface totale ?

Je ne comprends pas cette phrase. Mais j'essaie de la reformuler.
On a mesuré toutes les surfaces , on a une liste d'une trentaine de valeurs. On constate qu'avec ces 30 nombres, si on les associe de telle ou telle façon, on arrive à 4 groupes avec des surfaces cumulées très proches.
Peut-on avoir l'assurance qu'il y aura un coloriage qui donne cette amplitude ? NON.

Prenons un cas tout simple. J'ai 5 zones réparties comme sur ce dessin.

On aimerait avoir au final ((7),(6),(6),(2,3)). Mais à cause des règles sur les couleurs, les zones de surface 2 et 3 ne peuvent pas avoir la même couleur.
On ne peut pas non plus faire ((2,6),(7),(6),(3))
Au final, la meilleure disposition est ((2,7),(6),(6),(3))

Donc, pour trouver la solution optimale, comme je disais dans mon précédent message, pas de miracle. Le tableau avec les tailles des différentes zones ne suffit pas pour calculer l'amplitude minimale.

Ps : mon dessin n'est vraiment pas à l'échelle, la zone de surface 3 est toute petite par rapport à la zone de surface 7. Mais peu importe.

[Geckoo1337]

Hum. Tu es dans le juste. Je te remercie du temps que tu as pris afin de m'expliquer - que je n'y arriverai pas en me portant sur les éléments à ma disposition
Merci beaucoup ++

[Geckoo1337]

Bonjour. Pardon de déterrer une ancienne requête, mais j'ai complètement oublié de vous signaler la réalisation de mon jeu qui se rapporte au théorème des quatre couleurs. Je l'ai développé dans l'hypothèse selon laquelle quelques élèves de collège chercheraient un exemple concret du susdit théorème qui voudrait que quatre couleurs suffisent afin de colorier une carte ou une image fractionnée sans qu'aucune portion n'ait la même couleur qu'une portion adjacente. Ce n'est pas franchement fun, mais ça a au moins le mérite d'être explicite. C'est gratuit. C'est édifiant ++

https://geckoo1337.itch.io/four-color-theorem-game