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.
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.
2 tas de n paquets chacun !!Envoyé par monnoliv
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.
Pourquoi les cadeaux restants auraient-ils tous le même poids ?
T'es sûr d'avoir bien recopié ton problème ?
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...
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.
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 !
Merci. Peux-tu donner la solution que tu connais ?
Ne soldez pas grand mère, elle brosse encore.
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.
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...
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.
Ah ben non, pense à
par exemple...
Ah oui
Ne soldez pas grand mère, elle brosse encore.
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.
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.
Y a un truc d'algèbre dont je ne me souviens plus. Quand tu écris
on parle bien du système homogène suivant: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)
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.
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.
