Forum de mathématiques - Bibm@th.net

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 340

Le facteur

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

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le facteur

Salut à tous .

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

▼une idée

.
4! x 3! = 24 x 6 = 144

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 218

Re : Le facteur

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

Administrateur

Inscription : 26-09-2005

Messages : 7 340

Re : Le facteur

@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

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 847

Re : Le facteur

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 14:22:04)

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 218

Re : Le facteur

Re,
Je dirais :

▼une idée

.
3*2*2 possibilités

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

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 340

Re : Le facteur

▼@Zebulor @Bernard-maths

Je ne trouve pas la même chose que vous...

Bernard-maths

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 847

Re : Le facteur

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 15:13:25)

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 218

Re : Le facteur

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 15:38:00)

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le facteur

Re. ,

Zebulor :

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

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 218

Re : Le facteur

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

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 218

Re : Le facteur

Je dirais mais avec des pincettes :

▼une idée

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

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

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 798

Re : Le facteur

Bonsoir,

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

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.

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

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le facteur

Re ,

▼J'ai tracé...

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.

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

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 340

Re : Le facteur

Re-

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

F.

LEG

Membre

Inscription : 19-09-2012

Messages : 790

Re : Le facteur

Bonjour

  --70--

Bernard-maths

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 847

Re : Le facteur

Bonjour !

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

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

(;-) ... B-ml

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : Le facteur

Salut .

▼tous les chemins que j'ai trouvés

Il y en aurait 18
14763852
14763258
14725836
14527638
14583276
14583672
16327458
16385274
16385472
16723854
16745238
16745832
18325476
18367254
18367452
18547236
18547632
18523674

Fred

Administrateur

Inscription : 26-09-2005

Messages : 7 340

Re : Le facteur

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

Roro

Membre expert

Inscription : 07-10-2007

Messages : 1 798

Re : Le facteur

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

Administrateur

Inscription : 26-09-2005

Messages : 7 340

Re : Le facteur

18 est un multiple de 3...

Zebulor

Membre expert

Inscription : 21-10-2018

Messages : 2 218

Re : Le facteur

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

Membre Expert

Lieu : 34790 Grabels

Inscription : 18-12-2020

Messages : 1 847

Re : Le facteur

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

Membre expert

Inscription : 07-10-2007

Messages : 1 798

Re : Le facteur

18 est un multiple de 3...

Certes, mais 70 ne l'est pas trop !

Bonjour
  --70--

Je suis vraiment perdu...

Glozi

Invité

Re : Le facteur

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