Facile , on aligne les 7 et 1 segment suffit .

Si ils ne sont pas alignés, c'est moins facile. Tes énigmes sont un niveau au dessus de mes capacités, je donne ma langue au chat.

Vindiou... au moins une heure et demi pour résoudre le cas général avec une preuve pas trop pourrie :-)
... belle énigme vu sa concision.

Pour le cas n=7, on découvre plus ou moins vite qu'il faut 9 segments.

Pour le cas général, je suis passé par les graphes puisque ça n'est pas un problème de géométrie mais de pure combinatoire. Je suis preneur d'une preuve plus courte...

Disons que 3 points tels que deux soient reliés entre eux sont "copains".
Soit [latex]G=(X,Y)[/latex] le graphe tel que : [latex]X[/latex] est l'ensemble des [latex]n[/latex] points, et [latex]U[/latex] est l'ensemble des arêtes les reliant :
[TeX](x,y)\in U \Leftrightarrow[/latex] il y a un segment entre [latex]x[/latex] et [latex]y[/latex].

Un stable est un sous-ensemble de points non reliés deux à deux.

On s'aperçoit que pour toute partition en stables de [latex]G[/latex], chaque stable ne contient au plus que deux éléments (sinon il y aurait 3 points non copains), donc ne contient qu'un ou deux éléments.

Soit [latex]\Pi_{k,j}=(P_1,\ldots,P_k,Q_1,\ldots,Q_j)[/latex] une partition minimale de [latex]G[/latex] en [latex]k[/latex] stables de taille 2 et [latex]j[/latex] stables de taille 1 et je compte le nombre minimum d'arêtes nécessaire pour que G soit correct :
- les deux éléments d'un [latex]P_i[/latex] doivent à eux deux relier ceux de [latex]P_{i'}[/latex] ([latex]i\neq i'[/latex]): deux arêtes pour chaque couple [latex]1\leq i<i'\leq k[/latex], soit un total de [latex] k.(k+1)[/latex] arêtes;
- l'élément de chaque [latex]Q_i[/latex] doit être relié à celui de chaque [latex]Q_{i'}[/latex], sinon on pourrait les regrouper dans un même stable or [latex]\Pi[/latex] est minimale : soit [latex]j.(j-1)/2[/latex] arêtes;
- enfin, l'élément de chaque [latex]Q_i[/latex] doit être relié à l'un des deux de chaque [latex]P_{i'}[/latex], sinon on a 3 "pas copains", soit [latex]k.j[/latex] arêtes.

En tenant compte du fait que [latex]2k+j=n[/latex], j'obtiens un total de :
[latex]T(k)=n^2/2 + k^2 - nk - n/2[/latex] arêtes au minimum.
Après dérivation par rapport à [latex]k[/latex], je constate que [latex]T(k)[/latex] est minimale pour [latex]k=n/2[/latex] dans les cas où [latex]n[/latex] est pair (et donc [latex]j=0[/latex]) ce qui s'étend facilement à [latex]k=(n-1)/2[/latex] et [latex]j=1[/latex] quand [latex]n[/latex] est impair.

Après un petit calcul je trouve :
- si [latex]n[/latex] pair alors [latex]T(n)=(n^2-2n)/4[/TeX]
- si [latex]n[/latex] impair alors [latex]T(n)=(n^2-2n+1)/4[/latex]

Pour 7 points je trouve : [latex]T(7)= (7^2-2*7+1)/4=9[/latex]

Ouf. Et merci je m'en resservirai

Les points ne sont pas alignés...

En effet, mes 7 points ne sont pas alignés.

Dois-je comprendre que trois points quelconques parmi les 7 doivent être non-alignés ?

Si c'est le cas, je propose rapidos la solution suivante:

Je laisse un point de coté et relie tous les autres. J'ai donc 5+4+3+2+1 liaisons.
15 segments de droites
Y a peut-être moyen de faire mieux, mais là comme ça, j'en trouve pas.

Rectification:
En ne mettant pas le septième de coté.
Je fais un heptagone + 4 liaisons internes.
11 segments de droites

La réponse est 9. Ceux qui veulent le démontrer ont encore 2 jours.

@gasole: je te vends mon Touran ? 

Sans changer l'énoncé, la réponse est 1!

Je ne vois vraiment pas.
Avec 9 segments je trouve toujours une seule combinaison de 3 points dont aucun n'est joint a un autre. Donc pour moi la solution est 10 segments.

il faut former un triangle et un carré (dont tout les point sont relier entre eux)

Par conséquent, si on prend comme premier point un point du triangle, on peut soi:
-prendre 2 point du carré. Il seront relié, donc OK
-prendre 1 point du carré et 1 du triangle, le point 1 sera relier a celui du triangle, donc OK
-prendre 2 point du triangle, donc ok

On fait exactement le même raisonnement pour le carré !!!

Et ca marche

Soit A un des points dont le nombre de liaison est minimum.
Soit E l'ensemble des points non reliés à A.
Pour satisfaire l'énoncé, soit E est vide soit tous les points de E sont connectés.
-  Si E est vide alors notre graphe est un graphe complet de 7 points et possède donc 7*6/2 = 21 arrêtes.
-  Sinon E possède au moins un élément B.  Soit F l'ensemble des points non connectés à B. F contient au moins A.  Donc l'ensemble des points de F doivent être connectés entre eux.

Soit n le cardinal de E et (7-n) le cardinal F. il y donc au moins n(n-1)/2+(7-n)(7-n-1)/2 segments qui atteint son minimum 9 pour n=3 ou n=4

En généralisant pour N points on a au moins n(n-1)/2+(N-n)(N-n-1)/2 segments.
On trouve suivant le même procédé que le min est N'^2 pour N = 2N' et N'^2-N' pour N= 2N'+1

:(Bon je n'irai pas par 4 chemins, je pas compris pourquoi la réponse est 9.
PS : Je n'ai pas compris la dernière ligne de l'énoncé.
Y a t-il quelqu'un qui puisse dans un moment de grâce m'expliquer? D'avance merci;
Shadock

Tromaril a écrit:

Après réflexion il y a une autre approche

Si on passe au problème dual, il faut trouver un graphe sans triangle ayant le maximum d'arêtes.
Or d'après le théorème de Mantel, ce graphe a [latex]\lfloor n^2/4\rfloor[/latex] arêtes  (merci wikipédia !!! http://en.wikipedia.org/wiki/Tur%C3%A1n's_theorem )

il faut donc au minimum [latex]1/2*n(n-1)-\lfloor n^2/4\rfloor[/latex] arêtes.

pour n=7, ça fait bien 21-12=9

Ca, c'est ce que j'appelle une superbe solution. Mes félicitations, mon cher !