On ne peut pas toujours gagner

Pas de proposition indécidable ? Nous ne pensons pas au même professeur christophe c...

amicalement,

e.v.

C'est une variante de l'énigme des 200 prisonniers, non ?
http://www.les-mathematiques.net/phorum/read.php?9,1120265,1125743#msg-1125743

On peut garantir 50% de chances de gagner avec une méthode très simple. Qui dit mieux?

3 chances sur 4

Alors probabilité de gagner est $1- \frac 1 {2^n}$

La solution de "l'énigme des cocus" s'adapte.

@cc : avoir les yeux bleus dans l'énigme des prisonniers $\leftrightarrow$ avoir une proposition vraie sur son dos.

Je ne sais pas... Une réponse brouillonne :

C'est un peu compliqué. la distribution de VRAI/FAUX est équiprobable, cela signifie-t-il qu'il y a autant de propositions vraies que de fausses ? Non, sinon le test serait trop facile. Il suffirait d'avoir un excès de VRAI pour répondre FAUX et un excès de FAUX pour répondre VRAI.

En fait qu'une proposition soit vraie ou fausse revient à considérer une loi binomiale. Imaginons qu'il y ait $n$ élèves dans la salle.

Le premier élève qui répond (il en faut au moins un) doit faire un test. Supposons que $k$ élèves aient V (proposition vraie) et $n-1-k$ ont F (proposition fausse) puisqu'on suppose que tout le monde est un génie. La probabilité que ce $n$-ième élève aie une proposition VRAIE est alors égale à :
$$\binom{n}{k+1}\left(\dfrac{1}{2}\right)^n$$
La probabilité que cet élève aie une proposition fausse est égale à :
$$\binom{n}{k}\left(\dfrac{1}{2}\right)^n$$
Ça c'est dans l'absolu. L'élève n'a qu'à choisir la probabilité la plus grande de ne pas se tromper.

Maintenant il lui faut trouver en réalité la probabilité $P_{k,n-1}(V)$ et $P_k(F)$ où $P_{k,n-1}$ désigne la probabilité « sachant que $k$ élèves portent une proposition vraie. Dans ce cas :
$$ P_{k,n-1}(V)=\dfrac{P((k,n-1)\cap(k+1,n))}{P(k,n-1)}$$
et
$$ P_{k,n-1}(F)=\dfrac{P((k,n-1)\cap(k,n))}{P(k,n-1)}$$
Cette esquisse n'est pas très bonne mais il y a quelques formules. Ceci dit, un des élèves va devoir répondre et il ne pourra le faire qu'en utilisant une probabilité conditionnelle il me semble. Si une preuve exacte des chances raisonnables de succès existe (ie $1-\frac{1}{2^n}$, c'est quand même bien, cela signifie que quand $n$ tend vers l'infini, le jeu est gagné d'avance).

PS : j'ajouterai que si les élèves ne répondent jamais, ils ne perdent pas. Enfin la probabilité $1-\frac{1}{2^n}$ correspond au complémentaire de l'évènement : « toute la classe est déclarée matheuse en disant VRAI ou FAUX au hasard ». Ça me paraît très optimiste tout de même... Ça voudrait dire que si un seul de ces élèves savait à l'avance si son dossard est 0 ou 1, la classe gagne. Est-ce bien le cas ?

Bon comme l'ordre de passage est imposé (alphabétique) voilà la stratégie en 3 tours à laquelle j'avais pensé :

Au premier tour, chaque élève passe son tour sauf si tous ceux qui le précèdent ont une affirmation vraie. Si le premier est dans ce cas, il dit qu'il a une affirmation fausse. Le dernier à parler passe son tour si le premier a une affirmation vraie et qu'il a passé son tour.
A l'issue de ce premier tour, si le premier a une affirmation vraie ainsi que tous ceux qui le précèdent (probabilité $\frac 1 {2^n}$), la classe a perdu.
Sinon, tous ceux qui ont parlé ont dit vrai et le premier sait s'il a une affirmation vraie ou fausse.

Au 2ème tour, chacun passe son tour si celui qui le précède a une affirmation vraie, sinon il parle.
A l'issue de ce 2ème tour, tout le monde sait si son affirmation est vraie ou fausse.

Au 3ème tour chacun parle et dit si son affirmation est vraie ou fausse.

1) Il n'y a pas de stratégie gagnante à 100%
En effet, une telle stratégie impliquerait que le premier interrogé passe son tour (car étant le premier à parler, il n' a aucune information quant à la véracité de son affirmation, il ne peut donc que répondre au hasard à ce sujet) mais alors le problème se retrouve au niveau n-1. A la fin si personne n'a parlé, c'est comme si on recommençait le jeu à zéro.

2) On ne peut pas améliorer le résultat probabilité de gagner $p =1- \frac 1 {2^n}$
En effet une stratégie consiste à associer à chaque distribution possible des affirmations (il y en a $2^n$ et elles sont équiprobables) le résultat ''la classe gagne en adoptant la stratégie'' ou ''la classe perd en adoptant la stratégie''
Donc la probabilité de gagner $p$ est un nombre de la forme $\frac k {2^n}$, $k \in \N$, $0 \le k \le n$
Or il est $< 1$ (voir1 )), donc il vaut maximum $1- \frac 1 {2^n}$

Edit : comme 1) n'est pas clair (voir post d'aléa juste après ) je redis un peu autrement :
Dans une stratégie à 100% :
le 1er n'a aucune info donc il ne peut être sûr, il passe son tour
le 2ème n'en a aucune non plus du coup (le fait que le 1er passe n'en est pas une) donc il passe forcément
le 3ème n'a lui non plus aucune info (puisque 1 et 2 passent forcément) donc il passe
etc..
de proche en proche, ils passent tous juqu'au dernier
Une stratégie gagnante à 100% ferait passer tout le monde au 1er tour, ce qui fait un premier tour pour rien, idem au deuxième tour (on recommence comme si il ne s'était rien passé) et ainsi de suite. Absurde.