Apply the pigeonhole principle to answer the following question. If the pigeonho

Question

Apply the pigeonhole principle to answer the following question. If the pigeonhole principle can not be applied, give a specific counterexample.

Seven members of the track team run the mile. Their mile times are all faster than 7 minutes but not faster than 6 minutes. Can you conclude that there are two runners whose times are less than nine seconds apart? What if there are eight runners? Times are measured to a precision of 0.01 second.

Seven members of the track team run the mile. Their mile times are all faster than 7 minutes but not faster than 6 minutes. Can you conclude that there are two runners whose times are less than nine seconds apart? What if there are eight runners? Times are measured to a precision of 0.01 second.

Explanation / Answer

Pigeonhole principle states that if n pigeons are slotted into m holes, where n>m then there will be atleast one hole which will have more than 1 pigeon.

In our race, there are 7 racers whose timings are between 6 minutes and 7 minutes (i.e there are 60 seconds)

Let us say that the first racer completes at 6 mins 1 second.

to put 7 racers with 9 seconds apart we needs(7-1)*9 = 54 seconds between 1st racer and the last racer as follows

So we can't say for certainty that there are two runners whose times are less than nine seconds apart.

If there are eight runners, then we will require (8-1)*9 = 63 seconds between 1st racer and the last racer. But we have only 60 seconds between 6 minutes and 7 minutes.

So we can conclude that there are atleast 2 runners whose times are less than 9 seconds apart.

Racer minutes seconds 1 6 1 2 6 10 3 6 19 4 6 28 5 6 37 6 6 46 7 6 55

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.