2 tas

[miikou]

salut,

On considere 2n+1 cailloux. Si on enleve n'importe lequel on peut toujours faire 2 tas de n cailloux de poids identiques. Montrer qu'ils ont tous le meme poids :happy2:

[Nightmare]

Salut !

As-tu une autre preuve que la classique d'algèbre linéaire?

[miikou]

salut Jord je n'en ai a l'heure actuelle aucune ..

[Lostounet]

Salut,
Est-ce une vraie énigme ? :hum:
Je n'arrive pas à saisir la difficulté en soi..! (S'il y en a).

[Finrod]

Je ne connais pas la preuve et à priori si Nightmare parle d'algèbre linéaire, tu n'es pas censé pouvoir trouver Lostounet.
En tout cas, je ne vois pas de solution évidente.

[Ben314]

Salut,
Comme Nightmare, la seule preuve que je connais utilise de l'algèbre linéaire et le corps Z/2Z (mais on peut évidement s'en passer en parlant de parité...)

Indic (blanc) :
Plus précisément, il faut évaluer le rang de matrices d'un certain type...

[carzou]

N'est ce pas immédiat par récurrence ?
- Vrai pour 3 cailloux (trivial)
- On suppose vrai pour 2n+1 cailloux
- On rajoute 2 cailloux, qui ont donc forcément le meme poids que les autres ?

[miikou]

N'est ce pas immédiat par récurrence ?
- Vrai pour 3 cailloux (trivial)
- On suppose vrai pour 2n+1 cailloux
- On rajoute 2 cailloux, qui ont donc forcément le meme poids que les autres ?

"donc forcement "? non c'est faux ..

[Finrod]

L'hypothèse supposée pour 2n+3 cailloux (si on en enlève un, on peut séparer en deux tas de même poid) ne suffit pas a assurer sans preuve que l'on a la même chose pour 2n+1 cailloux. Donc non, ça ne marche pas directement.

[Doraki]

Quand tu dis "on rajoute 2 cailloux", tu as l'air de supposer que dans un tas de 5 cailloux vérifiant l'hypothèse de l'énoncé, il existerait un sous-tas de 3 cailloux qui vérifie les hypothèses de l'énoncé.

En outre je vois pas d'où tu déduis qu'ils auraient le même poids.

[carzou]

L'hypothèse supposée pour 2n+3 cailloux (si on en enlève un, on peut séparer en deux tas de même poid) ne suffit pas a assurer sans preuve que l'on a la même chose pour 2n+1 cailloux. Donc non, ça ne marche pas directement.

Oui effectivement il y a une faute de raisonnement, j'avais supposé (à tort) que si l'on suppose vrai pour 2n+1, alors si l'on prend 2n+3 n'importe quel sous groupe de 2n+1 verifie l'hypothese, ce qui est faux bien sur ....

[Nightmare]

Salut,
Comme Nightmare, la seule preuve que je connais utilise de l'algèbre linéaire et le corps Z/2Z (mais on peut évidement s'en passer en parlant de parité...)

Indic (blanc) :
Plus précisément, il faut évaluer le rang de matrices d'un certain type...

Salut !

Quelle preuve vois-tu utilisant la parité?

[Nightmare]

Je crois avoir trouvé en "suivant" la construction :

Supposons qu'on soit dans une première configuration ou l'on ait deux tas A et B de n caillous même masse et un cailloux x de masse retiré.

Je réitère le processus avec un cailloux y à la place de x. Je choisis donc de rentrer par exemple x dans A et d'en sortir un cailloux y de masse . Pour équilibrer les masses des deux tas, je dois échanger un même nombre de cailloux entre les deux. Si j'appelle alors la masse des cailloux de A qu'on met dans B et la masse des cailloux de B qu'on met dans A, on a le bilan suivant :

.

Et comme on doit avoir m(B)=m(A), on a alors

Ainsi, si lorsqu'on échange x et y, 2|(m(x)-m(y)). On en déduit que c'est vrai pour n'importes quels paire de cailloux qu'on échange. En particulier, on obtient donc que 2|[m(1)-m(2)] puis 4|[m(x)-m(y)] donc 4|[m(1)-m(2)] d'ou 8|[m(x)-m(y)] etc.. vous l'aurez compris, on a donc m(x)-m(y)=0 d'ou m(x)=m(y) CQFD.

Qu'en pensez-vous?

[Finrod]

Pourquoi 2 divise m1-m2 ?

[Nightmare]

Il suffit de faire l'échange des masses m1 et m2 cailloux par cailloux, chaque échange apporte une différence de masse paire, l'échange global en le regroupant par paire de cailloux échangé fournit donc une différence de masse aussi paire non?

[Finrod]

Ben la différence de masse est pas entière donc divisible par 2 n'implique par pair.

[Ben314]

Je pense que le raisonnement de Nightmare fonctionne à condition de supposer les poids des différents cailloux entiers (ou, ce qui revient au même, quotient).

Perso, la preuve que je connais consiste à dire que l'énoncé dit trés exactement que le vecteur colonne (de taille 2n+1) formé des poids des cailloux est dans le noyau d'une matrice (2n+1)x(2n+1) telle que la diagonale contienne des 0, que, sur chaque ligne, à part le 0, il y ait n fois '1' et n fois '-1'.
Le noyeau de cette matrice contient évidement le vecteur colonne (1 1 1 ... 1) et pour démontrer le résultat, il suffit de montrer que le noyau est de dim 1, c'est à dire que le rang de la matrice est 2n.
Pour cela, il suffit de montrer qu'une matrice 2nx2n avec des 0 sur la diagonale et des +-1 ailleurs a un determinant non nul.
2 méthodes :
1) On regarde la matrice à coeff dans Z/2Z : tout les coeff non nuls deviennent des 1 et on calcule trés simplement le déterminant par récurrence.
2) On utilise la formule générale qui donne le déterminant comme somme sur toute les permutations, on constate que les termes de la somme non nuls sont égaux à +-1 et correspondent aux "dérangements", (i.e. aux permutations sans points fixes) qui sont en nombre impairs.

[Imod]

Bonjour à tous :we:

C'est en effet un problème classique ( habituellement avec des vaches ) . Il y a des solutions plus ou moins élaborées selon la nature des nombres ( entiers , rationnels , réels ) .

Pour les réels celle de Ben convient parfaitement :++:

Imod