Forum de mathématiques - Bibm@th.net

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

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...

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 220

Re : Le facteur

@Glozi : Bravo ! C'est aussi comme cela que j'ai raisonné sans aller jusqu'au cas général !

Glozi

Invité

Re : Le facteur

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.

Glozi

Invité

Re : Le facteur

Oups j'avais cru voir un message de Zebulor mais il n'est plus là, j'ai dû halluciner :p

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

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 !!

Dernière modification par Zebulor (20-10-2023 17:03:41)

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Glozi

Invité

Re : Le facteur

Ça me rassure !

▼quelques précisions

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

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

ok merci :-)

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 659

Re : Le facteur

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

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

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

Dernière modification par bridgslam (17-11-2023 17:05:37)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

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

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

Bonsoir,
intéressant. Merci Alain

Bonne soirée.

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

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

Dernière modification par bridgslam (17-11-2023 18:09:09)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

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

Dernière modification par bridgslam (18-11-2023 11:36:36)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

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

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

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.

Dernière modification par bridgslam (18-11-2023 15:30:02)

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

Bonjour,

Enfin pour rester sur des questions très voisines, en nettement plus facile ( mais demandant néanmoins un peu d'attention...)

On doit placer autour d’une table ronde un groupe de 2n personnes, n hommes et n femmes, qui constituent n
couples. Combien existe-t-il de dispositions . . .
1. au total ?
2. en respectant l’alternance des sexes ?
3. sans séparer les couples ?
4. en remplissant les deux conditions précédentes

Bonne recherche

A.

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

Hello,
Ça me demande pas mal d attention...

▼Idée

1. Je suppose que les distances entre les personnes sont identiques. Toute rotation de centre le centre de la table et d angle multiple de $\dfrac {\pi}{n}$ laisse inchangée une disposition. Or il y a $2n$ Rotations  principales qui laissent inchangée une disposition, dont celle où chacun fait un tour complet.
Pour la 1, je dirais donc  (2n-1)!
Pour les autres réponses, je verrai ça plus tard...c est dimanché’ :-)

Dernière modification par Zebulor (19-11-2023 16:57:51)

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Dalal

Membre

Inscription : 14-09-2023

Messages : 57

Re : Le facteur

Bonjour,

J'ai encore quelques doutes. Sans regarder la réponse de Zebulor je trouve :

▼proposition

Je trouve :
1)2n!
2)2(n!)^2
3)2^(n+1)*n!
4)4*n!

Bonne journée.

Dernière modification par Dalal (19-11-2023 11:26:01)

Dalal

Membre

Inscription : 14-09-2023

Messages : 57

Re : Le facteur

▼@Zebulor

Pour la première question je n'ai pas trouver la même réponse que toi je me suis dis que la première personne qui s’assoit peut choisir parmi 2n sièges libres, la deuxième en a donc (2n−1)ainsi de suite jusque la dernière qui n’a plus qu’une seule place pour s’assoir. D'où ma réponse 2n!

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

Re,

▼@Dalaï

j ai raisonné comme toi au départ, mais je ne dénombre pas les dispositions où les placements des $2n$ personnes les unes par rapport aux autres  sont les mêmes : par exemple si chacun prend la place de son voisin de gauche...

Dernière modification par Zebulor (19-11-2023 20:52:05)

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Dalal

Membre

Inscription : 14-09-2023

Messages : 57

Re : Le facteur

Re,

▼@Zebulor

Ne t'inquiète pas Zebulor je n'avais pas très bien compris à la première lecture de ton raisonnement mais maintenant c'est clair. Merci:).
Par contre une petite faute à mon prénom c'est Dalal et non Dalaï

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

Re,
Dalal : oui pardon. C est la presbytie .. :-). J’ai essayé de clarifier le post en question..

Dernière modification par Zebulor (19-11-2023 16:58:37)

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

Dalal

Membre

Inscription : 14-09-2023

Messages : 57

Re : Le facteur

Re,
Ce n'est pas grave :)

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 160

Re : Le facteur

Re,
BIen que ce soit dimanche ...

▼Lasuite

Q2 : $[(n-1)!]^2$
Q3 : $2^n (n-1)!$
Q4: $(n-1)!$

Dernière modification par Zebulor (19-11-2023 20:46:31)

---

En matière d'intégrales impropres les intégrales les plus sales sont les plus instructives.

bridgslam

Membre

Lieu : Rospez

Inscription : 22-11-2011

Messages : 1 496

Re : Le facteur

Bonsoir,

Pour la première, les places ont de l'importance ( être plus près de la fenêtre ou de la cheminée etc...), il ne s'agit pas de dispositions relatives... donc pas besoin de se compliquer la vie.
La suite demain car il est tard. Merci pour l' intérêt suscité.
Bonne nuit.

A.

---

"Ceux qui ne savent rien en savent toujours autant que ceux qui n'en savent pas plus qu'eux" -Pierre Dac
"Travailler sur un groupe haddock, ou être heureux comme un poisson dans l'eau..."