Mathematics 357 – Combinatorics Problem Set 1 – Selected Solutions February 7, 2005

Chapter 2/13. Note: There are many correct ways to prove this. The key idea of the following “brute-force” proof is to use this consequence of the pigeonhole principle:

(*) At every one of the six points, there are three lines of the same color

“for all it’s worth.” So start at some vertex P. As we saw in class, there are three points Q, R, S such that the lines P Q, P R, P S all have the same color, say red. Then either one of the lines QR, QS, RS is also red so we have a red triangle, or else all three lines QR, QS, RS are blue so we have a blue triangle.

Case 1: Suppose one of the lines QR, QS, RS is red. In particular we may assume QR is red (by choosing the names of the three points appropriately), and P QR is our first monochromatic triangle (red). Now apply (*) at one of the two remaining points T ≠ P, Q, R, S. If the three lines of the same color at T are red, we have either a red triangle with one corner at T, or else a blue triangle. In either case, the new monochromatic triangle must be different from the first monochromatic triangle and the proof is complete. If the three lines of the same color at T are are blue, and the three endpoints are not Q, R, S, then we also have a second monochromatic triangle either way by the same reasoning and we are done. If the three lines at the same color at T are all blue, and the endpoints are Q, R, S, then the monochromatic triangle found starting from T is the same one we already know. Now we repeat the same argument using (*) at the one remaining point U, and we see that there is a second monochromatic triangle unless there are three blue lines at U, with endpoints Q, R, S again. So the only case left to consider (in Case 1) is the following:

We have several blue triangles (like T RU) in addition to the first red triangle if T U is blue. So we assume T U is red. P RS is a second red triangle if RS is red. So we assume RS is blue. But then RSU is a blue triangle if SU is blue. But then, assuming SU is red, either choice of color for ST produces a second monochromatic triangle. If ST is red then ST U is red; if ST is blue, then RST is blue. Hence in Case 1, we always get at least two distinct monochromatic triangles.

Case 2: Now assume that QR, QS, RS are all blue so the first monochromatic triangle found is the blue triangle QRS. Apply (*) at a fourth point T ≠ P, Q, R, S. As in Case 1, we find a second monochromatic triangle unless the three lines of the same color at T are all red and their endpoints are Q, R, S. Similarly applying (*) at the remaining point U, we get a second monochromatic triangle unless the three lines of the same color at U are all red, and they join U to Q, R, S. The situation in the case we have not yet handled is:

We get second monochromatic triangles (red) if any of P T, P U, T U are red. If they are all blue, then P T U is a second blue triangle. Hence also in Case 2, we always get at least two distinct monochromatic triangles.

Chapter 2/26. Instead of a “brute-force” argument for this one, we will present a “clever” approach, based on the following observation: If one of the band members in column j + 1 is taller than p different people in column j, then he or she must be taller than the pthshortest person in column j. In symbols, let a_{kl} denote the height of the person in row k and column l of the array in the original arrangement. We claim that if a_{k,j+1} ≥ a_{i,j} for p different row numbers i, then a_{k,j+1} ≥ a_{i(p),j} where i(p) denotes the row number where the pth shortest person appeared (in column j). This follows since if we put the people in column j into increasing order by height:

a_{i(1),j} ≤ a_{i(2),j} ≤ ⋯ ≤ a_{i(m),j}

and a_{k,j+1} ≥ a_{i,j} for p different i’s, then a_{k,j+1} ≥ a_{i(l),j} for at least one l ≥ p (pigeonhole!). But then a_{k,j+1} ≥ a_{i(p),j} also. Now, the proof is complete if we notice that for all j, the pth-shortest person in column j + 1 is taller than the person to his or her left in column j and also taller than all the people to the left of the p − 1 shorter people in column j + 1. Hence for all 1 ≤ j ≤ n − 1 and all 1 ≤ p ≤ m the pth-shortest person in column j + 1 is taller than the p-th shortest person in column j. This says that when the columns are rearranged in increasing height order front to back, the rows will still be increasing in height left to right(!)

Chapter 3/6. We want to count the numbers larger than 5400 with distinct digits, in which the digits 2, 7 do not appear. Note first that since the digits are distinct, the largest possible number of digits is 8. So we will partition the set of numbers by the number of digits appearing (Addition Rule), and then count each of those subsets using the Multiplication Rule (or general formulas for P (n, m)).

• There are 7P (7, 7) = 7 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 35280 8-digit numbers here, all larger than 5400 (the first factor of 7 counts the possible leading digits – all except 0, the second digit can then be chosen in 7 possible ways, etc.)

• There are 7P (7, 6) = 7 · 7 · 6 · 5 · 4 · 3 · 2 = 35280 7-digit numbers, all larger than 5400.

• There are 7P (7, 5) = 7 · 7 · 6 · 5 · 4 · 3 = 17640 6-digit numbers, all larger than 5400.

• There are 7P (7, 4) = 7 · 7 · 6 · 5 · 4 = 5880 5-digit numbers, all larger than 5400.

• The 4-digit numbers require some more care. Note that the first digit must be 5, 6, 8, 9, and if the first digit is 5, then the second must be 4, 6, 8, 9. If the first two digits are 5, 4, then the other two can be any of the P (6, 2) = 6˙5 = 30 ordered pairs of distinct numbers in {0, 1, 3, 6, 8, 9}. If the first digit is 5 but the second is larger than 4, we get 3 · 6 · 5 = 90 additional numbers. Finally, if the first digit is larger than 5, we get 3 · 7 · 6 · 5 = 630 additional numbers. The total number of 4-digit numbers is

30 + 90 + 630 = 750

and the total of all sizes is

2 · 35280 + 17640 + 5580 + 750 = 94830.