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
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.
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
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.
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...
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.
20.02.2008 15:54
So, any corrections?
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$
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?