Recitation 13 (c) In every set of 100 integers, there exist two whose difference is a multiple of 37 Solution. The pigeons are the 100 integers. The pigeonholes are the numbers 0 to 36. Map integer k to k rem 37. Since there are 100 pigeons and only 37 pigeonholes, two pigeons must go in the same pigeonhole. This means ki rem 37=k2 rem 37, which implies that k1- k2 is a multiple of 37. (d) For any five points in a unit square, there are two points at distance less than v2 Solution. The pigeons are the points. The pigeonholes are the four subsquares of the unit square, each of side length There are five pigeons and four pigeonholes, so more than one point must be in the same subsquare. Points in the same subsquare are at distance at most (e) For any five points in an equilateral triangle of side length 2, there are two points at distance less than 1 Solution. The pigeons are the points. The pigeonholes are the four sub-equilateral triangles of side length 1. There are five pigeons and four pigeonholes, so more than one point must be in the same sub-equilateral triangle. Points in the same sub-equilateral triangle are at distance at most 1 (f)Let al,..., a201 be a set of natural numbers less than 300. Then there are i, j such that 3 for some k>0 Solution. The pigeons are the numbers. The pigeonholes are the 200 numbers less than 300 that are not divisible by 3. Write each number ai= 3. bi, where bi is not divisible by 3. Place a; in the pigeonhole b;. Then there are two numbers ai, a, placed in the same pigeonhole, i.e. bi=bi, so ai= 3-c(Assume ci >c without loss of generalityRecitation 13 5 (c) In every set of 100 integers, there exist two whose difference is a multiple of 37. Solution. The pigeons are the 100 integers. The pigeonholes are the numbers 0 to 36. Map integer k to k rem 37. Since there are 100 pigeons and only 37 pigeonholes, two pigeons must go in the same pigeonhole. This means k1 rem 37 = k2 rem 37, which implies that k1 − k2 is a multiple of 37. 1 (d) For any five points in a unit square, there are two points at distance less than √ . 2 Solution. The pigeons are the points. The pigeonholes are the four subsquares of the unit square, each of side length 1 2 . There are five pigeons and four pigeonholes, so more than one point must be in the same subsquare. Points in the same subsquare 1 are at distance at most √2 . (e) For any five points in an equilateral triangle of side length 2, there are two points at distance less than 1. Solution. The pigeons are the points. The pigeonholes are the four sub­equilateral triangles of side length 1. There are five pigeons and four pigeonholes, so more than one point must be in the same sub­equilateral triangle. Points in the same sub­equilateral triangle are at distance at most 1. (f) Let {a1, . . . , a201} be a set of natural numbers less than 300. Then there are i, j such that ai = 3k for some k > 0. aj Solution. The pigeons are the numbers. The pigeonholes are the 200 numbers less than 300 that are not divisible by 3. Write each number ai = 3ci bi, where bi · is not divisible by 3. Place ai in the pigeonhole bi. Then there are two numbers ai, aj placed ai in the same pigeonhole, i.e. bi = bj , so aj = 3ci−cj . (Assume ci > cj without loss of generality)