Mathématiques - Groupe d amis

Groupe d amis
(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)

Posted by: ffpower

On a un groupe de 2007 personnes,telle que a chaque fois qu on en prend 2,elles ont un et un seul ami en commun.Montrer qu il y a un "président" qui est l ami de tout le monde..(L amitié étant considérée comme réciproque hein)
(Plus précisément,la seule configuration est la suivante:le président qui a invité 1003 couples d amis,les differents couples ne se connaissant pas..)

Petite indic pour ceux qui veulent(mais je pense que c est dur sans):
Commencez par montrer que si 2 personnes ne sont pas amies,alors elles ont meme le nombre d amis(en espérant etre clair lol)

Posted by: Imod

Amusant ! Je regarde de plus près ce soir

Imod

Posted by: thekingoflove

le new compte ou pas

Posted by: ffpower

Qu est ce tu entend par "le new"?

Posted by: thekingoflove

moi méme mon cher ami

Posted by: lapras

c'est de la triche si je fais un programme qui me donne le tableaux des amis ?
apres tout meme a la main théoriquement on a un nombre fini de cas a traiter :)

Posted by: ffpower

lol,c est effectivement un moyen,mais c est pas trés drole..De plus ma méthode a le mérite de marcher avec beaucoup d autres nombres que 2007...

Posted by: lapras

Ok.
C'est vrai que c'est plus marran (quoique chercher le bon algo peut etre pas mal)
déja le nombre de personnes doit etre impair
j'aurais voulu par récurrence forte mais bon, pas sur !

Posted by: thekingoflove

amitié étant considérée comme réciproque hein

enfaite ami sig koi pour vous

Posted by: lapras

es ce que une personne A est considérée amie avec elle ?
je suppose que nan

Posted by: ffpower

Tu suppose bien,ya pas de narcissique ou de schiso^^

Posted by: thekingoflove

je n'est rin compris

Posted by: raito123

Citation:

Posté par thekingoflove

amitié étant considérée comme réciproque hein

enfaite ami sig koi pour vous

Ami sig koi pour vous!!!??

Posted by: fati

hein!!? c'est quoi ça! je pige plus rien moii!!

Posted by: thekingoflove

moi non plus

Posted by: ffpower

Bon,je vais tacher d expliquer plus clairement alors...Donc on a un groupe de 2007 personnes,jusque la ok.Quand on prends 2 personnes,soit elles sont amies,soit elles le sont pas,toujours ok?On suppose maintenant que l on a une propriété bien particulieres:

si on prend 2 personnes parmi ces 2007,disons a et b,alors a a un certain ensemble d amis A,b a certain ensemble d amis B..On suppose que $A\cap B$ est toujours réduit a un point,peu importe le choix de a et b

Il faut alors montrer que dans un groupe de 2007 personnes vérifiant une telle propriété,il y a forcément un gars qui est l ami des 2006 autres,ce en s aidant de l indic...

Bon ché pas si j espere avoir été plus clair maintenant,car je vois pas trop comment réexpliquer ca(si c est toujours pas clair,merci de poser des questions plus précises)

Posted by: thekingoflove

donc tu essassye de fair sa avec de la probabilité le problem c'est l'absence d'un facteur logique

Posted by: aviateurpilot

Citation:

Posté par ffpower

Bon ché pas si j espere avoir été plus clair maintenant,car je vois pas trop comment réexpliquer ca(si c est toujours pas clair,merci de poser des questions plus précises)

voila une autre facon pour expliquer

Citation:

soient $3$ S=\{p_i|i\in\{1,2,...,2007\}\}$ un ensemble fini de personnes.
R une relation tel que: $3$ xRy$ <=> $3$ x$ et $y$ sont des amis
et pour $i\in[|1,2007|]$ $A_{p_i}=\{p_j|\ p_jRp_i\}$
sachant que $\forall i\neq j\in[|1,2007|]:\ card(A_i\cap A_j)=1$
montrer que $\exists i\in[|1,2007|]:\ \{p_i\}=\bigcap_{j=1,j\neq i}^{2007}A_j$

voila le debut de mon raisonnement, je suis presque sure que ce raisonnement va donner klk chose, lool

on a $\forall i\neq j\in[|1,2007|]:\ card(A_i\cap A_j)=1$
donc $\forall i\in[|1,2007|]:\ A_i\neq\emptyset$
on prend $n=max\{card(A_i)|i\in[|1,2007|]\}$
soit $A_g=\{p_1,p_2,...,p_n\}$
si $n<2006$ alors $\exists i\in[|1,2007|]:\ p_i\not\in A_g\cup\{p_g\}$
$\forall j\in[|1,n|]$ on prend $A_i\cap A_j=\{{p'}_i\}$
si pour $a\neq b\in[|1,n|]:\ p'_a =p'_b$ alors $\{p_g,p'_a\}\subset A_a\cap A_b$ (imppossible)
donc $card(\{p'_1,p'_2,...,p'_n\})=n$ et on a $\{p'_1,p'_2,...,p'_n\}\subset A_i$ et $card(A_i)\le n$
donc il est evident que $A_i=\{p'_1,p'_2,...,p'_n\}$
maintenant on peux prendre sans perte de generalité $\{p_1\}=\{p'_2\}=A_g\cap A_i$
je continue apres, mais si klk'un a remarque une absurdité dans le fait que $n<2006$ j'aurai le plaisir de la voire

j'ai meme montrer que $n=2k$ est pair
et qu'on peux ecrire $A_g$ de cette facons $A_g=\{(p_1,p_2),(p_3,p_4),...,(p_{2k-1},p_{2k})\}$ tel que $p_{2j-1} R p_{2j}$ et 2 couple ne se connaissent pas.

Posted by: ffpower

Je pense que ce début semble prometteur effectivement.
Juste un petit truc dans ta reformulation:ce qu il faut montrer c est qu il existe i tel que $\bigcap_{j\neq i} A_i=\{p_i\}$ .Car comme me l a fait remarqué lapras,personne n est ami de lui meme donc on n a jamais $p_i \in A_i$ .Et du coup,ce qu il faut montrer c est qu on ne peut avoir $n<2006$ .Mais ca ne change pas grand chose a ce que tu as fait.
Bonne chance,tu vas p-e meme trouver une autre solution que la mienne

Posted by: Imod

J'ai commencé à jetter un coup d'oeil , c'est clairement un problème de théorie des graphes dont les solutions sont presque toujours courtes et limpides mais certainement pas simples . Je continue à regarder à mes temps perdus .

Imod

Posted by: lapras

par réccurence on peut obtenir un truc je suppose
regardons pour n = 5 personnes
on a les personnes A, B, C, D, E
A ami avec B
C ami avec D
E ami avec tout le monde
cette situation marche (facile a vérifier)
pour n+2 personne, on fait en sorte que les deux personnes de plus soient amis entres elles et aussi amis avec E.
cette situation marche
donc par récurrence forte on démontre qu'il existe tjrs un gars ami avec tout le monde ?
pas sur...

Posted by: bruce.ml

Bon je me lance,

edit : une clique de longueur n est un ensemble de n sommets dans lequel tous les sommets sont reliés entre eux.

re edit : une clique de longueur 3 n'est rien qu'un cycle de longueur 3 c'est à dire "un triangle". Une clique de longueur 4 est un quadrilatère convexe avec ses deux diagonales.

considérons tout cela comme un graphe à 2007 sommets, les sommets représentent les invités, les arrêtes la relation d'amitié.
Chaque sommet est dans une clique de longueur 3, car si on prend deux noeuds dans ces trois là, il faut qu'il y ait une et une seule personne qui connaisse les deux. De plus, chaque arrête est sur une clique de longueur 3, car les sommets qu'il joint doivent être sur une clique de longueur 3. Et il n'y a pas de clique de longueur supérieure à 4, sinon deux personnes sur cette clique auraient 2 amis communs. Il n'y a donc QUE des cliques de longueur 3.
Par ailleurs, le graphe est connexe, si deux cliques de longueur 3 on 2 sommets communs, cela fait une clique de longueur 4, c'est donc impossible : deux cliques différentes ont donc un et un seul sommet en commun.
Il reste à montrer que ce sommet est commun à toutes les cliques. On peut raisonner par recurrence sur le nombre de cliques : s'il y en a 2 c'est ok, sinon, si on a (n-1) cliques ayant un sommet commun A. Considérons deux cliques dans ces (n-1) : ABC et ADE, et la nème clique : FGH. On suppose qu'on la relie au reste par le point F, sur la clique ABC. On a donc soit F=A, soit F=B (le cas F=C est symétrique). si F=B, les sommets E et G n'ont pas d'ami commun. CQFD

Posted by: raito123

Bonsoir bruce.ml,
tu peux s'il te plaît faire un petit dessin?
merci

Posted by: bruce.ml

Salut Raito,

je ne suis pas un spécialiste des dessins informatisés, prends un papier et un crayon et dessine ce dont je parle pour t'en convaincre :) sinon demande moi où tu ne comprends pas.

Posted by: ffpower

lapras:tu n as pas prouvé grand chose j ai l impression.juste qu il existe une configuration a 2007 personnes verifiant les hypotheses demandées avec un president..

Bruce:l idee semble sympa(bien que rien a voir avec ma methode),mais je suis pas sur que ta reccurence marche.Rien ne dit a priori que si tu as 2n+1 personnes verifiant les hypotheses du probleme,qu alors on peut en enlever 2 tel que les 2n-1 personnes restantes verifient les memes hypotheses..(a savoir que a chaque fois qu on en prend 2 elles ont un ami commun parmi les 2n-1 personnes restantes).Il faudrait prouver qu on peut trouver parmi les 2n+1 personnes un couple d amis tel que chacun des 2 a exactement 2 amis(a savoir l autre gars du couple et l ami commun aux 2)

Posted by: bruce.ml

je ne comprends pas trop ta dernière phrase, sinon ma preuve semble bien fonctionner !

Posted by: raito123

slt bruce.ml,
peut-être la difference de langue qui fait que je comprend pas bien ce que tu veux dire par un graphe à 2007 sommets! et comment un sommet peut avoir une forme triangulaire?
merci

Posted by: ffpower

J avoue ne pas avoir été clair^^.Je vais expliquer plus clairement:

je dirai qu un groupe de gens vérifie (p) si a chaque fois qu on en prends 2,ils ont exactement un ami commun

Voila en gros ce que tu fais:tu as un groupe de 2n+1 gars qui vérifie la propriété (P),tu en prends 2n-1,tu dis qu il y a un président parmi eux puis tu en déduis que c est un président pour les 2n+1 persones

Seulement,pour utiliser la propriété de reccurence,il faut que tu prouve que 2n-1 vérifie la propriété (P),ce que tu n as pas fait..

Voila,je pense que c est plus clair.Ca me fait vraiment penser a la fausse demo du grand classique:
"Montrer que si on a n points tel que toute droite passant par 2 points passe par un 3eme point,alors ils sont tous alignés.."
Fausse demo:reccurence sur n..C est vrai pour n=1,2,3..Soit n plus grand que 4.On prend n-1 points parmi les n,par l hypothese de reccurence ces n-1 points sont tous sur une meme droite,puis le point restant est aligné avec 2 autres points donc est lui aussi sur la meme droite,et donc les n points sont alignés...

Posted by: raito123

slt ffpower,
j'ai compris ce que tu voulais dire!!!
Cependant j'arrive pas à comprendre ce que buce.ml voulais dire avec le graphe?(j'arrive pas à le dessiner!!)

Posted by: bruce.ml

Je ne vois pas en quoi ta preuve est fausse ff. La propriété semble être juste, tu as peut être fait une erreur dans ton énoncé.

Sinon Raito regarde ici pour avoir les définitions de base sur les graphes

Posted by: Imod

Citation:

Posté par ffpower

"Montrer que si on a n points tel que toute droite passant par 2 points passe par un 3eme point,alors ils sont tous alignés.."
Fausse demo:reccurence sur n..C est vrai pour n=1,2,3..Soit n plus grand que 4.On prend n-1 points parmi les n,par l hypothese de reccurence ces n-1 points sont tous sur une meme droite,puis le point restant est aligné avec 2 autres points donc est lui aussi sur la meme droite,et donc les n points sont alignés...

Bruce ,

la propriété est juste , bien sûr , mais pas la démonstration .

Imod

Posted by: bruce.ml

Ah je ne m'attendais pas à ce qu'on fasse une preuve fausse d'un truc vrai. Il y a moyen de la rendre juste assez simplement quand même, enfin il me semble, j'y rêflechis ;)

Posted by: Imod

Citation:

Posté par bruce.ml

J'y réfléchis ;)

Ne cherche pas trop longtemps , c'est un problème très difficile ( mais la solution est courte et simple ) .

Imod

Posted by: bruce.ml

Hum en fait la propriété est fausse. Soient A, B et C 3 points distincts non alignés, et D=A, E=B, F = C. Ces 6 points vérifient la propriété, et ne sont pas tous alignés. Il faut ajouter "distincts" pour que ce soit juste me semble-t-il.

Posted by: ffpower

Effectivement,j ai oublié de dire qu ils devaient etre distincts..

Posted by: Imod

Citation:

Posté par bruce.ml

Hum en fait la propriété est fausse. Soient A, B et C 3 points distincts non alignés, et D=A, E=B, F = C. Ces 6 points vérifient la propriété, et ne sont pas tous alignés. Il faut ajouter "distincts" pour que ce soit juste me semble-t-il.

Six points qui en font trois , de mon temps on appelait ça enc... les mouches : dans tout texte mathématique ou autre il y a toujours une part d'implicites . Si on veut tout dire rigoureusement on ne s'exprime plus que par logique formelle et là , c'est sans moi

Imod

Posted by: bruce.ml

Citation:

Posté par Imod

Imod

Je suis d'accord sur le fait qu'il n'y a QUE la logique formelle qui permet d'être certain à 100% du sens d'un texte. En revanche, éssayons quand même qu'il y ait le moins possible de choses implicites dans un texte mathématiques, ajouter le mot "distincts" ne coute pas grand chose.

Posted by: Imod

Et la solution au nouveau problème ou à l'original ?

Imod

Posted by: ffpower

Ouais,je suis d accord,il est temps de revenir a nos moutons...Je pensais pas faire toute une histoire avec le "probleme de sylvester",c était juste pour expliquer en quoi sa reccurence ne marchait pas lol

Posted by: Help

Pour revenir à nos amis. Une piste que j'ai commencé et qui me semble prometteuse (un peu lourde, donc je compte sur vous pour pouvoir simplifier) :

Je considère a0 un de ceux qui a le plus d'amis (il peut être le seul, mais à ce stade on ne peut pas le dire) et je les appelle les ai (a1, a2, ...)

A partir de là, j'appelle ennemis ceux qui ne sont pas amis avec a0.
Supposons que a0 a au moins un ennemi (e1) (s'il n'en a pas c'est terminé...)
Alors a0 a un ami commun avec e1, que je nomme a1
et a1 a un ami commun avec a0 que j'appelle a2

e1 et a1 ont un ami commun : pas un ai (car alors a1 et ai seraient 2 amis communs de a0 et e1), c'est donc un ennemi : e2

Donc a1 a déjà 4 amis : a0, a2, e1 et e2

Comme a0 fait partie de ceux qui ont le plus d'amis, a0 a lui aussi au moins 4 amis. Donc a3 et a4 existent.

Quand je continue sur cette voie-là, j'arrive à montrer que a1 ou e1 ont au moins 5 amis.
Donc a0 doit en avoir au moins 5 aussi.

Je pense qu'il y a matière à prouver que quelque soit le nombre d'amis de a0, cela conduira a1 ou e1 a avoir plus d'amis et que c'est donc impossible.

La seule hypothèse de départ (a0 avait au moins un ennemi) serait ainsi invalidé et on résoudrait le problème.

Posted by: ffpower

J ai compris ce que tu as fait,mais il faut trouver une organisation globale si tu veux poursuivre l idée,car tu pourras pas bidouiller ainsi jusqu au 2007 gens(enfin si tu pourrais,mais bonne chance alors

)

On peut prouver assez facilement que e1 a autant d amis que a0(c est ce qu a fait aviateurpilot) mais ca suffit pas..

Posted by: Help

En fouillant un peu sur le web, j'ai découvert que ce problème est en fait plus connu sous le nom de "théorème de l'amitié". Théorème qui a été démontré.
Je ne vais pas recopier la démonstration ici (la marge est trop petite...)
La conjecture porte maintenant sur l'existence de tels graphes avec des chemins entre chaque sommet de longueur exactement égale à l (l>2).

Posted by: ffpower

Tricheur lol..

Posted by: Imod

C'est en effet un des résultats "magiques" développé dans "Raisonnements divins" de Martin Aigner et Günter M. Ziegler ( un beau cadeau de noël pour ceux qui n'auraient pas encore fait leur choix ) .

Imod

Posted by: raito123

Ah! oui c'est interressant ce que j'ai appris durant cette discussion!!!!!un vrai cadeau de noël

Posted by: ffpower

C est effectivement de ce livre que je tiens la démo..C était un pote qui me l a prété l année derniere et ya pas mal de trucs sympa dans ce livre..Démo simple du postulat de Bertrand,du théoreme des 5 couleurs(c est pas le théoreme des 4 couleurs,mais c est pas vraiment un cas particulier non plus) et d autres,je me
souviens plus trop.
La j ai pris un cas particulier ou la démo est élémentaire(c est pourquoi j y crois pas trop a une démo par récurrence).Bon je vais poster un début de piste histoire de faire avancer un peu le schmilblik:
Soit a et b 2 ennemis,A l ensemble des amis de a et B l ensembles des amis de b.
On a donc $a\notin B$ (et $b\notin A$ ).Trouvez une bijection naturelle entre A et B et en déduire donc que a et b ont autant d amis..C est ce qu avait fait Aviateurpilot dans un cas particulier..