\magnification=\magstep1
\centerline{Mathematics 357 -- Combinatorics}
\centerline{Problem Set 1 -- Selected Solutions}
\centerline{February 7, 2005}
\bigskip
\noindent
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:
\bigskip
\noindent
{\it (*) At every one of the six points, there are three lines of 
the same color}
\bigskip
\noindent
``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 $PQ,PR,PS$ 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.
\bigskip
\noindent
{\it 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 $PQR$ is our 
first monochromatic triangle (red).  Now apply (*) at one
of the two remaining points $T \ne 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
{\it 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:  
\vglue 1.0truein
\noindent
We have several blue triangles (like $TRU$) in addition to 
the first red triangle if $TU$ is blue.  So we assume
$TU$ is red.  $PRS$ 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 $STU$ is red; if $ST$ is blue, then 
$RST$ is blue.  Hence in Case 1, we always get at least
two distinct monochromatic triangles.
\bigskip
\noindent
{\it 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 \ne 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: 
\vglue 1.0truein
\bigskip
\noindent
 We get second monochromatic
triangles (red) if any of $PT$, $PU$, $TU$ are red.
If they are all blue, then $PTU$ is a second blue
triangle.  Hence also in Case 2, we always get at least
two distinct monochromatic triangles.
\bigskip
\noindent
Chapter 2/26.  Instead of a ``brute-force'' argument
for this one, we will present a ``clever'' approach,
based on the following observation:  {\it 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 $p$th-shortest 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} \ge a_{i,j}$ for $p$ different row numbers
$i$, then $a_{k,j+1} \ge a_{i(p),j}$
where $i(p)$ denotes the row number where the $p$th
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} \le a_{i(2),j} \le \cdots \le a_{i(m),j}$$
and $a_{k,j+1} \ge a_{i,j}$ for $p$ different $i$'s,
then $a_{k,j+1} \ge a_{i(l),j}$ for at least one 
$\ l \ge p$ (pigeonhole!).  But then $a_{k,j+1} \ge a_{i(p),j}$
also.  Now, the proof is complete if we notice that
for all $j$, the $p$th-shortest person in column $j+1$
is taller than the person to his or her left in column $j$
{\it and} also taller than all the people to the left
of the $p-1$ shorter people in column $j+1$.  Hence
for all $1\le j\le n-1$ and all $1\le p\le m$ the $p$th-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(!)
\bigskip
\noindent
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)$).
\bigskip
\item{$\bullet$}  There are $7P(7,7) = 7\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 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.)
\item{$\bullet$} There are $7P(7,6) = 7\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2 = 35280$
$7$-digit numbers, all larger than $5400$.
\item{$\bullet$} There are $7P(7,5) = 7\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3 = 17640$
$6$-digit numbers, all larger than $5400$.
\item{$\bullet$} There are $7P(7,4) = 7\cdot 7\cdot 6\cdot 5\cdot 4 = 5880$
$5$-digit numbers, all larger than $5400$.
\item{$\bullet$}  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\dot 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\cdot 6\cdot 5 = 90$ additional
numbers.  Finally, if the first digit is larger than $5$, we get
$3\cdot 7 \cdot 6 \cdot 5 = 630$ additional numbers.  The total number
of $4$-digit numbers is
$$30 + 90 + 630 = 750$$
and the total of all sizes is 
$$2\cdot 35280 + 17640 + 5580 + 750 = 94830.$$
\bye
