Répondre à la discussion
Affichage des résultats 1 à 30 sur 30

[exo] Dénombrement



  1. #1
    kNz

    [exo] Dénombrement


    ------

    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.

    -----

  2. Publicité
  3. #2
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par kNz Voir le message
    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,

  4. #3
    kNz

    Re : [exo] Dénombrement

    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

  5. #4
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par kNz Voir le message
    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,

  6. A voir en vidéo sur Futura
  7. #5
    kNz

    Re : [exo] Dénombrement

    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,

  8. #6
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par kNz Voir le message
    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
    Dernière modification par invité576543 ; 12/09/2006 à 20h12.

  9. Publicité
  10. #7
    kNz

    Re : [exo] Dénombrement

    Citation Envoyé par mmy Voir le message
    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

  11. #8
    Gwyddon

    Re : [exo] Dénombrement

    Effacé, j'avais répondu à la première question sans voir dans le dernier post que cela avait été résolu (pas taper !).
    Dernière modification par Gwyddon ; 13/09/2006 à 00h05. Motif: Julien tu es bête
    A quitté FuturaSciences. Merci de ne PAS me contacter par MP.

  12. #9
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par kNz Voir le message
    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,

  13. #10
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par mmy Voir le message
    Il ne restera plus qu'à généraliser le dénombrement...
    Ce qui n'est aussi simple que cette phrase peut laisser penser...

  14. #11
    kNz

    Re : [exo] Dénombrement

    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.

  15. #12
    shokin

    Re : [exo] Dénombrement

    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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  16. Publicité
  17. #13
    shokin

    Re : [exo] Dénombrement

    Je crois que je viens de trouver la formule.

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

    Sans vraiment pouvoir le démontrer.

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  18. #14
    kNz

    Re : [exo] Dénombrement

    Salut shokin,

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

    Quid ?

  19. #15
    kNz

    Re : [exo] Dénombrement

    Citation Envoyé par shokin Voir le message
    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 )

  20. #16
    invité576543
    Invité

    Re : [exo] Dénombrement

    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.

  21. #17
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par kNz Voir le message
    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?

  22. #18
    kNz

    Re : [exo] Dénombrement

    Citation Envoyé par mmy Voir le message
    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.

  23. Publicité
  24. #19
    kNz

    Re : [exo] Dénombrement

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

  25. #20
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par kNz Voir le message
    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,

  26. #21
    kNz

    Re : [exo] Dénombrement

    Citation Envoyé par mmy Voir le message
    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 ..

  27. #22
    shokin

    Re : [exo] Dénombrement

    Citation Envoyé par kNz Voir le message
    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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  28. #23
    kNz

    Re : [exo] Dénombrement

    Citation Envoyé par shokin Voir le message
    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 ??

  29. #24
    mécano41

    Re : [exo] Dénombrement

    Citation Envoyé par shokin Voir le message
    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

  30. Publicité
  31. #25
    kNz

    Re : [exo] Dénombrement

    Citation Envoyé par mécano41 Voir le message
    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 :?

  32. #26
    shokin

    Re : [exo] Dénombrement

    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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  33. #27
    shokin

    Re : [exo] Dénombrement

    Citation Envoyé par mécano41 Voir le message
    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 :

    Citation Envoyé par kNz
    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
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

  34. #28
    mécano41

    Re : [exo] Dénombrement

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

  35. #29
    invité576543
    Invité

    Re : [exo] Dénombrement

    Citation Envoyé par shokin Voir le message
    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,

  36. #30
    shokin

    Re : [exo] Dénombrement

    Citation Envoyé par shokin Voir le message
    Restait alors à trouver t, lequel est évidemment constant, et facile à trouver.
    Scusez...

    Finalement... on y est arrivés.

    Shokin
    Pardon, humilité, humour, hasard, tolérance, partage, curiosité et diversité => liberté et sérénité.

Discussions similaires

  1. Pb Exo Denombrement
    Par drossvach dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 30/09/2007, 19h57
  2. [EXO TS] Blocage sur un dénombrement
    Par wilfredd dans le forum Mathématiques du collège et du lycée
    Réponses: 1
    Dernier message: 26/09/2007, 15h29
  3. [TS] petit exo >dénombrement<
    Par Nizm dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 07/03/2007, 18h43
  4. [exo] Dénombrement
    Par kNz dans le forum Mathématiques du collège et du lycée
    Réponses: 7
    Dernier message: 17/09/2006, 20h29
  5. exo denombrement
    Par TYTOI dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 17/11/2005, 20h59