Let $n\geq 1$ and B a group of elements $(i _1,i_2,…,i_n)$ so $i_j \in \{-1,1\}$. Let’s assume $ |B|>\dfrac{2^{n+1}}{n}$. Show that exists 3 diffrent elements in B so every 2 of them differ from each other in exactly 2 coordinates( 3 points in B are vertexes of a Equilateral triangle with length √8)
Tried to solve with pigeon hole principle but it doesn't really work.I really not sure what to even try to use in the question. If someone have any leads how to try and solve it will be really helpful
It can be solved using double counting method and pigeonhole principle. Define for $v=(v_i)_{i=1}^n$ and $ w=(w_i)_{i=1}^n$ in $V:=\{-1,1\}^n$, $$ d(v,w) = |\{i \;|\;v_i \neq w_i\}|. $$ That is, $d(v,w)$ is the number of coordinates $i$ such that $v_i \neq w_i$. We will show there exist $v\in V$ and distinct $w_i \in B$, $i=1,2,3$ such that $d(v,w_i) = 1$ for $i=1,2,3$. Then it follows $d(w_i, w_j) = 2$ for all $i\neq j$ as we wanted.
Proof: Let us define $$X= \{(v,w)\in V\times B\;|\;d(v,w) =1\}. $$ We will count $|X|$ using double counting method. First, note that $$ |X| = \sum_{(v,w)\in X}1 = \sum_{v\in V} |\{w\in B\;|\; d(v,w) = 1\}|. $$ On the other hand, we have $$ |X| = \sum_{w \in B} |\{v\in V \;|\; d(v,w) =1\}| =\sum_{w \in B} n = n|B|>2^{n+1}. $$ Since $|V| = 2^n$, this gives us $$ \frac{1}{|V|}\sum_{v\in V} |\{w\in B\;|\; d(v,w) = 1\}|>2. $$ By pigeonhole principle, it follows that there exists $v\in V$ such that $$ |\{w\in B\;|\; d(v,w) = 1\}|\ge 3. $$ Thus, there exist distinct $w_i, i=1,2,3$ in $B$ such that $d(v,w_i) = 1$. This proves the claim.