Solve Pigeon Hole Theory Problems

  • MHB
  • Thread starter JProgrammer
  • Start date
  • Tags
    Hole Theory
In summary, the man has to pull out 5 black socks, 11 brown socks, and 12 blue socks before he gets two of the same color.
  • #1
JProgrammer
20
0
So I need to use pigeon hole theory to solve these problems:

3. A man has 10 black socks, 11 brown socks and 12 blue socks in a drawer. He isn’t a morning person, so every morning he just reaches in and pulls out socks until he gets two that match.
a. Use the generalized pigeonhole principle to determine how many socks he has to pull out before he gets two of the same color.
b. How many must he pull out to be certain of getting a blue pair?

a. I am thinking that the pigeons are the colors and the pigeon holes are the number of socks that are pulled out. If that were the case, I believe the answer would be 5. But the number of each color of socks is not the same. So am I right about this or do I need to take into consideration the different amount of socks?

b. The most I could go with this problem is that since there are 33 socks total and 12 of those socks are blue, the pigeon hold theory would yield 3. My question is: where would I go from here?
 
Physics news on Phys.org
  • #2
JProgrammer said:
So I need to use pigeon hole theory to solve these problems:

3. A man has 10 black socks, 11 brown socks and 12 blue socks in a drawer. He isn’t a morning person, so every morning he just reaches in and pulls out socks until he gets two that match.
a. Use the generalized pigeonhole principle to determine how many socks he has to pull out before he gets two of the same color.
b. How many must he pull out to be certain of getting a blue pair?

a. I am thinking that the pigeons are the colors and the pigeon holes are the number of socks that are pulled out. If that were the case, I believe the answer would be 5. But the number of each color of socks is not the same. So am I right about this or do I need to take into consideration the different amount of socks?

b. The most I could go with this problem is that since there are 33 socks total and 12 of those socks are blue, the pigeon hold theory would yield 3. My question is: where would I go from here?

Hey JProgrammer! ;)

a. We're talking about a bad day here.
Worst case scenario is that he pulls out a black sock, a brown sock, and a blue sock.
After that there is no choice anymore - he will pull out one of the colors he already has.
So that means that with 4 socks he will get a pair.
That is, the pidgeon hole theory says that if you pull 4 items when there are only 3 choices, you'll get at least 2 identical choices.

b. Same thing - a bad day.
He can pick 10 black socks and 11 brown socks before getting to blue socks.
And then he still has to pull 2 blue socks.
 

FAQ: Solve Pigeon Hole Theory Problems

1. What is the Pigeon Hole Principle?

The Pigeon Hole Principle is a mathematical principle that states that if there are n items to be placed into m containers, with n > m, then at least one container must contain more than one item.

2. How is the Pigeon Hole Principle applied to problem solving?

The Pigeon Hole Principle is a useful tool in problem solving, particularly in situations where there are a limited number of options or outcomes. It can be used to prove the existence of a solution or to eliminate certain possibilities.

3. What types of problems can be solved using the Pigeon Hole Principle?

The Pigeon Hole Principle can be applied to a wide range of problems in various fields such as mathematics, computer science, and logic. It is commonly used in counting and probability problems, scheduling problems, and in proving the existence of solutions in number theory and graph theory.

4. Can you provide an example of a problem that can be solved using the Pigeon Hole Principle?

One example of a problem that can be solved using the Pigeon Hole Principle is the "Birthday Problem". In this problem, a group of people are asked to guess each other's birthdays. According to the Pigeon Hole Principle, if there are more people than days in a year, at least two people must share the same birthday. This principle can be used to calculate the probability of two people sharing the same birthday in a group of a certain size.

5. Are there any limitations to the Pigeon Hole Principle?

While the Pigeon Hole Principle is a useful tool in problem solving, it does have its limitations. It can only be applied to discrete situations where items are being placed into distinct containers. It also cannot be used to determine the exact number of items in a container, only that there must be at least one item. Additionally, it may not be applicable in certain situations where there are overlapping possibilities or when the items being placed are not distinct from each other.

Similar threads

Replies
1
Views
3K
Replies
14
Views
1K
Replies
2
Views
2K
Replies
5
Views
2K
Replies
19
Views
1K
Replies
12
Views
909
Replies
2
Views
2K
Back
Top