Question sur la correction de la série 1

Question sur la correction de la série 1

par Lucas Antoine Reymond,
Number of replies: 5

Bonjour

J'ai une question sur l'exercice 2.2 de la série de la semaine 1 (l'exercice sur le marchant itinérant).

La correction dit que le nombre totale d'itinéraire est N! mais comme chaque itinéraire est compté deux fois (puisque par exemple un itinéraire où le marchant commence par la première ville et termine dans la 148ème est le même que l'itinéraire où il commence dans la 148ème et termine dans la première mais en ayant visité les villes dans l'ordre inverse), pourquoi le nombre totale d'itinéraires n'est pas (1/2)N! ?

Merci pour les réponses.

In reply to Lucas Antoine Reymond

Re: Question sur la correction de la série 1

par Prune August,

Coucou,

Je ne suis pas forcément la plus douée pour t'expliquer mais en fait justement, l'idée même d'une factorielle c'est qu'elle "évite" ces "répétitions" dont tu parles (sinon on utiliserait une puissance).


En fait, la manière dont moi je le vois est la suivante :

Tu pars de ta "première" ville, donc tu as N choix. Tu peux maintenant potentiellement aller dans N-1 villes, ce qui te fait jusqu'à maintenant déjà N*(N-1) choix.

Ensuite, tu "choisis" ta prochaine ville, mais vu que tu en as déjà vues 2, il ne te reste plus que N-2 choix... etc 

Donc en fait ton "arbre" si tu veux (comme tu as du en faire en proba je pense) perd une "branche" à chaque nouvelle étape puisque tu élimines une ville (tu vas pas utiliser une ville deux fois).

Je ne sais pas si tu as fait du dénombrement mais du coup là il s'agit d'un cas qu'on appelle parfois "sans remise".


En tout cas, si tu m'as suivie tu vois que au final tu as N*(N-1)*(N-2)*... choix jusqu'à ce que tu arrives à ta dernière ville, donc bien N! itinéraires.


J'espère avoir été à peu près claire et surtout ne pas avoir dit de bêtises :')


Bonne soirée.

In reply to Prune August

Re: Question sur la correction de la série 1

par Emil Heimo Bennewitz,
A priori, N! "compte" avec ordre sans répétition, donc les villes A-B-C-D et D-C-B-A sont comptés deux fois alors qu'on pourrait les considérer comme un seul itinéraire je crois...

In reply to Emil Heimo Bennewitz

Re: Question sur la correction de la série 1

par Teymour Beydoun,

Salut,

Il me semble que la question était de trouver le nombres d’itinéraires possibles, dans ce cas ce serait N! Cependant je comprend que si l’on recherche le nombre de chemins qui ont a priori une longueur différente ce serait 1/2*N! (Chemins dans les 2 sens comptés 1 seule fois) et même si l’on y pense 1/2*(N-1)! étant donné que le choix de la première ville ne change pas la longueur du chemin.

P.S. Je ne suis pas certain de mon raisonnement.

In reply to Lucas Antoine Reymond

Re: Question sur la correction de la série 1

par Matthieu Claude Marie Protais,

Je pense que tu ne dois pas diviser par deux simplement parce que un itinéraire et son symétrique (l'itinéraire parcouru en sens inverse) n'est pas le même ! Quand tu vas de Genève à Neuchâtel, ce n'est pas le même itinéraire que de Neuchâtel à Genève. Puisque ce n'est pas le même sens ! 
Je ne sais pas si je me suis bien fait comprendre, mais j'espère. 
Bon courage !

In reply to Lucas Antoine Reymond

Re: Question sur la correction de la série 1

par Jean-Cédric Chappelier,

Réponse sur deux plans différents :

  1. comme vous l'avez suggéré : toute la question est de savoir ce que l'on compte ; c.-à-d. qu'est-ce qu'un « itinéraire » ? Est-ce que A-B-C-D est pareil que D-C-B-A ?
    Et l'on pourrait même, du coup, pousser plus loin : est-ce pareil que C-B-A-D ou B-A-D-C, etc. (même « cycle ») ?
    Dans cet exercice nous concidérons, de façon similaire au problème précédent (comme suggéré), que tous ces itinéraires sont différents (ce n'est pas le même itinéraire pour venir de chez vous à l'EPFL que pour rentrer).
    La notion sous-jacente est la notion de graphe ORIENTÉ (ou non) : on considère ici que les chemins ont un sens (graphe orienté).
    Dans ce cas, le nombre d'itinéraires est bien N!

  2. A un autre niveau : est-ce que vraiment ce coefficient une-demi change quelque chose sur le FOND ? Est-ce que cela change les conclusions vus les ordres de grandeurs impliqués ?
    Justement non : est c'est pour cela que l'on utilise la notation O(.) (notation de Landau) que je vais vous présenter aujourd'hui (il n'est donc, évidemment, pas question que vous trouviez cela tout seul la semaine passée ; je profite juste de l'occasion pour illustrer concrètement pourquoi on utilise cette notation).