Isn't 126 integers enough?

Albanian Eagle, I think isn't. Lets took all integers looks like $ 1 + 23*i$, $ 2 + 23*i$, $ 3 + 23*i$, $ 4 + 23*i$, $ 5 + 23*i$, $ 6 + 23*i$ for all $ i$ bigger than $ - 1$ and lesser than $ 22$. All this numbers lesser than $ 501$, because $ 23*21 + 6 = 489$. It's easy to see that for $ t = 2$ we cann't choose $ a_1$, $ a_2$, $ a_3$, $ a_4$. And we choose $ 22*6 = 132$ - more than $ 126$ integers. But if we use one theorem about prime numbers it will be obvious that something about 200 integers is enough. Theorem: if we have $ 2$ set $ A$ and $ B$ of remainders at prime modulus $ p$ wiht $ k$ and $ l$ elements. Then set of sums pair of elements from $ A$ and $ B$ (Set of remainders $ a + b$, where $ a$ - element from $ A$ and $ b$ element from $ B$) have at least $ k + l - 1$ element. (or $ p$ elemets if $ k + l - 1 > p$). But i suppose people from junior league at Tuymaada don't know this theorem. Maybe i am wrong.) Sorry for my very bad english, I hope i didn't make a mathematical mistake.

Akella wrote: Theorem: if we have $ 2$ set $ A$ and $ B$ of remainders at prime modulus $ p$ wiht $ k$ and $ l$ elements. Then set of sums pair of elements from $ A$ and $ B$ (Set of remainders $ a + b$, where $ a$ - element from $ A$ and $ b$ element from $ B$) have at least $ k + l - 1$ element. (or $ p$ elemets if $ k + l - 1 > p$). But i suppose people from junior league at Tuymaada don't know this theorem. Maybe i am wrong.) It seems to me that this is Cauchy-Davenport theorem. I'm pretty sure that this theorem can not be used at Tuymaada olympiad,if one doesn't prove it during the contest.And I'm sure that 8 or 9 grader wouldn't be able to find its proof. So let's try to find proof without using of this theorem...

Erken wrote: It seems to me that this is Cauchy-Davenport theorem. Thank you. I always forgot names of theorems. And i think simple solution is something like this: Obvious that we not need numbers and need only they remainders at modul $ 23$. Also every remainder we can take maximally $ 22$ times. (because $ 23*22 = 506 > 501$). Then obviously there is a remainder that we take at least 2 times. Let it be $ a$. And let our problem is wrong and $ t$ is the remainder such that for it we cann't choose $ a_1$, $ a_2$, $ a_4$, $ a_4$. Then let $ a_3 = a_4 = a$. We cann't choose $ a_1$ and $ a_2$ such that $ a_1 + a_2 = (t - 2a)$ (at modul $ 23$ off course). Then we take $ 12$ pairs of remainders such that sum of remainders in every pair is $ (t - 2a)$. (every remainder is element of only one pair, and one pair has two equate elements). In every pair we have only $ 1$ element. Then maximum number of elements that we can take is $ 11*22 + 1 + 2 = 245 < 250$. ($ 11$ elements from $ 11$ pairs with inequate remainders, $ 1$ element from pair with equate remainders and $ 2$ elements that we take at the beginnig of solution)

Very very nice!!

By the way the thorem of Chaushy Davenport has a quite nice and beautiful solution by using the so called Combinatorial Nullstellensatz

Modulo 23, there can be at most 22 equal remainders among the 250. Let's split remainders into "good", that is, ones that do not reoccur more than 4 times among the 250 numbers, and "bad" that occur 5 and more times. Say, there are $ n$ numbers that give good remainders, then there are at least $ \frac{250 - n}{22}$ bad remainders. Let's form sets $ A_1, A_2, A_3, A_4$ from the 250 remainders as follows: split reocurring good remainders into different sets, and let each bad remainder occur in all 4 sets. This can be done in a manner such that none of the 4 sets remains empty. Then $ |A_1| + |A_2| + |A_3| + |A_4| \geq n + 4\frac{250 - n}{22} = \frac{11n + 500 - 2n}{11} \geq \frac{500}{11}$, so $ |A_1| + |A_2| + |A_3| + |A_4| \geq 46.$ Let $ f(a_1, a_2, a_3, a_4) = (a_1 + a_2 + a_3 + a_4 + t)^{22} - 1$ Then $ f(a_1, a_2, a_3, a_4) = \sum_{k_1 + k_2 + k_3 + k_4 + k_5 = 22}{\frac{k_1!k_2!k_3!k_4!k_5!}{22!}{a_1}^{k_1}{a_2}^{k_2}{a_3}^{k_3}{a_4}^{k_4}t^{k_5}} - 1$ (where $ k_i$ are nonnegative integers), and in particular, coefficient of each monomial of the form $ {a_1}^{k_1}{a_2}^{k_2}{a_3}^{k_3}{a_4}^{k_4}$ with $ k_1 + k_2 + k_3 + k_4 = 22$, is nonzero. Choose $ k_1, k_2, k_3, k_4$ in a way that $ k_1 < |A_1|, k_2 < |A_2|, k_3 < |A_3|, k_4 < |A_4|$ and $ k_1 + k_2 + k_3 + k_4 = 22$ (this is possible since $ |A_1| + |A_2| + |A_3| + |A_4| \geq 26$ and none of the sets is empty). Apply now Combinatorial Nullstellensatz: there should exist $ a_1 \in A_1, a_2 \in A_2, a_3 \in A_3, a_4 \in A_4$ such that $ f(a_1, a_2, a_3, a_4) \neq 0$. That, in turn, means that $ a_1 + a_2 + a_3 + a_4 + t = 0$, q.e.d.

p.s. the proof actually shows that 143 numbers is always enough. There's a gap between 126 and 143... I wonder what's the least number for which the problem statement is still valid