exercice sup, algèbre lineaire

Je change de prepa entre la sup et la spé et pour rattraper un potentiel retard j'essaie de faire quelques exos. Tandis que la plupart passe presque (du moins avec une indication) je reste complètement bloqué sur celui ci:

Soit $n \in \mathbb N*$ Soit $X_i$ ($ i \in \{1 ... n+1\}$) une famille de parties non vides de {1 … n} Montrer qu'il existe deux ensembles disjoints I et J tel que :

union […] = union […]

Comme indication, il y a qu'il faut passer par le vecteur indicateur des parties (dans $\{0,1\}^n$ je suppose donc ) et trouver une relation non triviale entre les vecteurs.

Malheureusement je n'arrive pas à trouver grand chose (le systeme est evidemment lié (n+1 vecteurs), on peut les supposer tous distincts (sinon trivial) , rien d'autre de réellement concluant )

Si quelqu'un a une piste un peu plus, disons précise, je suis preneur.

Tu es sûr que ce n'est pas des unions plutôt ? Parce qu'avec des intersections, c'est faux pour n=2 mais c'est vrai pour des unions (ce qui revient à interdire X_i={1,…,n} au lieu de X_i=∅). Par contre ma preuve ne passe pas par de l'algèbre linéaire (je ne vois pas comment parler de l'intersection ou de l'union dans ce langage (si on se met dans un demi-anneau ?), au contraire de la différence symétrique). Et ça prouve un truc plus fort et plus facile à prouver.

C'est bien des unions (mathjax m'affiche des intersections avant de passer aux unions, je pensais que c'était le cas pour tout le monde mais tu dois rester bloqué à l'étape 1 …)

Du coup tu t'es orienté vers quoi ? en tout cas qu'elle est le "truc plus fort et plus facile à prouver" ?

Merci

Pour les unions versus les intersections, si je regarde ton code tu as bien mis \bigcap, non ? C'est des intersections en latex. Bizarre tout ça…

Cherches des manières de te représenter la situation (tu en as déjà donnée une, avec des points du cube {0,1}ⁿ, mais je ne l'ai pas trouvée très utile). Ensuite tu peux supposer ta propriété vraie de 1 jusqu'à n-1, ça ne peut pas faire de mal… Regardes alors les cas éliminés par cette récurrence. Demandes-toi ensuite ce que tu aimerais prouver pour les cas non couverts (c'est légèrement plus fort que la propriété de départ du coup mais devient plus compliqué). Il reste encore des idées à trouver après ça mais voilà le début si ça peut te débloquer.

Si tu ne trouves pas d'autre représentation, voici celle que j'ai utilisée.

edit Sinon, je suis curieux de voir quelle preuve l'indication suggère… S'il y a une correction tu pourrais nous la donner quand tu auras résolu l'exo ? Quelqu'un a une idée ?

Tu as un premier ensemble, dont le cardinal est 2^n.

Et si tu regardes bien, tu as un 2ème ensemble dont le cardinal est 2^(n+1).

Or, ce 2ème ensemble est inclus dans le 1er ! Je te laisse conclure.

@elegance : Ça ne fonctionne pas, il faut que I et J soient disjoints. C'est aussi le premier truc auquel j'ai pensé aussi le principe des pigeons, mais je vois pas trop comment l'utiliser ici. Si c'était une différence symétrique au lieu d'unions ça fonctionnerait en enlevant à I et J les éléments qu'ils ont en commun (et on pourrait aussi faire avec de l'algèbre linéaire). Au fait, tu vois des unions ou des intersections ?

Dans ma première interprétation du problème, j'avais le sentiment que Union ou Intersection, les 2 se démontraient de la même façon. Mais avec ta remarque, je doute. Réponse demain, peut être.

Voila comment j'ai finalement traité le problème:

On se place dans $\mathbb R^n$, $\mathbb R$-ev (celui dont les vecteurs indicateurs à une composante égale à 1 forment une base) et on s’intéresse à E, l'ensemble des vecteurs de cette espace à coordonnées positifs.

On crée une partition de E en fonction de la nullité de chacune des composantes sur la base ($2^n$ classes, chaque vecteur de $\{0,1\}^n$ est un représentant de chaque classe)

On prend les vecteurs indicateurs des parties On a n+1 vecteurs non nuls pour un espace à n dimensions, ils sont donc forcément liés On prend une famille de coefficient $\alpha$ qui lie les vecteurs (en particulier $\alpha \neq (0,...,0)$)

Soit A l'ensemble des vecteurs indicateurs avec un coef positif Soit B l'ensemble des vecteurs indicateurs avec un coef negatif

N.B.: on ignore ceux avec un coef nul

Soit a la somme des vecteurs de A multipliés par $\alpha_i$, b la somme des vecteurs de B multipliés par - $\alpha_i$ On a : a - b = 0 donc a = b

En particulier on remarquera que : Soit Y,Z deux parties; Q,R les vecteurs associés, s,t dans $\mathbb {R^*_+}^2$ s.Q+t.R est dans la classe d'équivalence associée au vecteur de Y union Z

(il y a t'il un nom pour ce genre d'homomorphisme entre "demi-structure ?")

donc les parties associés aux vecteurs de A et ceux associés aux vecteurs de B recouvrent le même ensemble

Ah oui, c'est beaucoup plus simple que ce que j'ai fait !

La mienne passe par le théorème de Hall (on peut faire en utilisant le théorème ou bien en utilisant l'idée de sa preuve algorithmique). On commence par mettre un X_i de côté. Deux cas se présentent : soit on peut trouver parmi les X_i restants un nombre k d'ensembles dont l'union est de cardinal strictement inférieur à k, soit non. Dans le premier cas, on peut appliquer une récurrence. Dans le deuxième, on peut d'après le théorème de Hall coupler les X_i avec les entiers de 1 à n, de telle sorte que chaque ensemble contienne l'élément avec lequel il est couplé. Cela nous donne un graphe orienté à n nœuds, avec un arc de i vers j si l'ensemble couplé avec i contient j. On ajoute à ce graphe un nœud correspondant au X_i que l'on a mis de côté, avec un arc vers chaque entier qu'il contient. On considère la composante du graphe constituée des nœuds accessibles depuis ce nouveau nœud. On prend un arbre couvrant de cette composante (dont la racine est le nœud ajouté, tous les arcs de l'arbre dirigés comme on l'imagine). On sépare ensuite les nœuds en deux parties, en plaçant un nœud sur deux dans chaque partie lors d'un parcours de l'arbre. Chaque entier correspondant à un nœud de l'arbre est alors contenu dans un ensemble correspondant à un nœud pour chaque partie.

La question qui reste est de comprendre le lien entre ces deux manières de faire… Peut-être que l'on peut faire quelque chose en interprétant le graphe biparti comme un application linéaire sur ℝ²ⁿ⁺¹, je sais pas…

Sinon, qu'entends-tu par « demi-structure » ici ?

C'est à dire que l'on travail sur des structures stables par une loi mais qui ne presentent pas d'inverse: d'un coté l'ensemble des parties, stable par union avec un element nul ($\emptyset$) et de l'autre les classes d'équivalences muni de l'addition. Est-ce que cela forme des semi-groupes ? peut-on parler d'isomorphisme ?