Discussion :

[Celelibi]

Bonjour,

Je me suis penché sur le problème de la célébrité et sa solution en 2N tests.

Pour ceux qui ne connaîtraient pas ce problème, il peut s'énoncer comme ça :
Soit un ensemble de N personnes parmi lesquelles figure peut-être une célébrité. Une célébrité est défini comme étant une personne que tout le monde connaît mais qui ne connaît personne.

On peut représenter ce problème sous forme d'une matrice NxN remplie comme suit. Si la personne de la j-eme colonne connaît la personne de la i-eme ligne, alors l'élément d'indice (i, j) est un 1, sinon c'est un 0.

Par exemple :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
   1  2  3  4  5
 
1  0, 1, 1, 0, 0
2  1, 0, 1, 0, 0
3  0, 0, 1, 0, 0
4  1, 1, 1, 1, 1
5  1, 1, 1, 0, 1

La personne numéro 2 connaît la personne numéro 1 mais ne connaît pas la personne numéro 3.

Chercher la célébrité (elle est forcément unique) revient à chercher dans la matrice un n tel que la n-ième ligne soit remplie de 1 et la n-ième colonne remplie de 0. (Bien évidemment sans s'occuper de savoir si on se connaît soi-même.)

Notre prof nous a indiquer comment procéder pour trouver la célébrité avec un maximum de 2N questions.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
Soient A et B deux personnes prises au hasard dans la foule
Si A connaît B alors
    A n'est pas la célébrité
sinon
    Si B connaît A alors
        B n'est pas la célébrité
    sinon
        A n'est pas la célébrité
    fin si
fin si

C'est là que commencent mes problèmes :
Si j'ai bien compris, à chaque itération on élimine une des deux personnes. Mais je ne comprend pas comment cet algorithme peut garantir qu'une fois terminé la personne restante est bien la célébrité sachant qu'on est pas sûr qu'il y ait une célébrité dans l'ensemble.

De plus je ne comprend pas pourquoi la deuxième question est indispensable car si A connait B, alors A n'est pas la célébrité, mais si A ne connait pas B, alors B n'est pas la célébrité.

Et aussi, je ne vois pas comment on peut peut-être trouver la célébrité en moins de 2N tests puisque à supposer qu'on tombe directement sur la célébrité, il faudra dans le pire des cas 2N tests pour vérifier qu'on est bien tombé sur la célébrité.


J'aimerais comprendre où mon raisonnement est faux.


Merci d'avance
Celelibi

[Nemerle]

D'accord avec toi. Pour moi, c'est par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
Soient A et B deux personnes prises au hasard dans la foule
Si A connaît B alors
    A n'est pas la célébrité
sinon
    B n'est pas la célébrité
    si B ne connait pas A
       A n'est pas la célébrité
    fin si
fin si

[souviron34]

l'énoncé est faux...

Forcément la personne se connait elle-même..

Donc il faut trouver une ligne ou il y a 1 seul 1 en position diagonale et une colonne avec que des 1 (ou l'inverse ça dépend comment on crée la matrice) passant à cette colonne (ligne respectivement). ici la personne 3

[souviron34]

Donc le pseudo algo est :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
Pour toutes les personnes i
   c'est une celebrite 
   Si i different de j et i connait j
       alors pas une celebrite
       sortie de si
   fin si
   si celebrite
        indicateur = 0
        pour toutes les personnes j
        si j connait i
            indicateur = indicateur + 1
        fin si
        si indicateur different de nombre de personnes
             alors pas une celebrite
        fin si
        si celebrite sortie de pour
    fin si
fin pour

Au maximum 2*N passages...

[souviron34]

désolé c'est pas en 2*N.. Je vais réfléchir un peu...

[souviron34]

tu es sûr que ce n'est pas N^2 ??

Il faut au moins passer une fois par ligne....

même si on ne teste pas la diagonale, ça fait quand même N*(N-1)....