- Thread starter
- #1

- Mar 10, 2012

- 834

Using the Pigeon hole principle I was able to prove that $n \leq 9$. Then by computation (mostly) I arrived at the result that $n=7$.

The only counter examples I could find for $n=6$ are: $\{2,2,2,3,3,3 \}$, $\{0,0,0,1,1,1\}$, $\{0,0,0,3,3,3\}$, $\{1,1,1,2,2,2\}$. (I have taken integers mod $4$). I am pretty sure these are the only counter examples for $n=6$

2) DEFINITION: An element $(a,b) \in \mathbb{Z} \times \mathbb{Z}$ is said to be divisible by $4$ if $4|a$ and $4|b$. Summation of two elements $(a_1,b_1), (a_2,b_2) \in \mathbb{Z} \times \mathbb{Z}$ is simply $(a_1+b_1,a_2+b_2)$.

QUESTION: Given $n$ elements from $\mathbb{Z} \times \mathbb{Z}$. What is the minimum value of $n$ such that one can always choose $4$ elements from these $n$ elements such that summation of then chosen $4$ elements is divisible by $4$.

Using the result from (1) and using the pigeon hole principle we easily get 25 as an upper bound on the value of $n$. I am pretty sure this is not the

*minimum*value of $n$. Can someone bring down the upper bound or find the minimum value of $n$ (that would be great).