\problemdata      
        {counting-19} % latex-friendly label for the prob.
        {Counting} % The topic(s) of the problem content.
        {?} % Source (if known)
        {S02 PS8} % Usage (list ones you are aware of).
        {Christos Kapoutsis, S02} % Last revision info (author, date).



\begin{problem} {\bf Do you know this person?}
Suppose that every two people either know one another or else are
strangers.  How many people must there be in a room to guarantee that
there are either 6 people who all know each other or 6 people who are all
strangers to one another?

The solution to this problem is a number called the Ramsey number $R(6, 6)$.  
The solution to the simpler problem involving groups of only 5 people is 
called $R(5,5)$.  Last week, we solved a still simpler version of this
problem involving groups of just 3 people using the pigeonhole principle.  
Finding $R(5, 5)$ and $R(6, 6)$ is a bit more tricky.  The following is taken
from, \emph{Ten Lectures on the Probabilistic Method}, by Joel Spencer:

\begin{quotation}\noindent
Erd\"os [possibly the 20th century's top mathematician] asks us to
imagine an alien force, vastly more powerful than us, landing on Earth
and demanding the value of $R(5, 5)$ or they will destroy our planet.
In that case, he claims, we should marshall all our computers and all
our mathematicians and attempt to find the value.  But suppose,
instead, that they ask for $R(6, 6)$.  In that case, he believes, we
should attempt to destroy the aliens.
\end{quotation}

Given rumors that a new fleet is forming on Xoros 19, we had better
take a stab at $R(6, 6)$.  For now, however, we will only try to prove
that $R(6, 6) > 17$.

\begin{problemparts}
\problempart If there are $n$ people in a room, then how many
different groups of two people are there?

\solution{
\[
\binom{n}{2}
\]
}

\problempart A {\em configuration} of a group of people is a setting
of who-knows-who.  For example, there are two possible configurations
of a group of just two people: either they know each other or they are
strangers.  How many different configurations are possible in a room
with $n$ people?

\solution{Since every two people either know each other or are
strangers, the number of configurations is

\[
2^{\binom{n}{2}}.
\]
}

\problempart Suppose that there is a specific group of six people who
all know each other.  How many configurations are possible with this
restriction?

\solution{
\[
2^{\binom{n}{2} - \binom{6}{2}}
\]
}

\problempart In a set of $n$ people, how many different subsets of six
people are there?

\solution{
\[
\binom{n}{6}
\]
}

\problempart 
There are at most
\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]
configurations in which some set of six people all know each other.  
Give an explanation to justify this answer.


\solution{There are $\dbinom{n}{6}$ different sets of six people.  For
each set of six people, there are $2^{\binom{n}{2} - \binom{6}{2}}$
configurations in which these people all know each other.  Therefore,
there are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some set of six people all know each other.
}

\problempart 
There are at most
\[
2 \cdot \binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]
configurations in which some six people either all know each other or
are all strangers.  Give an explanation to justify this answer.


\solution{
There are at most

\[
\binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people all know each other.  By the
same argument, there are at most this many configurations of six
people that are all strangers.  Therefore, there are at most

\[
2 \cdot \binom{n}{6} \cdot 2^{\binom{n}{2} - \binom{6}{2}}
\]

configurations in which some six people either all know each other or
are all strangers.}

\problempart Use your answers to parts (b) and (f) to prove that there
exists a configuration of $17$ people such that no set of six people
all know each other or are all strangers.  This implies that $R(6, 6)
> 17$.

\solution{
By part (a), there are

\[
2^{\binom{17}{2}}
\]

configurations of 17 people.  By part (f) there are at most

\[
2 \cdot \binom{17}{6} \cdot 2^{\binom{17}{2} - \binom{6}{2}}
\]

configurations in which some set of six people either all know each
other or are all strangers.  If the first quantity is greater than the
second, then there must exist a configuration of 17 people such that
there is no set of six people that all know each other or are all
strangers.  The second quantity divided by the first is

\begin{eqnarray}
2 \cdot \binom{17}{6} \cdot 2^{- \binom{6}{2}} & \approx & 0.75.
\end{eqnarray}

Therefore, the first quantity is greater than the second, as desired.

The best known bounds are $102 \leq R(6, 6) \leq 165$.
Asymptotically, the simple technique outlined above gives a lower
bound on $R(k, k)$ that is within a factor of 2 of the best known.}

\end{problemparts}
\end{problem}

