Les points sur les L

oh purée!

(Je l'avais pas vu, sinon j'aurais dit ça plus tôt)

Merci Domi,

S

Bonsoir à tous,

j'avoue n'avoir pas avancé, même sur le problème simplifié de ne considérer que les colonnes.

Par contre, ces triminos m'ont donné l'idée d'un jeu à deux joueurs, à jouer sur un échiquier.

Chacun son tour place un trimino sur l'échiquier. Celui qui ne peut plus jouer a perdu.

J'ai l'impression que ce n'est pas évident...

Aldo

Je dirais même plus : si la proba de l'évènement est non nulle, alors c'est possible ! (:D

Bonjour,

Pour plus de simplicité, nous considérons le cas d'un carré de côté 12. A chaque fois, entre crochets, se trouvera le cas général correspondant à un carré de côté n, avec n divisible par 6. Dans l'énoncé initial, n = 2010 = 6 x 335.

On commence par placer un point sur le coin de chacun des 48 [n²/3] triminos.

La méthode de résolution consistera à déplacer ce point une fois sur certains triminos horizontalement ou verticalement de manière à égaliser toutes les rangées et toutes les colonnes.

Nous disposons donc de 48 points déplaçables.

On observe que si l'on déplace un point horizontalement, cela ne change rien au nombre de points de chaque rangée.

Idem si l'on déplace un point verticalement, le nombre de points dans chaque colonne ne change pas.

Nous allons donc montrer que 24 [la moitié des n²/3 disponibles] déplacements verticaux suffisent à égaliser le nombre de points par rangée (c'est à dire 4 [n/3] points par rangée). Il nous restera alors 24 [l'autre moitié des n²/3] points déplaçables pour égaliser le nombre de points par colonne (donc aussi 4 [n/3] points par colonne). Rappelons-nous que ces opérations sont indépendantes !

Pour montrer que 24 [n²/6] déplacements suffisent, quelques remarques :

au départ, après avoir placé un point à l'angle de chaque trimino, de par la répartition naturelle à peu près équilibrée des triminos, le problème est presque résolu. En effet, les triminos servent à recouvrir le carré et sont à peu près bien répartis, ils ne peuvent pas tous être dans une zone alors que le reste de la figure serait presque vide !

C'est ceci que nous allons préciser : si on considère une surface S (un nombre S de petits carrés (cases), elle comporte à peu près S/3 triminos, les irrégularités étant le fait de la frontière de cette zone.

Pour limiter ces irrégularités, nous considérons le carré rangée par rangée. En les numérotant depuis le haut (1ère rangée) vers le bas (2e puis 3e etc.... éniième rangée).

Si on considère un rectangle composé des k premières rangées, il comporte environ 4k [k.n/3] points.

On peut vérifier qu'il comporte au maximum 2 [n/6] points en plus, soit un total de 4k + 2 [k.n/3 + n/6].

Bien entendu, il y a une certaine symétrie, et il comporte au moins 4k - 2 points (il faut bien que le rectangle complémentaire vérifie la propriété énoncée.

A présent, on va compter le nombre de points sur chaque rangée et faire le total du nombre de points des k premières rangées.

On a donc une fonction de k, sorte de fonction en escalier avec

f(1) = nombre de points sur la rangée 1

f(2) = somme des points sur les rangées 1 et 2

.............

pour finir à

f(12) = 48 [f(n) = n²/3].

Nous savons que, quel que soit k, f(k) = 4k plus ou moins 2

[f(k) = k.n/3 plus ou moins n/6]

Notre objectif sera de lisser cette fonction pour qu'elle devienne f(k) = 4k

[f(k) = k.n/3]

Observons que lorsque nous faisons une correction en faisant passer un point de la rangée 1 à la rangée 2, cela ne change pas les valeurs de f(3), f(4) etc.

D'après ce qui a été dit, il suffit de changer au maximum 2 [n/6] points (déplacements verticaux) à chaque interligne pour obtenir autant de points dans chaque rangée. Or, s'il y a 12 [n] rangées, cela donne 11 [n-1] interlignes. On n'a donc besoin que de 11 x 2 [(n-1) n/6] déplacements verticaux de points pour avoir autant de points dans chaque rangée.

Or, nous avons vu que nous disposons de 24 [la moitié des n²/3] points.

On peut absolument choisir d'utiliser n'importe quel point à condition de travailler interligne par interligne, afin de ne pas perturber le graphe de la fonction f.

Il suffit de répéter ensuite cette opération sur les colonnes. Nous disposons de 24 [la moitié de n²/3] points déplaçables horizontalement dans le but d'égaliser les colonnes. Nous avons vu que ceci est indépendant de l'opération précédente.

A la fin de ces deux opérations, il y aura 4 [n/3] points sur chaque rangée et sur chaque colonne.

Voir les illustrations qui suivent : résolution d'une grille de 12 x 12, sa fonction f pour les rangées, sa fonction g pour les colonnes (de gauche à droite).

Bon, j'espère que c'est assez clair.

Aldo

Quelques explications :

un point ne sera déplacé qu'une fois. Ensuite le trimino concerné est "gelé".

Lorsque l'on déplace un point verticalement, cela ne change pas le nombre de points sur chaque colonne.

Ensuite, c'est vrai qu'en rédigeant, j'ai zappé un argument en pensant (à tort !) qu'il n'avait pas d'utilité.

C'est le fait qu'il n'y a jamais deux lignes consécutives en-dessous de la moyenne. Donc, par exemple deux colonnes consécutives ayant chacune moins de 4 points.

Ainsi lorsque nous lissons le graphe de f, c'est à dire que nous faisons passer 1 ou 2 points à un interligne i - i+1 pour rendre f(i) égal à 4i, la rangée à laquelle nous otons des points en comporte toujours plus de 4. Après avoir utilisé au maximum 2 points, nous sommes certains qu'il en restera au moins 2 lorsque viendra le moment d'équilibrer les colonnes.

Il y a en fait deux points que je n'ai pas prouvés correctement : le fait que tout rectangle composé des k première lignes contient au plus 4k + 2 points.

Et cette dernière affirmation qu'il ne peut y avoir deux lignes consécutives à moins de 4 points.

Mais je pense que ce n'est pas très difficile, je le ferai dès que j'ai un peu de temps.

Aldo

Je trouve toujours que ton argument n'en est pas un. Pourquoi peut-on éviter la situation suivante :
Pour égaliser les lignes, je bouge beaucoup de fois verticalement des points situés dans la 5e colonne. Après, pour égaliser les colonnes, je suis coincé parce que je ne peux plus bouger assez de points sur la 5e colonne.

Je ne serai d'accord avec ça:

Et on n'a pas à se poser de question sur le choix du point que l'on déplace, n'importe lequel convient, du moment que l'on respecte l'ordre des interlignes sur f et sur g.

que quand tu donneras un VRAI ARGUMENT. Un exemple n'est pas une démonstration.

Tu as sans doute remarqué que j'ai indiqué plus haut un argument pour égaliser les lignes, qui est le même que le tien. Et si j'ai indiqué à la fin de mon message "Après, il faut traiter les colonnes...", c'est parce que je vois bien que les deux opérations ne sont pas indépendantes. Imagine par exemple qu'on a une grille 12x12, que les trois premières colonnes sont comme ça :

Imagine maintenant qu'en plaçant un point sur chaque case de coin d'un L, on arrive à la répartition 5-3-5-3-5-3-5-3-5-3-5-3 suivant les lignes. On décide d'équilibrer les lignes en abaissant tous les points sur la première colonne. Comment fait-on ensuite pour équilibrer les colonnes ? Il n'y a pas indépendance.

:SBonjour,

Pas assez de travail pour appeler ça une conjecture! On dira un sentiment:

J'ai l'impression que si l'on considère les $n^2$ carrés de côté $3$ qui pavent notre grille carrée de côté $3n$ on peut mettre en évidence dans chacun d'entre eux une des six matrices de permutations de trois éléments...de façon qu'elle "colle" avec ses voisines, au sens que chaque triamino recevra un $1$ et deux $0$.

Un argument:
Tout carré de côté $3$ recouvre complètement au moins un triamino: celui dont un tiers occupe la case centrale dudit carré.
Un carré de côté $3$ peut recouvrir complètement deux triaminos (accouplés en escargots) mais jamais trois.
"Sous" un carré de côté $3$ apparaissent en totalité ou partiellement de $4$ à $7$ triaminos et il existe toujours une matrice de permutation de trois éléments qui marque d'un de ses trois $1$ et chacun des un (ou deux) triamino(s) qu'elle recouvre totalement et deux (ou un) triamino(s) qu'elle recouvre partiellement, ces derniers deux (ou un) triamino(s) pouvant être choisis d'avance.

En attendant critique et/ou réconfort,
amicalement
Paul

EDIT: mon sentiment était mauvais! J'ai un exemple où il est impossible de marquer chacun des $n^2$ carrés de côté $3$ avec $3$ points disposés comme les $1$ d'une matrice de permutation:X

Bonjour Domi,

très heureux de voir ressurgir ce casse-tête si difficile à saisir.

J'ai essayé de suivre ta démo mais j'avoue que j'ai du mal.

Mes difficultés commencent avec la phrase : "On considère le graphe obtenu en reliant chaque case d'angle aux lignes ou colonnes quelles peuvent atteindre pour équilibrer le carré ."

Si tu peux m'expliquer déjà ça, merci.

Aldo

Bonsoir Domi,

c'est malheureusement encore loin d'être clair pour moi, notamment dès que je vois le mot graphe apparaître, tout se brouille car je ne vois ni les sommets ni les arêtes de ce graphe.

Mais bon, même avant ça ce n'est pas clair du tout.

Plaçons nous dans le cas de la figure extraite d'un carré de 6x6.

Comment équilibrer la ligne k uniquement en faisant appel à la ligne k+1 et sans utiliser la ligne k-1 ?

Aldo

Bonjour Domi,

c'est ok, le fait qu'on puisse équilibrer les lignes ne pose pas de difficulté.

C'est vraiment le graphe qui reste bien mystérieux pour moi...

Aldo