— Raisonnement par récurrence
Répondre à la discussion
Affichage des résultats 1 à 16 sur 16

— Raisonnement par récurrence



  1. #1
    invite5c80985b

    Bonsoir

    Voici un raisonnement qui permet de démontrer par récurrence que dans toute boite de n crayons de couleurs, les n crayons sont de la meme couleur (ben vi c'est faux évidemment) :

    On initialise :
    Au rang n=1, il y a un crayon de couleur, donc il est de la meme couleur que lui meme c'est bon.

    On suppose la propriété vraie au rang n et on montre qu'elle est alors vraie au rang n+1 :
    Si P(n) vraie, alors dans tout ensemble de n crayons, les n sont de la meme couleur. Bon, on en prend n+1, dans ces n+1, il y a les n premiers qui sont de la meme couleur. On prend les n derniers, comme ils sont n, alors ils sont de la meme couleur par hypothèse de récurrence.

    Au final, les n+1 sont de la meme couleur.

    Donc par propirété des récurrences, la propriété est vraie pour tout n.

    Alors ?

    -----

  2. #2
    Coincoin

    Je croyais que ta propriété P(n) était: "dans toute boîte de n crayons, n crayons sont de même couleur" et non "dans tout sous-ensemble de n crayons d'une boîte de n+1 crayons, n crayons sont de même couleur"...

  3. #3
    invite5c80985b

    Oui bah la tu joues sur les mots. Je rectifie P(n) : "Dans tout ensemble de n crayons de couleurs, les n crayons sont de la meme couleur"

    Alors dans un ensemble de n+1, tu prends les n premiers, ils sont n >> donc de la meme couleur, ensuite tu prends les n derniers >> ils sont n donc de la meme couleur.

    Ce passage est inattaquable, il est juste, ce n'est pas là que ça cloche.

    Et honnetement, ce n'est pas évident de voir ou est le problème

    Naoli

  4. #4
    Quinto

    Mon prof de combinatoire nous avait fait ce truc là l'an dernier.
    J'ai mis 1/2h à répondre correctement.
    Ca ne m'étonnerait pas que ce soit le même prof qui te l'a fait

    Sinon c'est pas évident en effet et ca joue sur des points bizarres de la récurrence...

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

    au fait:
    de mémoire, aucun passage n'est attaquable
    C'est ca le pire ....

  7. #6
    Quinto

    Oui je sais je flood, désolé.
    En fait je crois que c'est un problème de fondement générique, on arrive jamais à fonder la réccurence, je me trompe?

  8. #7
    Coincoin

    Ca y est, j'ai trouvé!!! Il y a un passage attaquable: pour démontrer que les n+1 crayons sont de la même couleur, on dit que les n premiers le sont et que les n derniers aussi, et on en déduit que les n+1 crayons sont de la même couleur... ce qui suppose que n+1<n+n, soit n>1. Bref l'implication P(1)=>P(2) n'a pas été démontrée. Et pour cause: lorsqu'on a 2 crayons, que le premier est de la même couleur que lui-même et que le dernier est de la même couleur que lui-même, on ne peut pas en déduire que les 2 crayons ont la même couleur...
    Le principe de récurrence est sauf.

    Ce passage est inattaquable, il est juste, ce n'est pas là que ça cloche.

  9. #8
    Quinto

    Oui y'a de ca

  10. #9
    Evil.Saien

    Moi je dirais que le passage P(n) à P(n+1) est un peu douteux, puisqu'on utilise l'hypothèse sur 2 lots de cryons différents. Dons chacun des 2 lots peut en effet contenir uniquement des crayons de meme couleur, mais c'est pas dit que ces 2 couleurs soient les meme.
    Prenons un cryon vert et un crayon bleu.
    Le premier lot est de la meme couleur, le deuxieme lot aussi, pourtant le tout reuni ne l'est pas !
    L'hypothèse de départ est mal définie !

  11. #10
    invite5c80985b

    Non c'est coincoin qui a trouvé, bien joué !

    Attentiopn, je parlais de l'hypothèse : pour n > 2 ça fonctionne très bien, donc le passage dont tu disais que ça ne fonctionnait pas était "inattaquable", néanmoin, oui, on n'a pas démontré le passage à n = 2.

    En revanche on a pourvé, et c'est logique, que si l'on avait pas le droit dfe vendre enszemble deux crayons qui ne soient pas de la meme couleur, tous les crayons d'un ensemble seraient de la meme couleur !

    ++

  12. #11
    olle

    il y a pas de raison de vérifier pour n=2 spécifiquement, c'est tout l'intérêt de la récurrence !
    vérifier pour n=1 et n=n+1. et c'est tout.

    donc pour en venir au fait que je trouve l'explication d'evil.saien beaucoup beaucoup plus pertinante. en fait, votre contre exemple avec n=2 est un cas particulier de l'explication d'evil.saien qui, lui, démontre que ce n'est pas forcément juste pour n+1 si ça l'est pour n.

    enfin je suis pas prof de mathématique, c'est juste mon approche des choses.

  13. #12
    invite5c80985b

    Mais non ! Pas du tout ! la récurrence te permet de le vérifier pour tout n > no, avec en général no = 0 ou 1, mais ici, utilise la récurrence en initialisant à n= 1, alors que ça devrait etre à n=2.

    Mais le passage de n à n+1, lui, est bon. C'est l'initilaisation qui est mauvaise (cet exo vient de ma prof de maths qui a eu 18 au concours de l'ENS donc elle sait ce qu'elle dit )

    En revanche, si l'initialisation était vraie : imagine que des qu'il y a deux crayons de couleurs ensemble, les 2 soient de la meme couleur, alors pour n, et pour n+1, ce serait vrai également

    ++

    Naoli

  14. #13
    olle

    mouais tu as ptet raison, mais personnellement j'ai appris à ne plus avoir une confiance aveugle en mes profs, aussi bons soient-ils

  15. #14
    invite5c80985b

    Bonjour

    Oui je suis d'accord, et je reste très critique cis à cis de ce qu'on m'enseigne, néanmoins, là, je suis d'accord avec elle.

    Evidemment, le pb je ne sais peut etre pas bien l'expliquer, mais à l'écrit comme ça, c'est difficile

    A bientôt

  16. #15
    Quinto

    Oui, Naoli a raison, c'est ce qu'on appelle un fondement générique.
    Ce que dis Olle n'est pas vrai n'importe où, mais vrai à partir du moment où c'est bien fondé.

  17. #16
    invite5c80985b

    -

    Quelle sagess




    -

Discussions similaires

  1. Raisonnement par récurrence
    Par inviteeaabc6e5 dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 18/09/2007, 09h04
  2. Le raisonnement par récurrence.
    Par invitea250c65c dans le forum Mathématiques du collège et du lycée
    Réponses: 9
    Dernier message: 23/02/2007, 06h27
  3. Vive le raisonnement par récurrence!
    Par Jojo1989 dans le forum Mathématiques du collège et du lycée
    Réponses: 7
    Dernier message: 02/10/2006, 18h04
  4. raisonnement par l'absurde ou par contraposé, URGENT!
    Par invitec00664cf dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 21/09/2006, 12h43
  5. raisonnement par récurrence , SVP !
    Par invite492114f6 dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 10/09/2004, 21h19