Bonjour,

 Cliquez pour afficher

Partons d'une configuration telle que se soit le cas et déplaçons les points. Au moment ou les bords des triangles se croisent (et donc que les triangles se décroisent), on peut recréer une autre configuration croisée en échangeant les deux bords qui se croisent.

Bonjour  Weierstrass

Il faudrait expliciter davantage ta stratégie , pour moi ce n'est pas clair même si je comprends l'idée .

Imod

salut

une idée : je pense que c'est peut-être une histoire de régionnement de l'espace ...

 Cliquez pour afficher

à partir de six points partons de deux triangles non imbriqués  ABC et DEF :

donc les points D, E et F sont dans un même demi-espace de frontière le plan (ABC)



alors permutons le point (ici C) avec l'un des trois points du triangle DEF (ici F) alors on a deux cas : les deux nouveaux triangles ABF et CDE ne sont pas imbriqués ... ou ils le sont comme sur la figure ...
et alors A et B sont dans un même demi-espace et F est dans l'autre demi-espace de frontière le plan (CDE)

si ces deux nouveaux triangles n'étaient pas imbriqués alors on recommence avec les triangles ABE et CDF ...

et ainsi de suite ...

si avec les 20 configurations possibles on n'y arrivait pas alors cela signifierait que tout triplet de point est dans un même demi-espace de frontière le plan défini par les autres trois points ...

ce qui serait absurde ...

 Cliquez pour afficher

dans une configuration initiale où les deux triangles ne sont pas imbriqués et vu mon PPS peut-être faut-il développer le raisonnement en considérant
les deux cas : les points D, E et F sont dans un même demi-espace de frontière le plan  (ABC) ou non ...

Il parait qu'on va tout faire pour fabriquer du paracétamol en France sans dépendre de la chine ou autre , il va falloir faire vite

Pour moi , il y a au moins deux façons d'aborder le problème :

1°) Celle esquissée par Weierstrass et Carpediem , je pense que ça peut marcher mais il faut être extrêmement rigoureux et préciser clairement de quoi on parle . Par exemple pour six points donnés , est-on capable en partant d'une configuration quelconque avec deux triangles imbriqués , de déformer cette position pour arriver à la position initiale en conservant l'imbrication  ( en changeant éventuellement quelques côtés lorsqu'il y a collision ) ?

2°) En considérant l'enveloppe convexe des six points et en détaillant toutes les possibilités , ça marche mais c'est vraiment pénible ( à moins que j'ai raté une simplification ) .

Il y a peut-être une troisième approche qui tue le problème mais laquelle ? Un graphe , une projection , .....

Imod

PS : il s'agit d'un problème d'olympiades .

Carpediem et moi n'avons pas la même approche du problème, en effet, carpediem ne parle pas de déformation continue, mais change juste les permutations de sommets pour les triangles.

Je ne comprends pas très bien la démo de Carpediem. Déjà, il est possible d'avoir deux triangles non imbriqués tel que les 3 points ne sont pas dans le même demi plan défini par l'un des triangles. (Sans même parler des cas ou le triangle rentre et ressort de l'autre triangle). Après, il y a effectivement peut être une idée dans cette veine là, à creuser.

Bonjour
Imod, s'il s'agit d'un problème d'olympiades tu as la solution proposée ?

Bonjour à tous

J'avais en effet mal lu la solution de Carpediem , je ne pense pas qu'on arrive à démontrer quoique ce soit en permutant les sommets . J'avais aussi pensé à la solution « dynamique » proposée par Weierstrass mais il me semble que la conservation du caractère « imbriqué » au moment du croisement n'est pas si évidente que ça . Du coup j'ai une autre idée qui combine celle de l'enveloppe convexe ( il y a quatre cas possibles et pas vraiment marrant ) avec celle du point mobile . Au passage critique l'enveloppe convexe est un polyèdre à cinq ou six sommets dont quatre sont coplanaires ce qui ( sauf erreur ) ne laisse que trois possibilités . Il reste à voir si parmi ces trois possibilités , il y en a toujours une qui laisse imbriqués les triangles . Pour cette imbrication il faut considérer que n'importe lequel des quatre points coplanaires peut-être légèrement en dessous ou au-dessus du plan .

PS : Ce n'est sans doute pas clair car rédigé sur un coin de table .

PPS : @ Derny , je n'aurais pas fait tant de mystère si j'avais une solution clé en main  

Imod  

Je suis d'accord sur le fait qu'il faille détailler plus la solution du mouvement continu, mais j'ai pas trop le temps de regarder ça. En revanche, on doit pouvoir tout ramener à un seul cas : celui où dans le cas critique dans le cas critique, les triangles se décroisent au niveau des côtés. (et dans ce cas, il n'y a normalement qu'un cas de figure pour la permutation des sommets). Si les triangles se décroisent au niveau d'un sommet, on peut se ramener au cas précédent en faisant un petit crochet et en croisant deux fois au niveau des côtés. (On doit pouvoir justifier proprement qu'entre deux positions, il existe un chemin sans décroisement au niveau d'un sommet par un raisonnement de dimension - les cas ou il y a de tels croisements étant infiniment peu nombreux). J'essayerais de voir ça ce soir.

Je suis d'accord que l'on peut supposer que le croisement se fait à l'intérieur des côtes , n'empêche qu'il y a plusieurs configurations à envisager .

Imod

Les dessins 3D me tordent vraiment l'esprit , je cherche une explication plane .

Si on projette proprement deux triangles sans sommets communs sur un plan lointain , on obtient deux triangles dont les côtés se coupent en un nombre pair de points  : 0 , 2 , 4 ou 6  .  Si on redéfinit la couleur des points verts comme celle du segment supérieur , j'ai l'impression que l'on dispose d'un moyen de caractériser les triangles imbriqués .  Après il reste à voir comment conserver cet invariant en déplaçant des points .



Imod

Ils sont imbriqués si un nombre impairs de croisement, le rouge passe au dessus.
Dessinons deux cordes fermées vérifiant cette propriété. On aura forcément deux noeuds consécutifs deu même type. On peut donc faire glisser la corde pour retirer ces deux noeuds. On garde une répartition impaire. Ca continue jusqu'à ce qu'il ne reste que deux croisements. (et donc de types différents). Les cordes sont donc imbriquées. C'est du raisonnement assez classique dans la théorie des noeuds

Oui , c'est clair . Je ne suis pas sûr que ça fasse progresser le problème

Imod

Bonjour,

J'ai regardé les polyèdres à 4, 5, puis 6 sommets à faces triangulaires,
avec 2, 1 puis 0 points intérieurs respectivement, représentés en perspective cavalière :
arêtes extérieures en noir, intérieures en rouge.
Quand il y a intersection factice de la perspective, le trait le plus épais en rouge
est le plus proche.
Les triangles imbriqués sont ACE et BDF
Mieux qu'un long discours sur la vue présentée, on voit ce sui se passe
si le point F passe à gauche de l'arête AC en restant plus proche que E dans l'espace intérieur

Oui , c'est un peu le genre de réponse que je souhaitais éviter . Il y a quatre enveloppes convexes différentes avec 0 , 1 ou deux points à l'intérieur et en analysant chacun des cas en fonction de la position des points intérieurs on voit bien que c'est toujours possible .
Je suis d'accord que ça marche mais grosso-modo on renvoie le lecteur à la vérification de chacun des cas , c'est un peu facile et c'est une ( petite ) usine à gaz .

J'attend plutôt une idée à la Weierstrass qui règle le problème sans ambiguïté et sans analyse de multiples cas .

Imod

Bonsoir,

Il s'agit pourtant bien de caractériser d'abord dans quelles configurations peut se trouver tout groupe de 6 points avant d'évaluer ces configurations...

Je ne vois pas d'obligation , si on arrive par exemple à monter qu'on peut atteindre continûment six points quelconques à partir d'une configuration imbriquée sans jamais perdre l'imbrication , on a la conclusion .
Il y a peut-être d'autres idées .

Imod

Bonjour,

Je doute que votre démarche soit valable, si par exemple il y a un nombre différent de triangles imbriqués suivant les configurations. En conservant deux triangles imbriqués vous pouvez peut-être devoir passer d'une configuration de départ à une autre qui en a moins... Etc

Il suffit peut-être de montrer que si deux triangles sont imbriqués, toute autre connexion des 6 points en 2 triangles donne 2 triangles non imbriqués...

Je suis quasiment sûr que pour chaque configuration, il n'y a qu'une seule paire de triangles, et lors des croisements, j'ai l'impression que c'est toujours la même permutation qui s'effectue. Sur les schémas, ça se voit bien, mais j'ai du mal à démontrer proprement l'imbrication...

@Wham

Quand je parlais de passer d'une configuration de six points à n'importe quelle autre , j'autorisais bien sûr des échanges à chaque croisement .

@Weierstrass

Une seule paire de triangles imbriqués , j'ai du mal à y croire ?

Imod

PS : j'ai réagi un peu sèchement à la solution de Wham , ce n'était certainement pas une marque d'hostilité mais ce type d'exercices est pratiquement toujours expédié de cette façon : ici ça marche et on fait sensiblement pareil pour tous les autres cas . Bien souvent on ne peut pas échapper à une étude cas par cas , mais quand on peut on a une belle énigme

Bonjour,

--> imod : vous n'êtes pas obligé de me donner un double v, et majuscule en plus.
Oui je suis aussi en recherche de rigueur dans le raisonnement, mais pas moins que vous mes interventions ne donnent d'explications complètes sur mes démarches

Imod, as tu un exemple avec deux paires de triangles imbriqués ?

J'ai l'impression que le problème est plus topologique que géométrique...
c'est à dire que même si on reliait parmi six points, on reliait toutes les paires de points par des traits non droits, on pourrait toujours extraire deux cycles de longueur 3.
Je ne suis pas sûr de ce que j'avance, hein...

Du coup, le problème me parait très proche de la question de graphe planaire ou toroïdal. D'ailleurs, la famille de graphes vérifiant la propriété : "il existe un plongement dans l'espace tel que, pour toute paire de cycles disjoint, les cycles ne sont pas imbriquée" me semble close par mineure.

J'ai donc espoir d'une démo mêlant théorie des graphes et topologie...

@Weierstrass

Je n'ai pas de contre-exemple pour l'unicité de la solution mais je ne suis pas sûr quelle soit utile pour la résolution du problème . J'ai bien aimé ton idée initiale , partir d'une position croisée pour obtenir l'ensemble des sextuplés en déplaçant un point et échangeant quelques segments aux passages délicats .  Dans la pratique l'analyse est vraiment trop compliquée , je me demande s'il n'est pas plus simple de déplacer un segment .

Je crois comme toi qu'il y a une idée simple cachée sous ce problème , mais comment la trouver ( je cherche depuis un bon moment ) ?

Imod    

Pour moi, l'idée que j'ai présentée en premier est celle qui me semble la plus facile à aboutir, car je"voit" ce qui se passe, sans arriver à le prouver rigoureusement. Les problèmes de topologie sont souvent traîtres au niveau de la difficulté à montrer quelque chose qui parait évident (comme le théorème de Jordan, par exemple)?

C'est à voir , il y a aussi des problèmes apparemment extrêmement complexes ayant laissé secs les plus malins avant qu'on ne trouve un bon angle d'attaque  ( je pense au problème de Sylvester-Gallai ) .

Imod

Bonsoir,

En réponse à l'intervention du 24-06-20 à 12:50, j'ai une configuration de 6 points
pour laquelle il y a 3 paires de triangles imbriqués.
(Vérification complète analytiquement et comparée avec GeoGebra).
Bonne suite...

Bonjour,

pour ne pas rester sans solution démontrée :
Cas où l'enveloppe convexe des 6 points est un tétraèdre , 2 des points, E et F intérieurs au tétraèdre.

 Cliquez pour afficher

La droite (EF) intersecte 2 des faces en I et J, que nous dénommons respectivement faces ABD et ACD, Supposons (sans perte de généralité) E entre I et F, Construisons le tétraèdre ACDE ayant le point F en son intérieur. Le segment [FB] intersecte obligatoirement une des faces parmi ACE, CDE ou ADE, supposons (sans perte de généralité) que c'est le triangle ACE.
Les deux triangles ACE et BDF sont imbriqués car [BD] et [DF] sont entièrement extérieurs au triangle ACE.

L'arète [BC] du tétraèdre enveloppe n'est pas tracée...tous les triangles sont supposés transparents

Bonsoir,

Il y a un raisonnement de même pour les configurations pentaèdres et hexaèdres irréguliers convexes à faces triangulaires sans avoir à énumérer tous les cas de paires de triangles possibles.
On montre en sus qu'il ne peut y avoir qu'une seule paire de triangles imbriqués pour les tétraèdres et les pentaèdres, et qu'il y en a trois pour les hexaèdres.

Bonjour,

J'ai découvert que ce "magnifique petit casse-tête" avait été étudié il y a onze années sur un autre site de haut niveau mathématique.

Les configurations possibles de polyèdres irréguliers convexes à faces triangulaires que l'on peut construire dans l'espace euclidien de dimension 3 avec 6 points non coplanaires
se résument pour moi à 3 bien définies : il y a 2, 1 ou 0 points intérieurs.
Pour chacune de ces configurations la démonstration est courte.

A noter qu'il n'est pas interdit que 2 faces soient parallèles (ce qui ne change pas les raisonnements).

Bonjour Vhan

Je suppose que tu fais référence à ce lien que j'avais initié sur les Mathématiques.net .

Généralement je ne cache pas mes sources , j'ai fait une exception ici car je cherchais une nouvelle approche .

Il est parfois judicieux d'aborder un problème sans être enfermé dans le cadre d'une solution déjà fournie .

La question que je pose ici est exactement celle que posais à la fin du fil .

N'ai-je pas annoncé que ce problème me tracassait depuis très longtemps ?

D'un autre côté , s'il y a comme tu le dis une solution très courte justifiant l'ensemble des configurations possibles et les solutions dans chaque cas , je suis très impatient de la voir .

Imod

Désolé Vham , j'ai vraiment du mal avec ton pseudo

Imod

Bonjour,

--> imod : est-ce que pour vous la démonstration du 02-07-20 10:21 règle correctement toutes les configurations comportant 2 points intérieurs ?
Pour moi, oui. Et le raisonnement est du même genre pour un seul point intérieur. Quant à l'hexaèdre qui contient 3 diagonales intérieures, prises 2 à 2 elles donnent les 3 solutions qui suivent le même comportement par permutation circulaire.
Espérant avoir été assez complet

J'ai écrit un programme qui donne tout ce que l'on peut tirer de 6 points : Enveloppe convexe, validités, intersections de plans et de droites, imbrications....
Ce n'est pas une démonstration mais un outil excellent pour comprendre et bien voir que ce casse-tête n'est pas si complexe.

J'avais aussi vérifié tous les cas de figures et j'étais déjà convaincu que tout se passait toujours très bien mais je suis tout de même ravi que tu le confirmes

Il s'agit d'un problème d'olympiade à résoudre en temps très limité et sans outil informatique .

J'ai encore un peu d'espoir qu'il existe une solution courte et simplissime

Imod

    

La seule évidence simple qu'il faut dégager est : Quand un espace est partitionné par une frontière, pour aller d'un domaine à un autre il faut intersecter la frontière.
C'est le guide efficace dans les solutions mises en oeuvre ici.
Ne dites pas par exemple pour le problème des 4 couleurs : ah, il doit exister une solution courte et simplissime sous prétexte qu'il a fallu traiter tous les cas sur ordinateur !
(C'est la différence entre problème subtil et problème complexe cité par Paul Erdös)

Bonjour à tous
Imod, pour ne pas avoir à écrire les pseudos, il te suffit de cliquer sur la petite figurine tout à droite du pseudo...(au delà des guillemets de citation)

Ma conjecture était bonne, à savoir que le problème restait vrai quand on autorisait des arcs courbe.


Je n'ai pas accès au papier par contre...

Comme je le faisait remarquer, on a une caractérisation des graphes avec cette propriété en terme de fermeture par mineurs. (et on à même la liste complète des mineurs)
Le problème avec des segments droits (comme dans l'énoncé) n'a en revanche pas encore de classification complète. (on ne sait pas si la famille coïncide avec le cas où les arcs peuvent être tordus)

Oups, mon lien pointe sans le faire exprès vers un lien (mais ce n'est pas l'article dans lequel il y a la démo...)

weierstrass, remets en réponse le lien que tu voulais, je vais aller le changer au dessus si tu veux

En fait, je voulais juste pointer vers la page wikipédia, mais comme j'avais cliqué sur une référence vers le lien, l'url intégrais le lien vers la référence, mais on arrive quand même sur la bonne page (juste ça l'affiche tout en bas)

J'ai commencé à regarder les différents documents dans ton lien mais c'est vraiment pointu et en english : il me faudra du temps pour décrypter tout ça

J'aimerais bien voir la solution "officielle" du problème mais c'est un problème iranien et comme les russes ils ne fournissent pas facilement les solutions de leurs olympiades .

Imod

Bonjour,

Imod : vous n'aviez juste que parlé d'olympiades et j'ai découvert le site de haut niveau dont je parle le 09-07-20 11:42 "par hasard" un peu avant (vous confirmez par le lien à 12:20).
Je pense y avoir reconnu votre façon d'intervenir pour laquelle l'inversion dans les pseudos est assez transparente.
Heureusement vous y dites : "mais j'ai du mal à me satisfaire d'une telle démonstration sans doute efficace mais pas très jolie ."  en évoquant l'utilisation de l'enveloppe convexe des 6 points.
Je suis satisfait d'avoir trouvé le même cheminement pour une démonstration....qui ne vous satisfait toujours pas après 11 années.

Ca y est, j'ai trouvé une preuve accessible (et elle tient en 5 lignes, c'est dégueulasse )


Si je traduit en français :
Pour tout couple de triangles C1, C2, on définit lk(C1, C2) qui vaut 1 si les triangles sont emboités, et 0 sinon. Dans le cas d'arcs pouvant être courbe, cette fonction vaut l'enlacement.
L'enlacement vaut 0 si il n'y a pas d'imbrication, 1 si on imbrique en passant une fois dans l'autre boucle, n en passant n fois dans le même sens dans l'autre boucle. voir .

On définit comme la somme des lk(C1, C2) sur toutes les paires de triangles modulo 2.

Quand on croise deux arcs, pour toutes paires de triangles C1, C2 telles que C1 et C2 contiennent chacune un arc qui se croise, si les triangles étaient imbriquées, il ne le sont plus, et s'ils ne l'étaient pas, ils le deviennent. (Dans le cas général, ça modifie de plus ou moins 1 l'enlacement). Le changement de parité de s est donc équivalent à la parité du nombre de couples C1, C2 contenant chacun un arc qui se croise.

Reste plus qu'à compter. Il suffit d'associer à chaque arc un sommet de plus pour former un triangle. Comme il ne reste plus que 2 sommets à associer, il n'y a que deux possibilités. La parité de s ne changera donc pas.

Il suffit de vérifier qu'il existe un graphe ou s est de parité 1.
Si il n'existait pas de couples avec imbrication, tout les enlacements vaudrait 0, et donc s vaudrait 0. Ce ne sera donc jamais le cas, s sera forcément impair.
(Et dans notre cas, s ne vaudra que 1 ou 3, comme vham l'a fait remarqué dans sa démo)

Au final, une bête histoire de parité, c'est franchement élégant...

La démo dans l'article est la toute première (pour que vous ne vous perdiez pas dans les abysses de l'article)

J'ai du mal à te suivre Weierstrass mais c'est certainement de ma faute

Dans une configuration avec deux triangles imbriqués , il y a deux points de rencontre ( en projetant sur un plan ) .  Si tu conserves les segments passant par l'un de ces points et que tu passes les sommets restant d'un triangle à l'autre , tu risques de conserver la parité de l'enlacement . On arrive peut-être à changer la parité en considérant l'autre point de croisement mais ça ne me semble pas évident .

Imod

  

Bonjour,

weierstrass : Je n'ai pas bien compris comment décompter les intersections.
Pourriez-vous traiter en exemple ce graphe planaire
qui est la projection des six points A à F de l'espace, sans préjuger de l'appartenance ou non des points E et F à l'enveloppe convexe dans l'espace ?

Je me perds dans les orientations qu'il faut donner aux 10 paires de triangles
pour sommer aux 9 intersections notées G à O.

@Vham

Les six points et le "au dessus , au dessous" sont des données , il faudrait que tu précises qui passe au dessus et au dessous .

Imod

Le changement de parité intervient pour une paire de triangles données lorsque l'on croise deux côtés. On ne touche pas au sommet, il faut s'imaginer que les cotés sont mous. Sur le dessin, si à un point de croisement, un côté passait au dessus d'un autre, alors si on croise ces deux côtés, alors il passera cette fois ci en dessous. Donc pour une paire de triangle donnée, la parité change.

Comme tu le dis, un fois que tu as pris des deux côtés, pour les deux côtés restants, il ne reste que deux possibilités de les distribuer. Il n'y aura donc que ces deux paires qui seront affectées par le changement de parité. Au total, la parité ne changera donc pas.

Vham
Il faudrait que tu me décrives qui passe au dessus et qui passe au dessous...