Ensembles finis - algèbre linéaire (ENS Lyon)

Un problème, une question, un nouveau théorème ?

Messages : 0

Inscription : 15 mai 2017 21:23

Profil de l'utilisateur : Élève de lycée

Ensembles finis - algèbre linéaire (ENS Lyon)

Message par btsix » 05 avr. 2018 14:54

Bonjour,

J'ai trouvé un exercice intrigant dans le poly d'algèbre linéaire sur le site d'Alain Troesch :
Soit $ n \in \mathbb{N}^* $. Montrer que pour toute famille $ (X_i)_{i \in [\![ 1, n+1 ]\!]} $ de $ n+1 $ parties non vides de $ [\![ 1,n ]\!] $, il existe des sous-ensembles disjoints $ I $ et $ J $ de $ [\![ 1, n+1 ]\!] $ tels que :
$$
\bigcup_{i \in I} X_i = \bigcup_{j \in J} X_j
$$
Les vecteurs indicateurs des parties $ X_i $ dans le $ \mathbb{F}_2 $-espace vectoriel $ \mathbb{F}_2^n $ forment une famille liée, et la relation linéaire aboutit à l'existence de $ C \in \mathcal{P}([\![1, n+1]\!]) $ tel que $ \vert C \vert \geqslant 2 $ et :
$$
\sum_{i \in C} \mathbb{1}_{X_i} \equiv 0 \ [2]
$$

i.e. l'existence de $ A,B \in \mathcal{P}([\![1, n+1]\!]) \backslash \{\emptyset\} $ tels que :
$$
\bigoplus_{i \in A} X_i = \bigoplus_{j \in B} X_j
$$

$ \oplus = \Delta $ est l'opérateur de différence symétrique.
À partir de là, je n'arrive pas à conclure.

En bonus, je suis intéressé par toute résolution élémentaire qui n'utilise pas l'algèbre linéaire.

Merci.
Dernière modification par btsix le 05 avr. 2018 15:17, modifié 2 fois.

Messages : 0

Inscription : 15 mai 2017 21:23

Profil de l'utilisateur : Élève de lycée

Re: Ensembles finis - algèbre linéaire

Message par btsix » 05 avr. 2018 15:12

oups j'ai oublié de dire que I et J sont disjoints :)

Messages : 0

Inscription : 13 févr. 2018 09:22

Profil de l'utilisateur : Élève de lycée

Re: Ensembles finis - algèbre linéaire (ENS Lyon)

Message par matmeca_mcf1 » 05 avr. 2018 16:04

Avec l'algèbre linéaire, vous devez effectuer votre raisonnement en regardant un ev sur $ \mathbb{Q} $ et non un ev sur $ \mathbb{Z}/2\mathbb{Z} $. Considérez alors les signes des coefficients pour choisir I et J.
Ancien ENS Cachan (maths) 1999--2003
Enseignant-Chercheur à l'Enseirb-Matmeca (Bordeaux INP) filière matmeca
Les opinions exprimées ci-dessus sont miennes et ne reflètent pas la position officielle de l'école dans laquelle j'enseigne.

Messages : 0

Inscription : 15 mai 2017 21:23

Profil de l'utilisateur : Élève de lycée

Re: Ensembles finis - algèbre linéaire (ENS Lyon)

Message par btsix » 05 avr. 2018 16:41

Ah, je vois ! En fait même avec R^n en tant que R-ev ça marche aussi, non ?

Messages : 0

Inscription : 13 févr. 2018 09:22

Profil de l'utilisateur : Élève de lycée

Re: Ensembles finis - algèbre linéaire (ENS Lyon)

Message par matmeca_mcf1 » 05 avr. 2018 16:42

Je confirme que cela marche aussi avec R.
Ancien ENS Cachan (maths) 1999--2003
Enseignant-Chercheur à l'Enseirb-Matmeca (Bordeaux INP) filière matmeca
Les opinions exprimées ci-dessus sont miennes et ne reflètent pas la position officielle de l'école dans laquelle j'enseigne.

Messages : 0

Inscription : 15 mai 2017 21:23

Profil de l'utilisateur : Élève de lycée

Re: Ensembles finis - algèbre linéaire (ENS Lyon)

Message par btsix » 05 avr. 2018 16:45

D'accord, merci !

Messages : 6

Inscription : 30 avr. 2017 01:48

Profil de l'utilisateur : Élève de lycée

Re: Ensembles finis - algèbre linéaire (ENS Lyon)

Message par oty20 » 05 avr. 2018 20:40

Soit $ x_{i} \in \{0,1\}^{n} $ le vecteur caractéristique de $ X_{i} $ , comme on a $ n+1 $ vecteurs inclus dans R^{n} , cette famille ne peut être libre , d'ou l'existence de $ a_{1},...a_{n+1} $ non tous nuls tel que :
$ \sum_{i=1}^{n+1} a_{i}x_{i}=0 $ , soit $ i_{1} $ Le premier coefficient égal a $ 1 $ dans $ x_{1} $ , si pour tout les autres
$ x_{i} $ le coefficient $ i_{1} $ est nul , alors $ a_{1}=0 $ , le processus ne peut pas continuer indéfiniment vu que , les
$ a_{i} $ ne sont pas tous nul , soit donc $ a_{r} $ le premier coefficient non nuls de cette famille et $ i_{r} $ le premier coefficient égal a un $ 1 $ dans $ x_{r} $ , il existe donc $ j_{1},j_{2},..,j_{r}=r $ , tel que le coefficient $ i_{r} $ dans les vecteur $ x_{j_{1}}...,x_{j_{r}} $ est égal a $ 1 $ , d'ou $ a_{j_{1}}+a_{j_{2}}+..a_{j_{r}}=0 $ , je forme $ I $ a partir des indices $ i $ tel que $ a_{i} >0 $ et $ J $ a partir des indices $ j $ tel que $ a_{j} < 0 $
''L’ennemi du savoir , n'est pas l'ignorance , mais l'illusion du savoir '' .

Répondre