Let $S$ be the set of $n$-uples $\left( x_{1}, x_{2}, \ldots, x_{n}\right)$ such that $x_{i}\in \{ 0, 1 \}$ for all $i \in \overline{1,n}$, where $n \geq 3$. Let $M(n)$ be the smallest integer with the property that any subset of $S$ with at least $M(n)$ elements contains at least three $n$-uples \[\left( x_{1}, \ldots, x_{n}\right), \, \left( y_{1}, \ldots, y_{n}\right), \, \left( z_{1}, \ldots, z_{n}\right) \] such that \[\sum_{i=1}^{n}\left( x_{i}-y_{i}\right)^{2}= \sum_{i=1}^{n}\left( y_{i}-z_{i}\right)^{2}= \sum_{i=1}^{n}\left( z_{i}-x_{i}\right)^{2}. \] (a) Prove that $M(n) \leq \left\lfloor \frac{2^{n+1}}{n}\right\rfloor+1$. (b) Compute $M(3)$ and $M(4)$.
Problem
Source: Romanian TST 2 2007, Problem 4
Tags: floor function, geometry, 3D geometry, pigeonhole principle, combinatorics proposed, combinatorics
probability1.01
16.04.2007 03:12
Call two n-tuples neighbors if they differ by exactly one element. If $M(n) > \lfloor \frac{2^{n+1}}{n}\rfloor+1$, then for the corresponding S, each element of S has n neighbors. Now $nM(n) > n \lfloor \frac{2^{n+1}}{n}\rfloor+1 \ge 2^{n+1}$, so there is some n-tuple x such that three elements a, b, and c of S are neighbors of x. Then these three elements eacher differ from each other in two places, a contradiction. Now to find M(3) and M(4). For n = 3, we can have 000, 100, 010, 110. If we could have 5 elements, we can't have three elements with the same number of 1's. Also, either some two have exactly one 1, or some two have exactly one 0, and WLOG we'll take the latter. Then we can not have 000, so then we must have some pair having exactly one 1. But that means we can't have 111, so either some three have exactly one 1 or some three have exactly one 0, contradiction. For n = 4, we can have 0000, 1000, 0100, 1010, 0101, 0111, 1011, 1111, and by the arguments in proving the general bound, we can show that this is optimal.
Megus
16.04.2007 12:06
probability1.01 wrote: If $M(n) > \lfloor \frac{2^{n+1}}{n}\rfloor+1$, then for the corresponding S, each element of S has n neighbors. Now $nM(n) > n \lfloor \frac{2^{n+1}}{n}\rfloor+1 \ge 2^{n+1}$, so there is some n-tuple x such that three elements a, b, and c of S are neighbors of x. Then these three elements eacher differ from each other in two places, a contradiction. I don't get a single thing from it, could you elaborate on it? maybe I'm just blind at the moment
pohoatza
21.04.2007 10:45
probability1.01 wrote: Now to find M(3) and M(4). For n = 3, we can have 000, 100, 010, 110. If we could have 5 elements, we can't have three elements with the same number of 1's. Also, either some two have exactly one 1, or some two have exactly one 0, and WLOG we'll take the latter. Then we can not have 000, so then we must have some pair having exactly one 1. But that means we can't have 111, so either some three have exactly one 1 or some three have exactly one 0, contradiction. actually $M(3)=5$ is the sollution. and a hint for finding this is by considering a cube and translating the problem geometrically.
probability1.01
21.04.2007 15:28
I think I proved M(3) = 5. Except I thought M(n) was the largest integer such that you don't have three elements of equal distance to each other, so it looks like I have M(3) = 4. Unless you really meant M(3) = 6? To Megus, I just used the pigeonhole principle...
radio
31.12.2007 07:57
probability1.01 wrote: $ n \lfloor \frac {2^{n + 1}}{n}\rfloor + 1 \ge 2^{n + 1}$, This is not true! Take $ n=5$ as an example.
radio
20.02.2008 15:54
So, any corrections?
limsk1
21.02.2008 06:24
i think he wanted to write $ n(\lfloor \dfrac{2^{n + 1}}{n} \rfloor + 1)$ then there is no error in the solution and maybe $ M(3)=5$ $ M(4)=9$
P-H-David-Clarence
27.10.2016 04:23
pohoatza wrote: probability1.01 wrote: Now to find M(3) and M(4). For n = 3, we can have 000, 100, 010, 110. If we could have 5 elements, we can't have three elements with the same number of 1's. Also, either some two have exactly one 1, or some two have exactly one 0, and WLOG we'll take the latter. Then we can not have 000, so then we must have some pair having exactly one 1. But that means we can't have 111, so either some three have exactly one 1 or some three have exactly one 0, contradiction. actually $M(3)=5$ is the sollution. and a hint for finding this is by considering a cube and translating the problem geometrically. What are you talking about?How can you get 5?