Groupe d amis

par **Imod** » 18 Déc 2007, 20:32

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

par **lapras** » 18 Déc 2007, 23:20

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...

par **bruce.ml** » 18 Déc 2007, 23:37

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 :++:

par **raito123** » 19 Déc 2007, 01:23

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

par **ffpower** » 19 Déc 2007, 01:48

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)

par **bruce.ml** » 19 Déc 2007, 08:30

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

par **raito123** » 19 Déc 2007, 13:28

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

par **ffpower** » 19 Déc 2007, 13:50

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...

par **raito123** » 19 Déc 2007, 14:05

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!!)

par **bruce.ml** » 19 Déc 2007, 18:54

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 :id:

par **Imod** » 19 Déc 2007, 19:23

ffpower a écrit:"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

par **bruce.ml** » 19 Déc 2007, 19:43

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 ;)

par **Imod** » 19 Déc 2007, 20:11

bruce.ml a écrit: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

par **bruce.ml** » 19 Déc 2007, 22:12

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.

par **ffpower** » 19 Déc 2007, 22:21

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

par **Imod** » 20 Déc 2007, 12:46

bruce.ml a écrit: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 :triste:

Imod

par **bruce.ml** » 20 Déc 2007, 13:04

Imod a écrit: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 :triste:

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.

par **Imod** » 20 Déc 2007, 13:31

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

Imod

par **ffpower** » 20 Déc 2007, 14:10

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

par **Help** » 20 Déc 2007, 16:26

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.

Groupe d amis

Qui est en ligne