Petites enigmes > Réponse Sciences sujet

Soit n, m. On suppose dans la suite n <= m.

Si une telle grille existe, c'est qu'en prenant deux lignes au pif dans la grille, ils n'ont pas deux cases de même couleur dans les deux même colonnes.

Si on prend n=3, on regarde des lignes de 3 chiffres. Clairement m ne doit pas être plus grand que 8, sinon deux lignes sont identiques et comme ces deux lignes contiennent deux cases noires ou deux cases blanches, on exhibe un rectangle.
Et si jamais on prend une grille plus grande, elle contient une sous-grille de taille 3*9 et ça ne marche pas.

Cherchons la plus grande grille 3xM qui existe et telle qu'il n'y a pas de rectangle.

Soit la première ligne est de la forme 111 soit de la forme 110 à permutation des cases près (ce qui ne change pas le problème), où 1 est une case blanche et 0 une case noire. Je vous épargne la recherche et les preuves qui suivent et on trouve cette grille maximale :

110
011
001
100
101
010


n=2 : c'est possible : il suffit de prendre une ligne noire et une ligne blanche
n=3 : c'est possible si m <= 6 avec la grille ci-dessus
n=4 : possible avec m <= 6 :

1100
0110
0011
1001
0101
1010


Conclusion :
Possible si n=2, n=3,4 et m<=6

J'ai juste pas prouvé formellement que ça marche (ou pas mais je pense pas) pour n=m=5 mais je verrai ça plus tard.