KGD a écrit:
[quote=« Liebig »]
On se donne un entier non nul d\in\mathbb{N}^* et pour tout (x,y)\in\{0,1\}^d (c’est à dire x=(x_1,...,x_d), y=(y_1,...,y_d) où les x_i et y_j sont des 0 ou des 1), on pose x.y=x_1y_1+x_2y_2+...+x_dy_d.
On fixe maintenant un w\in\{0,1\}^d tel que w\neq (0,...,0).
Montrer que \sum_{x\in\{0,1\}^d} (-1)^{w.x}=0 (c’est à dire la somme sur tous les éléments x\in\{0,1\}^d de (-1)^{w.x}).
Soit f: \{0,1\}^d \to \mathcal{P}([\![1,d]\!]) qui à tout d-uplet x=(x_1,...,x_d) associe l’ensemble X = \{k \in [\![1,d]\!] / x_k = 1\}. Elle est bijective et sa réciproque associe à toute partie X de [\![1,d]\!] le d-uplet x=(x_1,...,x_d) où x_i = 1 si i \in X et 0 sinon.
On vérifie (plus bas) que pour tous d-uplets x et y, on a x.y = |X\cap Y| donc que la somme peut également s’écrire: \displaystyle S = \sum_{X \in \mathcal{P}([\![1,d]\!])} (-1)^{|X\cap W|}. On vérifie ensuite que la relation X \sim Y \Leftrightarrow X \cap W = Y \cap W est une relation d’équivalence sur \mathcal{P}([\![1,d]\!]) (évident) et on pose Q = \mathcal{P}([\![1,d]\!])/\sim l’ensemble quotient (on note \~ X la classe de X). On montre que toutes les classes de Q sont équipotentes (notons le cardinal C) et que chaque classe de Q contient une unique partie de W. On peut donc écrire:
\displaystyle S = \sum_{\~X \in Q} C(-1)^{|X\cap W|} = C\sum_{X \in \mathcal{P}(W)} (-1)^{|X|}.
En regroupant les parties de Q selon leur cardinal, on obtient: \displaystyle S = C\sum_{k=0}^{|W|}{|W| \choose k} (-1)^k = 0
Démonstrations des propositions:
Pour tous d-uplets x,y, on a x.y = |X\cap Y|:
On a \displaystyle x.y = \sum_{k=1}^d x_ky_k. Or, on a x_ky_k = 1 \Leftrightarrow x_k = 1, y_k = 1\Leftrightarrow k \in X\cap Y
Donc: \displaystyle x.y = \sum_{k \in X\cap Y} 1 = |X\cap Y|
Toutes les classes d’équivalence pour \sim sont équipotentes:
Soient alors X et Y deux parties de [\![1,d]\!], on définit g: \~X \to \~Y par g(A) = (A\backslash(A\cap W)) \cup (Y\cap W) où Y est un représentant quelconque de \~Y. Elle est bijective de réciproque g^{-1}(A) = (A\backslash(A\cap W)) \cup (X\cap W) où X est un représentant quelconque de \~X donc toutes les classes d’équivalence sont équipotentes (on montre qu’elles sont de cardinal 2^{d - |W|} mais la flemme d’écrire 
).
Chaque classe de Q correspond à une unique partie de W
Soit f: \mathcal{P}(W) \to Q qui associe à X \subset W sa classe \~X. f est injective car on a \~X = \~Y \Leftrightarrow X\cap W = Y \cap W \Leftrightarrow X = Y car X et Y sont des parties de W. Elle est surjective car pour toute classe \~X\in Q, il suffit de prendre pour antécédent X\cap W (X étant un représentant quelconque de \~X) et donc bijective. Chaque classe de Q contient donc une unique partie de W.
[/quote]
T’as sorti l’artillerie lourde là 
.
Moi j’ai une presque-solution plus élémentaire. Il me reste un truc (le plus important en fait) à montrer.
Si on note x=(x_{1};x_{2};...;x_{n}), la somme à calculer est un des cas suivants (aux indices près mais étant donné que c’est symétrique, ça ne pose pas problème) : \sum (-1)^{x_{1}} ou \sum (-1)^{x_{1}+x_{2}}… ou \sum (-1)^{x_{1}+x_{2}+...+x_{d}} suivant que w contient un seul 1, deux 1,…; d 1. Maintenat il faut montrer que dans chaque cas le nombre d’exposants pairs est égal au nombre d’exposants impairs c’est à dire 2^{n-1}. J’ai une piste mais toute idée est la bienvenue 
Edit: Vlastilin finit la preuve sans passer par ma disjonction de cas
, c’était faisable sans programme de sup?
