Pigeonhole Principle Problems

[Yankel]

Hello all,

I have a few small questions, related to the pigeonhole principle, which should be the guiding line for the solution. I had more, but solved the easier ones.

1) Prove that each series of 10 integer numbers has a sub-series of following numbers such that the sum of the sub-series is divisible by 10. For example: From 4,4,1,3,5,2,2,5,6,3 we can take 3,5,2

2) Prove that every choice of 5 points in a square with side equal to 2, has a couple of points that the distance between them is at most a square root of 2.

3) Prove that every choice of 5 points in a triangle that each of it's sides is 2, there is a couple of points that the distance between them is at most 1.

Thank you !

 

[Opalg]

2) Prove that every choice of 5 points in a square with side equal to 2, has a couple of points that the distance between them is at most a square root of 2.

3) Prove that every choice of 5 points in a triangle that each of it's sides is 2, there is a couple of points that the distance between them is at most 1.

For 2), divide the square into four smaller squares with side $1$. Any two points in the same smaller square will be within distance $\sqrt2$ of each other.

Similar idea for 3). This time, divide the triangle into four smaller equilateral triangles with side $1$.

In each case, you can then use the pigeonhole principle to get two points in the same smaller region.

 

[Evgeny.Makarov]

1) Prove that each series of 10 integer numbers has a sub-series of following numbers such that the sum of the sub-series is divisible by 10.

Here the pigeons are sums of subsequences that start from the first number (there are 10 of them) and the holes are non-zero remainders when divided by 10 (there are 9 of those). If some "pigeon" is divisible by 10, then the claim is proved. Otherwise there exist two subsequences whose sums have the same remainders...