Le facteur

Fred · 19-10-2023 13:12:38

Bonjour,

Dans ma rue, il y a 8 maisons. D'un côté de la rue, il y a les maisons qui portent un numéro impair, 1,3,5,7,
et de l'autre, il y a les maisons qui portent un numéro pair 2,4,6,8.
Mon facteur est un peu étrange. Chaque jour, ils visitent toutes les maisons en commençant par la 1, mais
il traverse la rue entre chaque maison et sans aller à la maison directement en face.
De combien de façons différentes peut-il apporter le courrier?

F.

PS: Il faut profiter qu'il y ait encore des facteurs pour poster cet énigme!

jpp · 19-10-2023 13:56:18

Salut à tous .

Si le facteur commence toujours par le numéro 1 ,

▼une idée

Zebulor · 19-10-2023 13:59:33

Salut Fred et à tous,
j'aurais dit comme jpp, mais je viens de voir "sans aller à la maison directement en face" ce qui pourrait limiter les possibilités...

Fred · 19-10-2023 14:13:08

@jpp @Zebulor : oui, sans aller voir la maison d'en face! ce qui signifie en clair qu'on ne peut pas passer du 1 au 2 par exemple...

Bernard-maths · 19-10-2023 14:53:38

Bonjour !

A première lecture je dis pareil !

Mais à la deuxième lecture, je diviserais bien par 6 ???

B-m

Ben non, par 4 ???

Je cherche encore ...

Dernière modification par Bernard-maths (19-10-2023 15:22:04)

Zebulor · 19-10-2023 15:35:38

Re,
Je dirais :

▼une idée

Dernière modification par Zebulor (19-10-2023 15:40:04)

Fred · 19-10-2023 15:58:27

▼@Zebulor @Bernard-maths

Bernard-maths · 19-10-2023 16:12:21

Coucou, c'est moi !

Bon, avec un regain de jeunesse, je suis monté sur un arbre, et un peu bigleux , je lui compte 29 branches. Certaines sont pourris, et je profite pour en élaguer10 !

Cet arbre n'a donc plus que 19 branches ... à 1 près !???

B-m

Dernière modification par Bernard-maths (19-10-2023 16:13:25)

Zebulor · 19-10-2023 16:34:57

Re,
Les maisons qui se font face sont 1 et 2 , 3 et 4 , 5 et 6, 7 et 8 si j’ai bien compris ...
Ah.. mais j’ai oublié que ce facteur peut livrer deux maisons à la suite du même côté de la rue..

Dernière modification par Zebulor (19-10-2023 16:38:00)

jpp · 19-10-2023 16:46:09

Re. ,

Zebulor :

Non , il traverse la rue à chaque changement de maison d'après Fred

Zebulor · 19-10-2023 16:51:26

Re
Jpp: exact.. je devrais pas faire deux choses en même temps...

Zebulor · 19-10-2023 17:01:21

Je dirais mais avec des pincettes :

▼une idée

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

Dernière modification par Zebulor (19-10-2023 21:26:16)

Roro · 19-10-2023 17:32:25

Bonsoir,

▼une idée pas très différente :

Roro.

Dernière modification par Roro (19-10-2023 17:37:15)

jpp · 19-10-2023 17:45:55

Re ,

▼J'ai tracé...

J'ai dû en oublier quelques uns . Je vais poursuivre.

Dernière modification par yoshi (19-10-2023 19:47:40)

Fred · 19-10-2023 22:44:06

Re-

Je n'ai pas encore lu la réponse que j'ai trouvée....

F.

LEG · 20-10-2023 09:12:29

Bonjour

--70--

Bernard-maths · 20-10-2023 10:19:40

Bonjour !

Fred ! Es-tu sûr de TA réponse ???

Y'en a beaucoup qui ont trouvé AUTRE CHOSE ...

(;-) ... B-ml

jpp · 20-10-2023 10:28:05

Salut .

▼tous les chemins que j'ai trouvés

Fred · 20-10-2023 10:41:08

Sûr ce serait présomptueux mais maintenant que JPP a trouvé la même réponse j'ai plutôt confiance !

Roro · 20-10-2023 11:27:32

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 · 20-10-2023 11:42:10

18 est un multiple de 3...

Zebulor · 20-10-2023 11:42:38

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 · 20-10-2023 12:21:39

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 · 20-10-2023 12:55:03

Fred a écrit :

18 est un multiple de 3...

Certes, mais 70 ne l'est pas trop !

LEG a écrit :

Bonjour
--70--

Je suis vraiment perdu...

Glozi · 20-10-2023 14:39:25

Bonjour,
Merci pour l'énigme

▼idée

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

Forum de mathématiques - Bibm@th.net

#1 19-10-2023 13:12:38

Le facteur

#2 19-10-2023 13:56:18

Re : Le facteur

#3 19-10-2023 13:59:33

Re : Le facteur

#4 19-10-2023 14:13:08

Re : Le facteur

#5 19-10-2023 14:53:38

Re : Le facteur

#6 19-10-2023 15:35:38

Re : Le facteur

#7 19-10-2023 15:58:27

Re : Le facteur

#8 19-10-2023 16:12:21

Re : Le facteur

#9 19-10-2023 16:34:57

Re : Le facteur

#10 19-10-2023 16:46:09

Re : Le facteur

#11 19-10-2023 16:51:26

Re : Le facteur

#12 19-10-2023 17:01:21

Re : Le facteur

#13 19-10-2023 17:32:25

Re : Le facteur

#14 19-10-2023 17:45:55

Re : Le facteur

#15 19-10-2023 22:44:06

Re : Le facteur

#16 20-10-2023 09:12:29

Re : Le facteur

#17 20-10-2023 10:19:40

Re : Le facteur

#18 20-10-2023 10:28:05

Re : Le facteur

#19 20-10-2023 10:41:08

Re : Le facteur

#20 20-10-2023 11:27:32

Re : Le facteur

#21 20-10-2023 11:42:10

Re : Le facteur

#22 20-10-2023 11:42:38

Re : Le facteur

#23 20-10-2023 12:21:39

Re : Le facteur

#24 20-10-2023 12:55:03

Re : Le facteur

#25 20-10-2023 14:39:25

Re : Le facteur

Réponse rapide

Pied de page des forums