Inscription / Connexion Nouveau Sujet
Niveau énigmes
Partager :

Aurais-je ma place?

Posté par
jarod128
01-12-20 à 18:26

Bonjour, une petite énigme en attendant le déconfinement (n'oubliez pas de blanker)
Les salles de spectacles vont pouvoir accueillir du public. Ils vont numéroter leur places assises. Considérons donc une salle ayant n places numérotées de 1 à n. Tous les billets sont vendus et tous les spectateurs viennent. Le premier spectateur qui n'a pas lu les consignes choisit sa place au hasard. Les autres spectateurs entrent un par un en suivant la règle suivante: si la place attribuée sur son billet est disponible, il s'assoit à sa place. Sinon, il en choisit une au hasard parmi celles encore libres.  Ma question: je suis le dernier à entrer dans la salle, quelle est la probabilité que ma place soit libre?

Posté par
dpi
re : Aurais-je ma place? 01-12-20 à 19:11

Bonjour,
Merci d'animer.

 Cliquez pour afficher

Posté par
jarod128
re : Aurais-je ma place? 01-12-20 à 19:26

Dpi: tu écris le premier spectateur... Les spectateurs arrivés avant lui...
S'il est le premier  il n'y a personne arrivé avant lui.

Posté par
carpediem
re : Aurais-je ma place? 01-12-20 à 20:47

salut

 Cliquez pour afficher


avec peu de certitude ... même s'il me semble raisonnable que cette probabilité tende vers 0 avec n (quoique cette affirmation semble être aussi une trivialité )

Posté par
flight
re : Aurais-je ma place? 01-12-20 à 21:29

salut

 Cliquez pour afficher

Posté par
ty59847
re : Aurais-je ma place? 01-12-20 à 23:23

 Cliquez pour afficher

Posté par
dpi
re : Aurais-je ma place? 02-12-20 à 08:49

suite,
Plus difficile que prévu....

 Cliquez pour afficher

Posté par
Imod
re : Aurais-je ma place? 02-12-20 à 10:59

Bonjour

Je dirais une chance sur ...

 Cliquez pour afficher

Imod

Posté par
jarod128
re : Aurais-je ma place? 02-12-20 à 12:30

Je ne sais pas si je donne la réponse tout de suite? S'il faut attendre que quelqu'un ait trouvé (je ne dévoile pas si à cet instant c'est déjà le cas)
Peut être un indice pour ceux qui veulent :

 Cliquez pour afficher

Posté par
LittleFox
re : Aurais-je ma place? 02-12-20 à 13:16


Bonjour,

 Cliquez pour afficher

Posté par
LittleFox
re : Aurais-je ma place? 02-12-20 à 13:30


Une rapide simulation montre que j'ai tord et Imod a probablement raison.
Je ne vois pas le "clairement la même probabilité" par contre

Posté par
dpi
re : Aurais-je ma place? 02-12-20 à 15:34

Suite,
Vivement la solution...

 Cliquez pour afficher

Posté par
perroquet
re : Aurais-je ma place? 02-12-20 à 15:50

Bonjour à tous.

Merci à jarod128 pour ce joli exercice que je ne connaissais pas.

 Cliquez pour afficher

Posté par
littleguy
re : Aurais-je ma place? 02-12-20 à 17:22

Bonjour,

 Cliquez pour afficher

Posté par
Imod
re : Aurais-je ma place? 02-12-20 à 17:54

Pour répondre à LittleFox

Tu échanges les numéros du premier et dernier entré , le problème a-t-il changé ?

Imod

Posté par
LittleFox
re : Aurais-je ma place? 02-12-20 à 17:56

@littleguy
J'aime vraiment bien la "rédaction plus imagée" à la fin de l'article détaillé.

Citation :
Si la place d'un spectateur n'est pas disponible, il en prend une autre au hasard.
Ce serait pareil si ce spectateur chassait l'intrus et que ce dernier reprenne une place au hasard.
Au final les spectateur 2 à n-1 ont leur place et il y a une chance sur deux que le premier spectateur ait pris ma place.


Maintenant calculons combien de spectateurs en moyenne auront trouvé leur place occupée quand ils sont arrivés

Posté par
littleguy
re : Aurais-je ma place? 02-12-20 à 17:56

Complément :

 Cliquez pour afficher

Posté par
littleguy
re : Aurais-je ma place? 02-12-20 à 17:58

Bonjour LittleFox,

No comment.

Posté par
dpi
re : Aurais-je ma place? 02-12-20 à 18:18

Bonsoir,

Finalement mon raisonnement "citoyen" de 15h34 n'est pas si mauvais

Posté par
jarod128
re : Aurais-je ma place? 02-12-20 à 18:27

Et bien certains ont donc trouvé. J'ai volontairement mis n places pour vous emmener vers une probabilité en fonction de n même si je demandais la probabilité sans préciser en fonction de n...
Bravo à ceux qui ont trouvé et pour la démonstration je pense que les liens donnés par littleguy sont plus explicites qu'une rédaction ici. Même si j'aime beaucoup la démo de Imod
On remarquera que, quitte à renommer les tickets, on pouvait supposer que les n spectateurs entrent dans l'ordre du numéro 1 à n.

Posté par
perroquet
re : Aurais-je ma place? 02-12-20 à 18:37

Je pense avoir la réponse à la question que posait   LittleFox:
Quel est le nombre moyen de spectateurs qui trouveront leur place occupée ?

Pour cela, je réponds d'abord à la question suivante:
Quelle est la probabilité que le k-ième spectateur entrant trouve sa place occupée?

Posté par
flight
re : Aurais-je ma place? 03-12-20 à 04:23

salut

une simulation avec  50 personnes me donne environ 4,5 personnes qui ne seront pas assises à leur place (on pourra arrondir à 5) ..je ne sais pour vous?

Posté par
LittleFox
re : Aurais-je ma place? 03-12-20 à 10:47


@flight
Ma simulation semble donner une personne de moins que la tienne. Je ne compte pas le premier spectateur puisque sa place est disponible même s'il ne la prend presque jamais.

Tu verras peut-être que le nombre de mécontent augmente avec le nombre de spectateur. Et non, ce n'est pas un nombre rond comme 5. Mais il reste facile à calculer.
J'ai environ 3.499205 pour 50 spectateurs.
1.928968 pour 10.
4.187378 pour 100.

Posté par
jarod128
re : Aurais-je ma place? 03-12-20 à 13:32

J'ai en formule: log2(n)-1 ou -2 selon que l'on compte le premier. En tout cas un équivalent en log2(n)

Posté par
LittleFox
re : Aurais-je ma place? 03-12-20 à 13:54


@jarod128
Pourquoi \log_2 et pas \ln?
Et non, ce n'est pas correct mais presque.

J'ai \sum_{k=2}^{n}\frac{1}{k} = H_n - 1.

H_n est le nème nombre harmonique.

Et H_n \approx \ln(n) + \gamma pour les grands n. Avec \gamma \approx 0.577215 la constante d'Euler-Mascheroni.

Posté par
perroquet
re : Aurais-je ma place? 03-12-20 à 14:50

Je confirme que le nombre moyen de spectateurs qui ne sont pas à leur place est égal à \displaystyle \sum_{k=1}^{n-1}\dfrac{1}{k} si on compte le premier spectateur et de \displaystyle \sum_{k=2}^{n}\dfrac{1}{k} si on ne le compte pas.
Saurez-vous trouver une démonstration ?

Posté par
jarod128
re : Aurais-je ma place? 03-12-20 à 15:15

Mon raisonnement (pas forcément juste)
Comme déjà dit, on peut, quitte à renumeroter, supposer que les spectateurs entrent dans l'ordre du 1 au n. Le premier choisit au hasard par exemple p puis jusqu'à p plus de problème et ainsi de suite. Le choix est donc uniforme entre son propre numéro exclu (sauf pour le premier) et n. Donc en moyenne l'intervalle est divisé par 2 à chaque étape d'où mon log en base 2...

Posté par
LittleFox
re : Aurais-je ma place? 03-12-20 à 15:49


Le premier spectateur qui arrive a une probabilité de \frac{n-1}{n} ne n'être pas à sa place.

On a bien  \sum_{k=1}^{n-1}\dfrac{1}{k} = \frac{n-1}{n}  + \sum_{k=2}^{n}\dfrac{1}{k} jusque là tout va bien

Le second spectateur a une probabilité de \frac{1}{n} que sa place soit prise.
Si elle est prise, il prend une autre place au hasard. Sinon c'est que le premier spectateur avait pris une autre place (et chacune a la même probabilité d'avoir été prise).

Le problème pour le troisième spectateur est donc le même avec la place du second en moins. Il a donc une probabilité de \frac{1}{n-1} que sa place soit occupée.

Et ainsi de suite jusqu'au dernier spectateur qui a \frac{1}{n-(n-2)} = \frac{1}{2} de probabilité.

Au total on a donc en moyenne  \frac{1}{n} + \frac{1}{n-1} + ... + \frac{1}{2} = \sum_{k=2}^n \frac{1}{k} personnes qui ont trouvé leur place occupée quand ils sont arrivés.

En ajoutant le premier spectateur on obtient le nombre de personnes qui ne sont pas à leur place :  \frac{n-1}{n} + \sum_{k=2}^n \frac{1}{k} = 1 - \frac{1}{n} +  \sum_{k=2}^n \frac{1}{k}  =  \sum_{k=1}^{n-1} \frac{1}{k}

@jarod128
Je crois que ce qui ne va pas dans ton raisonnement c'est que les intervalles après division n'ont pas tous la même espérance. Mais je ne suis pas sûr du tout.

Répondre à ce sujet

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !