[exo] Dénombrement

[kNz]

Bonjour à tous,

Je butte sur un problème, en voici l'énoncé :

Soit n points sur un cercle.

1) Combien déteminent-ils de cordes ?

2) Quel est le nombre de points d'intersection situés à l'intérieur du cercle lorsque, en chaque point, passent au plus deux cordes ?

1) On remarque qu'on a (n-1) cordes pour le premier point, puis (n-2) cordes pour le deuxième, etc.

On a donc cordes dans ce cercle.

2) Et c'est là que je bloque, je sais pas trop comment faire... On a n-1 possibilités pour placer la première corde, idem pour la deuxième, ensuite on distingue deux cas :

- soit les deux cordes se rejoignent en un point, auquel cas on a (n-2) possibilités pour placer la troisième.

- soit les deux cordes ne se rejoignent pas en un point, et on a toujours (n-1) possibilités pour placer la troisième.

Voilà je sais pas trop quoi faire..

Merci.
-----

[invité576543]

1) On remarque qu'on a (n-1) cordes pour le premier point, puis (n-2) cordes pour le deuxième, etc.

On a donc cordes dans ce cercle.

Faudrait que tu donnes un résultat plus "fermé", en calculant la somme...

Il y a une méthode plus rapide qui donne le résultat fermé, et c'est ce résultat qui est attendu...

2) Et c'est là que je bloque, je sais pas trop comment faire... On a n-1 possibilités pour placer la première corde, idem pour la deuxième, ensuite on distingue deux cas :

Ca ne commence pas bien. C'est quoi ces "n-1" possibilités?

Il n'y a pas beaucoup de différence avec le premier exercice, si tu réfléchis bien. Relis bien la question. Qu'est-ce qui définit un point d'intersection?

Cordialement,

[kNz]

Dois-je compter toutes les cordes et retirer celles que je compte plusieurs fois ?

On a (n-1) cordes par point, donc n(n-1) cordes, mais on a compté plusieurs fois les mêmes..

Pour le premier point, on n'a pas compté de cordes en trop,
Pour le deuxième point, on en a compté une en trop,
Pour le troisième, deux, etc.

Mais ça me ramène toujours à une somme

[invité576543]

Dois-je compter toutes les cordes et retirer celles que je compte plusieurs fois ?

On a (n-1) cordes par point, donc n(n-1) cordes, mais on a compté plusieurs fois les mêmes..

Exact. Mais on peut savoir combien de fois on les a compté sans faire de somme.

Un truc tout bête, dans ce genre d'exo, est de prendre les petits cas, et de regarder ce qu'il se passe. Si n=2, combien de cordes? n=3?

Cordialement,

[A voir en vidéo sur Futura]

[kNz]

Ok merci

Si on prend des cas simples, on peut conjecturer qu'il faut diviser par 2 pour obtenir le nombre réel de cordes dans le cercle.

Mais je trouve pas d'explication,

[invité576543]

Ok merci

Si on prend des cas simples, on peut conjecturer qu'il faut diviser par 2 pour obtenir le nombre réel de cordes dans le cercle.

Mais je trouve pas d'explication,

Il suffit de prendre la question à l'envers : pour combien de points une corde apparaît-elle?

Une fois cela compris, tu peux t'attaquer aux intersections, le raisonnement est le même, à quelques détails près.

Cordialement,

EDIT pour l'erreur

[kNz]

Il suffit de prendre la question à l'envers : pour combien de points une corde apparaît-elle?

Une fois cela compris, tu peux t'attaquer aux intersections, le raisonnement est le même, à quelques détails près.

Cordialement,

EDIT pour l'erreur

Ah ok d'accord je vois pour les cordes ..

Un point d'intersection est défini par deux cordes. Mais je comprends pas, on peut obtenir un nombre de points d'intersection différents selon la disposition des cordes

En tout cas, merci

[Gwyddon]

Effacé, j'avais répondu à la première question sans voir dans le dernier post que cela avait été résolu (pas taper !).

[invité576543]

Un point d'intersection est défini par deux cordes. Mais je comprends pas, on peut obtenir un nombre de points d'intersection différents selon la disposition des cordes

Bonjour,

Très bien, c'est le petit détail à voir... Mais le nombre de cas différents est limité, et chacun des cas est bien caractérisé.

Là encore, si on prend un petit nombre, que trouve-t-on? Les cas n=2 et n=3 apparaissent particuliers, ensuite n=4 donne combien d'intersections intérieures? n=5? Si on prend deux cordes au hasard avec n=4 ou 5, que peut-on dire de l'intersection?

Il ne restera plus qu'à généraliser le dénombrement...

Cordialement,

[invité576543]

Il ne restera plus qu'à généraliser le dénombrement...

Ce qui n'est aussi simple que cette phrase peut laisser penser...

[kNz]

Pour n=2 et n=3 on n'a pas de points d'intersection.

Pour n=4, on peut avoir soit 0 soit 1 point d'intersection.

Pour n=5, on peut avoir 0, 1, 2, 3 ou 5 points d'intersection (étoile à 5 branches).

On remarque qu'il est nécessaire qu'une corde ne joigne pas deux points côte à côte sur le cercle pour obtenir une intersection avec deux cordes.

Pour placer la première corde, il y a donc (n-3) possibilités de relier deux points.

On pose A l'ensemble des points situés entre les deux points du cercle reliés par la première corde sur l'arc le plus court et B le reste des points.

Il est nécessaire que la corde relie un élément de A à un élément de B.

On pose A' l'ensemble des points situés entre les deux points du cercle reliés par la première corde sur l'arc le plus court et B' le reste des points.

La troisième corde devra à nouveau relier un élément de A' et un élément de B' pour obtenir un point d'intersection, qui devront être également deux éléments de A et de B si on veut obtenir un nombre de points d'intersection maximal.

Bon j'marque ça mais j'marque rien, déjà, il faut exprimer le nombre de cordes utilisées dans la formule, parce qu'on peut très bien choisir de ne placer aucune corde, ou simplement une, ou deux, par point.

J'ai l'impression qu'il y a beaucoup trop de cas possible,

Je vais réfléchir,

Merci.

[shokin]

1) Pour le nombre de cordes en fonction de n, on peut aussi écrire n(n-1)/2, n étant le nombre de points.

2) Quel est le nombre de points d'intersection situés à l'intérieur du cercle lorsque, en chaque point d'intersection des cordes, passent au plus deux cordes ?

A partir de 3 points, tu constates que :

En rajoutant un n-ième point, tu rajoutes n-1 cordes.

Ce n-ième point est situé, sur le cercle, entre deux points déjà placés. Les deux cordes de ce n-ième point vers ses deux voisins ne coupent pas d'autres cordes déjà présentes. Par contre, les n-3 autres cordes que tu rajoutent vont couper des cordes, mais combien ?

On peut voir le problème autrement :

Imagine (dessine) un cercle avec n points sur ce cercle et toutes les cordes tracées reliant ces n points.

Une question alors est de se poser : combien de cordes coupe une corde ? on voit assez vite que le nombre de cordes que croise une corde n'est pas le même pour toutes les cordes.

Nommons alors ces n points dans l'ordre :

p(1), p(2), p(3), ..., pn, dans leur ordre sur le cercle.

Les n cordes reliant p(i) et p(i+1) ne croisent pas de cordes car p(i) et p(i+1) sont consécutifs.

Voyant alors les cordes reliant p(i) à p(i+2) :

Chacune de ces cordes coupe le cercle en deux parties.

Pour (p(i);p(i+2)), il y aura un point d'un côté et n-3 points de l'autre côté.

Donc 1*(n-3) cordes couperont cette corde (ainsi que toutes les n cordes reliant p(i) à p(i+2)).

Pour (p(i);p(i+3)), il y aura deux points d'un côté et n-4 points de l'autre côté. Donc 2*(n-4) cordes qui couperont chaque corde (p(i);p(i+2)).

...

ainsi de suite jusqu'à (p(i);p(i+n-1)).

On calcule la somme des cordes qui croisent chacune des cordes partant d'un point. [ça va être le plus dur, calculer cette somme, généralisée en fonction de n].

On multiplie par n cette somme, pour considérer tous les points, et pour que chaque croisement de deux cordes ait été pris autant de fois en trop.

Reste à trouver combien n fois trop a été pris chaque croisement de deux cordes.

Chaque croisement a été considéré 2n fois trop.

2 car il est le croisement de 2 cordes, et l'on a considéré (dans ma méthode) chaque corde.

n car on a multiplié par n.

Il faudra alors diviser par 2n (après avoir multiplié par n ).



NB : je ne garantis pas toute la justesse de ma méthode.

Ce serait bien qu'on trouve une méthode plus simple.

Shokin

[shokin]

Je crois que je viens de trouver la formule.

n(n-1)(n-2)(n-3)/24

Sans vraiment pouvoir le démontrer.

Shokin

[kNz]

Salut shokin,

Je pensais que l'énoncé nous disait qu'il y avait au plus deux cordes par point sur le cercle. :?

Quid ?

[kNz]

Je crois que je viens de trouver la formule.

n(n-1)(n-2)(n-3)/24

Pour n=5, ça ferait 5*4*3*2 / 24 = 120 / 24 intersections, ça n'est pas entier et on devrait trouver 5 (que l'on prenne ta compréhension de l'énoncé ou la mienne )

[invité576543]

Bonjour,

La formule que j'avais ne colle pas à celle de Shokin, mais c'est moi qui ai fait une erreur.

Mais la formule de Shokin permet de trouver un raisonnement simple qui explique immédiatement la formule...

C'est finalement très simple! Si je ne me trompe pas ce coup là...

Joli problème, en fait...

Cordialement,

Un point d'intersection intérieur de deux cordes définit un ensemble de 4 points (les sommets de cordes). Réciproquement, tout ensemble de 4 points définit un et un seul point d'intersection intérieur.

[invité576543]

Pour n=5, ça ferait 5*4*3*2 / 24 = 120 / 24 intersections, ça n'est pas entier et on devrait trouver 5 (que l'on prenne ta compréhension de l'énoncé ou la mienne )

Depuis quand 120/24 n'est pas entier?

[kNz]

Depuis quand 120/24 n'est pas entier?

Toutes mes excuses à shokin qui a apparemment trouvé la bonne formule

Je réfléchis, merci à tous les deux.

[kNz]

Bon, merci la formule de shokin et le lemonchiffon de mmy,

n(n-1)(n-2)(n-3) = n! / (4! (n-4)!)

ça revient à choisir 4 points parmi n pour déterminer un point d'intersection...

[invité576543]

Bon, merci la formule de shokin et le lemonchiffon de mmy,

n(n-1)(n-2)(n-3) = n! / (4! (n-4)!)

ça revient à choisir 4 points parmi n pour déterminer un point d'intersection...

C'est interdit de regarder les lemonchiffon! C'était à toi de bosser.

Cordialement,

[kNz]

C'est interdit de regarder les lemonchiffon! C'était à toi de bosser.

Cordialement,

J'avais quand même fait le lien avec les factorielles, je n'ai lu ton lemonchiffon qu'après ..

[shokin]

Bon, merci la formule de shokin et le lemonchiffon de mmy,

n(n-1)(n-2)(n-3) = n! / (4! (n-4)!)

ça revient à choisir 4 points parmi n pour déterminer un point d'intersection...

Tiens, je n'avais pas pensé à ça. Astucieux !

Et lux fit !

Shokin

[kNz]

Tiens, je n'avais pas pensé à ça. Astucieux !

Et lux fit !

Shokin

Oui merci encore à vous deux,

Et shokin, tu l'avais trouvé comment ta formule alors ??

[mécano41]

Je crois que je viens de trouver la formule.

n(n-1)(n-2)(n-3)/24


Shokin

Bonjour,

Sauf erreur de ma part et en traçant les cordes :

- avec 6 points on trouve 12 intersections de 2 cordes + 1 de plus de deux cordes alors que la formule donne 15

- avec 8 points on trouve 40 intersections de 2 cordes + 9 de plus de deux cordes alors que la formule donne 70

Pour les valeurs n=4, 5, et 7 on trouve bien respectivement 1, 5 et 35 (il n'y a que des intersections de 2 cordes)

Cordialement

[kNz]

Bonjour,

Sauf erreur de ma part et en traçant les cordes :

- avec 6 points on trouve 12 intersections de 2 cordes + 1 de plus de deux cordes alors que la formule donne 15

- avec 8 points on trouve 40 intersections de 2 cordes + 9 de plus de deux cordes alors que la formule donne 70

Pour les valeurs n=4, 5, et 7 on trouve bien respectivement 1, 5 et 35 (il n'y a que des intersections de 2 cordes)

Cordialement

Moi pour 6 points je trouve 15 :?

[shokin]

heu... par tatonnements algébriques.

En fait, je me suis dit, au début :

Comme la formule pour trouver le nombre de cordes en fonction du nombre de point était : n(n-1)/2.

Je me suis dit (sans réel fondement que je pourrais expliquer rigoureusement) alors que la formule était du même genre, à un degré plus élevé.

J'ai essayé avec n(n-1)(n-2)/t, t un réel encore inconnu, mais ça ne marchait pas.

Mais j'ai remarqué, avec la fonction f(n) = n(n-1)(n-2) = n! / (n-3)! que :

si n augmente de 1, f(n) est multiplié par (n+1)/(n-2), ce qui est logique quand on y observe de plus près. La différence entre n+1 et n-2 est toujours égale à 3.

J'ai alors compté le nombre de points d'intersections en fonction du nombre de points sur le cercle.

n => f(n)

1 => 0
2 => 0
3 => 0
4 => 1
5 => 5
6 => 15
7 => 35
8 => 70
...

J'ai alors remarqué que :

f(5) = f(4)*5/1
f(6) = f(5)*6/2
f(7) = f(6)*7/3
f(8) = f(7)*8/4
...
f(n) = f(n-1)*(n/n-4)

Donc la fonction était du type : (n!)/(n-s)!. En l'occurence, t=4.

(n!)/[(n-4)!*t] = n(n-1)(n-2)(n-3)/t

Restait alors à trouver, lequel est évidemment constant, et facile à trouver.

Shokin

[shokin]

Bonjour,

Sauf erreur de ma part et en traçant les cordes :

- avec 6 points on trouve 12 intersections de 2 cordes + 1 de plus de deux cordes alors que la formule donne 15

- avec 8 points on trouve 40 intersections de 2 cordes + 9 de plus de deux cordes alors que la formule donne 70

Pour les valeurs n=4, 5, et 7 on trouve bien respectivement 1, 5 et 35 (il n'y a que des intersections de 2 cordes)

Cordialement

Mais il a bien spécifié dans sa question :

2) Quel est le nombre de points d'intersection situés à l'intérieur du cercle lorsque, en chaque point, passent au plus deux cordes ?

Il est clair que si tu prends des polygones plus ou moins réguliers, des intersections vont rencontre plus de trafic routier, car le nombre d'intersection est alors régulier (un hexagone régulier par exemple).

Shokin

[mécano41]

Exact. J'ai fait l'erreur de prendre des points régulièrement espacés sur le cercle.
Bon courage

[invité576543]

heu... par tatonnements algébriques.

Ce matin, j'étais parti sur un décompte par catégories, intersections à l'intérieur, sur le cercle, à l'extérieur et à l'infini. Ca semblait simple au début, puis bien moins après, pour accoucher d'un résultat faux.

Ce qui est curieux dans cet exercice c'est que la solution est très simple, mais elle me semble difficile à voir d'entrée. Sans la formule proposée par Shokin, je ne sais pas si j'aurais pensé à cette démo en 2 lignes...

Exercice très intéressant!

Cordement,

[shokin]

Restait alors à trouver t, lequel est évidemment constant, et facile à trouver.

Scusez...

Finalement... on y est arrivés.

Shokin