How Can the Pigeonhole Principle Solve These Mathematical Puzzles?

  • MHB
  • Thread starter Yankel
  • Start date
  • Tags
    Principle
In summary: 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.For this, you can use the pigeonhole principle to get two points in the same square.
  • #1
Yankel
395
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
  • #2
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.
 
  • #3
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...
 

FAQ: How Can the Pigeonhole Principle Solve These Mathematical Puzzles?

What is the Pigeonhole Principle?

The Pigeonhole Principle is a mathematical concept that states that if there are more pigeons than pigeonholes, then at least one pigeonhole must contain more than one pigeon. In other words, if there are n objects and m containers with n>m, then at least one container must contain more than one object.

How is the Pigeonhole Principle used in problem-solving?

The Pigeonhole Principle is often used in problem-solving to prove the existence of a solution or to show that a certain scenario is impossible. It helps to identify patterns and relationships between objects and containers, and can be applied to various fields such as computer science, economics, and statistics.

What are some common examples of Pigeonhole Principle problems?

Some common examples of Pigeonhole Principle problems include the "Birthday Problem", where the probability of two people sharing the same birthday in a group is calculated, and the "Socks in a Drawer Problem", where the probability of having at least two socks of the same color in a drawer is determined.

What is the difference between the strong and weak forms of the Pigeonhole Principle?

The strong form of the Pigeonhole Principle states that if there are n+1 objects and n containers, then at least one container must contain more than one object. The weak form, on the other hand, states that if there are n+1 objects and n containers, then at least one container must contain exactly one object.

Can the Pigeonhole Principle be used to solve real-world problems?

Yes, the Pigeonhole Principle can be applied to solve real-world problems such as scheduling conflicts, resource allocation, and data analysis. It can also be used in decision-making processes, as it helps to identify constraints and limitations in a given situation.

Similar threads

Replies
2
Views
2K
Replies
1
Views
3K
Replies
7
Views
2K
Replies
1
Views
3K
Replies
10
Views
6K
Back
Top