Enigmes

Forum dédié aux énigmes et à toutes formes de jeux de logique.

Déconnexion

Tu n'es pas identifié sur Prise2tete : s'identifier.

accueil Accueil forum Forum
[+]

 #26 - 06-05-2020 19:34:28

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,233E+3

Déformattion d'un treillis

Pour moi c'est une évidence , chaque composante connexe impose sa direction les autres sont libres , après , on peut pinailler à l'infini smile

http://www.prise2tete.fr/upload/Vasimolo-treillis.png
Vasimolo

#0 Pub

 #27 - 07-05-2020 00:09:26

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 393

Déformation d'un trellis

Vasimolo
Oui, je peut comprendre que ça puisse paraitre évident. On peut même tirer une construction pas trop compliquée en suivant ton schéma. Il y a une construction plus simple (qui est un cas particulier de la tienne) sauf que l'on ne se base que sur une seule de tes composantes connexes.

 #28 - 07-05-2020 09:53:22

TOUFAU
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 90

Déforrmation d'un treillis

Tu as raison, mon raisonnement n’était pas clair.

En fait je ne cherche pas à construire les treillis de façon récursive : (n,p) rigide n’impose clairement pas que ses ‘sous-treillis’ (n-1,p) soit rigides.
Je dis juste que la règle n+p-1 marche pour les ‘petits’ treillis, et que si on arrive à battre cette règle à partir d’une certaine taille, le plus petit qui bat la règle a autant ou moins de cellules rigidifiées que le minimum possible de tout treillis (n-1,p) ou (n,p-1) rigides. Et que ça amène un pb. Et c’est là où je ne suis pas clair. Je reprends…

Imaginons que (n,p) est le plus petit treillis battant la règle n+p-1 : Il est donc rigide avec au plus n+p-2 cellules rigidifiées.
Toutes ses lignes et toutes ses colonnes ont au moins une cellule rigide (sinon cisaillement possible). Donc aucun sous-treillis (n-1,p) ou (n,p-1) obtenu en supprimant une ligne ou une colonne quelconque (et en ‘recollant’ si ce n’est pas un bord) n’est rigide, car il ne contient plus que n+p-3 cellules rigidifiées max. De fait toute ligne ou colonne est structurelle pour le treillis (n,p).

Prenons une de ces lignes au hasard. Sans elle, le sous treillis ‘recollé’ n’est pas rigide. Avec elle, le treillis l’est devenu. Donc la ligne ajoutée fait mieux que les lignes de bord des sous-treillis pour transmettre la rigidité à l’ensemble.
Si la ligne ajoutée ne contenait qu’une cellule rigidifiée, elle ferait au mieux aussi bien que chacun des bords des sous-treillis précédents (qui ne peuvent avoir 0 cellule rigidifiée, sinon cisaillement inévitable). Ie il suffirait pour l’un des 2 sous-treillis de choisir de localiser la cellule rigidifiée à la même position que celle de la ligne ajoutée, et le résultat serait identique : le sous-treillis (n-1,p) serait aussi rigide que le treillis (n,p). Et on aurait donc un sous-treillis (n-1,p) rigide avec seulement n+p-3 cellules rigides, ce qui est impossible. Donc la ligne ajoutée ne peut contenir ni 0 ni 1 seule cellule rigidifiée. Elle en contient à minima 2. Le raisonnement marche aussi si la ligne ôtée est au bord.
Si toute ligne et toute colonne du treillis contient à minima 2 cellules rigidifiées, le nombre total de ces cellules est égal à max(2n, 2p). Mais max(2n, 2p)>n+p-1, ce qui contredit notre hypothèse.
On ne peut trouver de plus petit treillis battant la règle n+p-1.

 #29 - 07-05-2020 10:16:17

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3786

Déformatioon d'un treillis

......reste à prouver que si le treillis ne respecte pas la construction, alors le treillis est rigide.

Je suppose que tu as voulu écrire :..... le treillis est non-rigide ?

J'ai tout de même développé un exemple à 2 réseaux indépendants. ça ne suffit pas ?

 #30 - 07-05-2020 12:41:12

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 393

Défformation d'un treillis

Toufau
Spoiler : [Afficher le message] "Et on aurait donc un sous-treillis (n-1,p) rigide avec seulement n+p-2 cellules rigides, ce qui est impossible"
n-1 + p - 1 = n+p-2
D'après ce que tu cherches à démontrer, c'est possible de rigidifier un treillis (n-1,p) avec n+p-2.
Si tu essayes de résoudre par récurrence, il faudrait que tu montres que l'on peut rendre le sous treillis rigide sans ajouter de cellules (mais en en déplacant). Ici, tu en ajoutes une, donc ça ne t'apprend rien.

"Ie il suffirait pour l’un des 2 sous-treillis de choisir de localiser la cellule rigidifiée à la même position que celle de la ligne ajoutée, et le résultat serait identique : le sous-treillis (n-1,p) serait aussi rigide que le treillis (n,p)."
Pourquoi est-ce vrai? (C'est vrai, ça peut se démontrer directement, via un argument déjà amené par les autres p2tiens, mais ça n'est pas une propriété si évidente)

Si tu arrives à mener cette preuve à bien, tu auras trouvé une preuve différente de celle trouvée par tout les autres (qui ont tous la même que moi), mais je ne sais pas si on peut mener à bien l'approche par récurrence directement, c'est à dire sans donner pour le prouver une construction qui marche directement....


nodgim
Oui, je modifie. wink

Vasimolo m'a donné un exemple à 3 réseaux. J'ai du mal à évaluer à quel point cette construction est évidente (mais si on voit bien l'idée, personnellement, comme ça, je ne l'ai pas trouvée 100% évidente) mais il est vrai que l'évidence reste assez subjective. Personnellement, j'ai une construction plus évidente (où on ne se base que sur un seul des réseaux), ce qui permet de clore la preuve vraiment rigoureusement, mais si vous juger que votre construction est suffisamment évidente, je ne vous jetterais pas la pierre...

 #31 - 07-05-2020 18:17:11

nodgim
Elite de Prise2Tete
Enigmes résolues : 0
Messages : 3786

déforlation d'un treillis

Oui, en fait on peut voir un réseau comme un ensemble de rectangles indéformables disjoints, tous orientés de la même façon, et séparés par des parallélogrammes déformables. Je ne sais pas reproduire de dessin ici, mais j'ai pu dessiné un réseau droit ( les espaces entre rectangles sont des rectangles) et le même réseau avec les espaces inclinés. On se rend compte que l'intersection des lignes et des colonnes d'espaces restent des rectangles, ce qui prouve la déformabilité du treillis en double réseau. Donc, sur dessin, ça semble assez évident.

 #32 - 07-05-2020 19:59:19

TOUFAU
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 90

Déformatiion d'un treillis

Caduk, le 'n+p-2' était une erreur... n+p-2-1=n+p-3! (corrigé dans le post précédent)

Concernant le "Ie il suffirait pour l’un des 2 sous-treillis de choisir de localiser...", je comprends ta remarque.
J'utilise un autre argument (que je n'avais pas exprimé, bêtement) : Une ligne de bord qui ne possède qu'une cellule rigidifiée n'aura pas plus de cellules rigides - et au même endroit - que la ligne sur laquelle elle s'appuie. Au mieux, si la cellule rigidifiée s'appuie elle même sur une cellule rigide de la ligne précédente, elle propage cette rigidité (en créant un 'L' ou un 'T') sur sa ligne, pour toute cellule contiguë et en regard d'une cellule rigide de la ligne précédente.
Si toutes les cellules rigides de la ligne précédente étaient elles-mêmes contiguës, on obtient la même ligne, pas mieux.
De fait, l'utiliser pour réunir deux treillis non rigides ne sert à rien pour rigidifier l'ensemble. Pas plus en tout cas que si elle n'avait pas été là. Si l'ensemble n'était pas rigide sans elle, il ne le sera pas plus avec.
C'était globalement le sens de mon raisonnement, décidément pas hyper clair :-)

 #33 - 09-05-2020 12:20:33

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 393

Déformtaion d'un treillis

Toufau
Spoiler : [Afficher le message] Je ne comprends pas ton n+p-3, ton treillis souple possède n+p-3 cellules rigidifiées, et tu en rigidifies une nouvelle (en la localisant au même niveau que celle de la ligne que tu enlèves), donc ça te donne n+p-2, non?
Concernant ton dernier message, la rigidité ne se propage pas que par proximité immédiate, il est possible de complètement rigidifier le treillis sans avoir deux cellules rigidifiées adjacentes.

 #34 - 09-05-2020 21:16:31

TOUFAU
Passionné de Prise2Tete
Enigmes résolues : 0
Messages : 90

Déformation d'un treills

Caduk,

Sur ton premier point
Ce que je dis : je prends un treillis (n,p) contenant n+p-2 cellules rigidifiées (mon hypothèse à ‘casser’), et j’enlève une ligne ou une colonne contenant 1 cellule rigidifiée => le sous treillis (n-1,p) ou (n,p-1) reconstitué va contenir exactement n+p-3 cellules rigidifiées.

Sur ton second point
Je suis d’accord, la rigidité ne se propage pas que par proximité immédiate à l’intérieur d’un treillis. C’est même vrai pour la majorité des treillis rigides.

La rigidité se propage par contre par contact direct d'une ligne de bord si celles-ci ne contient qu’une unique cellule rigidifiée : il ne pourra pas y avoir de cellule de cette ligne de bord qui devienne rigide sans être au contact elle-même d’une cellule rigide de la ligne précédente (ie d’une cellule qui aurait déjà été rigide sans cette ligne de bord complémentaire).
Donc en ajoutant une ligne avec une unique cellule rigidifiée entre deux sous-treillis qui, réunis, ne formaient pas un treillis rigide, on n’obtiendra pas plus un treillis rigide :
-    soit la cellule rigidifiée de notre ligne intercalaire est en regard d’une cellule rigide d’un des sous-treillis qu’on cherche à réunir, et elle reproduira au mieux la même ligne que ce sous-treillis, sans aucun apport à l’ensemble de fait. Pas rigide sans, pas rigide avec...
-    Soit la cellule rigidifiée de la ligne intercalaire n’est au regard d’aucune cellule rigide des deux sous-treillis. Dans ce cas, même rigide elle-même, elle n’est pas figée : elle peut toujours pivoter faute d’être tenue figée par ses cellules de contact. Et aucune des cellules de sa ligne n’est rigide car elle ne transmet pas la rigidité sur sa ligne (quand bien même d'ailleurs toutes les autres cellules des deux bords des sous-treillis étaient rigides : pas de L ni de T pour transmettre la rigidité).
Ce qui, dans mon raisonnement, permettait de conclure à l’impossibilité d’un treillis (n,p) rigide avec seulement n+p-2 cellules: on ne peut, en ajoutant une ligne avec une unique cellule rigidifiée à un treillis (n-1,p) non rigide, obtenir un treillis (n,p) rigide.

Bon d’un autre côté, si je n’avais pas été clair dans mes posts précédents, celui-ci n’y changera sans doute rien 😊

 #35 - 10-05-2020 10:32:23

caduk
Professionnel de Prise2Tete
Enigmes résolues : 45
Messages : 393

déformation d'un teeillis

Toufau
Je comprend ton raisonnement comme ça :
(n,p) est le plus petit treillis rigide avec n+p-2 cellules.
Quand tu enlèves une colonne, le treillis (n-1,p) (qui a alors n+p-3 cellules est souple. Seulement, pour le rendre rigide, il me semble que tu ajoutes une cellule (celle que tu localises sur la colonne enlevée, mais je ne suis pas sûr d'avoir tout à fait compris cette partie là...). On obtient alors un treillis rigide de taille (n-1,p) avec n+p-2 cellules rigidifiées, ce qui ne nous apporte rien. J'ai sans doute mal compris ton raisonnement, le confinement n'aide effectivement pas beaucoup mon cerveau déjà lent lol

tous
Le temps est arrivé au bout, on peut voir les réponses de gwen, nodgim et vasimolo pour une construction de treillis rigide. Pour la preuve de la réciproque, si comme moi vous voulez quelque chose de bien rigoureux :

Prendre l'une des classes d'équivalences de cellules rigidifiées.
On note L (resp C) l'ensemble des lignes (resp colonnes) qui possèdent l'une de ces cellules.
On rigidifie de nouvelles cellules comme suit :
- Si une cellule appartient à un croisement de L et C, alors on la rigidifie.
- Si une cellule n'appartient ni à une ligne de L, ni à une colonne de C, on la rigidifie.
On peut noter que les cellules préalablement rigide de la classe d'équivalence choisie rentrent dans le 1er cas, et les cellules des classes d'équivalence restantes rentrent dans le deuxième cas.
Conséquence : On obtient un damier (irrégulier) alternant rectangles de cellules rigidifiées et rectangle de cellules non rigidifiées. On voit assez facilement que l'on peut déformer ce damier.

Exemple :
En reprenant l'exemple de Vasimolo, et en choisissant comme classe d'équivalence les carrés verts:

Code:

OOXX
XXOO
OOXX
XXOO

(X cellules rigidifiées, O cellules non rigidifiées)
Et si on prend comme classe d'équivalence le carré bleu :

Code:

XOXX
OXOO
XOXX
XOXX

Les damiers correspondent en fait aux cas avec le moins de degrés de liberté de treillis amovibles.

 #36 - 10-05-2020 11:47:04

Vasimolo
Le pâtissier
Enigmes résolues : 49
Messages : 5,233E+3

Déformation d'un treilis

Oui Caduk , c'est une façon de voir les choses .

Nous avons chacun notre perception de ce qui est clair ou pas . Personnellement j'ai aussi beaucoup de mal à suivre les réponses traînant un paquet de sous-entendus censés être évident . Mais comme j'ai aussi ce défaut ...

Joli problème en tout cas smile

Vasimolo

 

Réponse rapide

Rédige ton message
| | | | Upload | Aide
:) :| :( :D :o ;) :/ :P :lol: :mad: :rolleyes: :cool:
Sécurité

Répondez à la devinette suivante : 

Le père de toto a trois fils : Pim, Pam et ?

Sujets similaires

Pied de page des forums

P2T basé sur PunBB
Screenshots par Robothumb

© Copyright 2002–2005 Rickard Andersson

Prise2Tete Forum Statistiques Liste des membres Hall of Fame Contact
© Prise2tete - Site d'énigmes et de réflexion.
Un jeu où seules la réflexion, la logique et la déduction permettent de trouver la solution.

Flux RSS de Prise2Tete Forum Jeux & Prise2Tete Test & Prise2Tete Partenariat et Publicité sur Prise2Tete