The Line Segments Joining 10 Points Are Arbitrarily Colored Red or Blue

Problem 1

Concerning Application 4 , show that there is a succession of days during which the chess master will have played exactly $k$ games, for each $k=1,2, \ldots, 21$. (The case $k=21$ is the case treated in Application 4.) Is it possible to conclude that there is a succession of days during which the chess master will have played exactly 22 games?

Problem 2

* Concerning Application 5 , show that if 100 integers are chosen from $1,2, \ldots, 200$, and one of the integers chosen is less than 16 , then there are two chosen numbers such that one of them is divisible by the other.

Problem 3

Generalize Application 5 by choosing (how many?) integers from the set
$$
\{1,2, \ldots, 2 n\}
$$

Problem 4

Show that if $n+1$ integers are chosen from the set $\{1,2, \ldots, 2 n\}$, then there are always two which differ by 1 .

Problem 5

Show that if $n+1$ integers are chosen from the set $\{1,2, \ldots, 3 n\}$, then there are always two which differ by at most 2 .

Problem 7

* Show that for any given 52 integers there exist two of them whose sum, or else whose difference, is divisible by 100 .

Problem 8

Use the pigeonhole principle to prove that the decimal expansion of a rational number $m / n$ eventually is repeating. For example,
$$
34,478 / 99,900=.34512512512512512 \cdots
$$

Problem 9

In a room there are 10 people, none of whom are older than 60 (ages are given in whole numbers only) but each of whom is at least 1 year old. Prove that one can always find two groups of people (with no common person) the sum of whose ages is the same. Can 10 be replaced by a smaller number?

Problem 10

A child watches TV at least one hour each day for 7 weeks but never more than 11 hours in any one week. Prove that there is some period of consecutive days in which the child watches exactly 20 hours of TV. (It is assumed that the child watches TV for a whole number of hours each day.)

Problem 11

A student has 37 days to prepare for an examination. From past experience she knows that she will require no more than 60 hours of study. She also wishes to study at least 1 hour per day.

Problem 12

Show by example that the conclusion of the Chinese remainder theorem (Application 6) need not hold when $m$ and $n$ are not relatively prime.

Problem 13

*. Let $S$ be a set of 6 points in the plane, with no 3 of the points collinear. Color either red or blue each of the 15 line segments determined by the points of $S$. Show that there are at least two triangles determined by points of $S$ which are either red triangles or blue triangles. (Both may be red, or both may be blue, or one may be red and the other blue.)

Problem 14

A bag contains 100 apples, 100 bananas, 100 oranges, and 100 pears. If $I$ pick one piece of fruit out of the bag every minute, how long will it be before I am assured of having picked at least a dozen pieces of fruit of the same kind?

Problem 15

Prove that, for any $n+1$ integers $a_{1}, a_{2}, \ldots, a_{n+1}$, there exist two of the integers $a_{i}$ and $a_{j}$ with $i \neq j$ such that $a_{i}-a_{j}$ is divisible by $n .$

Problem 16

Prove that in a group of $n>1$ people there are two who have the same number of acquaintances in the group. (It is assumed that no one is acquainted with him or herself.)

Problem 17

There are 100 people at a party. Each person has an even number (possibly zero) of acquaintances. Prove that there are three people at the party with the same number of acquaintances.

Problem 18

Prove that of any five points chosen within a square of side length 2, there are two whose distance apart is at most $\sqrt{2}$.

Problem 19

(a) Prove that of any five points chosen within an equilateral triangle of side length 1 , there are two whose distance apart is at most $\frac{1}{2}$.
(b) Prove that of any ten points chosen within an equilateral triangle of side length 1, there are two whose distance apart is at most $\frac{1}{3}$.
(c) Determine an integer $m_{n}$ such that if $m_{n}$ points are chosen within an equilateral triangle of side length 1 , there are two whose distance apart is at most $1 / n$.

Problem 21

* Prove that $r(3,3,3) \geq 17$ by exhibiting a coloring, with colors red, blue, and green, of the line segments joining 16 points with the property that there do not exist 3 points such that the 3 line segments joining them are all colored the same.

Problem 22

Prove that
$$
r(\underbrace{3,3, \ldots, 3}_{k+1}) \leq(k+1)(r(\underbrace{3,3, \ldots, 3}_{k})-1)+2 .
$$
Use this result to obtain an upper bound for
$$
r(\underbrace{3,3, \ldots, 3}_{n}) .
$$

Problem 23

The line segments joining 10 points are arbitrarily colored red or blue. Prove that there must exist 3 points such that the 3 line segments joining them are all red, or 4 points such that the 6 line segments joining them are all blue (that is, $r(3,4) \leq 10)$.

Problem 24

Let $q_{3}$ and $t$ be positive integers with $q_{3} \geq t .$ Determine the Ramsey number $r_{t}\left(t, t, q_{3}\right)$.

Problem 25

Let $q_{1}, q_{2}, \ldots, q_{k}, t$ be positive integers, where $q_{1} \geq t, q_{2} \geq t, \ldots$, $q_{k} \geq t .$ Let $m$ be the largest of $q_{1}, q_{2}, \ldots, q_{k} .$ Show that
$$
r_{t}(m, m, \ldots, m) \geq r_{t}\left(q_{1}, q_{2}, \ldots, q_{k}\right)
$$
Conclude that, to prove Ramsey's theorem, it is enough to prove it in the case that $q_{1}=q_{2}=\cdots=q_{k}$.

Problem 26

Suppose that the $m n$ people of a marching band are standing in a rectangular formation of $m$ rows and $n$ columns in such a way that in each row each person is taller than the one to her or his left. Suppose that the leader rearranges the people in each column in increasing order of height from front to back. Show that the rows are still arranged in increasing order of height from left to right.

Problem 27

A collection of subsets of $\{1,2, \ldots, n\}$ has the property that each pair of subsets has at least one element in common. Prove that. there are at most $2^{n-1}$ subsets in the collection.

Problem 28

At a dance-hop there are 100 men and 20 women. For each $i$ from $1,2, \ldots, 100$, the $i$ th man selects a group of $a_{i}$ women as potential dance partners (his dance list), but in such a way that given any group of 20 men, it is always possible to pair the 20 men up with the 20 women with each man paired up with a woman on his dance list. What is the smallest $\operatorname{sum} a_{1}+a_{2}+\ldots+a_{n}$ that will guarantee this?

robertsbantiong.blogspot.com

Source: https://www.numerade.com/books/chapter/the-pigeonhole-principle-2/