Anonymous
Anonymous asked in Science & MathematicsMathematics · 3 weeks ago

# Discrete math - pigeonhole theorem help?

Can someone teach me how to do the following? My teacher went over the pigeonhole theorem in class but literally nothing makes sense to me.

Use the pigeonhole principle to solve each of the following problems:

1. In an anonymous survey of a group of 20 men and 20 women, the men reported a total of 81 sexual encounters with women in the group, and all women reported having at most 4 sexual encounters with men in the group. Is everyone telling the truth?

2. A group of n agents all start at the same location and each one takes a ≤m-walk on the line, where a ≤m-walk is a sequence of at most m steps and each step moves the agent one unit to the left or one unit to the right. (Different agents might take different walks.) Prove that, if n>2m+1, then some pair of agents finishes their walk at the same location.

Relevance
• 3 weeks ago

Problem 1:

If the women are all telling the truth, then there are a total of 20*4 = 80 encounters, but the men claim 81. It's not possible for 81 pigeons to fit into 80 different pigeonholes, so someone is being untruthful. Either that or there was at least one pigeonhole (encounter with a woman) involving at least 2 pigeons (men).

Problem 2:

The pigeonholes are the m spaces to the left, the m spaces to the right, or the space where they started. That's 2m+1 pigeonholes, but if the number of agents is higher than that (n > 2m+1) then at least one of the agents (pigeons) must end up in the same pigeonhole (location).

• Dylan
Lv 6
3 weeks ago