Griffonnages

Commentaires

1. Le jeudi 14 juin 2007, 15:20 par Joun

Si on suit l'exposé à la lettre, un mathématicien ne peut qu'actionner l'interrupteur. S'il rentre dans la pièce et décide de ne rien faire, les suivants n'ont aucun moyen de savoir qu'il est venu. Il n'a d'autre choix que d'actionner l'interrupteur une seule fois, mais au final cela ne fournit guère d'informations.
Il ne manque pas une info ? Par exemple que la période à laquelle les mathématiciens sont amenés dans la pièce est constante, ou donnée ?

2. Le jeudi 14 juin 2007, 15:35 par Celui

La notion de temps n'intervient pas.

(D'ailleurs les mathématiciens sont séquestrés dans des geôles sans fenêtre, la luminosité est artificielle et les durées des «jours» et des «nuits» sont différentes d'un mathématicien à l'autre puisque le Dr. No effectue des expériences sur le rythme circadien de ses cobayes. Non mais quel sadique !)

Indice : Un mathématicien n'a pas nécessairement besoin d'indiquer toutes les fois où il rentre dans la pièce, une seule suffit.

3. Le jeudi 14 juin 2007, 20:26 par Christophe

Spoiler : Ne pas lire les commentaires plus loin si vous ne souhaitez pas connaître la réponse !

Les mathématiciens sont ils amenés indéfiniment dans cette pièce? Ou se pourrait il qu'un mathématicien n'y soit amené qu'une seul fois?

Dans le cas ou ma première hypothèse est vérifiée cas les mathématiciens peuvent adopter cette approche:

Un seul d'entre eux est autorise à éteindre la lumière. Les autres mathématiciens n'allument la lumière qu'une seule fois. C'est à dire que trouvant la lumière éteinte et n'ayant jamais allumé la lumière auparavant un mathématicien doit alors l’allumer.

Le mathématicien responsable d’éteindre la lumière peut alors compte combien de fois il l’éteint. Lorsqu’il l’éteint pour la 99eme fois il sait que tous les mathématiciens sont entrés dans la pièce.

4. Le jeudi 14 juin 2007, 21:02 par Joun

@Christophe: C'est une bonne idée (en tout cas bien meilleure que ce que j'étais en train de cogiter ;)), mais il y a un os, on ne sait pas si la lumière est éteinte au début.

5. Le vendredi 15 juin 2007, 01:39 par Celui

Bravo Christophe (et Joun) !

On suppose qu'ils peuvent rentrer une infinité de fois. C'est un peu lourd à mathématiser, mais je vais tenter (sachant qu'il est 1:40, pardonnez-moi une erreur probable). On note P_i(n) la probabilité que le mathématicien i aille dans la pièce secrète lorsque le Dr. No choisit en choisit un pour la n-ième fois. P_i vérifie la relation :

Pour tout n0, il existe une suite d'entiers u, strictement croissante, telle que n0=u(0) et pour tout entier j, P_i(u(j)) > 0

Je pense qu'il s'agit là de l'hypothèse la plus faible. Comme l'a remarqué Joun, ta solution est valide que si la lumière est initialement éteinte. Or les matheux ne connaissent pas l'état initial. Ce n'est pas très grave, l'idée générale y est, il suffit de faire une modification minime.

Maintenant, on peut compliquer le problème. On fixe la loi de probabilité. Par exemple les mathématiciens sont choisis de manière équiprobables (hypothèse irréaliste lorsque l'on connaît leur kidnappeur). On se pose maintenant la question de trouver plus rapide (en moyenne et en nombre de passages dans la salle). De meilleures stratégies sont connues, mais l'optimale ne l'est pas.

6. Le vendredi 15 juin 2007, 09:00 par Celui

C'es plus simple d'énoncer l'hypothèse ainsi : Soit Ti(n) le nombre de fois où le mathématicien i est allé dans la pièce à la lampe lorsque n mathématiciens y sont déjà allés. La limite de Ti en l'infini est l'infini.

7. Le vendredi 15 juin 2007, 13:57 par Joun

Je modifie la solution de Christophe ainsi : les mathématiciens non responsables suivent les mêmes règles, mais en plus n'allument la lumière que s'ils l'ont déjà vue allumée. Le responsable, lui, a un comportement complètement différent ; il modifie à chaque fois l'état de l'interrupteur, enlève un (à un compteur initialisé à zéro) si la lumière est éteinte lorsqu'il entre, et ajoute un si elle est allumée, sauf s'il n'a encore jamais éteint la lumière, auquel cas il ne modifie pas le compteur. Quand le compteur arrive à 99, il sait que tous les mathématiciens sont entrés dans la pièce. Je n'ai pas trouvé plus simple :)

8. Le vendredi 15 juin 2007, 17:42 par Celui

Joun, votre méthode ne fonctionne pas. Rien ne permet de dire qu'un mathématicien verra la lumière éclairée une première fois.

Prenons un cas simple. La lumière est initialement éclairée. Les 98 premiers mathématiciens passent et la voient donc. Le "compteur" (math. n°100) passe et l'éteint.
1. Le mathématicien n°1 passe et allume la lumière. Le compteur passe et l'éteint.
2. Le mathématicien n°2 passe et allume la lumière. Le compteur passe et l'éteint.
etc jusqu'au mathématicien n°98.
À ce moment-là, le Dr No change de technique :
Il fait indéfiniment :
* Il choisit un des 99 premiers mathématiciens et le met dans la pièce
* Fait passer le compteur deux fois consécutivement.

Les 98 premiers mathématiciens n'allumeront jamais la lumière puisqu'ils l'ont déjà fait.
Le compteur allumera puis éteindra la lumière.
Le mathématicien n°99 n'ayant jamais vu la lumière éclairée une première fois la laissera en permanence éteinte.

Vous cherchez une méthode trop compliquée...

9. Le vendredi 15 juin 2007, 20:56 par Joun

@Celui: J'y avais pensé, mais avais éliminé cette éventualité à cause du terme « aléatoirement » dans l'énoncé. Bon, j'y retourne, s'il y a plus simple, ça m'intéresse, parce que je sèche pour calculer le nombre moyen de passages avec cette solution.

10. Le samedi 16 juin 2007, 20:01 par Joun

Je reviens sur mon commentaire précédent, il suffit que le compteur passe toujours 2 fois de suite pour faire planter ma solution, qui n'en est donc pas une.

11. Le samedi 16 juin 2007, 20:26 par Joun

Dans la solution de Christophe, il suffit que chacun éteigne la lumière 2 fois au lieu d'1 pour ne pas être embêté par l'incertitude sur l'état initial de l'interrupteur. Ouf !!!

12. Le dimanche 17 juin 2007, 10:37 par valerio

les autres mathématiciens n'allument la lumière, 1 seule fois, que s'ils l'ont déjà vue changer d'état. Le compteur l'éteint systématiquement à part quelques changements d'état, au début et ensuite, sporadiquement.

13. Le dimanche 17 juin 2007, 10:40 par valerio

zut, la solution juste précédente de joun est plus rapide (pas vue avant: page non rafraîchie)

14. Le dimanche 17 juin 2007, 14:55 par Celui

Bravo à tous. Reposez-vous bien pour celle de la semaine prochaine qui sera foncièrement plus difficile. Et votez bien ;)

15. Le dimanche 17 juin 2007, 16:23 par Joun

Je n'ai pas trouvé d'autre solution, mais me suis intéressé au nombre moyen de passages avec celle-ci.

Supposons que i (0≤i≤98) mathématiciens aient déjà allumé 2 fois la lampe, et le compteur vient de passer dans la pièce pour éteindre la lampe.
On cherche le nombre de passages moyen pour que le compteur voit la lampe allumée de nouveau. On aura besoin des développements limités suivants : si |x| < 1,

 (1) 1/(1-x) = Σ{k=0;+inf} x^k

En dérivant

 (2) 1/(1-x)^2 = Σ{k=0;+inf} k * x^(k-1) = Σ{k=1;+inf} k * x^(k-1)

Pour alléger les calculs, on pose α = 99/100.
Soit p(n) la probabilité que le compteur éteigne de nouveau la lampe après le passage de n mathématiciens dans la salle (en toute rigueur il faudrait écrire p_i(n)).

p(1) = 0

Pour p(2), la seule solution est qu'un des 99-i mathématiciens qui n'ont pas encore allumé la lampe 2 fois peuvent le faire, et que le compteur passe juste après.

p(2) = ((99-i)/100) * (1/100)

Pour p(3), il y a 2 solutions : un des 99-i autres mathématiciens allume la lampe, puis n'importe qui d'autre que le compteur vient, puis arrive le compteur. L'autre solution est qu'undes i mathématiciens ou le compteur passent le premier, puis on se retrouve dans la configuration précédente.

p(3) = ((99-i)/100) * α * (1/100) + ((i+1)/100) * p(2)

Et ainsi de suite :

p(4) = ((99-i)/100) * α² * (1/100) + ((i+1)/100) * p(3)
...
p(k) = ((99-i)/100) * α^(k-2) * (1/100) + ((i+1)/100) * p(k-1)

On commence par calculer

S(i) = Σ{k=2;+inf} p(k)
     = ((99-i)/100) * (1/100) * (Σ{k=2;+inf} α^(k-2)) + ((i+1)/100) * S(i)

implique

((99-i)/100) S(i) = ((99-i)/100) * (1/100) * (Σ{k=0;+inf} α^k)

En utilisant la relation (1)

S(i) = 1

C'est le résultat attendu, la somme de toutes les probabilités vaut 1.
Calculons maintenant le nombre moyen de passages :

M(i) = Σ{k=2;+inf} k * p(k)
     = ((99-i)/100) * (1/100) * (Σ{k=2;+inf} k * α^(k-2)) + ((i+1)/100) * (M(i) + S(i)(i))

implique

((99-i)/100) M(i) = ((99-i)/100) * (1/100) * (Σ{k=1;+inf} (k+1) α^(k-1)) + ((i+1)/100)

En utilisant les relations (1) et (2)

Σ{k=1;+inf} (k+1) α^(k-1) = (Σ{k=1;+inf} k α^(k-1)) + (Σ{k=0;+inf} α^k)
                          = 100² + 100 = 100 * 101

Donc

M(i) = 101 + (i+1)/(99-i)

Avec le changement de variable j = 99-i (1≤j≤99)

M(99-j) = 101 + (100-j)/j = 100 + 100/j

Si la lumière est éteinte au début, chaque mathématicien doit allumer 2 fois la lampe, le résultat cherché est

 R0 = 2 * (Σ{j=1;99} (100 + 100/j))
    ≃ 200 * (99 + 5.177)
    ≃ 20835 passages

Si la lumière est allumée au début, il faut que le compteur l'éteigne. Avec le même raisonnement que ci-dessus, il est facile de montrer que cela nécessite 100 passages en moyenne. Puis les 98 premiers mathématiciens doivent allumer 2 fois la lampe, le dernier une fois seulement ; le résultat cherché est :

 R1 = 100 + R0 - M(98) ≃ 20735 passages

Chercher