Forum de mathématiques - Bibm@th.net

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

réponses vraies en majorité

Bonjour,

Ce problème, peut-être déjà posé par freddy, grand amateur de vrai-faux, qui alors voudrait bien m'en excuser :

Dans une conférence annoncée pour réunir des chimistes sont venus aussi des alchimistes. Tous se connaissent et les chimistes sont en majorité parmi les k personnes présentes
Un journaliste  décide de savoir qui est chimiste et qui est alchimiste.
Il pose donc à différentes personnes des questions du genre :" X est-il un chimiste (ou un alchimiste) ? ", ou " Êtes-vous un chimiste (ou un alchimiste)? "
Sachant qu'un chimiste répond  toujours vrai et qu'un alchimiste peut donner une réponse fausse, quel est le nombre minimal de questions que le journaliste doit poser pour déterminer qui est chimiste et qui est alchimiste ?

Donner une réponse (démontrée) pour k=15 ou une formule générale pour tout k

Cordialement

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : réponses vraies en majorité

salut

▼une réponse pour k=15

avec 15*8+7=127 questions, il est sur de savoir qui est qui! mais je doute fort que ça soit le nombre minimal!

A+

Dernière modification par amatheur (10-04-2012 15:58:02)

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : réponses vraies en majorité

re

▼plus économique

avec 15+14+13+12+11+10+9=84 questions ça marche aussi!

MathRack

Membre

Inscription : 02-04-2012

Messages : 78

Re : réponses vraies en majorité

Bonjour,

Une fois que le journaliste a trouve un chimiste, peut-il le harceler de questions? Si oui, le nombre minimum de questions est atteint lorsque le premier X est chimiste. On peut savoir que le premier X est (al)chimiste en 15 questions. Si il est chimiste, on lui demande ensuite que font les 14 autres. Donc 29 questions au minimum?

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : réponses vraies en majorité

bonsoir,

La démarche de MathRack est bonne, Oui, dès qu'on a trouvé avec certitude un chimiste.
Le raisonnement aboutit à un peu moins que 29.....

La surprise c'est qu'il y a encore mieux, avec une démonstration utilisant un algorithme de M.K. et A.L., démontrée pour tout k.
Source : Pierre Bornsztein

Cordialement

amatheur

Membre

Inscription : 02-10-2011

Messages : 299

Re : réponses vraies en majorité

salut
la proposition de MathRach traite le cas le plus favorable! mais si par malheur il y a 7 alchimistes parmi les 15 participants et que le premier sondage en 15 questions révèle un alchimiste, puis on aura à sonder 13 autres personnes, ce deuxième sondage pourrait révéler un autre alchimiste! et ainsi de suite..
alors en somme avec cette stratégie, et au pire des cas,  on aura besoin d'un minimum de 15+13+11+9+7+5+3=63 questions avant de tomber sur le premier chimiste!

Dernière modification par amatheur (10-04-2012 23:33:04)

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : réponses vraies en majorité

salut.

si un alchimiste peut mentir une seule fois, alors :

▼réponse

je prend au hazard 8 personnes parmi lesquelles je suis sur d'y découvrir au moins un chimiste ,

parmi les 8 , j'en choisis un et je l'interroge 2 fois sur chacun des 7 autres .

au pire j'interroge un alchimiste qui peut mentir une fois . mais de toute façon je trouve au moins un chimiste en 14 questions.

et si parmi les sept, je n'ai que des alchimistes , alors c'est que j'interroge un chimiste.

  et quand j'ai trouvé ce chimiste, je l'interroge sur les 7 personnes que j'ai laissées de coté . donc en 21 questions.

mais alors , si la personne interrogée a donné les memes réponses aux sept dernières questions par rapport aux sept premières ,

je dois interroger le chimiste sur son identité ; par contre s'il a menti , alors je sais que c'est un alchimiste et je dois savoir s'il a menti au début ou s'il a menti à la fin ; je dois donc me renseigner sur lui auprès du chimiste

donc 1 question supplémentaire cela fait 22  questions

  soit [tex]3\times{\frac{n-1}{2} + 1 }[/tex]    pour nimpair

soit [tex]3\times{(\frac{n}{2} - 1 ) + 2}[/tex]    pour npair  si je n'ai pas fait d'erreur.

Dernière modification par jpp (11-04-2012 06:07:44)

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : réponses vraies en majorité

Bonjour,

si un alchimiste peut mentir une seule fois, alors :

Un alchimiste peut mentir plusieurs fois et même ne pas se contredire pour tromper celui qui l'interrogerait plusieurs fois.

Les résultats de jpp sont corrects pour n pair, pas exactement pour n impair

La clé est de montrer comment on trouve un chimiste avec certitude, en utilisant le fait que les chimistes sont en majorité.
La première démonstration sur ce problème a été faite par récurrence en étendant le résultat de k = 3
Mais cette première formule obtenue est un résultat plus élevé que celui de la formule donnée par jpp pour n pair,

@jpp : Peut-être voudrez-vous justifier comment vous trouvez un chimiste avec certitude ? Ce n'est pas si facile...

Cordialement

MathRack

Membre

Inscription : 02-04-2012

Messages : 78

Re : réponses vraies en majorité

Bonjour,

On a besoin d'avoir "X répond qu'il est chimiste" pour que "X soit chimiste"...
1:"1=Chim?" => Oui
On va voir un autre chercheur:
2:"1=Chim?" => Oui
1:"2=Chim?" => Oui
Dans cette situation, ils sont tous les 2 chimistes ou tous les 2 alchimistes. On continue...
3:"1=Chim?" => Oui
1:"3=Chim?" => Oui
...
On considère un groupe de n personnes. En 2*n-1 questions et de la chance, on sait qu'elles sont toutes alchimistes ou toutes chimistes. Si la situation se présente avec un groupe majoritaire, ce sont tous des chimistes.

k=15 :
  * 8 chimistes en 15 questions.
  * les autres sont déterminés en 7 questions
  ** 22 questions pour k=15?

Pour le k général, par récurrence, et on suppose que les chimistes sont strictement majoritaires :
k impair : 3*(k-1)/2+1
k pair : 3*k/2-1

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : réponses vraies en majorité

salut.

soit: n le nombre de chercheurs,  a , le nombre d'alchimistes , c , le nombre de chimistes.

   Je sais aussi que dans le pire des cas , n = 2a + 1 c.a.d.    c = a + 1 pour  n impair

                                                                n = 2a + 2   c.a.d.   c = a+2 pour n   pair

autrement A est une réponse qui définit un alchimiste
                  C  est une réponse qui définit un chimiste.

je définis par exemple une stratégie pour n = 6 (nombre pair).

je me renseigne sur une première personne que j'appellerai X.

dans le pire des cas  pour cet exemple ,  a = 2  et c = 4

j'interroge donc parmi 5 personnes sur le métier de X .

je commence mes investications:

a) CCC me donne un chimiste en 3 questions  . je me renseigne auprès du chimiste sur les 5 autres en 5 questions de plus.

b) AAA me donne un alchimiste en 3 questions .

c) CCA me donne un chimiste en 3 questions . je me renseigne auprès du chimiste sur les 5 autres en 5 questions de plus.

d) CAA je ne peux pas conclure , je  dois donc questionner un quatrième chercheur .

        --- CAAA me donne un alchimiste , mais je sais aussi que la réponse C est donnée par le second alchimiste

        ---CAAC me donne un chimiste mais aussi  les 2 alchimistes qui ont répondu A.

je reviens sur le b) avecAAA ou je n'ai pas trouvé de chimiste. je prend les 5 chercheurs ( 4 chimistes + 1 alchimiste) .je procède de la meme façon en prenant un chercheur Y

et là , en 2 questions je sais si Y est alchimiste ou chimiste car je ne peux avoir que 3 réponses : AC ou CC ou AA

et dans ce dernier cas j'ai mon dernier alchimiste et je conclus C pour les 4 autres.

dans le cas AC  je conclus que Y est chimiste , les réponses A --> alchimiste et C --> chimiste et les 2 derniers sont chimistes.

dans le cas ou les réponses sont CC , alors Y est un chimiste  j'en suis alors à 5 questions  Y me renseigne sur 3 chercheurs
puisque qu'il ne reste plus qu'un alchimiste à trouver ---> total  8 questions maximum.

                                                                                                                                       

  j'aurais les formules suivantes: 

pour n impair : [tex]q = \frac{3n + 1}{2} - 1[/tex]    ---> n = 5 , q = 7      n = 15 , q = 22  par exemple

pour n pair : [tex]q = \frac{3n}{2} - 1[/tex] -->  n = 6 , q = 8        n = 16 , q = 23  par exemple

ma stratégie consiste bien évidemment à trouver un  chimiste , mais lorsque je découvre un alchimiste , pour le tour suivant j'ai

moins de questions à poser , et je répète le processus pour trouver un chimiste , voire le dernier alchimiste en sachant qu'ils sont au pire c - 1 pour n impair et c - 2 pour n pair.

                                                                                                               à plus

Dernière modification par jpp (13-04-2012 16:47:05)

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : réponses vraies en majorité

Bonjour,

Une piste vers une solution :

Il convient de démontrer un résultat pour toute valeur de k, nombre de participants.
La propriété à exploiter est : Les chimistes sont en majorité.

Si l'on raisonne par récurrence, on voudra montrer que le nombre maximal de questions peut rester <=(2k-3) qui est vrai pour k=3 et que l'on suppose vrai jusqu'à (k-1)

Soit k>=4 et k=2t ou k=2t+1. On groupera alors les participants par couple (Pi,Qi), i =1 à t pour les Pi et i=1 à k-t pour les Qi.
Chaque Pi est interrogé sur Qi : Est-il un chimiste ?

Si la réponse est non, il est certain qu'il y a au moins un alchimiste dans les deux, car s'il n'y en avait pas, la réponse aurait été oui.
On écarte donc (momentanément) les couples où Pi a répondu non, les chimistes restant majoritaires dans les participants non écartés.

Or dans les couples où Pi a répondu oui, si Qi est alchimiste, alors Pi aussi : Les chimistes restent majoritaires dans les Qi, ce qui permet d'utiliser l'hypothèse sur un nombre inférieur à k-t, donc de reconnaître un chimiste et d'établir la récurrence.

Ce premier résultat obtenu (sans tout détailler ci-dessus) un algorithme a été établi qui a amélioré (2k-3) et démontré que le nombre de questions peut rester <=  (partie entière de 3k/2)-1.

A+ si désiré. Cordialement

jpp

Membre

Inscription : 31-12-2010

Messages : 1 170

Re : réponses vraies en majorité

salut.

dans le cas ou n = 6 par exemple  j'ai  3 P_i & 3 Q_i

je choisis moi meme mes binomes et rien ne m'empeche de tomber  sur  P₁ &  Q₁ alchimistes

les 4 autres étant chimistes  . à la question posée aux P_i je peux très bien obtenir 3 réponses C , puisque

les alchimistes peuvent mentir . Et là , 3 questions pour presque rien . Ou plutot si , et c'est important , comme je sais qu'il y a ou 1

ou 2 alchimistes , alors , s'il y en a 2 , ils sont dans le meme binome. et s'il n'y en avait qu'un il était en P

dans ce cas là , je décale d'un rang les  Q_i et je forme donc les binomes  (A₁Q₃) ,(A₂Q₁)(A₃Q₂).

et je repose 3 questions non pas aux P_i , mais aux  Q_i dans le meme ordre et après 2 réponses

successives C_iC_j  je trouve le chimiste en Q_j  donc en 6 questions. Il me reste à interroger Q_j sur Q_j-1 &    P_j-2  , ce qui fait 8 questions

totomm

Membre

Inscription : 25-08-2011

Messages : 1 093

Re : réponses vraies en majorité

Bonjour,

Une démonstration complète est donnée par l'algorithme dû à M. Katchalski et A. Liu (Référence : page 104 –Supermath de P. Bornsztein ISBN 2711752976)

Début :
(1)    Soit S l'ensemble des participants, numérotés de 1 à k.
et 3 ensembles  A, B, C initialement vides . Continuer.

Note : toute demande sera : …est-il chimiste ?
Si C est vide, A va recevoir des couples (x, y) dont au moins un membre est un alchimiste
Si C n'est pas vide, B va recevoir des couples (y, z) dont les membres ont répondu différemment concernant un participant x bien repéré.
C va contenir les éléments dont la réponse a été oui pour un même x

(2) Si Card S <= 2, alors pour cause de majorité, chaque élément de S est un chimiste. Aller à (6).
Si Card S > 2, soit x la personne de plus petit numéro qui se trouve dans S. Continuer.

(3) Soit y la personne de plus petit numéro dans S - {x}. Demander à y si x est un chimiste.
Si la réponse est oui, aller à (5) ; sinon continuer.

(4) Si C est vide, enlever x et y de S et mettre (x, y) dans A. Retourner à (2)
Si C non vide, soit z la personne de plus haut numéro dans C. Enlever y de S et z de C et mettre (y, z) dans B. Retourner à (3).

(5) enlever y de S et le mettre dans C.
Si Card S - Card C > 2, retourner à (3).
Si Card S - Card C <= 2, alors pour des raisons de majorité dans S U C,  x est un chimiste.
Pour chaque personne de S U C - {x}, demander à x si cette personne est un chimiste. Continuer.

(6) Pour chaque personne de A, demander à un chimiste identifié en (2) ou (5) si cette personne est un chimiste.
Pour chaque couple (y,  z) de B, il existe x au sujet duquel y et z sont en désaccord.
De plus, x n'est pas élément de B donc sa qualité est déterminée. Ainsi, y ou z est un alchimiste identifié par sa mauvaise réponse sur x. Demander au  chimiste ci-dessus si celui de y ou z non encore identifié est un chimiste.
Fin de l'algorithme

Il faut remarquer qu'aucun couple de A U B n'est formé de deux chimistes.  Enlever 2 éléments de S U C en (4) ne change donc pas le fait que les chimistes sont en majorité dans SUC (ce qui valide l'argument utilisé en (2) et en (5)).
L'algorithme s'arrêtera nécessairement, car le cardinal de S décroît strictement.

Supposons qu'à la fin on ait a paires dans A, b paires dans B, c personnes dans C, s personnes dans S.
• Si l'algorithme s'arrête via (2), alors c=0 et s>=1 ;
le nombre de questions posées dans (3) est a + 2b, alors qu'il est de 2a + b dans (6). Or 2a + 2b + s=k, donc :
(a+2b)+(2a+b) <=  k+(partie entière (k/2)-1 =(partie entière de 3k/2)-1

• Si l'algorithme s'arrête via (5), alors s-c >=1 et donc c <= (partie entière de (s+c) / 2 )
Le nombre de questions posées en (3) est a + 2b + c, en (5) il est de  c+s-1 ; alors qu'en (6), on utilise 2a+b questions, or 2a+2b + c+s = K,
(a + 2b + c) + (c + s - 1) + (2a + b) <= k+(partie entière (k/2)-1 =(partie entière de 3k/2)-1

(Publié avec l'autorisation des éditions Vuibert)