Aurais-je ma place?

 Niveau énigmesPartager :
			        
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 
dpire : Aurais-je ma place?  01-12-20 à 19:11
Bonjour,

Merci d'animer.

 Cliquez pour afficher
Il semble que le premier spectateur prenne la place k sans regarder son billet p.

Les spectateurs arrivés avant lui ont bien pris leur  bonne place. 

Ceux arrivés après lui vont aussi trouver leur place sauf le porteur du billet k.

Si j'ai le billet k ,j'ai toutes les chances de trouver une place (la seule libre...)

Si j'ai un billet b ,il y a peu de chance que ma place soit libre ,il me reste à trouver

la formule  entre 1 ,k,n,p,b......
 Posté par 
jarod128re : 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 
carpediemre : Aurais-je ma place?  01-12-20 à 20:47
salut

 Cliquez pour afficher
le dernier entré s'assoit à sa place si tout les autres sont assis n'importe comment ... sauf à la place numérotée n (que ce soit en respectant la règle ... ou pas ... enfin ce me semble-t-il !!!)

il y a (n - 1)! façons que les n - 1 premières personnes s'assoient à toutes les places sauf la n-ième et n! façons que tous s'assoient

donc je dirai que la probabilité que le dernier s'assoie à sa place est 1/n

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 
flightre : Aurais-je ma place?  01-12-20 à 21:29
salut

 Cliquez pour afficher
je dirais   P = (n-1)!/n! = 1/n
 Posté par 
ty59847re : Aurais-je ma place?  01-12-20 à 23:23
 Cliquez pour afficher
Le 1er spectateur peut avoir de la chance, et choisir sa place ( proba 1/n), ou une autre place(proba (n-1)/n )

S'il choisit sa propre place, alors pas de problème, chacun sera à sa place.

Et s'il choisit une autre place, alors j'ai une probabilité non nulle que les choses rentrent dans l'ordre.

La probabilité est donc supérieure à 1/n.
 Posté par 
dpire : Aurais-je ma place?  02-12-20 à 08:49
suite,

Plus difficile que prévu....

 Cliquez pour afficher
Supposons que le premier spectateur ait pris une mauvaise place dans (n-1)/n  des cas. 

Les (n-2 ) suivants trouveront leur bonne place sauf le possesseur *de la place usurpée

soit ( n-3 )/(n-1).

*(Je pense aussi que par logique ,il se mettra à la place disponible la plus proche).

J'arrive le dernier  ma probabilité de  trouver ma place libre est  supérieure  à 1/n

je dirai (mais je cherche encore )de l'ordre de 1/(n-3)

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

Je dirais une chance sur ...

 Cliquez pour afficher
... deux . En effet une fois les n-1 premiers spectateurs installés , la place libre ne peut être que celle du premier ou du dernier avec clairement la même probabilité .

Imod 
 Posté par 
jarod128re : 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
 contrairement à ce que j'ai lu la limite pour n tendant vers infini n'est pas 0
 Posté par 
LittleFoxre : Aurais-je ma place?  02-12-20 à 13:16

Bonjour,

 Cliquez pour afficher

Soit a,b,c respectivement le nombre de place disponible, le nombre place disponible qui appartient à un billet utilisé et le nombre de place disponible qui appartient à un billet non utilisé.

Au départ on a (a,b,c) = (n,0,n).

Après le premier spectateur, on a (a,b,c) = (n-1, 0, n-1) ou (n-1, 1, n-2).

Ensuite pour chaque spectateur, 

soit la place est disponible => (a,b,c) -> (a-1, b, c-1)

soit la place est indisponible et il prend la place d'un billet non utilisé => (a,b,c) -> (a-1, b, c-1)

soit la place est indisponible et il prend la place d'un billet utilisé => (a,b,c) -> (a-1,b-1,c)

On voit qu'après le premier spectateur b est 1 ou 0 et qu'après il ne peut que diminuer. En effet la seule place qui peut être disponible alors que le billet est déjà utilisé est celle du premier spectateur.

Tout calcul fait cela donne une probabilité d'avoir ma place de (n-1)/n.

 Posté par 
LittleFoxre : 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 
dpire : Aurais-je ma place?  02-12-20 à 15:34
Suite,

Vivement la solution...

 Cliquez pour afficher
Si tout le monde se place au hasard ,il y a (n-1)!/n! de voir un spectateur au bon siège. Mais les spectateurs étant respectueux,cela n'arrivera pas.

Le premier(l'intrus)  a une chance sur n de tomber sur sa vraie place.

Les n-3 autres spectateurs vont respecter leur place,sauf le vrai possesseur du billet

correspondant au siège usurpé.

Comme il est respectueux au lieu de se poser à une place voisine et de créer ainsi une

nouveau litige,il reste debout car il sait qu'il restera deux sièges disponibles à la fin.

il me laisse le mien et prend l'autre...

J'ai donc 100%  d'avoir ma place.

Je sais ,je rêve 

 Posté par 
perroquetre : 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

Je trouve le même résultat que Imod, mais avec un raisonnement beaucoup plus long.

On note  la probabilité demandée par jarod128.

On montre facilement que .

On revient maintenant au cas des  spectateurs.

Notons  l'événement: le dernier spectateur trouve sa place libre.

Notons  l'événement:  "le premier spectateur choisit la place qui était attribuée au -ième spectateur entrant".

On calcule la probabilité que le dernier spectateur ait sa place libre sachant que  est réalisé.

Si le premier spectateur choisit la place qui lui était attribuée (probabilité ), alors, tous les spectateurs seront assis à la place qui leur est attribuée(et en particulier le dernier). Donc  

Si le premier spectateur choisit la place qui était attribuée au k-ième spectateur entrant avec  (probabilité ),  alors, les spectateurs qui sont entrés à un rang strictement compris entre 2 et  seront bien placés. Il reste à placer les spectateurs entrant entre les rangs  et . On peut "échanger les rôles du premier et du -ième spectateur" et en déduire que 

Enfin,  

On en déduit que, pour :

Et, par récurrence, pour :   

 Posté par 
littleguyre : Aurais-je ma place?  02-12-20 à 17:22
Bonjour,

 Cliquez pour afficher
A l'époque où je m'occupais des énigmes j'avais envisagé de poser celle-ci puis renoncé par crainte d'être un peu "léger" en cas de contestation.

On peut regarder ici :  pour une argumentation rapide, ou là :  avec plus de détails.

 Posté par 
Imodre : 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 
LittleFoxre : 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 
littleguyre : Aurais-je ma place?  02-12-20 à 17:56
Complément :

 Cliquez pour afficher
L'argumentation de perroquet me conforte dans ma décision de ne pas avoir posé cette "énigme".  
 Posté par 
littleguyre : Aurais-je ma place?  02-12-20 à 17:58
Bonjour LittleFox,

No comment. 
 Posté par 
dpire : Aurais-je ma place?  02-12-20 à 18:18
Bonsoir,

Finalement mon raisonnement "citoyen" de 15h34 n'est pas si mauvais 
 Posté par 
jarod128re : 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 
perroquetre : 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 -ième spectateur entrant trouve sa place occupée?
 Posté par 
flightre : 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 
LittleFoxre : 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 
jarod128re : 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 
LittleFoxre : Aurais-je ma place?  03-12-20 à 13:54

@jarod128

Pourquoi  et pas ?

Et non, ce n'est pas correct mais presque.

J'ai . 

Où  est le nème nombre harmonique. 

Et  pour les grands n. Avec  la constante d'Euler-Mascheroni.
 Posté par 
perroquetre : 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 à  si on compte le premier spectateur et de  si on ne le compte pas.

Saurez-vous trouver une démonstration ?
 Posté par 
jarod128re : 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 
LittleFoxre : Aurais-je ma place?  03-12-20 à 15:49

Le premier spectateur qui arrive a une probabilité de  ne n'être pas à sa place.

On a bien   jusque là tout va bien 

Le second spectateur a une probabilité de  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  que sa place soit occupée.

Et ainsi de suite jusqu'au dernier spectateur qui a  de probabilité.

Au total on a donc en moyenne   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 : 

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