Éviter les rectangles – 2
Les croix (X) d'une grille peuvent former les sommets de rectangles à côtés horizontaux et verticaux. Dans la première grille, les croix forment deux rectangles. Or, le but est d'éviter la formation de rectangles. Dans la seconde grille, les croix sont donc placées de manière à éviter tout rectangle.
LE DÉFI
Placez autant de X que possible dans cette grille 4 par 4 et évitez de créer des rectangles.
EXPLORATION
Quelle est la valeur maximale pour les autres tailles de grilles ? Observez-vous des tendances dans vos réponses ?
Remarques
LE DÉFI
Résoudre ce problème est une difficulté majeure et reste à ce jour un problème mathématique non résolu. Cependant, cela ne devrait pas empêcher un élève de s'y essayer et d'apprendre beaucoup de choses intéressantes au passage.
Supposons que la grille comporte m lignes et n colonnes. Dans « Éviter les rectangles – 1 », nous avons trouvé les résultats suivants pour les meilleures solutions.
Lignes 1 et 2 : Nous avions m + n – 1 X
3 lignes : Nous avions m + n X en utilisant un diagramme initial pour une grille 3x3 semblable au diagramme suivant. En utilisant ce diagramme, si nous avions 3 lignes avec plus de colonnes, nous pourrions simplement ajouter un seul X dans chaque nouvelle colonne.
Le cas d'une grille 3x3 a nécessité une approche différente de celle utilisée pour les grilles à 1 ou 2 lignes, et il est tentant de penser que les exemples avec 4 lignes ou plus exigeront également une nouvelle réflexion. Il va de soi que nous souhaitons créer un ensemble de colonnes qui ne partagent jamais de lignes contenant des X.
Une stratégie consiste à remplir toute la colonne de gauche, sauf la case du bas, puis à placer un X dans la dernière ligne et un autre X dans une autre ligne des colonnes restantes. Cette méthode fonctionne systématiquement et donne (m – 1) + 2 × (m – 1) = 3 × (m – 1) X pour une grille carrée de dimensions m × m. On peut ensuite étendre cette méthode de remplissage (en ajoutant un X dans chaque nouvelle colonne) à toute grille de m lignes, ce qui donne 3 × (m – 1) + (n – m) = n + 2m – 3 X, lorsque m < n. Cette formule est valable pour toutes les grilles, quelle que soit leur taille (avec plus d'une ligne).
EXPLORATION
La recherche des meilleures réponses en ligne montre que vous pouvez faire 12 X pour le cas 5 par 5 (que vous pouvez obtenir en utilisant le modèle), puis 16 X pour le cas 6 par 6 (illustré ici).
Ensuite, les nombres commençant par 7, dans l'ordre, sont : 21, 24, 29, 34, 39, 45, 52, 56, 61, 67, 74, 81, 88, 96, 105, 108, 115 et 122. Les mathématiciens ont mené de nombreuses recherches intéressantes sur leur fonctionnement, et vos élèves mathématiciens peuvent aussi s'amuser beaucoup avec !
