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

Exercice de Noël



  1. #1
    BS

    Exercice de Noël

    Joyeux Noël à tous !

    Fêtons cela avec un problème classique mais toujours amusant.

    On a 2n+1 cadeaux. Si on choisit n'importe lequel de ces cadeaux, alors on peut toujours s'arranger pour répartir les 2n restants en 2 tas de n paquets chacun, les deux tas ayant le même poids. Montrer qu'alors tous les cadeaux ont même poids.

    -----


  2. Publicité
  3. #2
    monnoliv

    Re : Exercice de Noël

    Si j'ai bien compris l'énoncé, ça ne marche déja pas avec 5 cadeaux dont les poids sont de 1,1,1,1,3
    Si je choisis le cadeau de poids 3 alors je peux partager le restant en deux tas égaux.
    Si je choisis un des autres cadeaux, alors je peux aussi partager le restant en deux tas égaux: 1+1+1 et 3
    Quid ? Les cadeaux n'ont pas le même poids !
    Ne soldez pas grand mère, elle brosse encore.

  4. #3
    justine&coria

    Re : Exercice de Noël

    Citation Envoyé par monnoliv
    Si je choisis un des autres cadeaux, alors je peux aussi partager le restant en deux tas égaux: 1+1+1 et 3
    Quid ? Les cadeaux n'ont pas le même poids !
    2 tas de n paquets chacun !!

  5. #4
    la_christe

    Re : Exercice de Noël

    Par l' absurde :
    Supposons que tous les cadeaux n' ont pas le meme poids.
    Alors il existe au moins un cadeau de poids différent de tous les autres , notons p1 le poids de ce cadeau et p0 le poids de chacun des autres cadeaux.
    Alors si on prend ce cadeau de poids p1 , on peut bien partager les autres cadeaux en 2 tas de n cadeaux de poids identique p0.
    Si on prend un autre cadeau que celui là, alors le cadeau de poids p1 sera forcément dans un des deux tas, donc ce tas aura pour poids total : (n-1)p0+p1 et l' autre aura pour poids n*p0 .
    Pour avoir l' égalité :

    (n-1)p0+p1=n*p0 ssi -p0+p1=0 ssi p0=p1 ... contradiction : les cadeaux ont tous le meme poids.

  6. #5
    BS

    Re : Exercice de Noël

    Citation Envoyé par la_christe
    , notons p1 le poids de ce cadeau et p0 le poids de chacun des autres cadeaux.
    Pourquoi les cadeaux restants auraient-ils tous le même poids ?

  7. A voir en vidéo sur Futura
  8. #6
    ITISAR

    Re : Exercice de Noël


    T'es sûr d'avoir bien recopié ton problème ?

  9. Publicité
  10. #7
    BS

    Re : Exercice de Noël

    Oui oui, pour être plus clair on pourrait peut-être remplacer "en 2 tas de n paquets" par "en 2 tas de n cadeaux", paquet étant sous-entendu poquet-cadeau, mais c'est du vocabulaire...

  11. #8
    monnoliv

    Re : Exercice de Noël

    Je pense avoir trouvé la solution.

    Supposons deux tas de n élements chacun (il reste un élément extérieur dont le poids est d).
    La somme des poids du premier tas (TasA) est A
    La somme des poids du deuxième tas (TasB) est B
    On a A = B
    Echangeons l'élément extérieur de poids d avec un élément de B (par exemple), l'élément échangé de B a le poids e
    Le poids de TasB devient B - e + d
    Comme il faut garder le même nombre d'éléments de TasA et TasB, on ne peut qu'échanger un élément de TasA par un de TasB. Et répéter l'opération de manière à essayer d'obtenir à nouveau le même poids pour les deux tas. Soit a et b les poids des éléments de TasA et TasB qu'on échange, on a (en poids):
    A - a + b = B + a - b - e + d
    Donc
    d-e = 2*(b-a) puisque A = B
    Si b est différent de a, cette relation nous apprend que (d - e) doit être pair. Donc l'échange entre l'élément extérieur des deux tas et un quelconque élément des deux tas doit être pair. Donc dans l'ensemble des 2n+1 éléments, la différence entre un élement et un autre doit être paire. Mais alors, il en est de même pour a et b. Ce qui nous apprend (par la relation ci-dessus) que non seulement d-e doit être pair mais aussi multiple de 4. Par le même raisonnement on s'aperçoit que a-b doit aussi être multiple de 4, mais alors (d-e) doit être multiple de 8, ... La seule solution est donc que a = b, d'où d=e et tous les éléments ont le même poids.
    Ne soldez pas grand mère, elle brosse encore.

  12. #9
    BS

    Re : Exercice de Noël

    Ca m'a l'air de très bien marcher comme raisonnement. Et en plus c'est très joli, je ne connaissais pas. Bravo !

  13. #10
    monnoliv

    Re : Exercice de Noël

    Merci. Peux-tu donner la solution que tu connais ?
    Ne soldez pas grand mère, elle brosse encore.

  14. #11
    la_christe

    Re : Exercice de Noël

    Dans mon raisonnement , je prouve que la proposition suivante est fausse : "au moins un cadeau a un poids différent des autres".Le contraire est donc vrai , cad : tous les cadeaux ont le meme poids.
    non ?

  15. #12
    BS

    Re : Exercice de Noël

    Citation Envoyé par la_christe
    Dans mon raisonnement , je prouve que la proposition suivante est fausse : "au moins un cadeau a un poids différent des autres".Le contraire est donc vrai , cad : tous les cadeaux ont le meme poids.
    non ?
    En fait ce que tu démontres est un peu différent. Je te rappelles ton raisonnement :
    "Alors si on prend ce cadeau de poids p1 , on peut bien partager les autres cadeaux en 2 tas de n cadeaux de poids identique p0."
    Ce que tu as montré, c'est qu'il faux qu'un cadeau ait un poids p1 et que tous les autres aient le même poids p0. Donc ce que tu as montré c'est que si tous les cadeaux n'ont pas tous le même poids, alors il en existe au moins trois de poids tous différents, mais ça ne suffit pas.

  16. Publicité
  17. #13
    BS

    Re : Exercice de Noël

    Citation Envoyé par monnoliv
    Merci. Peux-tu donner la solution que tu connais ?
    Oui bien sûr. L'idée est d'écrire l'énoncé sous forme d'un système linéaire (2n+1)x(2n+1). Les poids des 2n+1 cadeaux s'écrivent par exemple comme un vecteur de taille 2n+1. Soient p_1, ..., p_(2n+1) les poids des 2n+1 cadeaux. On forme le système de 2n+1 équations m_(i,1)p_1+...+m_(i,2n+1)p_(2n +1)=0. Où les m(i,j) sont égaux à +1 ou -1 et m(i,i)=0 (la i-ème équation correspond au retrait du i-ème cailloux). En fait on pose m(i,j)=1 si le cailloux p_j est dans le premier tas, -1 si il est dans le deuxième tas. On cherche donc à résoudre le système Mv=0 où M est une matrice de taille (2n+1)x(2n+1) de la forme suivante : sa diagonale est nulle et tous les autres termes sont égaux à 1 ou -1. De plus sur chaque ligne il y a n termes égaux à 1 et n termes égaux à -1 (car les deux tas sont de taille n). le vecteur (1,...1) est une solution évidente de cette équation. Si on montre que la matrice M est de rang 2n, c'est terminée, toute solution est un multiple de (1,...,1) et donc p_1=...=p_(2n+1).

    Il reste donc à prouver qu'une matrice (2n+1)x(2n+1) dont les termes diagonaux sont nuls et tous les autres sont 1 ou -1 est de rang supérieur à 2n, petit exercice...

  18. #14
    monnoliv

    Re : Exercice de Noël

    La matrice est au plus de rang 2n puisque tous les éléments diagonaux sont nuls et donc le déterminant = 0...
    Ne soldez pas grand mère, elle brosse encore.

  19. #15
    BS

    Re : Exercice de Noël

    Citation Envoyé par monnoliv
    La matrice est au plus de rang 2n puisque tous les éléments diagonaux sont nuls et donc le déterminant = 0...
    Ah ben non, pense à
    par exemple...

  20. #16
    monnoliv

    Re : Exercice de Noël

    Ah oui
    Ne soldez pas grand mère, elle brosse encore.

  21. #17
    monnoliv

    Re : Exercice de Noël

    Ah mais que penses-tu de celle-ci:

    Son déterminant vaut bien 0. Donc pour 2n+1 = 3 ça ne fonctionne déjà pas .
    Ne soldez pas grand mère, elle brosse encore.

  22. #18
    BS

    Re : Exercice de Noël

    Oui effectivement, mais ce qu'il faut montrer, ce n'est pas qu'elle est inversible, mais que son rang est 2n. En effet le vecteur (1,...,1) est toujours solution du système en question. Tu peux bien constater que la matrice que tu donnes est de rang 2.

  23. Publicité
  24. #19
    monnoliv

    Re : Exercice de Noël

    Y a un truc d'algèbre dont je ne me souviens plus. Quand tu écris
    Si on montre que la matrice M est de rang 2n, c'est terminé, toute solution est un multiple de (1,...,1) et donc p_1=...=p_(2n+1)
    on parle bien du système homogène suivant:
    A.x=0

    Si la matrice est de taille (2n+1) X (2n+1) et que son rang est de 2n alors les autres solutions sont-elles nécessairement multiple de celle qu'on a trouvée (1,1,1,...,1) ?
    Ne soldez pas grand mère, elle brosse encore.

  25. #20
    BS

    Re : Exercice de Noël

    Citation Envoyé par monnoliv

    Si la matrice est de taille (2n+1) X (2n+1) et que son rang est de 2n alors les autres solutions sont-elles nécessairement multiple de celle qu'on a trouvée (1,1,1,...,1) ?
    Oui c'est cela, c'est un résultat qu'on appelle théorème du rang. Si la matrice est de rang 2n, alors son noyau est de dimension 1.

Sur le même thème :

Discussions similaires

  1. Noël à Marseille
    Par jbfe dans le forum Matériel astronomique et photos d'amateurs
    Réponses: 10
    Dernier message: 26/12/2006, 16h47
  2. joyeux NoËl
    Par hammadi dans le forum Matériel astronomique et photos d'amateurs
    Réponses: 21
    Dernier message: 25/12/2006, 19h01
  3. Noël
    Par mike12z dans le forum Science ludique : la science en s'amusant
    Réponses: 27
    Dernier message: 25/07/2005, 23h03
  4. Joyeux Noel
    Par garsdu62 dans le forum Orientation après le BAC
    Réponses: 1
    Dernier message: 26/12/2004, 12h07