Enigme des 3 maisons

[invite35452583]

Alors le cas suivant serait la caractéristique -1, avec comme seule surface le plan projectif avec une anse... Graphe (5,4) à trouver par exemple... Ca devient cauchemardesque, j'ai plus les pavages pour aider... Temps de passer à autre chose

Cordialement,

Pas forcément maintenant, mais un angle d'attaque du problème me semble celui-ci. On a m+n sommets, mn arêtes, comment fabriquer un graphe sans bord à partir de ceci avec uniquement des faces quadrilatères. Il vaut mieux commencer avec n ou m pair, on a puisq'il n'y a que des faces quadrilatères 4f=2a=2mn f=mn/2. c=mn/2-mn+m+n=m+n-mn/2. Après regardé le problème des orientables. Pour les caractéristiques inférieures : on découpe une face on colle ce qu'il faut et c'est gagné.
L'avantage est de rendre le problème plus algébrique et donc, a priori, plus facile d'accés (sans que ce soit évident) : trouver une famille F(ai,ai', bj,bj') tel que chaque arête ak-bl soit dans exactement deux faces.
-----

[invite35452583]

Pas forcément maintenant, mais un angle d'attaque du problème me semble celui-ci. On a m+n sommets, mn arêtes, comment fabriquer un graphe sans bord à partir de ceci avec uniquement des faces quadrilatères. Il vaut mieux commencer avec n ou m pair, on a puisq'il n'y a que des faces quadrilatères 4f=2a=2mn f=mn/2. c=mn/2-mn+m+n=m+n-mn/2. Après regardé le problème des orientables. Pour les caractéristiques inférieures : on découpe une face on colle ce qu'il faut et c'est gagné.
L'avantage est de rendre le problème plus algébrique et donc, a priori, plus facile d'accés (sans que ce soit évident) : trouver une famille F(ai,ai', bj,bj') tel que chaque arête ak-bl soit dans exactement deux faces.

Il manque une condition, celle que j'ai donné permet aux points intérieurs des arêtes d'être régulière : exactement 2 faces sont collées sur l'arête donc c'est localement un disque ouvert.
Pour les sommets de la famille A, ils sont reliés à tous les sommets de la seconde famille B. Avec la condition précédente concernant les faces et arêtes, on peut aller de proche en proche. BkAiBk' est le début d'une face (il existe Ai' tel que BkAiBk'Ai' soit une face). Comme je n'ai pas encore donné de numéro, je peux prendre un 1er sommet B1, une face B1A1B2(A?), ce qui définit B2, ... et on a une séquence B1B2...Bh. Ce qui peut arriver à ce sommet est qu'il y ait plusieurs tours avec des faces ainsi, on a alors plusieurs disques collés en ce sommet A qui est alors singulier. La condition est qu'en allant de face contenant A ainsi on fait le tour de tous les sommets B.

Maintenant, un cas facile famille A (resp. B) a un nombre pair de sommets m (resp.n)
On peut prendre les faces ainsi :
Bj Ai Bj+1 Af(i) si j impair (famille 1) (j+1-n si j+1>n)
Bj Ai Bj+1 Ag(i) si j pair (famille 2)
où f=(12)(34)...(m-1 m)
et g=(m1)(23)(34)...(m-2 m-1)

1) condition pour les arêtes
BjAi est dans une seule face de la famille 1 car i est dans un seul couple de la forme (i',f(i')). Il en est de même pour la famille 2.
2) condition aux sommets
trivial pour les sommets A (on a construit autour d'eux)
pour les sommets B.
On a pour j impair
BjA1Bj+1A2 est une face on repart avec l'arête BjA2
BjA2Bj-1A3 est une face (j-1 pair j=(j-1)+1 3=g(2))
BjA3Bj+1A4 est une face
...
BjAmBj-1A1 est une face (m est pair)
On a donc la séquence de sommets A autour de Bj :
A1A2A3...AiAi+1...Am, le sommet bj est régulier.

On a donc construit un espace-graphe de carcatéristique mn/2-mn+(m+n) ce qui était recherché.
On oriente les faces de la famille 1 Bimpair->A impair->Bpair->Apair
famille 2 Bimpair->Apair->Bpair->Aimpair
Les deux faces d'une même arête étant de deux familles distinctes, ce choix est compatible aux changements de face, la surface est orientable.

Il me semble qu'en découpant le long de :
B1A1B4A2B1A3B4....B1 et en recollant dans l'autre sens
B4A1B1A4B1A3B1....B4
on obtient un graphe d'une surface de même caractéristique mais non orientable si n>=6. Le cas 4-4 étant résolu ce serait suffisant pour régler le cas n et m pairs.
Resteraient les cas :
n pair, m impair orientable et non orientable (face=quadrilatère)
n et m impair (non orientable) une face est un "hexagone" les autre sont des "quadrilatères".

[invité576543]

J'essaye de suivre, mais ce n'est pas facile!

Amicalement,

[invite35452583]

On peut prendre les faces ainsi :
Bj Ai Bj+1 Af(i) si j impair (famille 1) (j+1-n si j+1>n)
Bj Ai Bj+1 Ag(i) si j pair (famille 2)
où f=(12)(34)...(m-1 m)
et g=(m1)(23)(34)...(m-2 m-1)

On peut simplifier
Bj Ai Bj+1 Ai+1 avec i,j impairs (famille 1)
Bj Ai Bj+1 Ai+1 si i,j pairs (famille 2)
avec congruences modulo m et n adaptées.

[invite35452583]

J'essaye de suivre, mais ce n'est pas facile!

Amicalement,

Je vais essayer de reprendre une partie de manière plus à la clarifier (enfin j'espère).
On essaie de définir une surface sans bord à l'aide d'un graphe (dans ce problème les sommets et les arêtes sont données on cherche à définir les faces).
Pour être une surface sans bord, une seule condition : pour tout point il doit y avoir un voisinage qui est un disque ouvert.
Maintenant pour notre graphe il y a trois types de points :
1) les points intérieurs aux faces : ces points sont sur une seule face (il suffit de donner une dimension particulière à chaque pour cela, les 3 1ères dimensions sont communes et permettent d'installer sommets et arêtes, les coeff X4,X5...Xk sont chacun "réservés" à une face) donc rien à vérifier
2) les points intérieurs des arêtes : il y a k faces collées sur l'arête, chacun "amène" un 1/2 disque il faut et il suffit que k=2
3) les sommets qui sont plus délicats.
Il y a k arêtes qui partent de ce sommet.
La condition sur les arêtes impliquent qu'il y a k faces contenant ce sommet.
La seule chose qui peut encore arriver est quel que chose de ce type : on prend deux cubes et on colle un sommet A' sur un sommet A" de l'autre. Il est clair que le sommet A=A'=A" est singulier (on ne lui trouver pas de voisinage qui soit un disque).
Une autre manière de voir ceci est que en allant de faces adjacentes en faces adjacentes on a deux cycles disjoints de faces et d'arêtes.
La condition à vérifier est donc qu'en allant de faces adjacentes en faces adjacentes on a un unique cycle. Il est assez facile de se convaincre que cela revient à dire que les arêtes forment aussi un unique cycle.

Pour le cas m et n pairs on a le cas assez simple cité ci-dessus.

[invité576543]

Ca devient plus clair. Au passage comment on "lit" l'orientation à la données des faces?

Dans le cas m et n pairs, la caractéristique est pair, donc il y a les deux cas, orientable et non orientable, sauf dans le cas où n=2 ou m=2.

Amicalement,

[invite35452583]

Ca devient plus clair. Au passage comment on "lit" l'orientation à la données des faces?

La non orientabilité : on donne une orientation à une des faces, celle-ci se "profuse" par contact avec ses voisines : son orientation donne une orienation à ses arêtes, la voisine aussi, les duex orientations de l'arête sont opposées (effet impair des symétries axiales).
Si en empruntant un chemin de faces adjacentes (ce qui se lit facilement à la donnée des faces) on retourne à la face initiale avec une orientation opposée, la surface n'est pas orientable.
L'orientabilité :
on fait un choix cohérent d'orientation pour toutes les faces. Ce choix doit être cohérent pour tous les contacts de faces adjacentes.(ce qui se lit facilement à la donnée des faces du moins si le choix est simple)
Dans le cas n et m pairs la division en deux familles (deux faces adjacentes sont chacune d'une famille) permet de définir une orientation et d'avoir une vérification somme toute assez aisée.

Dans le cas m et n pairs, la caractéristique est pair, donc il y a les deux cas, orientable et non orientable, sauf dans le cas où n=2 ou m=2.

Amicalement,

D'abord explication de l'exclusion du cas n=m=2. Ce cas nous donne un tétraèdre et donc une sphère, il n'y a pas de chemins fermés non triviaux (la sphère est simplement connexe) donc couper le long d'un chemin puis inverser le sens du collage (en gros on passe d'une sphère à une lentille biconvergente ou bidivergente, j'espère que tu vois ce que je veux dire, mais après une déformation élémentaire on retourne à une "belle" sphère). Il se passe la même chose sur les autres surfaces, si on découpe le long d'un chemin fermé homotopiquement trivial, on découpe en fait un disque on a beau le "retourner", la surface finale est la même. Par contre, si je découpe une surface orientable selon un lacet non trivial je récupère après découpe-recolle une surface non orientable.
En plus "vicieux" je découpe une surface de Boy le long d'un lacet (chemin fermé) non trivial je recolle dans l'autre sens je n'ai rien changé (ici facile à voir la caractéristique est toujours égale à 1 pas de risque de confusion). Ainsi passer de non orientable à orintable est encore plus délicat : selon le lacet pris sur la bouteille de Klein, on récupère après opération de découpage-recollage un tore ou on retourne sur la bouteille (tous les lacets non triviaux n'ont pas tout à fait la même nature).

Dans le cas m et n pairs, la caractéristique est pair, donc il y a les deux cas, orientable et non orientable, sauf dans le cas où n=2 ou m=2.

Amicalement,

(suite)
Dans le cas n et m pairs, j'ai découpé et recollé de telle manière que localement (autour d'un sommet A, je n'ai fait qu'échanger B1 et B4 ; les points B1 et B4 ont été échangé donc localement, ça roule, les autres sommets B sont inchangés) j'ai recollé sur les mêmes arêtes deux faces de famille 1, idem pour les faces de la famille 2. Le lacet pris a peu de chances d'être homotopiquement trivial ça devrait donc marcher (j'ai évité de prendre B1-Ai-B2 ou Bn car dès le départ cela donne une face pour déformer le lacet je crains que cela donne un lacet trivial) : on doit pouvoir trouver un chemin de faces adjacentes allant d'une face à sa nouvelle adjacente sans passer par le lacet recollé. Si cela est fait on a face type 1-face type 2-....-face type 1 (les passages se font bien car ce sont les "anciens passages" ceux de la surface orientable) et, si c'est le cas, ça coince au recollage sur le lacet de découpe-recolle donc non orientable. (Il faudrait prendre le temps de vérifier tout ceci de manière plus précise).

Dans le cas m et n pairs, la caractéristique est pair, donc il y a les deux cas, orientable et non orientable, sauf dans le cas où n=2 ou m=2.

Amicalement,

(suite et fin temporaire)
1) n et m pairs-> orientable OK, non orientable a priori OK
2) n, m 1 pair 1 impair
impair->c=m+n-mn+(mn)/2=2-(m-2)(n-2)/2
a) le pair est un multiple de 4, on doit en trouver un à mn/2 faces orientable et un orientable
b) le pair n'est pas un multiple de 4, on doit en trouver un non orientable à mn/2 faces et un orientable à mn/2-1 faces (on ne peut compter sur m(n+1) par exemple puis on retire un des (n+1) sommets, la caractéristique est trop grande)
3) n et m impairs
non orientable il en faut un avec (mn-1)/2 faces.
orientable : selon les cas avec (mn-3)/2=(mn-1)/2-1 faces (ex : n= m=5 ou n=5 m=9) ou avec (mn-1)/2 faces (ex : n=5, m=7 ; 2-(5-2)(7-2)/2=-5,5 il faut trouver un graphe pour c=-6)

Idée que je n'ai pas encore creusée : pour m pair et n+1 n pair (n+1 impair) partir du graphe orientable n,m et ajouter un sommet, on a droit à m/2 faces en plus (pas m malheureusement) ajouter ce (n+1)ème sommet autour des n sommets sur une seule des deux familles. Et tenter de recoller tout ça (un vrai obsédé du recollage que je suis, non ? )

En espérant que cela aide à continuer à clarifier.

Amicalement, Luc

[invité576543]

Bonjour,

Je vais essayer de reformuler ce que je comprend, plus un soliloque menant nulle part pour le moment...

Je note ABC... un type de sommet et 123... l'autre type de sommet, plus simple à écrire et à visualiser.

Une solution à faces carrées peut être décrite par la données des cycles des sommets d'un type autour de chaque sommet de l'autre type. Dans le cas orientables, les cycles sont donnés dans des ordres cohérents, c'est à dire vus d'une même orientation

Par exemple, la solution 4-4 sur le tore, dérivée de la solution générique proposée par homotopie, se décrit par les cycles suivants

A: 1432; B: 1234; C: 1432; D: 1234
1: ADCB; 2: ABCD; 3: ADCB; 4: ABCD

La liste des faces s'obtient alors en prenant un sommet (e.g., A), deux sommets consécutifs dans la liste (e.g., 1 et 4), et le successeur du premier sommet dans le cycle du deuxième (e.g., D, résultat A1D4) qui est identique au prédécesseur du premier dans le cycle du troisième.

La contrainte d'égalité peut se décrire généralement



(en notant succ_a la fonction succ dans le cycle autour du sommet a...)

Elle est automatiquement respectée par la construction de homotopie, qui consiste à prendre un cycle pour les sommets pairs et le même cycle dans l'autre sens pour les autres.

La solution (8,6) sur le 6-tore est alors:

A, C, E et G: 165432; B, D, F et H: 123456
1, 3 et 5: AHGFEDCBA; 2, 4 et 6: ABCDEFGH


En partant de ce type de description, on peut regarder à quoi ressemble une solution sur des cas autre que (m et n pair, orientable)

Une solution pour le cas (4, 4, n.o) est

A: 1423; B: 1324; C: 1432; D: 1234
1: ADBC; 2: BACD; 3: BDCA; 4: ABCD

La construction des faces est la même, par exemple A, 14 -> D, d'où le face A1D4, ou A, 23 -> C, face A2C3

comme c'est non orientable, le cycle et son inverse sont confondus, et on pourrait penser qu'on peut arbitrairement choisir le sens de lecture. Cela donnerait, pour faire apparaître les identités:

A: 1324; B: 1324; C: 1234; D: 1234
1: ABCD; 2: ACDB; 3: ACDB; 4: ABCD

Mais alors la construction des faces ne marche plus, et je ne vois pas comment la remplacer...

Néanmoins, cela laisse penser que la contrainte pred/succ sur les cycles est une bonne direction pour construire les solutions non orientable. ??

Une solution brute, qui ne respecte pas la contrainte pred/succ, pour le cas (4, 3, n.o.) est

A: 123; B: 132; C: 123; D: 132
1: ABCD; 2: ACDB; 3: ADBC

Mais il ne semble pas possible de trouver une description respectant la contrainte pred/succ, .

Du coup la construction des faces à partir de cette donnée ne peut pas être celle proposée...

Une contrainte plus faible est néanmoins respectée, à savoir



La construction des faces est alors, on prends un sommet (e.g., B), on prends deux sommets consécutifs dans la liste (e.g., 13), on prend le sommets commun entre les voisins du premier sommet dans le cycle du deuxième (A et C) et les voisins du premier sommet dans le cycle du troisième (C et D), soit ici C; la face est alors B1C3.

Cette description de la construction des faces marche aussi dans les cas (n pair, m pair)...

Amicalement,

[invite35452583]

Bonjour,

Je vais essayer de reformuler ce que je comprend, plus un soliloque menant nulle part pour le moment...

Pour la reformulation, je confirme que mmy a bien compris (c'est pour rassurer d'éventuels d'autres lecteurs, je suppose que mmy n'a pas beaucoup de doutes ) , pour le soliloque, ça semble intéressant, pas encore tout "digéré". Je ne sais pas si ça va aboutir mais il y a là une voie à explorer (je laisse mmy le faire, j'ai commencé à regarder "ma voie", ça semble pouvoir aboutir mais c'est encore fragile )

Amicalement

[invité576543]

Re-bonjour,

Tout ça me permet de construire à la main une tentative de solution pour le (5, 4) sur le plan projectif plus une anse (caractéristique -1). Ca donne(rait):

1: ABDEC, 2: ABECD; 3: ADCBE; 4: ACBDE

avec les faces qui se déduisent de la liste (chaque paire de lettres apparaît exactement deux fois en succession...)

AB12, AC14, AD23, AE34, BC34, BD14, BE23, CD23, CE12, DE14

Pas très générique, mais ça construit quelque chose...

Dans ce cas, il se trouve que f= C(5,2), ce qui simplifie: chaque paire de lettres doit apparaître exactement deux fois en succession.

Peut-être possible de généraliser aux solutions (m+1, m), caractéristique -(m²-3m-2)/2 ??

Amicalement,

[invite35452583]

1) n et m pairs-> orientable OK, non orientable a priori OK
2) n, m 1 pair 1 impair
impair->c=m+n-mn+(mn)/2=2-(m-2)(n-2)/2
a) le pair est un multiple de 4, on doit en trouver un à mn/2 faces orientable et un orientable
b) le pair n'est pas un multiple de 4, on doit en trouver un non orientable à mn/2 faces et un orientable à mn/2-1 faces (on ne peut compter sur m(n+1) par exemple puis on retire un des (n+1) sommets, la caractéristique est trop grande)
3) n et m impairs
non orientable il en faut un avec (mn-1)/2 faces.
orientable : selon les cas avec (mn-3)/2=(mn-1)/2-1 faces (ex : n= m=5 ou n=5 m=9) ou avec (mn-1)/2 faces (ex : n=5, m=7 ; 2-(5-2)(7-2)/2=-5,5 il faut trouver un graphe pour c=-6)

Oups, le dernier post de mmy m'a fait rendre compte que j'ai oublié le "-2" dans la formule donc les deux cas en rouge doivent être permuttés.

[invite35452583]

AB12, AC14, AD23, AE34, BC34, BD14, BE23, CD23, CE12, DE14

Pas très générique, mais ça construit quelque chose...

Oui et c'est peut-être généralisable.

Amicalement

[invité576543]

Bonjour,

Une nouvelle énigme: un club est fondé par 8 personnes ne se connaissant pas, elles ont pris contact par le réseau (sur FS?).

Les réunions du club se déroulent autour d'une table ronde.

A la première réunion, ils/elles s'assoient au hasard.

A la deuxième, il se trouve que chacun connaît un(e) des ses deux voisin(e)s (ils étaient assis côte à côte lors de la première réunion), mais pas l'autre.

A la troisième, tout le monde connaît ses deux voisin(e)s!

Proposer le plan des 3 tablées...

Ca a évidemment un rapport avec ce qui était discuté dans les messages précédents

Notons que je ne connais pas de solution, mais je cherche!!

Cordialement,

PS: Vu comme ça, ça fait plus ludique que visualiser le plan projectif avec une anse, non?

[invite35452583]

Jolie transformation.

[invité576543]

Après beaucoup de permutations (à la main!), j'ai enfin trouvé une solution
ABCDEFGH, HAGFDEBC, ABEFDCHG

Elle a quelques symétries, mais pas assez pour pointer clairement vers une généralisation...

Y'a peut-être mieux?

Cordialement,

PS: Le suivant au tableau de chasse est (10, 3), même problème avec 10 membres dans le club!

[invité576543]

Pour le (10, 3) ça tourne tout seul... Bizarre... Parce que c'est une solution orientable? (l'est-elle d'ailleurs? ou est-ce la nono?), ou parce que 5 est impair? (j'ai pris l'étoile à 5 branches pour construire le deuxième cycle; le troisième est alors "obligé"!)

Une solution:

ABCDEFGHIJ, ABEFIJCDGH, CBEDGFIHAJ

Le troisième cycle les paires sont dans l'ordre du deuxième, et l'inverse du premier; on peut faire le contraire!

Plus généralement pour un (m, 3) il suffit de trouver un deuxième cycle permettant de construire le troisième.

Parmi les propriétés utiles pour construire à la main (jusqu'à mieux) le deuxième cycle:

- pas de triplets (e.g., ABC ne peut pas être dans le deuxième cycle)

- par conséquence, tout se présente par paire, c'est une permutation de m/2 paires, mais chacune peut être permutée

- (m/2-1)!2^m/2-1 cas à tester, donc, en force brute (384 cas pour m=10, qaund même, mais seulement 24 pour le (6,3), j'ai pas été rapide!)

Amicalement,

[invité576543]

Au passage, les (2m, 3) et les (m, 4) ont la propriété de balayer toutes les caractéristiques. Une solution générique pour une famille ou l'autre permettrait de construire des graphes à faces carrées pour toutes les surfaces!

Doit y avoir moyen de faire quelque chose pour les (2m,3)...

Amicalement,

PS: j'ai du retard pour digérer les messages de homotopie, ça peut amener des redites ou des erreurs pas vues de ma part. En particulier, faut que j'applique le test orientable/non orientable pour la (10, 3), ça devrait être instructif...

[invité576543]

Une méthode qui marche pour les (2m, 3) de m=1 à 4!

Pour m=5, la permutation circulaire ne marche évidemment pas: la solution proposée dans le message d'avant utilise une permutation plus compliquée , mais il y a peut-être moyen de définir une permutation générique. Clairement, les permutations sur 1, 2 ou 3 sont assez limitées, le choix d'une permutation circulaire est obligée!

On construit le deuxième cycle comme suit:

- on démarre par AB,
- on tourne les m/2-1 autres paires d'un cran
- on inverse les m/2-1 paires si m/2-1 est impair

Application

pour le (8, 3)

AB CD EF GH

AB HG DC FE

AH BC FG DE

pour le (6, 3)

AB CD EF

AB EF CD

AF CB ED

pour le (4, 3)

AB CD

AB DC

AD BC

Amicalement,

[invité576543]

Suite de la bidouille pour une solution générique des (2m, 3), toujours pas prouvée mais là ça ne doit pas être trop dur...

Construction du deuxième cycle:

- on garde AB
- on permute les autres paires!

Simple non? Pourquoi ne pas l'avoir trouvé plutôt, ça c'est la bonne question!

Quelques exemples

AB CD EF GH IJ KL MN OP
AB DC FE HG JI LK NM PO
AP ML IH ED BC FG JK NO

AB CD EF
AB DC FE
AF CB DE

AB CD EF GH
AB DC FE HG
AH ED BC FG

AB CD EF GH IJ
AB DC FE HG JI
AJ GF CB DE HI

Comme c'est toujours la même chose, ça a des chances de donner la non-orientable... A vérifier!

Pour la (6,3) c'est bien la non-o qu'on obtient ainsi...

Cordialement,

[invite35452583]

Ca doit recoller avec ma "bidouille" pour ajouter un sommet n+1 au cas m et n pairs :
familles notées :
une i, ii, iii, ... (indice miniscule qui ne sont pas des chiffres romains, tant pis pour le i, les lettres de l'alphabet un peu limitées au bout d'un moment)
l'autre 1,2... (indice majuscule)
faces : k impair pour chaque :
a) k J k+1 J+1 avec J impair, J distinct de 1 et de n+1
b) k J k+1 J-1 avec J pair
c) k n+1 k+1 2
d) k 1 f(k) n+1
f {impairs}->>{pairs} (bijectif)
Il faudrait faire attention au sens mais on a :
$ Autour de k impair : 1(n+1)234...n (par construction)
$ Autour de k pair : idem (car f surjectif)
$ autour de J (J distincts de 1 et de n+1) : i,ii,iii... (inchangé par rapport au cas n-m)
$ Autour de 1 (k impair) on a des bouts k-1 k f(k)
$ Autour de n+1 (k impair) on a des bouts k+1 k f(k)

Peut-on trouver f telle que on est un unique cycle autour de 1 et de n+1. Réponse partielle (mais ce n'est pas inintéressant) : oui si m est congru à 2 modulo 4.
f(k)=k+3
$ autour de n+1 : k+1 k k+3, on voit facilement qu'on va de pair en pair k+1 k+3 éloignés de 2 (donc on les aura tous) et l'impair k décrira donc lui aussi tous les impairs.
$ autour de 1 : k-1 k k+3, on va de 4 en 4 et on se rend compte que si m est multiple de 4 on ne fait pas un cycle, par contre k-1 k+3 décrit les pairs en un seul ccle (et donc k décrit tous les impairs pendant ce cycle). La différence entre les deux cas est, ici, très visible. (pas encore vérifié si mon "truc" est orienté ou pas)
Pour m multiple de 4, f n'existe ni pour m=4, ni pour m=8 (c'est indépenadnt de la valeur de n). Pour trouver pour ce cas, ici, j'ai placé n+1 toujours entre 1 et 2 et changeant le 4ème sommet de k 1 .. n+1, je pense qu'en mixant (et profitant que m multiple de 4 !) et en changeant le 4ème sommet de k n+1 .. 2 ça devrait aboutir.

Amicalement

[invite35452583]

Suite de la bidouille pour une solution générique des (2m, 3), toujours pas prouvée mais là ça ne doit pas être trop dur...

Construction du deuxième cycle:

- on garde AB
- on permute les autres paires!

Simple non? Pourquoi ne pas l'avoir trouvé plutôt, ça c'est la bonne question!

Quelques exemples

AB CD EF GH IJ KL MN OP
AB DC FE HG JI LK NM PO
AP ML IH ED BC FG JK NO

AB CD EF
AB DC FE
AF CB DE

AB CD EF GH
AB DC FE HG
AH ED BC FG

AB CD EF GH IJ
AB DC FE HG JI
AJ GF CB DE HI

Comme c'est toujours la même chose, ça a des chances de donner la non-orientable... A vérifier!

Pour la (6,3) c'est bien la non-o qu'on obtient ainsi...

Cordialement,

Pas encore tout compris mais je regarde ça à tête reposée.

[invite35452583]

$ Autour de 1 (k impair) on a des bouts k-1 k f(k)
$ Autour de n+1 (k impair) on a des bouts k+1 k f(k)

Peut-on trouver f telle que on est un unique cycle autour de 1 et de n+1. Réponse partielle (mais ce n'est pas inintéressant) : oui si m est congru à 2 modulo 4.
f(k)=k+3
$ autour de n+1 : k+1 k k+3, on voit facilement qu'on va de pair en pair k+1 k+3 éloignés de 2 (donc on les aura tous) et l'impair k décrira donc lui aussi tous les impairs.
$ autour de 1 : k-1 k k+3, on va de 4 en 4 et on se rend compte que si m est multiple de 4 on ne fait pas un cycle, par contre k-1 k+3 décrit les pairs en un seul ccle (et donc k décrit tous les impairs pendant ce cycle).

Des petits exemples ne feront pas de mal
m=6
autour de n+1 : 2 1 4 3 6 5
autour de 1 : 2 3 6 1 4 5
m=10
n+1 : 2 1 4 3 6 5 8 7 10 9
1 : 2 3 6 5 10 1 4 5 8 9

Cordialement

[invité576543]

Bonjour,

Effectivement, il y a eu quelques ellipses dans mes messages...

Limitons nous aux cas m pair ou n pair, et m>n.

On cherche à construire une solution à mn/2 faces carrées, où chaque arête appartient à exactement deux faces.

On rajoute la contrainte suivante : pour tout doubleton {a, b} de faces de type m, il y au maximum une face contenant a et b.

Il n'y a pas de contradiction combinatoire puisque m>n implique que mn/2 <= m(m-1)/2.

Le nombre de faces étant nm/2 et chaque doubleton donnant une face apparaissant exactement deux fois dans l'ensemble des cycles (face unique pour un doubleton), on a alors exactement m doubletons donnant une face par cycle. Autrement dit, comme il y a exactement m doubletons de sommets contigus dans un cycle, tous correspondent à une face.

Alors une solution est entièrement décrite par les n cycles des sommets de type m autour des sommets de type n. En effet, on peut construire les faces comme suit (en notant a, b les sommets de type m, et i, j les sommets de type n):

- on prend deux sommets consécutifs a et b dans le cycle d'un sommet i
- on cherche dans les autres cycles le cycle j unique où a et b sont contigus
- cela donne la face (a, i, b, j)

En fait, une solution est entièrement donnée par n-1 cycles seulement. En effet, on peut construire le dernier en listant tous les doubletons manquants, et en les mettant dans l'ordre. Si cela ne donne pas un cycle unique, les n-1 cycles ne forment pas une solution.

A partir des faces, on peut construire les cycles autour des sommets de type m, et vérifier que l'on a bien des cycles de longueur n.

Résumons l'algorithme général de construction de solutions potentielles.

- On donne n-1 permutations cycliques des m sommets sous contrainte que chaque doubleton (a, b) de sommets apparaît au minimum une fois et au maximum deux fois en contiguïté dans l'ensemble des n-1 cycles
- On en dérive l'unique n-ième permutation à partir des doubletons manquants, de manière à ce que chaque doubleton apparaisse exactement deux fois en contiguïté dans les n permutation;
- Si la permutation obtenue n'est pas cyclique, la solution potentielle est rejetée
- On dérive des données les m permutations de n sommets
- Si toutes les permutations sont cycliques, on a obtenu une solution

Dans le cas particulier de n=3, la vérification des cycles de longueur n=3 est inutile. En effet les cycles sont de longueur 1, 2 ou 3. Un cycle de longueur 1 est impossible, puisque chaque arête doit appartenir à deux faces, donc chaque sommet à au moins 2 faces. Mais alors un cycle de longueur 2 est impossible, puisque cela donnerait une décomposition (2, 1). La seule possibilité est un cycle de longueur 3, inutile de vérifier.

Dans le cas (m pair, 3) on va encore se restreindre, aux cas où le nombre de doubletons communs entre deux cycles est exactement de m/2. (C'est peut-être une restriction imposée par le problème, à vérifier.)

Alors, pour construire une solution (2m, 3), un premier cycle est choisi arbitrairement, il sert pour choisir l'indexation des m sommets. Il ne manque alors pour une solution potentielle que le deuxième cycle.

On peut montrer qu'il ne peut pas y avoir de triplet commun entre deux cycles. En effet, cela correspondrait à un cycle de longueur 2 dans la permutation correspondant au sommet médian. Par conséquence le deuxième cycle se construit comme une permutation de paires successives, avec éventuellement une inversion dans la paire.

Prenons le cas simple m=6. Le premier cycle est noté ABCDEF. Les seules possibilités pour le deuxième sont (on se limite à AB comme première paire sans perte de généralité)

AB CD EF, AB DC EF, AB DC FE, AB CD FE
AB FE CD, AB EF CD, AB EF DC, AB FE DC

Certaines sont éliminées parce qu'elles contiennent des successions communes autres que celles des paires, en contradiction avec la contrainte de m/2 doubletons en commun, qui sont ceux des paires. Il ne reste que quatre cas:

AB DC FE, AB FE CD, AB EF CD et AB EF DC

La construction du troisième cycle donne

AB DC FE -> paires manquantes = (BC, DE, FA) et (BD, CF, EA)
d'où le cycle AEDBCF, c'est une solution

AB FE CD -> paires manquantes = (BC, DE, FA) et (BF, EC, DA)
d'où ADECBF, c'est une solution

AB EF CD -> paires manquantes = (BC, DE, FA) et (BE, FC, DA)
d'où le cycle ADEBCF, c'est une solution

AB EF DC -> paires manquantes = (BC, DE, FA) et (BE, FD, CA)
d'où ACBEDF, c'est une solution

Notons que la seule non orientable est AB EF CD, ce qui laisse penser que toute inversion de paire ne peut donner qu'une solution non orientable, à vérifier.

Une construction générique qui semble toujours donner une solution est l'équivalent du premier cas: les paires restent en place, et toutes sont permutées sauf la première. Ce serait une solution non orientable.

La caractéristique est paire si m n'est pas un multiple de 4. On faut alors trouver une permutation des m/2 paires telle que deux paires successives dans le premier cycle ne le soient pas dans le second, à l'image de AB EF CD. Il y a toujours des possibilités, genre x -> kx [m/2], avec x un numéro de paire et k>1, k premier avec m/2. Reste à vérifier les cas donnant une solution.

Cordialement,

[invite35452583]

Bonjour,
Ce qui précède est très intéressant.
Je parle de "ma" voie car l'"espoir" vient certainement de ce qui précède. En fait, je cherchais à définir autour des sommets de type m (m pair) ça marche pour m=2(4) mais ça bloque pour m multiple de 4 (j'ai pourtant emprunté 4 ou 5 voies. J'allais cherché autour des sommets type n quand je me suis rappelé que c'est ce que faisait mmy en fait dans le cas n=3, j'ai alors repris et j'ai mieux compris l'idée.
En tout cas, pour le cas m multiple de 4, n impair il vaut mieux de fait chercher autour des sommets type n. Et, il semble que mmy est sur une voie d'une solution générique (le cas n=3 est résolu déjà, d'accord c'est le plus simple pour les raisons données par mmy lui-même : autour des sommets de type m les 3-cycles sont "naturellement" présents)

Dans le cas (m pair, 3) on va encore se restreindre, aux cas où le nombre de doubletons communs entre deux cycles est exactement de m/2. (C'est peut-être une restriction imposée par le problème, à vérifier.)

Je n'arrive pas à écrire une preuve mais j'en suis persuadé.

Cordialement

[invite35452583]

Je finis mon idée. Je pense que ma voie va donner une solution générique pour les orientés (pas encore vérifié mais j'ai de l'espoir et j'ai une idée pour le cas m multiple de 4, je pense pouvoir colmater si j'ai le droit d'"abandonner" une face ce qui est le cas pour le cas orienté). Par contre l'idée de mmy (permutation dune paire me semble prometteuse mais en non orientable, une surface orientée pourrait également apparaître pour m pair non multiple de 4 mais réparer la non orientabilité du cas m multiple de 4 en "abanadonnant" une face ça risque d'être dur.)
Les deux voies me semblent complémentaires pour l'instant.

[invite35452583]

Suite des explorations :
ma solution pour m pair "non quadruple" est orintée.
Redéfinition des faces car je ne m'y retrouve plus :
A type en quantité paire
B type en quantité impaire
Aimpair Bk Apair Bk+1 pair=impair+1 ou impair-1 ou impair +3 selon les cas (cf post le définissant)
Le sens est donné par : Aimpair Bk Apair Bk+1
Comme autour de Aimpair on tourne k-k+1 pas de problème de compatibilité sur les arêtes AimpairB
A pair, on a :
Aimpair----Bk----Aimpair'
l l l
l l l
B'--------Apair----B"
On a B' et B" = B(k+1) ou B(k-1) mais sont distincts donc les deux sens sur l'arête ApairBk sont opposés et les deux orientations choisies pour les deux faces sont compatibles.
Donc en orientés :
n et m pair OK
n pair non quadruple et m impair OK
en non orienté (a priori) 3 et pair (il faut que je reprenne le cas n et m pairs , ma soluce est fausse et en plsu trivialement, je ne découpe que plusieurs disques )
Pour le cas orienté, il ne reste ""que"" des cas pour lesquels on est "soulagé" d'une "demi", d'une ou d'"une et demi" face(s).

[invite35452583]

Salut,
cas n impair m multiple de 4 surface orientée cas réglé .
On éteint les ceintures, on boucle les cigarettes, on décolle ( ) :
on part du graphe que j'ai donné pour ce cas.
Je donne un exemple histoire que ce soit moins acrobatique
Autour de 1 : a(4)b(2)c(8)d(2)e(8)a entre parenthèses le sommet qui finit la face
autour de 3 : a(6)b(4)c(2)d(4)e(2)a
autour de 5 : a(8)b(6)c(4)d(6)e(4)a
autour de 7 : a(2)b(8)c(6)d(8)e(6)a

Autour des pairs on a de même abcde : on peut vérifier sur ce cas mais la raison est la même que précédemment entre deux sommets consécutifs de ce cycle le sommet pair est défini de telle manière que c'est surjectif et injectif chez ceux-ci.
De même on peut orienter de manière cohérente toutes les faces (le passage par les arêtes se fait de la même façon que pour le cas m non multiple de 4)
Le problème est ailleurs :
autour de b : 2143658721 ça tourne (pas comme les autres on va le voir mais ça tourne)
autour de c,d et e : 23456781 OK
L'unique problème est autour de a :
2 m/2-cycles : 4185 et 2763 ici en l'occurence.
Notre espace (ce n'est pas encore une surface) a un seul défaut : deux nappes viennent se coller en le sommet A.
On a deux ensembles de faces qui font un disque autour de a : (a5e4 + a4b1 + a1e8 + a8b5) et (a2e3) + (a3b6) + (a6e7) +(a7b2)
Et donc deux composantes dans la frontière 1e8b5e4b et 2e3b6e7b2, celles-ci peuvent être orientées de manière cohérente avec le reste de l'espace (qui est une surface orientable à 2 bords si on retire les 2m faces autour de a). On ne touchera pas à la frontière ce qui permettra de faire notre opération uniquement avec nos deux disques collés (et en plus cette frontière est déjà un beau sac de noeuds comme cela, normal on construit un espace très contorsionné avec bien peu de cellules)

La réparation :
on prend une face de chaque nappe (disons a4b1 et a6e7) quand on tourne autour de a avec l'orientation choisie on va de 4 vers 1 et de 6 vers 7 (si je ne me suis pas trompé, l'essentiel est que on choississe la même orientation que le reste de la surface)
On fait un trou aa'a" dans les deux faces on a 4->a'->a"->1 et 6->a"->a'->7 le recollage se fait selon les lettres des sommets. Les nouvelles faces sont : a4a', 4b1a"a', aa"1, a6a", 6e7a'a", aa'7 (ils sont écrits avec l'orientation initiale on peut vérifier que tout va bien aux au passge dees arêtes)
Autour de a désormais on a : 1854a'7236a"1 on a désormais deux feuillets d'un même disque, le point a est régulier topologiquement.
Autour de a' : a4a"7a
Autour de a" : a6a'1a
a' et a" sont réguliers aussi.
La réparation est réussie et on a gardé un espace orienté mais cette fois c'est une surface.
Caractéristique, regardons la différence :
faces : 6 en plus mais 2 supprimées bilan : +4
arêtes : aa', aa", a'a", 4a', 1a", 6a", 7a' : +7
sommets : +2
Total : 4-7+2=-1, on a bien diminuer d'une unité la caractéristique, on a bien ce qu'on voulait.

[invité576543]

Bonjour,

Je continue mes explorations dans mon coin, toujours dans le mode "laborieux", en attendant qu'une régularité se manifeste...

Le cas suivant est (2m', 5). On peut jouer au même jeu qu'avec n=3, à savoir interdire les triplets communs en cycles de lettres, ce qui interdits ipso facto les cycles de 2 dans les permutations de chiffres. Du coup les cycles d'ordre 3 et 4 sont aussi interdits, puisque cela impliquerait au moins un cycle de longueur 1 ou 2. n=5 est le dernier nombre avec lequel on pourra jouer à cela, profitons-en.

Même raison, même résultat, entre deux cycles de lettres ayant au moins un doubleton commun, c'est une permutation de paires.

Fort de cela, en bidouillant un peu on trouve une solution pour le (6,5), a priori nono.

En partant de ABCDEF, il y a deux découpages en paires: AB CD EF, et BC DE FA. On va simplement prendre les deux et utiliser la même transformation que vu pour le (2m', 3) à savoir l'inversion de toutes les paires sauf une. D'où

1: AB CD EF
2: AB DC FE
5: BC ED AF

En rejouant le coup sur les deux nouveaux cycles, le miracle se produit

3: BD FC AE
4: EB FD AC

(Attention il y le choix à chaque fois de la paire non inversée, donc quelques essais et erreurs...)

Le choix de numérotation étant l'ordre tel que chaque cycle est la transformée du suivant, on trouve comme cycles de chiffre l'unique 12345 (pas vraiment étonnant à regarder de plus près).

Fort de ce résultat, j'ai essayé le (8, 5). Mais je ne trouve rien. En fait on obtient un (8,4) nono!

Ce qui est marrant, c'est qu'en même temps homotopie donne une solution pour le (8, 5) (plus tous les (4m', 2n'+1) orientés...).

Faudrait que je regarde (10, 5) avec mes bidouilles (pas vraiment des méthodes, il y a des degrés de liberté patchés à la main)...

Cordialement,

[invite35452583]

Salut,

cas n impair m multiple de 4 cas non orienté

Cette fois on coupe le longe de ab sur les deux disques collés en a. (disons a4b1 et a7b2) nouvelles faces a4ba' ; aa"b1 ; a7a'2 ; aa"b2 (Cette fois a' et a" sont dans le même sens pour les deux disques) on recolle selon aa'b et aa"b.
Pourquoi cette fois coller dans ce sens (car la perturbation du cycle de b le nécessite sinon b devient singulier, vérification aisée)
Ainsi la perturbation du sommet b laisse b régulier. La perturbation est une réparation du sommet a. Cette réparation est "anti-orientable", si on met les deux disques l'un au-dessus avec la même "orientation haut/bas" le petit coup de "chirurgie" pratiquée envoie le haut de l'un sur le bas de l'autre et inversement (mais ce haut-bas vient du reste de la surface, on pourra construire un ruban de Moëbius)
On pourrait le définir uniquement avec les faces mais cette "vision" m'a paru intéressante et c'est celle qui m'a fait aboutir.

Cordialement

[invité576543]

Sinon, j'essaye en parallèle de maintenir un résumé, avec mes notations (plus simple pour moi). Mais je n'ai pas encore fini de comprendre la méthode (2m'+2, 2n') --> (2m'+2, 2n'+1)! Du coup retard pour comprendre (4m', 2n') --> (4m', 2n'+1)

Amicalement,

EDIT:Croisement