Section47.1Exercises

Show that in a group of $n$ people where $n\gt 2\text{,}$ there are at least two people who have the same number of friends.

Solution

Let $j$ be the number of people with no friends. If $j\geq 2$ then there are at least two people who have the same number ($0$) of friends.

If $j\in\{0,1\}$ then there are $n-j\gt 0$ people who have between 1 and $n-j-1$ friends.

By the Pigeonhole Principle there must be at least two people with the same number of friends.

.

Prove that if there are 10 pairs of shoes on a shelf, picking 11 shoes randomly from the shelf will result in picking up at least one pair of shoes.

Solution

If there are 11 pigeons (shoes) sitting in 10 pigeonholes (one for each pair of shoes), at least one pigeonhole has 2 pigeons (so a pair of shoes) by the pigeonhole principle.

.

There are many beads in a box. There are two colours of beads, red and blue, divided equally. If someone were to make three bracelets, using 10 beads each, prove that when the bracelets are stacked on top of each other, there will be a rectangle with each vertex the same colour.

Solution

Observe that each vertical line of the stacked bracelets has three beads, and there are two colours, so each vertical line has a dominant colour by the pigeonhole principle, which means one colour appears a least twice in the vertical line.

Next recall that there are $2^3=8$ possible colour different configurations of three beads stacked vertically.

By the pigeonhole principle there must be at least two (out of ten) vertical lines with the same colour configurations. In two of those identically configured vertical lines we chose four beads coloured by the dominant colour that form a rectangle.

Show that, given five points in the plane with no three collinear, the number of convex quadrilaterals formed by these points is odd.

Solution

We consider three cases.

• Case 1: Suppose that the five vertices form a convex pentagon. Then any four of them form a convex quadrilateral.

There are five convex quadrilaterals in this case.

• Case 2: Suppose that four points form a convex quadrilateral (say $A_1, A_2, A_3\text{,}$ and $A_4$ in clockwise order) which contains the fifth point $A_5$ in its interior. Let $S$ be the intersection of the diagonals $\overline{A_1A_3}$ and $\overline{A_2A_4}$ . Then the point $A_5$ lies in one of the four triangles into which diagonals dissect the quadrilateral, say $\triangle SA_1A2\text{.}$ Observe that the quadrilaterals $A_1A_5A_3A_4$ and $A_2A_3A_4A_5$ are convex but the other two are not.

There are three convex quadrilaterals in this case.

• Case 3: Suppose that three points (say $A_1, A_2, A_3$) form a triangle with $A_4$ and $A_5$ in its interior. The line $A_4A_5$ intersects two of the three sides, say $\overline{A_1A_2}$ and $\overline{A_1A_3}\text{.}$ Then $A_2,A_3 A_4A_5$ is the only convex quadrilateral.

Prove that the upper bound for a diagonal Ramsey number is:

\begin{equation*} R(s, s) \leq {2s - 2 \choose s - 1} . \end{equation*}
Solution

Recall (Section 2.3) that, for any $s,t\geq 3\text{,}$ $\displaystyle {s+t - 2 \choose t - 1}\text{.}$ Hence, for $s=t$

\begin{equation*} R(s, s) \leq {2s - 2 \choose s - 1} . \end{equation*}

$\textbf{Note:}$ For the latest developments (as of December 2020) regarding the upper bounds for a diagonal Ramsey number see this article by Ashwin Sah, an undergraduate student from MIT: “Diagonal Ramsey via effective quasirandomness”.

.

Show that if $k\equiv \pm 1(\mbox{mod } 6)$ then $w(k,2,2;3)=3k\text{.}$

Solution

Suppose that $k\equiv \pm 1(\mbox{mod } 6)\text{.}$ The claim is obviously true for $k=1\text{.}$ Hence suppose that $k\geq 5\text{.}$ Let $l\geq 1$ be such that $k=6l+1$ or $k=6l-1\text{.}$ Observe that $k$ is an odd number.

To show that $w(k,2,2;3)=3k\text{,}$ it is sufficient to prove that $w(k,2,2;3)\leq 3k$ and $w(k,2,2;3)\geq 3k\text{.}$

To prove that $w(k,2,2;3)\leq 3k$ we need to show that any $3$-colouring (say, red, blue, and green) of the interval $[1,3k]$ will yield a red $k$-term arithmetic progression or a blue $2$-term arithmetic progression or a green $2$-term arithmetic progression.

Clearly, any colouring of $[1,3k]$ that contains two blue or two green elements will yield a blue $2$-term arithmetic progression or a green $2$-term arithmetic progression.

Hence we consider a three colouring $c:[1,3k]\to\{\mbox{red, blue, green}\}$ that colours at most one element of $[1,3k]$ blue and at most one element green.

Observe that if one of the colours blue or green is not used then there is a sequence of at least $k$ consecutive red elements. Clearly, in this case there is a red $k$-term arithmetic progression.

Hence assume that $c:[1,3k]\to\{\mbox{red, blue, green}\}$ is a colouring such that there is a unique $x\in[1,3k]$ such that $c(x)=\mbox{blue}$ and a unique $y\in[1,3k]$ such that $c(y)=\mbox{green}\text{.}$

Suppose that $y\lt x\text{.}$

If $y\gt k$ or $x\lt 2k$ then there is a sequence of at least $k$ consecutive red elements between $[1,y-1]$ or between $[x+1,3k]\text{,}$ i.e. there is a red $k$-term arithmetic progression.

Suppose that $1\leq y\leq k\lt 2k\leq x\leq 3k\text{.}$ Observe that the number of elements between $x$ and $y$ is given by $d=(x-1)-(y+1)+1=x-y-1\text{.}$

Note that if $y\lt k$ or $x\gt 2k$ then $d\geq k\text{,}$ which means that there is a sequence of at least $k$ consecutive red elements between $y$ and $x\text{.}$

Hence the only remaining case is if $y=k$ and $x=2k\text{.}$ Observe that, since $k\equiv \pm 1(\mbox{mod } 6)\text{,}$ neither $k$ nor $2k$ is divisible by 3.This implies that all elements of the $k$-term arithmetic progression

\begin{equation*} 3,3+3,\ldots, 3+3i,\ldots, 3+3(k-1)=3k \end{equation*}

are coloured red.

Therefore $w(k,2,2;3)\leq 3k$ .

To prove $w(k,2,2;3)\geq 3k\text{,}$ we must show that there is a $3$-colouring of $[1, 3k-1]$ which does not produce a red $k$-term arithmetic progression or a blue $2$-term arithmetic progression or a green $2$-term arithmetic progression.

Let the colouring $c:[1,3k-1]\to\{\mbox{red, blue, green}\}$ be defined in the following way:

\begin{equation*} c(k)= \mbox{green},\ c(2k)= \mbox{blue}, \mbox{ and } c(x)=\mbox{red,} \mbox{ otherwise}. \end{equation*}

Let

\begin{equation*} a,a+d,\ldots,a+id,\ldots, a+(k-1)d \end{equation*}

be a $k$-term arithmetic progression contained in $[1,3k-1]\text{.}$

Observe that $d\in\{1,2,3\}\text{.}$ Otherwise $a+(k-1)d\geq 1+4(k-1)=4k-3$ which is greater than $3k-1$ for $k\geq 5\text{.}$

Since any set of $k$ consecutive integers in $[1,3k-1]$ must contain the integer $k$ or the integer $2k$ we conclude that an arithmetic progression contained in $[1,3k]$ with the step $d=1$ cannot be $c$-monochromatic.

If the arithmetic progression $a,a+2,\ldots,a+2i,\ldots, a+2(k-1)$ is contained in $[1,3k-1]$ then $a+2(k-1)\leq 3k-1$ implies that $a\leq k+1\text{.}$

If $a$ is an odd number then, for some $i\in\{0,1,\ldots,k-1\}\text{,}$ $a+2i=k$ and the corresponding $k$-term arithmetic progression is not $c$-monochromatic.

If $a$ is an even number then, for some $i\in\{0,1,\ldots,k-1\}\text{,}$ $a+2i=2k$ and the corresponding $k$-term arithmetic progression is not $c$-monochromatic.

If the arithmetic progression $a,a+3,\ldots,a+2i,\ldots, a+3(k-1)$ is contained in $[1,3k-1]$ then $a+3(k-1)\leq 3k-1$ implies that $a\leq 2\text{.}$

If $a=1$ and $k=6l+1$ then $1+3\cdot(2l)=k$ and the corresponding $k$-term arithmetic progression is not $c$-monochromatic.

If $a=1$ and $k=6l-1$ then $1+3\cdot(4l-1)=12l-2=2(6l-1)=2k$ and the corresponding $k$-term arithmetic progression is not $c$-monochromatic.

If $a=2$ and $k=6l+1$ then $2+3\cdot(4l)=12l+2=2\cdot(6l+1)=2k$ and the corresponding $k$-term arithmetic progression is not $c$-monochromatic.

If $a=2$ and $k=6l-1$ then $1+3\cdot(2l)=6l+1=k$ and the corresponding $k$-term arithmetic progression is not $c$-monochromatic.

Hence, the colouring $c$ of $[1,3k-1]$ does not produce a red $k$-term arithmetic progression or a blue $2$-term arithmetic progression or a green $2$-term arithmetic progression which proves that $w(k,2,2;3)\geq 3k\text{.}$

Therefore, $k=\pm 1(\mbox{mod } 6)$ implies $w(k,2,2;3)=3k\text{.}$

1. Check if the following 4-colouring of the set $\{1,2,\ldots,13\}$ avoids monochromatic 3-term arithmetic progressions:

\begin{equation*} R \ B \ B \ G \ Y \ R \ Y \ G\ B \ Y \ Y\ B \ G \end{equation*}
2. Add 3 colours to the end to produce a monochromatic 3-term arithmetic progression.

Solution
• Since there are only two red ($R$) elements, $1$ and $6\text{,}$ there is no a red $3$-term arithmetic progression.

• There are four blue ($B$) elements, $2,3,9$ and $12\text{.}$ Clearly this set does not contain a $3$-term arithmetic progression.

• There are three green ($G$) elements, $4,8$ and $13\text{.}$ These three elements do not form a $3$-term arithmetic progression.

• There are four yellow ($Y$) elements, $5,7,10$ and $11\text{.}$ This set does not contain a $3$-term arithmetic progression.

1. For example,

\begin{equation*} R \ \underline{B} \ B \ G \ Y \ R \ Y \ G \ \underline{B} \ Y \ Y \ B \ G \ Y \ B\ \underline{B}. \end{equation*}

What is the density of the set of all powers of 3?

Solution

Consider the set of all powers of 3, i.e. consider the set $A=\{1,3,9,27,\ldots \}\text{.}$

Let $n \in \mathbb{N}$ and let $k \in \mathbb{N}\cup\{0\}$ be such that $3^k \leq n\lt 3^{k+1}\text{.}$ This is the same as

\begin{equation*} k \leq \log_{3}(n)\lt k+1. \end{equation*}

It follows that

\begin{equation*} a(n)=|A\cap [1,n]| \leq 1+\log_{3}(n). \end{equation*}

By definition,

\begin{equation*} \mbox{Density of } A= \lim_{n\to\infty} \frac{a(n)}{n} \leq \lim_{n\to\infty} \frac{1+ \log_{3}(n)}{n}= 0. \end{equation*}
.

Prove that for any $k,l\in \mathbb{N}$ there is $S(k, l)\in \mathbb{N}$ such that any $k$-colouring of the set of positive integers $[1,S(k,l)]$ contains a monochromatic arithmetic progression of length $l$ together with its difference.

Solution

We prove the claim by mathematical induction on $k\text{,}$ the number of colours.

For $k=1$ and any $l\in\mathbb{N}$ we take $S(1, l) = l\text{.}$

Assume that the claim is true for a fixed $k\geq 1$ and any $l\in \mathbb{N}\text{.}$ We fix $l \in\mathbb{N}$ and denote by $S(k,l)$ the corresponding number.

Next we define

\begin{equation*} S(k+1, l) = w(k+1, (l-1)S(k, l) + 1), \end{equation*}

where $w(\ast, \ast)$ denotes a van der Waerden number.

Let the set of integers $[1,S(k+1, l)]$ be $(k+1)$-coloured. Then, by van der Waerden's Theorem, there is a $((l-1)S(k, l) + 1)$-term monochromatic arithmetic progression

\begin{equation*} a, a+d, ..., a+(l-1)S(k, 1)d. \end{equation*}

For every $x = 1, 2, \ldots, S(k, l)d$ this monochromatic arithmetic progression contains the following $l$-term arithmetic progression:

\begin{equation*} a, a+xd, \ldots, a+(l-1)xd. \end{equation*}

If for one of the numbers $x\text{,}$ the difference $xd$ is coloured by the same colour as the original progression, we have concluded the proof of our induction step.

Otherwise, the $S(k,l)$-term arithmetic progression

\begin{equation*} d, 2d, \ldots S(k, l)d \end{equation*}

is coloured in only $k$ colours. Now we apply the inductive hypothesis to conclude that the $k$-coloured set $\{d, 2d, \ldots S(k, l)d\}\subset [1,S(k+1,l)]$ contains a monochromatic arithmetic progression of length $l$ together with its difference.

Show that the minimum integer $n$ such that any red/blue colouring of $[1,n]$ must admit either a red strict Schur triple, or a blue $3$-term arithmetic progression is $n=10\text{.}$

Solution

The question is to show that any red/blue colouring of $[1,10]$ must contain a red solution to $x+y=z$ (of distinct integers) or a blue solution to $x+y=2z\text{.}$

We also need to show that there is a red/blue colouring of $[1,9]$ with no red solution to $x+y=z$ (of distinct integers) or a blue solution to $x+y=2z\text{.}$ The following colouring of $[1,9]$ achieves this:

Next we try to build a red/blue colouring of $[1,10]$ that avoids a red ($R$) solution to $x+y=z$ (of distinct integers) or a blue ($B$) solution to $x+y=2z\text{.}$

We start by observing that such a colouring has to avoid monochromatic triples $\{1,2,3\}\text{,}$ $\{2,4,6\}\text{,}$ and $\{3,6,9\}$ because these triples are both $3$-term arithmetic progressions and Schur's triples.

In our attempt to avoid a red solution to $x+y=z$ (of distinct integers) or a blue solution to $x+y=2z\text{,}$ we consider all possible colourings of the triple $\{2,4,6\}$ with two colours, $R$ and $B\text{:}$

• Case 1: If $2=R,4=B,6=B$ then $5=R$ (because of the arithmetic progression $4,5,6$). This implies $7=B$ (because of $2+5=7$) and $8=R$ (because of the arithmetic progression $6,7,8$) and $10=R$ (because of the arithmetic progression $4,7,10$), But now, $2,8,10$ is a red Schur's triple.

• Case 2: If $2=B,4=R,6=B$ then $10=R$ (because of the arithmetic progression $2,6,10$).

Now, if $3=B$ then $1=R$ (because of the arithmetic progression $1,2,3$) and $9=B$ (because of $1+9=10\text{.}$) But then $3,6,9$ is a blue arithmetic progression.

If $3=R$ then $7=B$ (because of $3+4=7$) and $5=R$ (because of the arithmetic progression $5,6,7$) and $8=R$ (because of the arithmetic progression $6,7,8$). But then $3+5=8$ is a red Schur's triple.

• Case 3: If $2=B,4=B,6=R$ then $3=R$ (because of the arithmetic progression $2,3,4$). It follows that $9=B$ (because of $3+6=9$).

Now, if $1=R$ then $5=B$ (because of $1+5=6$) and $7=B$ (because of $1+6=7\text{.}$) But then $5,7,9$ is a blue arithmetic progression.

If $1=B$ then $5=R$ (because of the arithmetic progression $1,5,9$) and $7=B$ (because of $1+6=7\text{.}$) Also, $8=B$ (because of $3+5=8$). This implies $7=R$ (because of the arithmetic progression $7,8,9$) and then $10=R$ (because of the arithmetic progression $8,9,10$). Now, $3+7=10$ is a red Schur's triple.

• Case 4: Let $2=R,4=R,6=B\text{.}$

Now, if $3=R$ then $5=B$ (because of $2+3=5$) and $7=B$ (because of $3+4=7\text{.}$) But then $5,6,7$ is a blue arithmetic progression.

If $3=B$ then $9=R$ (because of the arithmetic progression $3,6,9$) and $5=B$ (because of $4+5=9$) and $7=B$ (because of $2+7=9$). Now, $5,6,7$ is a blue arithmetic progression.

• Case 5: If $2=R,4=B,6=R$ then $8=B$ (because of $2+6=8$).

Now, if $5=R$ then $1=B$ (because of $1+5=6$), $3=B$ (because of $2+3=5\text{.}$ and $7=B$ (because of $2+5=7\text{.}$) But then $1,4,7$ is a blue arithmetic progression.

If $5=B$ then $3=R$ (because of the arithmetic progression $3,4,5$) and $1=B$ (because of $1+2=3$) and $7=R$ (because of the arithmetic progression $1,4,7$). Now, if $9=B$ (because of $2+7=9$), then $1,5,9$ is a blue arithmetic progression.

• Case 5: If $2=B,4=R,6=R$ then $10=B$ (because of $4+6=10$).

Now, if $3=R$ then $1=B$ (because of $1+3=4$), $7=B$ (because of $3+4=7\text{.}$ and $9=B$ (because of $3+6=9\text{.}$) It follows that $8=R$ (because of the arithmetic progression $8,9,10$) and $5=B$ (because of $3+5=8$). But then $1,5,9$ is a blue arithmetic progression.

If $3=B$ then $1=R$ (because of the arithmetic progression $1,2,3$) and $5=B$ (because of $1+4=5$) and $7=B$ (because of $1+6=7$) . But then $3,5,7$ is a blue arithmetic progression.

Therefore, it is impossible to colour $[1,10]$ red and blue and to avoid a red Schur's triple or a blue $3$-term arithmetic progression.

Check if the equation $x-y+5z-3w=0$ is partition regular over $\mathbb{N}\text{.}$

Solution

Yes, the given equation is partition regular over $\mathbb{N}\text{.}$ If we look at all the coefficients: $c_1=1,c_2=-1,c_3=5,c_4=-3\text{,}$ the sum of the coefficients $c_1$ and $c_2$ turns out to be equal to 0. Hence, by Rado's theorem this equation is partition regular, i.e it has a monochromatic solution for any finite colouring of the set of natural numbers.

On the Rado graph, will vertex 3 be connected to vertex 9?

Solution

On the Rado graph, vertex 3 will be connected to vertices that have a non-zero 3rd bit of the binary representation. Vertex 9 in binary representation is $1001\text{.}$ The 3rd bit of $1001$ is 0, therefore vertex 3 will not be connected to vertex 9.

1. Draw the $2$-dimensional cube corresponding to $A=\{1,2,3\}\text{.}$ What does each word in the cube represent if we are playing tic-tac-toe?

2. First, list all the combinatorial lines in $A^2\text{.}$ Explain why a combinatorial line is a winning line in tic-tac-toe. Are there any winning lines in tic-tac-toe that is not a combinatorial line?

3. In Figure 47.1.14 you will see 4 lines on a 4x4x4 cube. For each line, write the combinatorial line and the root associated with the combinatorial line. If it is not a combinatorial line, briefly explain why.

Solution
1. Each word on the 2-dimensional cube corresponds to a position on the tic-tac-toe board.

2. Below is the list of all the roots in $A^2$ together with the corresponding combinatorial line:

\begin{equation*} \tau_1 = * 1 \implies L_{\tau_1}=\{1\:1, 2\:1, 3\:1\} \end{equation*}
\begin{equation*} \tau_2 = * 2 \implies L_{\tau_2}=\{1\:2, 2\:2, 3\:2\} \end{equation*}
\begin{equation*} \tau_3 = * 3 \implies L_{\tau_3}=\{1\:3, 2\:3, 3\:3\} \end{equation*}
\begin{equation*} \tau_4 = 1 * \implies L_{\tau_4}=\{1\:1, 1\:2, 1\:3\} \end{equation*}
\begin{equation*} \tau_5 = 2 * \implies L_{\tau_5}=\{2\:1, 2\:2, 2\:3\} \end{equation*}
\begin{equation*} \tau_6 = 3 * \implies L_{\tau_6}=\{3\:1, 3\:2, 3\:3\} \end{equation*}
\begin{equation*} \tau_7 = * * \implies L_{\tau_7}=\{1\:1, 2\:2, 3\:3\} \end{equation*}

Based on the tic-tac-toe board, we can see that $\tau_1, \tau_2, \tau_3$ correspond to a horizontal winning line in each row, $\tau_4, \tau_5, \tau_6$ correspond to a vertical winning line in each column, and $\tau_7$ is the diagonal winning line starting at $1\:1$ and finishing at $3\:3\text{.}$

One winning line that cannot be represented by a combinatorial line is $\{3\:1, 2\:2, 1\:3\}\text{.}$ This is because there is no root to represent this line. We can see that each word is changing in more than one position and to different letters.

3. We can see that $L_2$ is not a combinatorial line. Observe that the line $L_2$ begins at $(1,2,4)$ and ends at $(4,2,1)\text{.}$ This means $L_2$ contains the points $\{1\:2\:4, 2\:2\:3, 3\:2\:2, 4\:2\:1 \}\text{.}$ Since the first and third letter in each word change to different letters at different times, this set of words cannot be obtained from a root. It follows that $L_2$ is not a combinatorial line.

The corresponding roots and lines for the rest are:

\begin{equation*} \tau_1 = *32 \implies L_{\tau_1}=L_1=\{1\:3\:2, 2\:3\:2, 3\:3\:2, 4\:3\:2 \} \end{equation*}
\begin{equation*} \tau_3 = *** \implies L_{\tau_3}=L_3=\{1\:1\:1, 2\:2\:2, 3\:3\:3, 4\:4\:4 \} \end{equation*}
\begin{equation*} \tau_4 = 24* \implies L_{\tau_4}=L_4==\{2\:4\:1, 2\:4\:2, 2\:4\:3, 2\:4\:4 \} \end{equation*}

Find $HJ(2,2)\text{.}$ Show your work.

Solution

Let $A=\{1,2\}\text{.}$ Observe that $A^2=\{1\;1,1\;2,2\;1,2\;2\}\text{.}$

Let $c$ be any $2$-colouring of $A^2\text{.}$ Consider the set $A^\prime=\{1\;1,1\;2,2\;2\}\subset A^2\text{.}$ By the pigeonhole principle, there are at least two elements in $A^\prime$ that are coloured by the same colour. Observe that those two elements form a $c$-monochromatic combinatorial line in $A^2\text{.}$

Hence $HJ(2,2)=2\text{.}$

For what values of $n>1$ any $2$-colouring of $[1, n]^2$ will always contains a monochromatic combinatorial line with length $n\text{?}$

Solution

In Exercise 47.1.16 we have established that this is true for $n=2\text{.}$

Let $n\geq 3$ and let $A=\{1,2,\ldots,n\}$ be an alphabet. Let $c$ be a $2$-colouring of $A^2$ defined in the following way:

\begin{equation*} c(i,i)=B, \mbox{ if } i\lt n,\mbox{ and } c(n,n)=R \end{equation*}
\begin{equation*} c(n,i)=c(i,n)=B, \mbox{ if } i\lt n, \mbox{ and }c(i,j)=R, \mbox{ otherwise}. \end{equation*}

Recall that all combinatorial lines is $A^2$ are determined by one of the roots $\ast\; i\text{,}$ $i\; \ast\text{,}$ where $i\in [1,n]\text{,}$ and $\ast\; \ast\text{.}$

Since, for any $i\in [1,n]\text{,}$ the words $2\; i$ and $n\; i$ are of different colours, the combinatorial line generated by the root $\ast\; i$ is not $c$-monochromatic. Similarly, for any $i\in [1,n]$ the combinatorial line generated by the root $i\; \ast$ is not $c$-monochromatic.

Finally, the combinatorial linedetermined by the root $\ast\; \ast$ is not $c$-monochromatic because the words $1\; 1$ and $n\; n$ are not of the same colour.

Therefore, only if $n=2\text{,}$ any $2$-colouring of $[1, n]^2$ will always contains a monochromatic combinatorial line with length $n$