(a) A bag contains n white socks and n black socks. You take socks out of the ba
ID: 3753954 • Letter: #
Question
(a) A bag contains n white socks and n black socks. You take socks out of the bag one at a time until you have two socks of the same color (a matching pair). How many socks do you need to take out of the bag to guarantee that you will have one matching pair? How many socks do you need to take out of the bag to guarantee that you will have k (1 k n) matching pairs? Justify your answer using the Pigeonhole Principle
(b) A bag contains n left shoes and n right shoes. You take shoes out of the bag one at a time until you have at least one left shoe and one right shoe (a matching pair). How many shoes do you need to take out of the bag to guarantee that you will have one matching pair? How many shoes do you need to take out of the bag to guarantee that you will have k (1 k n) matching pairs? Justify your answer using the Pigeonhole Principle.
3. (a) A bag contains n white socks and n black socks. You take socks out of the bag one at a time until you have two socks of the same color (a matching pair). How many socks do you need to take out of the bag to guarantee that you will have one matching pair? How many socks do you need to take out of the bag to guarantee that you will have k (1S k n) matching pairs? Justify your answer using the Pigeonhole Principle. (b) A bag contains n left shoes and n right shoes. You take shoes out of the bag one at a time until you have at least one left shoe and one right shoe (a matching pair How many shoes do you need to take out of the bag to guarantee that you will have one matching pair? How many shoes do you need to take out of the bag to guarantee that you will have k (1 Skn) matching pairs? Justify your answer using the Pigeonhole PrincipleExplanation / Answer
a)The answer is 3. If I take 2 socks out, then either I get a matching pair or in the worst case I get 1 white and 1 black sock. When I pick the 3rd one, by pigeonhole principle it’s either white or black. But we already have 1 sock of each of white and black colors. Now, by the pigeonhole principle, the 3rd sock increases the number of white sock or black sock by 1. In either case, we will have a matching pair of any one color.
Similarly, if I take out 2(k - 1) + 2 (k - 1) = 4(k - 1) socks, either I will have at least k matching pair of socks (or 2k socks) of one color, or in the worst case I will have (k - 1) matching pair of socks (or 2k - 2) of each color. When I pick the next 3, by the argument used in the above answer, it will have at least 1 matching pair of socks of either white or black color. Since, there are already (k - 1) matching pairs of socks of each color. Taking out the next 3 socks adds 1 more matching pair of any white or black color, hence by pigeonhole principle increases the number of matching pairs of either white or black socks by 1 and makes it to k matching pairs (1 <= k <= n). The total number of socks to be taken out is 4(k - 1) + 3 = 4k - 1.
b)If I take out n shoes, in the worst case all of them could be of the same foot (left or right). Hence, without loss of generality, let us assume that all of them are left shoes. Thus, there are no left shoes in the bag any more. Since there are n shoes for each foot, by pigeonhole principle, when I take out the (n + 1)th shoe, it is impossible for all of them to be for the same foot. At least (n + 1) - n = 1 of them is from a different foot. Hence we have at least 1 shoe for each foot, hence 1 matching pair. The minimum number of shoes to take out is = (n + 1).
Similarly, if I take out (n + 2) shoes, at most n of them can be for one foot. Hence, by pigeonhole principle, the other 2 are for a different foot. Thus we will have 2 matching pair of shoes. Extending the same argument, we can claim that taking out (n + k) shoes (1 <= k <= n) will give us, by pigeonhole principle, at least k matching pair of shoes. Hence, the answer is (n + k).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.