jpp
Re. ,
Zebulor :
Non , il traverse la rue à chaque changement de maison d'après Fred
Zebulor
Re
Jpp: exact.. je devrais pas faire deux choses en même temps...
Zebulor
Je dirais mais avec des pincettes :
.
3*2*2*2 possibilités
Cette fois chaque maison a son courrier. Ca me fait pense que je dois donner des sous à mon facteur pour le calendrier ..
Avec 6 maisons {3 de chaque côté de la rue) on a que deux possibilites..
Roro
Bonsoir,
24 possibilités mais en faisant 3*2*4... et heureusement que la rue n'est pas trop longue ! Je ne suis pas certain d'y arriver avec 2n maisons !
Roro.
jpp
Re ,
un octogone régulier avec les 12 côtés ou diagonales représentant les traversées de rue possibles
J'ai trouvé 15 trajets possibles .
J'ai dû en oublier quelques uns . Je vais poursuivre.
Fred
Re-
Je n'ai pas encore lu la réponse que j'ai trouvée....
F.
LEG
Bonjour
--70--
Bernard-maths
Bonjour !
Fred ! Es-tu sûr de TA réponse ???
Y'en a beaucoup qui ont trouvé AUTRE CHOSE ...
(;-) ... B-ml
jpp
Salut .
Il y en aurait 18
14763852
14763258
14725836
14527638
14583276
14583672
16327458
16385274
16385472
16723854
16745238
16745832
18325476
18367254
18367452
18547236
18547632
18523674
Fred
Sûr ce serait présomptueux mais maintenant que JPP a trouvé la même réponse j'ai plutôt confiance !
Roro
Bonjour,
Je n'ai pas de doute que Fred et jpp ait trouvé la solution mais il y a un truc que je n'ai pas compris.
Pour moi, le facteur commençant par visiter la maison 1, il va ensuite au choix vers 4, 6 ou 8. Et pour moi ces 3 configurations sont équivalentes. Autrement dit, je m'attends à trouver un nombre de solutions multiple de 3.
Quelle est mon erreur ?
Roro.
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