You awake in your tent in pitch darkness and need to get dressed. You know that

Question

You awake in your tent in pitch darkness and need to get dressed. You know that your knapsack contains white, brown, blue, and black socks. Use the pigeonhole principle to determine the minimum number of socks that you must carry to the nearby campfire in order to be sure of having a pair with matching colors.

(a) 5

(b) 6

(c) 7

(d) 8

The key step for each problem is to identify the appropriate “pigeons”and “pigeonholes.”

1. Choose any five points inside the unit square. Prove that there is at least one pair for which the distance between the points is less than 1/ 2 ==> (1/sqrt(2)) . Hint: Split the square into equal-sized regions.

2. Show in the case of the 5 × 5 grid problem done in the minilecture that some square winds up empty

Explanation / Answer

You awake in your tent in pitch darkness and need to get dressed. You know that your knapsack contains white, brown, blue, and black socks. Use the pigeonhole principle to determine the minimum number of socks that you must carry to the nearby campfire in order to be sure of having a pair with matching colors.

(a) 5

(b) 6

(c) 7

(d) 8

Ans:

Here your legs will act as “pigeons”

and socks will act as “pigeonholes"

there are 4 different colored socks so your first leg (pigeon) can go into any one of those socks means total 4 choices . (those 4 choices may contain matching pair already but not guarnteed)

so to be sure that your second leg gets matching socks, at least one more sock is needed

hence total 5 socks needed to be sure of having a pair with matching colors.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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