1. Use the pigeonhole principle to solve the following problems. (a) Prove that among a group of 621 people, there are at least 21 who are born on the same day of the month (e.g., the 21st or the 12th, etc.). Is the same fact true if there are only 620 people? (b) Prove that, for any n +1 integers, you can find two integers so that their difference is divisible by n. Hint: you will want the holes to be the remainder when you divide a value by n. (c) You randomly select k distinct integers between 1 and 100, inclusive. What is the smallest k that guarantees that at least one pair of the selected integers will sum to 101? Make sure to be very explicit about what the pigeons and pigeonholes are