Problem Set 7 On even-numbered days, I'll say I'm sick On days that are a multiple of 3 I'll say i was stuck in traffic On days that are a multiple of 5, ill refuse to come out from under the blankets In total, how many work days will I avoid in the coming year? Solution. Let D2 be the set of even-numbered days, D3 be the days that are a mul tiple of 3, and D; be days that are a multiple of 5. The set of days I can avoid is D2 U D3 U Ds. By the Inclusion-Exclusion Rule, the size of this set D2 U D3U D D2 D3+IDs I D2∩D3-|D2nDs-|D3nDs +|D2∩D3∩D5 300300300300300300 52.32.53·52.3·5 Problem 4. Use the pigeonhole principle to solve the following problems (a) Prove that among any n=+ l points within an n x n square there must exist two points whose distance is at most Solution. Partition the n x n into m- unit squares. Each of the n2+ 1 points lies in one of these n2 unit squares. (If a point lies on the boundary between squares, assign it to a square arbitrarily. Therefore, by the pigeonhole principle, there exist two points in the same unit square And the distance between those two points can be at most v2 (b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of each flavor. Prove that some jar contains at least three jellybeans of one flavor and also at least three jellybeans of some other flavor Solution. We use the pigeonhole principle twice. Since there are 11 beans of a given flavor and there are only 5 jars, some jar must get at least 111/5=3 beans of that flavor. Since there are 6 flavors and only 5 jars, some jar must get two pairs of same- flavored beans (c) Prove that among every set of 30 integers, there exist two whose difference or sum is a multiple of 51 Solution. Regard the 30 integers as pigeons. Regard the 26 sets 01, ( 1, 501, ( 2, 49) [25, 26) as pigeonholes. Map integer n to the set containing n rem 51. By the pigeonhole principle, some two pigeons(integers a and b)are mapped to the same pigeonhole. Thus, either a rem 51= b rem 51 and so the difference of a and b is a multiple of 51Problem Set 7 5 • On even­numbered days, I’ll say I’m sick. • On days that are a multiple of 3, I’ll say I was stuck in traffic. • On days that are a multiple of 5, I’ll refuse to come out from under the blankets. In total, how many work days will I avoid in the coming year? Solution. Let D2 be the set of even­numbered days, D3 be the days that are a mul￾tiple of 3, and D5 be days that are a multiple of 5. The set of days I can avoid is D2 ∪ D3 ∪ D5. By the Inclusion­Exclusion Rule, the size of this set is: |D2 ∪ D3 ∪ D5| | | | | | = D2| + D3 + D5 − | | − | | − | | D2 ∩ D3 D2 ∩ D5 D3 ∩ D5 + |D2 ∩ D3 ∩ D5| 300 300 300 300 300 300 300 = 2 + 3 + 5 − 2 3 − 2 5 − 3 5 + · · · 2 3 5 · · = 220 Problem 4. Use the pigeonhole principle to solve the following problems. (a) Prove that among any n2 + 1 points within an n × n square there must exist two points whose distance is at most √2. Solution. Partition the n × n into n2 unit squares. Each of the n2 + 1 points lies in one of these n2 unit squares. (If a point lies on the boundary between squares, assign it to a square arbitrarily.) Therefore, by the pigeonhole principle, there exist two points in the same unit square. And the distance between those two points can be at most √2. (b) Jellybeans of 6 different flavors are stored in 5 jars. There are 11 jellybeans of each flavor. Prove that some jar contains at least three jellybeans of one flavor and also at least three jellybeans of some other flavor. Solution. We use the pigeonhole principle twice. Since there are 11 beans of a given flavor and there are only 5 jars, some jar must get at least �11/5�= 3 beans of that flavor. Since there are 6 flavors and only 5 jars, some jar must get two pairs of same­ flavored beans. (c) Prove that among every set of 30 integers, there exist two whose difference or sum is a multiple of 51. Solution. Regard the 30 integers as pigeons. Regard the 26 sets {0}, {1, 50}, {2, 49}, . . ., {25, 26} as pigeonholes. Map integer n to the set containing n rem 51. By the pigeonhole principle, some two pigeons (integers a and b) are mapped to the same pigeonhole. Thus, either: • a rem 51 = b rem 51 and so the difference of a and b is a multiple of 51