Dénombrement
Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
-
catamat
- Membre Irrationnel
- Messages: 1164
- Enregistré le: 07 Mar 2021, 11:40
-
par catamat » 17 Aoû 2021, 14:36
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
- Habitué(e)
- Messages: 3075
- Enregistré le: 08 Aoû 2007, 20:08
-
par Skullkid » 17 Aoû 2021, 14:47
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
- Habitué(e)
- Messages: 8707
- Enregistré le: 08 Sep 2009, 15:14
-
par beagle » 17 Aoû 2021, 15:10
". Ç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...
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
-
beagle
- Habitué(e)
- Messages: 8707
- Enregistré le: 08 Sep 2009, 15:14
-
par beagle » 17 Aoû 2021, 16:55
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
L'important est de savoir quoi faire lorsqu'il n' y a rien à faire.
-
Skullkid
- Habitué(e)
- Messages: 3075
- Enregistré le: 08 Aoû 2007, 20:08
-
par Skullkid » 17 Aoû 2021, 17:12
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.
Modifié en dernier par
Skullkid le 17 Aoû 2021, 17:18, modifié 1 fois.
-
lyceen95
- Membre Complexe
- Messages: 2255
- Enregistré le: 15 Juin 2019, 00:42
-
par lyceen95 » 17 Aoû 2021, 17:14
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.
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 136 invités