MHB How Can the Pigeonhole Principle Solve These Mathematical Puzzles?

  • Thread starter Thread starter Yankel
  • Start date Start date
  • Tags Tags
    Principle
AI Thread Summary
The discussion focuses on applying the pigeonhole principle to solve mathematical puzzles involving integer sequences and geometric configurations. It asserts that any series of 10 integers contains a sub-series whose sum is divisible by 10, leveraging the concept of remainders. Additionally, it demonstrates that selecting 5 points within a square of side 2 guarantees at least one pair of points with a distance of at most the square root of 2, and similarly for a triangle with sides of 2, ensuring a distance of at most 1 between some points. The solutions involve dividing the larger shapes into smaller regions to apply the pigeonhole principle effectively. Overall, the principle serves as a powerful tool for proving these geometric and numerical properties.
Yankel
Messages
390
Reaction score
0
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 !
 
Physics news on Phys.org
Yankel said:
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.
 
Yankel said:
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...
 

Similar threads

Back
Top