Chercher un fauteuil libre.

[invite42a8bebe]

Bonjour,
Voila un petit calcul amusant à faire sous forme de simulation :
"Dans un théâtre de N places toutes les places sont numérotées et il y a N spectateurs. J'arrive le premier mais j'ai perdu mon billet et je ne connais pas mon numéro de place. Je prends une place au hasard et je n'en prends une autre que quand un spectateur revendique sa place. Combien de fois, en moyenne devrais-je me lever ?"
J'ai fait le calcul avec un théâtre de 100 places et avec un théâtre de 300 places.
J'aimerais aussi confronter mes résultats.
Bonne journée.
-----

[azad]

Salut.
Je suppose que cela peut se simplifier : tu as perdu ton billet mais tu sais l'avoir acheté. Et tu sais aussi combien il t'a couté. On peut donc supposer que tu t'es installé à une place correspondant au prix du billet que tu as payé. Reste à connaître la répartition des places en fonction de leurs prix. Si tu va t'installer dans la loge du Président et que ce n'est pas le jour de la première, tu as des chances de ne pas être dérangé.

[azad]

Ha j'avais mal lu : N places et N spectateurs, donc je confirme, tu t'installe à la place du Président, et quand il va venir, alors tu prends la seule place disponible qui restera, car, c'est connu, il arrive toujours le dernier.

[invite42a8bebe]

Bonjour Azad,
Oui, on peut le considérer de cette façon, mais le problème était posé à l'origine dans un sous-forum "Probabilité".
Pour ce genre de calcul, j'aime bien le faire avec ma machine. Et il se trouve qu'ile est assez amusant à faire, donc, je voulais en faire profiter d'autres.
En fait le contexte est impossible dans le monde réel, jamais on ne m'aurait laissé entrer sans billet.
D'autant que, pour tout dire, je ne m'attendais pas vraiment à ce résultat.

[A voir en vidéo sur Futura]

[invite9dc7b526]

Je trouve que c'est un problème difficile.

il s'agit de calculer le nombre moyen d'essais pour trouver la bonne place. Comme le théâtre se remplit petit à petit, te laissant de moins en moins de places libres, tu as de plus en plus de chances de trouver la bonne place. Tu ne bouges que lorsqu'on te réclame la place que tu occupes, et cela advient aussi de plus en plus fréquemment. Il faut trouver une astuce (que je ne vois pas) sinon dès que N est un peu grand il n'y a que la simulation.

[invite42a8bebe]

Oui, en calcul de probabilité, c'est difficile et j'avoue que ça ne m'intéresse pas vraiment.
Par contre il n'est pas très difficile de faire une simulation et c'est ça que je propose. Tu sais bien que le notions élémentaires des probabilités me poussent à utiliser la méthode des simulations pour résoudre des problèmes difficiles, ou au moins vérifier les résultats obtenus par des calculs théoriques.
Dans ce cas précis, l'énoncé est clair et sans ambiguïté. L'algorithme est donc presque évident, mais c'est ce qui est amusant. Mon code en C/C++ prend 40 lignes, c'est un tout petit code.

[Spazi]

Bonjour,

Mes résultats tournent autour de (N+1)/2.

Je ne suis pas super fort en maths, mais il me semble que tous les évènements sont equiprobables.
Pour un theatre de 10 places, la proba de trouver en :
- 1 essai => 1/10
- 2 essai => 9/10*1/9 = 1/10
- 3 essai => 9/10*8/9*1/8 = 1/10
etc

Mes simulations me confortent dans cela.

[invite42a8bebe]

Bonjour Spazi,
La résolution de ce problème en math est très difficile.
Je ne pense pas que votre formule soit bonne. Par exemple pour une petite salle de 100 places il devrait changer 50 fois de siège, cela me parait beaucoup.
J'ai mis cette question dans le forum "informatique", parce que je pense que c'est encore le meilleur moyen de le résoudre.
Au début, il est le premier, donc il prend une place au hasard. Puis arrivent quelques spectateurs, ce serait vraiment pas de chance qu'il soit tout de suite obligé de changer de fauteuil. Par contre juste avant le levé de rideau, presque tout le monde a trouvé sa place, il n'a plus beaucoup de choix, et là ce serait de la chance qu'il choisisse le siège qui justement lui était réservé.

[Spazi]

oh, vous voulez dire que lorsque l'on doit trouver une nouvelle place, on dois simuler les personnes s'étant assises entre temps et donc le champs des possibles n'est pas réduit 1 mais d'un aléa ?

[invite42a8bebe]

Ben oui, vous n'allez pas vous asseoir dans un fauteuil où il y a déjà quelqu'un !

[Spazi]

Dans ce cas, j'obtiens pour 100 places ~4,19 levages (5,19 sélection de sièges), pour 300 places ~5,28 levages (6,28 sélection de sièges)

[invite42a8bebe]

Eh bien bravo, je trouve ça aussi. Pour une salle de 600 places, je trouve un peu moins de 6.
J'avoue que je m'imaginais plus, avant d'avoir fait le calcul.

[Spazi]

Ce nombre ne m'a pas tant choqué. En terme de fonctionnement, pour moi, cela ressemble à une recherche dichotomique, à la différence bien sur qu'ici, l'espace n'est pas divisé par 2 comme une dicho, mais est réduit d'un aléa. Donc j'avais en tête de trouver qq chose de proche d'une évolution logarithmique.

Et pour 600, je suis autour de 5,97~5,98

[azad]

Oui, j'ai fait des tests aussi,
10 000 places -> 4 déplacements
1 000 -> 5
100 -> 7
Par contre je ne comprends pas comment Spahi trouve des nombres décimaux ?

[azad]

Ha oui, d'accord, j'avais pas tout lu.

[Spazi]

Mon code C# est le suivant

 Cliquez pour afficher

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleTest
{
    class Program
    {
        static void Main(string[] args)
        {
            int nbmax = 600;

            Random rand = new Random();
            for (int a = 0; a < 5; ++a)
            {
                List<int> resultsimu = new List<int>();
                for (int i = 0; i < 100000; ++i)
                {
                    List<int> chaises = new List<int>(Enumerable.Range(1, nbmax).OrderBy(x => rand.Next(nbmax)));
                    List<int> cothers = new List<int>(chaises);

                    int tofind = chaises[rand.Next(nbmax)];

                    cothers.Remove(tofind);

                    int seated = chaises[rand.Next(nbmax)];

                    int nbassis = 1;
                    while(cothers.Count > 0)
                    {
                        int ipick = rand.Next(cothers.Count);

                        chaises.Remove(cothers[ipick]);
                        if (cothers[ipick] == seated)
                        {
                            seated = chaises[rand.Next(chaises.Count)];
                            nbassis++;
                        }

                        cothers.RemoveAt(ipick);
                    }

                    resultsimu.Add(nbassis);
                }

                Console.WriteLine("Simu " + a + " : Moy = " + resultsimu.Average());
                Console.WriteLine("Min " + resultsimu.Min() + "  Max " + resultsimu.Max());

                foreach (var item in resultsimu.GroupBy(x => x).OrderBy(x => x.Key))
                {
                    Console.WriteLine("Value " + item.Key + " Count " + item.Count());
                }
            }

            Console.ReadLine();
        }
    }
}

[albanxiii]

Oui, en calcul de probabilité, c'est difficile et j'avoue que ça ne m'intéresse pas vraiment.

C'est pourtant la seule chose qui ait un intérêt.

[leon1789]

Bonjour

La résolution de ce problème en math est très difficile.

Absolument pas : on peut assez facilement calculer la probabilité de s'asseoir sur k sièges lorsqu'il y en n dans la salle (c'est une espèce de triangle de Pascal).

Et ensuite calculer l'espérance du problème :
pour n=100, on trouve 4.1873775... levages (+1 pour les sélections de siège)
pour n=300, on trouve 5.282663880... levages (+1 pour les sélections de siège)
pour n=600, on trouve 5.9749784... levages (+1 pour les sélections de siège)

C'est un problème amusant car il va contre l'intuition commune, je trouve.

[leon1789]

J'avoue que je m'imaginais plus, avant d'avoir fait le calcul.

tu as fait un vrai calcul mathématique ou une simple simulation avec un ordinateur ?

[invite452d5a24]

Salut,

Absolument pas : on peut assez facilement calculer la probabilité de s'asseoir sur k sièges lorsqu'il y en n dans la salle (c'est une espèce de triangle de Pascal).

Je trouve que c'est un problème difficile.

Je ne doute pas des compétences de Minushaben, ni de celle de Léon en statistique, mais qui croire ?

Peut-être les 2 en admettant, que ce n'est pas parce que c'est facile à comprendre (ce que me semble dire Léon) que c'est facile à trouver (ce que me semble dire Minushaben).

Cordialement.

[invite42a8bebe]

Bonjour,
Dans un sous-forum informatique, je pense qu'on peut s'attendre à des questions concernant l'informatique, en l'occurrence la résolution d'un problème précis.
Ceci répond à AlbanXIII
Concernant la réponse de Léon, je voudrait bien savoir d'où viennent ces résultats. Avec un peu de chance, les participants à la question sur le sous-forum "Probabilités et théorie de la mesure" passeront par là.

[leon1789]

Pas de souci :
soit la probabilité de s'asseoir fois lorsqu'il y a sièges.

On a évidemment ,
et par récurrence pour tous (une fois que l'on a étudié les "symétries" du problème) :
avec les conventions pour k<1 ou k>n .

[leon1789]

Je ne doute pas des compétences de Minushaben, ni de celle de Léon en statistique

ce sont des probas

[invite9dc7b526]

est-ce que tu ne supposes pas (à tort) que lorsqu'on se lève de la première place où l'on s'est assis, il n'y a personne dans la salle (donc n-1 places libres)?

[leon1789]

Le n-1 désigne le nombre de places libres : la personne qui nous chasse de notre place prend cette place (mais pas les autres), il en reste donc n-1

[leon1789]

Je précise, suite à la question de Minushabens :
soit la probabilité de s'asseoir encore fois lorsqu'il y a sièges libres.

[invite9dc7b526]

mais la personne qui nous chasse le fait après qu'un certain nombre de personnes sont entrées et ont occupé autant de places. La situation est donc différente de la situation initiale, puisque l'énoncé précise : "j'entre le premier".

[leon1789]

Minushabens,
c'est une récurrence sur le nombre de places libres (je viens de le préciser) : soit les nombres de places libres... peu importe combien de personnes ont déjà pris places : ces personnes et leurs places sont maintenant hors jeu.
Le nombre de places libres diminue de un en un à chaque fois qu'une personne s'assoit. Donc le aussi, comme pour

[leon1789]

minushabens,
quand la personne n°i rentre, je suis déjà assis, pour i=1 , où pour i>1. La situation initiale se répète donc, mais avec moins de places libres.

[leon1789]

Dans ce cas, j'obtiens pour 100 places ~4,19 levages (5,19 sélection de sièges),
pour 300 places ~5,28 levages (6,28 sélection de sièges)
Et pour 600, je suis autour de 5,97~5,98

Combien de fois avez-vous réalisé vos expériences pour être à peu près certain de vos résultats (en terme de précision) ?