Dénombrement

[catamat]

Bonjour

Une autre solution toujours avec 121 mais en divisant par 5 au lieu de 4.
Donc 5 carrés de 16 couleurs soit 80 couleurs
plus deux diagonales de 20 couleurs soit 40 couleurs
plus la couleur de fond = 121 couleurs.

[Skullkid]

En ce qui concerne "ma" méthode, le fait qu'on ne peut pas mettre strictement plus de 120 cases noires dans une grille 20x20 sous contrainte que chaque/ligne colonne a au plus 6 cases noires découle de l'argument utilisé plus tôt dans le thread pour obtenir un majorant (20 lignes, maximum 6 cases noires par lignes). Il est aussi assez simple de montrer que, partant d'un coloriage en noir et blanc avec N cases noires et au plus 6 cases noires par ligne/colonne, on peut obtenir un coloriage à N+1 couleurs avec au plus 7 couleurs par ligne/colonne.

Du coup il resterait à montrer qu'on peut toujours transformer un coloriage à N+1 couleurs solution du problème de départ en un coloriage en noir et blanc avec N cases noires et au plus 6 cases noires par ligne/colonne. Intuitivement on pourrait se dire qu'il suffit de choisir N cases de couleurs distinctes, de les noircir et de chauler le reste, mais a priori le résultat pourrait contenir des lignes/colonnes avec 7 cases noires. Il s'agirait donc de montrer qu'on peut toujours choisir les N cases judicieusement.

On peut aussi se poser la question générale d'une grille NxN avec maximum k couleurs alignées. Les derniers exemples donnés par catamat et moi-même s'appuient sur une "macro-grille" dont les cases sont des blocs carrés de cases de la grille originale, et donc utilisent une factorisation de N. Ça pourrait laisser entendre que le problème devient coton quand N est premier ou quand il n'a pas de diviseurs non triviaux inférieurs à k.

[beagle]

". Ça pourrait laisser entendre que le problème devient coton quand N est premier ou quand il n'a pas de diviseurs non triviaux inférieurs à k."

N=7 k=5
a-t-on mieux que (5x5 - 5 ) + 3 + 4 =27 ?
qui semble tomber assez vite.
Peut-être trop vite mais bon...

[beagle]

les verticales deviennent horizontales dans les inter,
donc possiblement faux faut refaire le dessin pour n=19 k=7 erreur sur site de Pierre

mais 5 et 7 il n' ya pas d'inversion puisque un seul carré de 5

[Skullkid]

Les coloriages en noir et blanc avec maximum k-1 cases noires alignées fournissent des coloriages à N(k-1)+1 couleurs pour le problème de départ. Avec N = 7 et k = 5 ça donne 29 couleurs. Comme N est premier on ne peut pas tricher avec une macro-grille régulière, mais en fait on peut toujours appliquer une méthode de coloriage naïve du genre : on place une bande de k-1 cases noires consécutives sur la première ligne puis à chaque nouvelle ligne on place une bande similaire translatée horizontalement de k-1 cases par rapport à la précédente (en identifiant les bords latéraux de la grille). On peut aussi, par exemple, choisir de ne décaler que d'une case et/ou réarranger les lignes et colonnes pour obtenir des motifs un peu plus symétriques.



Quand N et k-1 ne sont pas premiers entre eux, le motif va se répéter et on peut réorganiser les lignes pour faire apparaître une macro-grille dont les macro-cases sont monochromes (qui diffèrent donc des motifs précédents obtenus en noirciçant uniquement une "macro-diagonale" puis en plaçant des motifs "micro-diagonaux" çà et là). Par exemple pour N = 20 et k = 7 :



Bien sûr ce qui compte vraiment dans les motifs diagonaux c'est le fait que si on prend deux cases dans une diagonale, elles ne sont jamais sur la même ligne/colonne. Après on peut faire agir ses permutations préférées pour mélanger un peu tout ça.

[lyceen95]

Je suis toujours sur la grille 20x20 avec 7 couleurs.
Partant d'une solution, (6 cases noires par lignes et par colonne ... ), on peut en obtenir plein d'autres, en permutant 2 lignes, ou en permutant 2 colonnes

Il y a donc plein de façons de disposer les cases noires.

Voici une autre solution :
Mais en permutant 2 lignes quelconques, ça peut donner des choses beaucoup moins régulières.