CHAPTER 1
INITIAL EnCOUNTers WITH COMBINATORIAL REASONING

PROBLEM SET 1.2

1. 1.2.1  A bag contains 7 blue, 4 red, and 9 green marbles. How many marbles must be drawn from the bag without looking to be sure that we have drawn

   1. a pair of red marbles?
   2. a pair of marbles of the same color?
   3. a pair of marbles with different colors?
   4. three marbles of the same color?
   5. a red, blue, and green marble?

   Answer

   (a) 18    (b) 4    (c) 10    (d) 7    (e) 17

2. 1.2.3.  There are 10 people at a dinner party. Show that at least two people have the same number of acquaintances at the party.

   Answer

   Each person can know any where from 0 (no one) to 9 (everyone) people. But if someone knows no one, there cannot be someone who knows everyone, and vice versa. Thus, place the 10 people into the 9 boxes that are labeled 1, 2, … , 8, and 0|9. By the pigeonhole principle, some box has at least 2 members. That is, there are at least two people at the party with the same number of acquaintances.

3. 1.2.5  Given any five points in the plane, with no three on the same line, show that there exists a subset of four of the points that form a convex quadrilateral.

   [Hint: Consider the convex hull of the points; that is, consider the convex polygon with vertices at some or all of the given points that encloses all five points. This scenario can be imagined as the figure obtained by bundling the points within a taut rubber band that has been snapped around all five points. There are then three cases to consider, depending on whether the convex hull is a pentagon, a quadrilateral containing the fifth point, or a triangle containing the other two given points.]

   Answer

   If the convex hull is a pentagon, each set of 4 points are the vertices of a convex quadrilateral. If the convex hull is a quadrilateral, the convex hull itself is the sought quadrilateral. If the convex hull is a triangle, the line formed by the two points within the triangle separates the vertices of the triangle into opposite half planes. By the pigeonhole principle, there are two points of the triangle in the same half plane. These two points, together with the two points within the triangle, can be combined to form the desired convex quadrilateral.

4. 1.2.7  Given five points on a sphere, show that some four of the points lie in a closed hemisphere.

   [Note: A closed hemisphere includes the points on the bounding great circle.]

   Answer

   Pick any two of the five points and draw a great circle through them. At least two of the remaining three points belong to the same closed hemisphere determined by the great circle. These two points, and the two starting points, are four points in the same closed hemisphere.

5. 1.2.9.  Suppose that 51 numbers are chosen randomly from [100] = {1, 2, … , 100}. Show that two of the numbers have the sum 101.

   Answer

   Each of the 51 numbers belongs to one of the 50 sets {1, 100}, {2, 99}, … , {50, 51}. Some set contains two of the chosen numbers, and these sum to 101.

6. 1.2.11. Choose any 51 numbers from [100] = {1, 2, … , 100}. Show that there are two of the chosen numbers that are relatively prime (i.e., have no common divisor other than 1).

   Answer

   Place each of the 51 numbers into one of the 50 sets {1, 2}, {3, 4}, … , {99, 100}. One of the sets contains a pair of consecutive integers that are relatively prime.

7. 1.2.13. Choose any 51 numbers from [100] = {1, 2, … , 100}. Show that there are two of the chosen numbers for which one divides the other.

   Answer

   Any natural number has the form , where dm ≥ 0 and km is odd. Call km the odd factor of m. For example, the odd factor of 100 = 22 · 25 is k100 = 25. Thus, the odd factors of the 51 chosen numbers are in the set {1, 3, 5, … , 99}. Since this is a set with 50 members, two of the 51 chosen numbers have the same odd factor. The smaller is then a divisor of the larger, with a quotient that is a power of two.

8. 1.2.15. Consider a string of 3n consecutive natural numbers. Show that any subset of n + 1 of the numbers has two members that differ by at most 2.

   Answer

   Suppose the 3n consecutive numbers are a, a + 1, … , b. Each of the n + 1 numbers in the given subset belongs to one of the sets {a, a + 1, a + 2}, {a + 3, a + 4, a + 5}. … , {b – 2, b – 1, b}. By the pigeonhole principle, one of these sets has two members of the subset and these differ by at most 2.

9. 1.2.17. Suppose that the numbering of the squares along the spiral path shown in Example 1.9 is continued. What number k is assigned to the square S whose lower left corner is at the point (9, 5)?

   Answer

   We want to find a solution to the equations k = 11i + 9 and k = 16j + 5 for some integers i and j. This gives us 11i + 4 = 16j. Both 4 and 16 are divisible by 4, so we see that i is divisible by 4. If we let i = 4, then j = 3 and we obtain the solution k = 53. The next multiple of 4 giving a solution is i = 20, but then k = 229 and we see that the spiral is overlapping itself with repeated squares covered a second time.

10. 1.2.19. Generalize the results of Problem 1.2.18.

    1. How many spiral paths exist on the torus if m = n?
    2. Suppose d ≥ 2 is the largest common divisor of m and n. How many distinct spiral paths exist on the torus?

    Answer

    1. Any path returns to its starting position in m steps, so there are m spirals each covering m squares. For example, there are three paths when m = n = 3, as shown here.
    2. Since m/d and n/d are relatively prime, there is a unique spiral with mn/d2 steps that covers a d by d square at each step. For example, if m = 6 and n = 9, then d = 3, and there is a unique spiral of length of 3 × 3 squares that covers the torus. This is seen at the left in the figure below. By part (a) we see there are d nonintersecting spirals on the torus, each of length . The case m = 6, n = 9, d = 3, is shown at the right below, with the d = 3 paths each of length shown in black, white, and gray.

PROBLEM SET 1.3

1. 1.3.1.  Consider an m × n chessboard, where m is even and n is odd. Prove that if two opposite corners of the board are removed, the trimmed board can be tiled with dominoes.

   Answer

   The left and right hand columns of height n – 1 of the trimmed board can each be tiled with vertical dominoes. The remaining board is has all of its rows of even length m – 2, so it can be tiled with horizontal dominoes.

2. 1.3.3.  Suppose that the lower left j × k rectangle is removed from an m × n chessboard, leaving an angle-shaped chessboard. Prove that that angular board can be tiled with dominoes if it contains an even number of squares.

   Answer

   Since mn − jk = (m − k)n + (n − j)k is even, (m − k)n and (n − j)k have the same parity. If both are even, we can tile the resulting (m − k) × n and (n − j) × k rectangles. If both are odd, then n and k are odd thus m and j must be even. We can then tile the m × (n − j)n and (m − k) × j rectangles.

   Alternate answer

   View the angular region as the union of rectangles A, B, and C, where the corner rectangle B shares an edge with each of A and C. If all three rectangles have even area, the angle can be tiled since A, B, and C can each be tiled individually. If A and B, or B and C, each have odd area, then combining the odd rectangles shows that the angle is a union of two even area rectangles and therefore can be tiled. If A and C are odd, their edges are all of odd length and therefore rectangle B is also odd; the angular board therefore is not of even area.

3. 1.3.5.  Consider a...