Fred
18 est un multiple de 3...
Zebulor
Bonjour,
@Roro : j ai l’impression que toi et moi avons comptabilisé des trajets où les maisons paires et impaires se font face..
Bernard-maths
Re-re-re !
Oui ! C'est 18, j'avais mal placé un numéro sur une branche ...
Merci Fred, c'était bien amusant !
B-m
Roro
Fred a écrit18 est un multiple de 3...
Certes, mais 70 ne l'est pas trop !
LEG a écritBonjour
--70--
Je suis vraiment perdu...
Invite
Message de Glozi (sans compte)
Bonjour,
Merci pour l'énigme
On traite directement le cas où on à $2n$ maisons, $n$ maisons du côté droit et $n$ maison du côté gauche.
On numérote les maisons de gauche $1,2,\dots,n$ et les maisons de droite $1',2',3',\dots,n'$ (je m’affranchis donc de la numérotation un peu pénible pair/impair).
On suppose que le facteur part de la maison $1$, il va effectuer un trajet de la forme $1\to x'\to a\to y'\to b\to z'\to c\to \dots$
De ce chemin on ne retient pour le moment que les maisons du côté gauche : $1$ puis $a$ puis $b$ puis $c$ etc... On se rend compte qu'il y a $(n-1)!$ possibilités pour l'ordre des visites des maisons de gauche. Une fois cet ordre fixé (et sans restriction de généralité quitte à renuméroter les maisons on suppose que l'ordre est fixé 1 puis 2 puis 3 etc...), il faut décider comment intercaler une maison de droite entre deux maisons de gauche de sorte à respecter la consigne.
Autrement dit on cherche $\sigma : \{1,\dots,n\}\to \{1,\dots,n\}$ tel que $\sigma(i)'$ représente la maison de droite à intercaler entre $i$ et $i+1$.
Le chemin final du facteur sera donc :
$1 \to \sigma(1)' \to 2 \to \sigma(2)'\to 3\to \dots, \to n \to \sigma(n)'$.
On impose donc que $\sigma$ soit une bijection et que $\forall i\in \{1,\dots,n\}, \sigma(i) \not\in \{i,i+1\}$.
Je note $D_n$ l'ensemble de ces permutations. Il s'agit donc de calculer le cardinal de $D_n$ et le résultat final du nombre de chemins pour le facteur sera $(n-1)!D(n)$.
Pour $n=4$ on peut calculer "à la main" $D_n=3$ et donc il y a $3(4-1)!=3\times 6=18$ chemins possibles.
De manière générale j'ai cherché une relation de récurrence sur $D_n$ mais je n'ai rien trouvé de simple...
En calculant avec python les premiers termes de $D_n$ j'ai trouvé la suite suivante sur OEIS https://oeis.org/A000271
On a $D_1=0,D_2=0,D_3=1,D_4=3,D_5=16,D_6=96,D_7=675,D_8=5413,D_9=48800,\dots$
Apparemment il y a la relation de récurrence suivante qui est vérifiée pour $n\geq 4$ :
$$D_n = (n-1)(D_{n-1}+D_{n-2})+D_{n-3}.$$
mais je n'ai pas trouvé d'interprétation combinatoire de cette formule...
Voilà où j'en suis.
Bonne journée
Zebulor
Bonjour,
on pourrait se demander quel est le chemin le plus court, de sorte à faire installer des passages piétons "obliques" pour le facteur.
Intéressante énigme...
Fred
@Glozi : Bravo ! C'est aussi comme cela que j'ai raisonné sans aller jusqu'au cas général !
Invite
Message de Glozi (sans compte)
Je ne suis pas sûr de comprendre ta question Zebulor ?
Si tu parles de la dernière ligne pour $i=n$ on demande quand même que $\sigma(n)!=n$ (sinon le facteur irait de $n$ à $n'$). Cette condition est bien équivalente à $\sigma(n)\not\in \{n,n+1\}$ puisque $n+1$ ne sera de toute façon pas une valeur de la permutation.
Invite
Message de Glozi (sans compte)
Oups j'avais cru voir un message de Zebulor mais il n'est plus là, j'ai dû halluciner :p
Zebulor
Non Glozi tu n’as pas halluciné :-). Je me suis aperçu que ce Que tu avais écrit était bon.
Je voulais raisonner avec des bijections mais tu es passé par là...c’est le $D_n$ qui m'échappe. Clap clap !!
Invite
Message de Glozi (sans compte)
Ça me rassure !
L'idée de $D_n$ c'est de dire qu'après chaque maison de gauche $i$ on doit visiter une maison de droite qu'on appelle $\sigma(i)'$. Alors il est clair que $\sigma$ est une application de $\{1,\dots,n\}$ dans $\{1,\dots,n\}$. De plus $\sigma$ est forcément bijective. En effet, le facteur ne visite jamais deux fois la même maison de droite et il visite au moins une fois chaque maison de droite.
Après la maison de gauche $i$ le facteur va à la maison de droite $\sigma(i)'$ puis il revient à gauche pour livrer le courrier de la maison $i+1$. Ainsi pour respecter la consigne il faut que $i\neq \sigma(i)$ (puisque le facteur traverse de $i$ vers $\sigma(i)'$) et aussi que $i+1\neq \sigma(i)$ (puisque le facteur traverse de $\sigma(i)'$ vers $i+1$).
Comme dit précédemment, il faut avoir en tête que le trajet du facteur sera $1\to \sigma(1)' \to 2 \to \sigma(2)'\to \dots \to n-1 \to \sigma(n-1)' \to n \to \sigma(n)'$.
On note $\mathcal{D}_n := \{\sigma\in \mathfrak{S}_n\ |\ \forall i\in \{1,\dots,n\},\ \sigma(i) \not\in \{i,i+1\}\}$ et $D_n = \sharp \mathcal{D}_n$ (dans mon précédent post j'avais noté indifféremment $D_n$ et $\mathcal{D}_n$).
Maintenant $\mathcal{D}_n$ est un ensemble "assez moche" de permutations et $D_n$ n'est a priori pas facile à calculer.
En fait, ce problème a été étudié cet est connu comme le problème des ménages https://en.wikipedia.org/wiki/M%C3%A9nage_problem
Il y a une version "circulaire" où on demande en plus $\sigma(n)\not\in \{1,n\}$ et la version en "ligne droite" qui est celle de notre $\mathcal{D}_n$.
On a dans la littérature une formule close pour $D_n$ :
$$D_n = \sum_{k=0}^n (-1)^k{2n-k\choose k}(n-k)!$$
Finalement le nombre de trajets pour le facteur est :
$$(n-1)!D_n = (n-1)!\sum_{k=0}^n(-1)^k{2n-k\choose k}(n-k)!.$$
(ça vaut bien 18 pour $n=4$)
Bonne journée
Zebulor
ok merci :-)
Roro
Bonsoir,
J'ai finalement trouvé 18 aussi... j'avais juste pas écrit sur une feuille les différentes combinaisons (que j'avais fait à la main pour 8 maisons).
Pour le cas général, je n'avais pas osé me creuser la tête !
Bravo.
Roro.
bridgslam
Bonjour,
On peut s'aider de graphes. Je reformule donc sous forme de conte oriental la question.
Il était une fois 4 princes et 4 princesses, les hommes (H) habitant tous d'un côté de la rue, les femmes (F) de l'autre.
Chaque prince a une préférée ( qui pour être le plus proche possible, habite juste en face de lui , le prince n°1 a sa promise au n°2 etc...).
Un beau jour, tout ce beau monde décide d'un banquet autour d'une table ronde, en alternant les H et les F.
Le plat de couscous est servi à un H (n°1) qui passera le plat sur sa droite et ainsi de suite (toujours dans le même sens) .
Le plat va donc d'H en F alternativement à chaque mouvement.
On recherche les dispositions alternées H-F autour de la table de façon qu' aux 7 passages de plat au voisin(e), personne ne le passe son conjoint(e).
Si on trace un trait pour une disposition entre chaque prince et sa princesse, il faut et il suffit qu'aucun trait ne joigne deux personnes voisines, sauf éventuellement
entre n°1 et la femme sur sa gauche ( puisqu'il n'y a plus de passage de plat, le tour étant terminé ).
On tombe sur 3 graphes possibles ( chaqu'un pouvant permuter sur les princes de 3! manières donc ideme sur leurs princesses reliées au trait):
premier graphe où n°1 a sa promise sur sa gauche: on trace ce trait, puis 3 autres, à permutation près 6 configurations.
second et troisième graphe , où chaque trait va vers quelqu'un de sexe opposé, sa promise en visant presque en face ( 2 types possibles) d'un sommet d'un octogone à un autre, et encore à 3! possibilité de permutation pour chaque graphe (sur les princes donc idem les princesses reliées).
En tout cela fait bien 3! + 2.3! = 18 possibilités.
Pas trop à l'aise avec les dessins mais c'est très clair sur papier... et sans doute plus facile et même immédiat à piger...
[ j'ai oublié de dire que le plat était l'équivalent du courrier, le passage au voisin au changement de côté de rue etc , les deux questions sont strictement
équivalentes ].
Apporter le courrier est donc festif puisque cela revient à faire le tour des popotes :-) !!
Alain
bridgslam
Un tracé vite fait pour un des deux graphes du second type:
https://www.cjoint.com/c/MKro2D1rVp4
un a un autre type voisin où la promise du n°1 est encore en face mais vers la gauche.
Puis un dernier type où sa promise finira avec le tour de table en étant sur sa gauche.
Bonne soirée
Alain
Zebulor
Bonsoir,
intéressant. Merci Alain
Bonne soirée.
bridgslam
Bonsoir,
De rien.
Si j'ai un peu de temps ce soir je ferai les 3 types de graphes en schémas puis généraliserai la formule à 2n maisons/convives , pas impossible à faire,
avec la même idée de tour de table :-). Il y a juste un peu plus de graphes, pas compliqué.
Celui où le n°1 a sa femme sur sa gauche (si on passe le plat à droite) est toujours à part, à ne pas oublier de toute façon.
Des récurrences par types de graphes sont aussi possibles.
La difficulté sur les graphes quand on cherche un problème équivalent, c'est d'oublier l'aspect spatial du problème initial.
A la table, le conjoint "à éviter" est généralement assez loin, tandis qu'il est juste à côté (en face) dans la course du facteur...
Mais j'aime bien dès qu'il s'agit de parcours complet dans un problème à tout mettre à plat sur un cercle.
Bonne soirée
A
bridgslam
Bonsoir,
Et ça augmente vite ! : avec deux fois 5 maisons ( ou 5 princes et leur princesse dans le pb équivalent, ça fait 11. 4! = 264 dispositions autour de la table (ou trajets si on en revient au facteur et son courrier ).
Le graphe en cercle montre de toute façon qu'avec 2n ( n au moins égal à 3) maisons, le nombre de trajets est toujours un multiple de (n-1)!
Résumé: avec 6 maisons (ou 3 princes et 3 princesses au banquet ...) : 2 = 1.2! solutions
8 maisons : 18 = 3.3! solutions
10 maisons : 264 = 11.4! solutions [ 16.4! = 384 en réalité voir ci-dessous ]
.....
Sauf erreur avec 10 maisons le décompte des graphes compatibles en cercle trigonométrique ( 1 arête = 1 couple ) se décompose comme suit:
- 3 graphes où le n°1 a sa femme immédiatement à sa gauche (une fois eu le plateau, elle n'a plus rien à faire, le tour étant terminé)
- 5 graphes où seul un homme a sa femme à l'opposé à la table (pas fait pour rapprocher les coeurs pour ces deux-là!!)
- 1 graphes où tous les hommes ont leur femme à l'opposé de la table ( encore pire....)
- 2 graphes en "pentagone" où chaque homme a sa femme 3 places plus loin.
[ - 5 graphes avec 3 couples successifs en // et deux croisés oubliés ]
Pour chaque graphe, le n°1 servant de pivot aux dispositions, on doit multiplier par les 4! permutations sur les autres hommes.
J'espère ne pas en avoir oublié, mais l'intérêt de ces graphes réguliers de degré 1 disposés en cercle permet des visions plus géométriques que celui vissé aux trajets du facteur, assez fouillis.
Le choix de tourner le plat dans le sens trigonométrique est arbitraire, mais dans le sens horaire, le n°1 peut seulement avoir sa femme sur sa droite.
Les graphes étant jolis je les dessinerai peut-être demain (geogebra ? ) pour n = 4 et n =5...
Il semble difficile de trouver une loi générale pour le coefficient en facteur de (n-1)! : 1, 3, 11 [16] , ... ça se complique vraiment, ou je suis à cours d'inspiration...
[noter que Glozi indique un facteur 16 au lieu de 11 pour n=5, j'ai peut-être oublié des graphes (5 ?) dans la bataille... pas impossible ]
.....
Il y en a bien 5 autres évidents , avec 3 couples en parallèles successifs côté graphe circulaire et deux croisés.
Je confirme donc le coefficients 16 et la bonne valeur est donc 16.24=384 pour 10 maisons.
Bravo Glozi.
L' approche avec l'appui des graphes peut peut-être s'automatiser , en tout cas servir à construire explicitement toutes les solutions.
Alain
bridgslam
Bonjour,
voici un des 5 graphes oubliés, le trajet du facteur se lit en tournant dans le sens trigo en partant de H1: 1-8-3-2-5-10-7-4-9-6
https://www.cjoint.com/c/MKsi6H7dxW4
Le graphe unique de type "bourreau des coeurs" :
https://www.cjoint.com/c/MKsi4KhKMI4 : 1-8-3-10-5-2-7-4-9-6
Alain
bridgslam
Bonjour,
Enfin, pour le fun , un des 3 types de graphes où c'est sa conjointe qui termine le tour, donc placée à sa gauche...
https://www.cjoint.com/c/MKsjGwKz5b4 : trajet 1-10-3-8-5-4-7-6-9-2
et un des deux types pentagones :
https://www.cjoint.com/c/MKsjY7wJkl4 : trajet 1-10-3-2-5-4-7-6-9-8
La surprise en regardant les mails précédents et notamment le dernier de Glozi, c'est que le problème des ménages ( celui en ligne, donc sans contrainte sur la fin de table ) (Lucas, Touchard..) se ramène à des plans de table.
Il y a apparemment un lien avec la théorie des noeuds, ce qui n'est pas trop étonnant, vu les questions de croisements multiples (ou non)
Bonne journée
A.