salut

cet enoncé me semble un peu vague , 12 personnes choisies au hasard ..daccord mais à partir de quel groupe de personnes , si je prend 12 personnes au hasard sur le territoire il se peut bien que A et B ne soient pas connues des 10 autres personnes (exactement 5 personnes je ne comprend pas pourquoi ?)

Bonjour.
Je suppose que la relation « connaître » est une relation d'équivalence.
Dans ce cas :  

 Cliquez pour afficher

Soit M le nombre de personnes dans une des classes d'équivalence ayant le plus grand nombre d'éléments.
Si M7 on prend A et B dans cette classe et il y a bien cinq autres personnes qui connaissent A et B.
Si 1<M<7 on prend A et B dans cette classe et les personnes en dehors de cette classe sont plus de  cinq et ne connaissent ni A ni B.
Si M=1 on prend A et B au hasard et il y a dix personnes qui ne connaissent ni A ni B.

Bonjour

Je ne pense pas que la relation "connaître" soit une relation d'équivalence

Imod

Il y a certainement une astuce qui tue le problème mais même dans le cas de 4 personnes où on chercherait quelqu'un qui connaisse A et B ou n'en connaisse aucun , il faut différencier les cas .

Imod

Bonjour,

@verdurin : je confirme ce qu'écrit Imod. Ce n'est évidemment pas une relation d'équivalence ne serait-ce que parce qu'elle n'est pas transitive. Si X connaît Y et Y connaît Z, on ne peut pas dire que X connaît Z.

@flight : Il faut comprendre l'énoncé  comme : "Soit 12 personnes, montrer que [etc...]". L'ensemble où l'on sélectionne les personnes peut-être la planète entière par exemple, ou même un ensemble infini de personnes.

@Imod : La difficulté vient du fait qu'il y a des tas de façons de choisir 2 personnes. Prouver l'existence par "construction" me semble effectivement très difficile, mais étudier les cas "n faibles" peut donner des intuitions.

salut

dans l'ensemble C des 10 personnes considérons les ensembles A et B des personnes qui connaissent A et des personnes qui connaissent B

je note E* l'événement contraire de E dans C

 Cliquez pour afficher

d'une part on a : Card (A B) = Card A + Card B - Card (A B)

d'autre part Card (A B) + Card (A* B*) = 10


première idée :

soit Card (A B) 5 et c'est fini : au moins 5 personnes connaissent A et B

soit Card (A B) < 5 et alors  Card (A B) > Card A + Card B + 5


deuxième idée :

soit Card (A* B*) 5 et c'est fini : au moins 5 personnes ne connaissent ni A ni B

soit Card (A* B*) < 5 et alors  Card (A B) 6 donc 6 + Card (A B) Card A + Card B 20

plus d'idée ...

C'est vrai qu'il était un peu bête de penser que la relation « connaître » est une relation d'équivalence.

 Cliquez pour afficher

On peut considérer le graphe, non orienté, de la relation.
Si il n'est pas connexe et que la plus grande partie connexe a au plus 10 sommets c'est gagné : on choisi A et B, avec des précautions éventuelles, en dehors de cette partie et il y a au moins 5 sommets qui ne sont reliés ni à A ni à B.
Il reste à examiner le cas d'un graphe connexe et celui où on a un graphe connexe à 11 sommets et un élément isolé.
Le second cas est facile, mais je n'ai pas encore d'idée vraiment précise pour le premier.

Je penche plus vers l'approche ensembliste de Carpediem qu'à celle de Verdurin , mais ce n'est qu'un avis

On peut ajouter à sa présentation que les relations connaître ou ne pas connaitre sont antagonistes , on peut donc supposer sans problème qu'au moins 6 personnes en connaissent au moins 5 et chercher deux individus partageant 5 connaissances .

Imod

Vu que la relation est symmétrique, on peut écrire aussi que dans tout ensemble de 12 personnes, il y a au moins deux personnes (A et B) qui ont 5 connaissances en commun ou qui ont 5 non-connaissances en commun.

Je ne sais pas si ça va marcher mais une approche récursive serait que dans tout groupe de 2n+2 personnes, il a au moins deux personnes qui ont n connaissances en commun ou n non-connaissances en commun.

C'est vrai pour le cas n=0: il n'y a que 2 personnes et elles n'ont personnes en commun.
C'est vrai pour n=1: il y a 4 personnes (A,B,C,D), Si A connait D alors B ne peut connaitre D (sinon la paire A,B est valide). Du coup, si C connait D alors la paire (A,C) est valide, sinon la paire(B,C) est valide.
Ça a l'air de marcher pour n=2 mais ça se complique vite.

Bonsoir
Voir peut-être la théorie de Ramsey.

Bonjour

Je ne connaissais pas cette théorie. Mais il s'avère en effet que le problème peut se conclure avec le principe des tiroirs. Reste à trouver quoi denombrer...

La théorie de Ramsey est un peu plus compliquée que le principe des tiroirs

On peut aussi penser au double comptage mais de toutes façons le problème n'est pas facile . Tu as une solution ?

Imod

Bonjour

Oui j'ai une solution assez simple (enfin... quand on l'a devant les yeux ) et qui exploite le principe des tiroirs. Je publierai la semaine prochaine.

Il n'y a pas d'urgence , la plaisir est dans la recherche

Imod

Bonjour,

Voici un indice sous la forme de deux questions intermédiaires.

 Cliquez pour afficher

1-Soit C₀ une personne qui a k connaissances, combien de triplets de la forme (A,B,C₀), tels que:
- soit C₀ connaît A et B,
- soit C₀ ne connaît ni A ni B,
peut-on former (en fonction de k) ?

2-Minorer cette expression.

L'indice n'est clairement pas de trop

Voilà où j'en suis , le côté proba ne me satisfait pas vraiment , je suppose que c'est là qu'il faut ouvrir les tiroirs  

Notons AB = 1 ou 0 selon que A et B se connaissent ou pas  . Si C connait k personnes , le nombre de triplets {A,B,C} tels que AC=1 et BC=1 est égal à (k²-k)/2 et celui ou AC=0 et BC=0 à (k²-21k+110)/2 . Le nombre total de triplets qui satisfait l'une des conditions est donc k²-11k+55=(k-5,5)²+24,75  qui est au supérieur ou égal à 25 .  Avec les 12 personnes on peut former 66 paires {A,B} , donc en moyenne on peut trouver à chaque point C au moins 25/66 = 0,378787…  paires convenables . Comme il y a 12 points , C va pouvoir s'associer en moyenne avec au moins 12X25/66 = 50/11=4,54545… paires {A,B} et l'une d'entre elles devra s'entendre avec 5 d'entre eux .

Imod

Bonjour,

Et BRAVO Imod pour cette solution !

Celle que j'ai utilise des paires et des triplets ordonnés, et n'utilise pas la notion de moyenne, mais ça conduit à des calculs très similaires.
Je poste quand même :

1- Il existe 12*11=132 façons de choisir deux personnes distinctes ; dans cette modélisation l'ordre importe donc (A,B) est différent de (B,A).
2- Appelons E l'ensemble des triplets de la forme (A,B,C) tels que : soit C connaît A et B, soit C ne connaît ni A ni B. A, B et C sont 2 à 2 différents; l'ordre importe ici puis que C n'a pas le même rôle que A et B.

L'idée est de montrer que |E| est strictement plus grand que 4*132, et de conclure par le principe des tiroirs.

Prenons une personne fixée C0 parmi les 12. On suppose que C0 connaît k personnes (0k11).
Donc, pour former un triplet de E de la forme (A,B,C0), on a f(k)=k(k-1) + (11-k)(10-k) choix possibles pour A et B.
La fonction f(x)=x(x-1) + (11-x)(10-x) est minimale pour x=5.5. On peut le voir par "symétrie" car f(x)=f(11-x) ou en dérivant façon classique.
Donc, pour un C0 fixé, le nombre de triplets de la forme (A,B,C0) est inférieur à f(5.5)=2*5.5*4.5 = 49.5.
Or, il y a 12 façons de sélectionner une personne "C0". Donc |E|<12*49.5=594=4.5*132

Le principe des tiroirs permet de conclure : 132 couples de la forme (A,B) possibles (tiroirs) et plus de 594 (4*132) triplets de la forme (A,B,C) (les chaussettes) tels que C connaît A et B ou que C ne connaît ni A ni B. Donc il existe bien un couple (A0,B0) tel qu'on peut trouver plus de 5 personnes "C" qui soit connaissent A0 et B0, soit ne connaissent ni A0 ni B0.

Généralisation :
En appliquant le même raisonnement à N personnes on peut montrer qu'il existe 2 personnes telles que parmi les autres, il existe floor(N/2)-1 personnes qui soit connaissent A et B, soit ne connaissent ni A ni B.

À bientôt