Les points sur les L

[Imod]

Puisque le forum semble revivre en ce moment avec un Ben survolté et débordant d'idées , je vous invite à chercher ce petit problème d'olympiades qui m’enquiquine depuis un moment ( j'étais persuadé de l'avoir déjà posté , il a dû disparaître durant le crack ).

On se donne un carré de cases que l'on recouvre avec des triminos en forme de "L" . Montrer qu'alors il est toujours possible de placer un point dans une case de chaque trimino de façon à ce que chaque ligne et chaque colonne du jeu contienne le même nombre de points .



Amusez-vous bien :zen:

Imod

[beagle]

"( j'étais persuadé de l'avoir déjà posté , il a dû disparaître durant le crack )."

j'ai des brouillons de pages de ce truc, oui cela a crashé.
Me rappelle plus ce que je faisais à base de matrices orthogonales,
j'ai bien joué à ça,
mais je n'avais rien démontré.
Tu disais avoir une solution chiadée en russe,
et je sais plus si c'était le niveau de maths ou le niveau de russe qui te génait ...

[Imod]

La solution que j'avais vue était fausse . Après quelqu'un avait balancé une trame de démonstration un peu douteuse :

mine proof is too long but i can write the ideas :

1-Inductive from n to n+3 for square tables
2-erase 6 column and 6 row from end of table n+3*n+3 and all of figure that has common with mentioned rows and column
3-complete the table that has created in step 2 and make one n*n table
4-prove that we can complete marking figure by the result of Inductive

Je retrouverai le lien , mais je peux déjà te dire qu'il s'agit d'un probleme ARO 2011 ( All Russian Olympiad ) .

Imod

[Ben314]

Je confirme aussi que tu l'avais déjà mis (donc c'était il y a un bon moment...)
J'avait LONGTEMMMMMMPS cherché (c'est pour ça que je m'en souvient) et... pas trouvé grand chose (il me semble)...

[beagle]

de mémoire, on peut mettre 1,2,3 sur chaque trimino et avoir le mème nombre de 1, de 2 de 3 sur chaque rangée et colonne.
pour les matrices, c'est par exemple au niveau d'un trimino
10
1.
plus deux fois la matrice
11
0.
qui donne le trimino:
31
2.

Alors ce n'est pas une démonstration, juste cela met le doigt sur les degrés de liberté,
tu as pour la matrice
10
1.
orthogonale
11
0.
et
01
1

ce qui permet de changer facilement au niveau d'un trimino donné une bascule avec un moins 1 de rangée qui devient +1 de colonne, ce sont des degrés de liberté faramineux,.
mais bon voilà...

[beagle]

enfin je voulais dire tu peux décharger une rangée en surchargeant celle adjacente,
ce qui fait aussi une opération de transfert sur les colonnes...
donc cela permet de combiner les opérations nécessaires là où il est utile...
Mais ceci ne fait qu'intuiter les degrés de liberté et n'explique rien.

Par contre c'est aussi bien de partir sur 3 symboles différents pour les 3 cases du trimino plutot que sur une seule case, sinon ensuite tu te payes l'exo de beagle à démontrer dans une revue maths chinoises.

[Imod]

Je suis pas sûr que ta démo marche , d'ailleurs je crois me souvenir qu'on ne peut pas toujours répartir les 123 sur les trois cases des triminos de façon à équilibrer les valeurs sur les lignes et les colonnes .

Imod

[beagle]

Je suis pas sûr que ta démo marche , d'ailleurs je crois me souvenir qu'on ne peut pas toujours répartir les 123 sur les trois cases des triminos de façon à équilibrer les valeurs sur les lignes et les colonnes .

Imod

give me a contre-exemple, I'll try my best.
Je reste persuadé que cela marche sur deux telles matrices additionnées, mais bon c'est pas très maths la croyance!

[Imod]

Il ne s'agit pas seulement de degrés de liberté , il y a imbrication des variables .

J'avais un contre-exemple ( car c'est une piste que j'avais suivie ) il faudrait que je le retrouve car il fait partie de brouillons jetés depuis longtemps . De toute façon la preuve de tes affirmations est à ta charge :lol3:

Un exemple :



Imod

[beagle]

Merci Dominique, j'essairai de voir.
Mais je n'ai plus toute ma boite à outils de l'époque.
déja commencé à cafouiller sur la simple permutation des matrices et les conséquences...
J'ai dit dès le départ que je prouvais rien.
quant à degré de liberté, j'emploie des mots comme cela ...

[Imod]

Il me semble que la grille que j'ai proposée ne peut pas être remplie de façon équilibrée avec des 1,2,3 mais je ne suis pas convaincu à 100% car elle fait partie d'un ensemble de grilles test que j'avais utilisé pour mes recherches .

Mais bon , pas d'affolement , chacun apporte sa pierre avec ses petits bras :we:

Imod

[beagle]

Bonsoir Dominique,
sauf erreur la structure indiquée n'est pas une impossibilité de placer 4 fois 1, 4 fois 2, 4 fois 3 par rangées et colonnes, en plaçant 123 dans chaque trimino:
132231231213
223113213132
131322323121
321311212323
213221313231
312133321122
122321132313
332132121321
211323131232
313212312213
221113233312
133232122131

à la mano, je ne sais pas programmer ...

[Imod]

En effet ça colle :doh:

Deux hypothèses , ou je n'ai pas retrouvé la bonne grille ou je m'étais trompé :cry:

Je vérifierai un peu plus tard .

Imod

[beagle]

Plusieurs hypothèses:
-c'est toujours vrai = faisable
-il existe des structures intragrille qui empèchent quel que soit n, ou les multiples patati
-il y a des grilles dans les faibles n qui permettent à la fois de coincer, n suffisamment grand ,
mais pas trop car au-delà on peut toujours contourner
il me semble avoir eu à l'époque plus de difficultés avec une grille 9x9

à voir!

[Imod]

J'ai proposé une solution à ce problème ici : http://www.les-mathematiques.net/phorum/read.php?8,672867

La lecture est fastidieuse ce qui explique sûrement que je n'ai pas eu de réponse

Sinon il reste le problème des trois couleurs pour les trois cases des "L" .

Imod