Un exercice vraiment vache
Vous avez un troupeau de 101 vaches vérifiant l’hypothèse suivante : chaque fois que vous prenez 100 vaches parmi elles il est possible de les séparer en deux parties de 50 vaches telle que les deux parties ont le même poids.
Démontrez que toutes les 101 vaches ont le même poids.
D’ailleurs, pour ceux qui se sont posés la question : le poids d’une vache (Bos primigenius taurus) se situe entre 500 et 800 kg, et celui d’un taureau peut atteindre 1200 kg. Evidemment cela n’a pas d’importance pour l’exercice.
Et comme je n’aime pas les billet trop courts, voici un autre exercice (indépendant du premier). Retrouvez les neuf mathématiciens célèbres cachés dans la phrase suivante :
Quand t’auras fini de classer des cartes et de les ranger, coche ici et ferme à clef la grange : la
dernière fois t’as laissé tout ouvert, et les chats l’ont saccagée et ont volé des poissons.
Cantor Descartes Euler Cauchy Fermat Lagrange Thalès Chasles Poisson.
Pour les vaches, je sèche pour l’instant… J’ai une matrice plein de +1 et -1 avec une valeur propre (0) mais je n’arrive pas à avancer…
Je crois que ça y est… (mais c’est des vieux souvenirs de maths pas touchées depuis 10 ans…)
n=101 (mais en fait pour tout impair ça marche)
On note C la matrice de Mn(R) telle que :
c_ij = +/- 1 si i est différent de j
c_ii = 0
somme(c_ij)(j=1_n) = 0 pour tout i
Cette matrice représente une façon de partager en deux lots égaux les vaches sauf la vache i (d’où le 0 sur la diagonale)
On veut montrer que le noyau de C est de dimension 1
V = (1….1) est un vecteur non nul de R^n tel que C*V = 0 et donc dim(Ker(C)) >= 1
On considère pour i dans 2…n le vecteur colonne Ui = (0 … 0 c_1i 0 … 0) où c_1i (non nul) est mis en position i
On a Vi = C*Ui = (1 +/-1 … +/-1 0 +/-1 … +/-1) avec le 1 en position 1 et le zero en position i
pour tout (l,k) dans [2,n]^2 Vl et Vk sont indépendants donc dim(Im(C)) >= n-1
comme dim(Im(C))+dim(Ker(C)) = n, on a dim(Ker(C)) = 1 et donc le seul vecteur propre de la valeur propre 0 est bien (1…1)
Je ne comprends pas la conclusion dim(Im(C)) >= n-1. Vous avez dans l’image des couples de vecteurs non-colinéaires — comment en déduire votre minoration ? A mon avis on peut seulement en déduire dim(Im(C)) >= 2.
ah oui… zut… ça suffit pas qu’ils soient indépendants 2 à 2 pour qu’ils soient une famille libre…
on dirait que le déterminant d’une matrice carée de dimension paire de diagonale nulle et avec que des +/- 1 est un entier impair mais j’arrive pas à le montrer… je suis sur la piste ?
Supposons par l’absurde que C soit de rang < n-1. Comme C est une matrice à coefficients rationnels, il existe un vecteur X à coefficients rationnels, non proportionnel à V, tel que CX=0. Quitte à retrancher un multiple de V, on peut supposer que la somme des coefficients de X est nulle. De plus, après multiplication de X par une constante, on peut supposer que les coefficients de X sont des entiers premiers entre eux dans leur ensemble. Soit i tel que \(x_i\) soit impair. Il existe une partition \(S\amalg T\) de \(\{1,\ldots,n\}\backslash \{i\}\) telle que \(x_S=x_T\), où \(x_S = \sum_{j\in S}x_j\). Comme \(x_i + x_S + x_T = 0\), on en déduit que \(x_i = -2x_S\), ce qui contredit le fait que \(x_i\) est impair.
je ne comprends pas l’existence de la partition telle que X_S = X_T …
S est l’ensemble des j tels que \(c_{ij}=1\) et T est l’ensemble des j tels que \(c_{ij}=-1\). Comme le i-ème coefficient de la colonne CX vaut \(x_S-x_T\), et que CX=0, on a bien \(x_S=x_T\).
ah oui, comme ça c’est clair…
de mon côté, j’ai montré (par récurrence) que la matrice avec des 1 partout sauf des 0 sur la diagonale à pour déterminant (-1)^(n-1)*(n-1) qui est bien impair pour n pair… mais je n’arrive pas pour des 1 et des -1…
MP : il suffit de reduire modulo 2.
Désolé de vous rejoindre si tard (je rentre de 4h de TD). Voilà tout est dit, le problème est résolu.
Ma propre solution était légèrement différente.
Je montre d’abord le résultat pour des poids entiers : on prouve sans peine que la différence de deux poids est toujours pair, donc ils sont tous pairs ou tous impairs. Quitte à ajouter 1 partout, on peut supposer qu’ils sont tous pairs. On peut donc diviser par 2 et on obtient un nouveau troupeau avec la même propriété mais la différence de poids entre la vache la plus légère et la plus lourde est aussi divisée par deux — et comme on peut continuer ainsi sans sortir des nombres entiers, cette différence était nulle dès le départ et tous les poids sont identiques.
Puis, par factorisation, on déduit le résultat pour les poids rationnels. Enfin, un simple raisonnement sur le rang montre que ça tient aussi pour des poids réels (et même complexes…).
Le 8 janvier 2010 MP disait :
Voici une idée très simple.
Lemme. Soit \(B\in {\scr M}_{2n}(\mathbb{Z})\) une matrice de coefficients diagonaux pairs et telle que ses autres coefficients sont impairs. Alors \(B\in GL(2n,\mathbb{Q}).\)
Preuve.
Pour tout entier k notons [k] sa classe dans \(\mathbb{Z}/2\mathbb{Z}.\) Par passage au quotient B induit une matrice [B] à coefficients dans \(\mathbb{Z}/2\mathbb{Z}.\) La diagonale de [B] est nulle et tous les autres coefficients sont [1]. On vérifie sans peine que [B] est une matrice orthogonale. Donc det([B])=[1]. Or le déterminant d’une matrice est un polynôme en les coefficients de la matrice et les coefficients de ce polynôme sont des entiers, donc le déterminant passe au quotient, c’est-à-dire det([B])=[det(B)].
Par conséquence det(B) et non-nul, donc B possède une inverse (à coefficients rationnels).