Pigeonhole principle

[24/83%]

Show

LaTeX

Show LaTeX

Problem 5.1.7 from de Souza P.N., Silva J. "Berkeley Problems in Mathematics" [deSi04]More problems in Section 5.1 "Complex Numbers"

Let $z_{1}, z_{2}, \ldots , z_{n}$ be complex numbers. Prove that there exists a subset $J \subset \left\{ 1,2,\ldots ,n\right\}$ such that

\left|\sum _{j \in J} z_{j}\right| \geq \frac{1}{4\sqrt{2}} \sum _{j=1}^{n} \left|z_{j}\right|.

Problem 6.13.1 from de Souza P.N., Silva J. "Berkeley Problems in Mathematics" [deSi04]More problems in Section 6.13 "Elementary Number Theory"

Prove that if six people are riding together in an Evans Hall elevator, there is either a three-person subset of mutual friends (each knows the other two) or a three-person subset of mutual strangers (each knows neither of the other two).

Problem I.3.10 from Макаров Б.М., Голузина М.Г., Лодкин А.А., Подкорытов А.Н. "Избранные задачи по вещественному анализу" [МГЛ+04]More problems in Section I.3 "Irrationality"

Let $x=\left(x_{1}, \ldots , x_{m}\right) \in \mathbb {R}^{m}$ . Prove that there exist fractions $\frac{p_{1}}{q}, \ldots , \frac{p_{m}}{q}$ with arbitrarily large denominator $q \in \mathbb {N}$ ( $p_{1}, \ldots , p_{m} \in \mathbb {Z}$ ) such that

\left|x_{j}-\frac{p_{j}}{q}\right|<q^{-\left(1+\frac{1}{m}\right)} \quad \text{ for all } j=1,2, \ldots , m .

Problem VIII.1.2 from Макаров Б.М., Голузина М.Г., Лодкин А.А., Подкорытов А.Н. "Избранные задачи по вещественному анализу" [МГЛ+04]More problems in Section VIII.1 "Lebesgue Measure"

Let $E \subset S^{1}, z_{1}, \ldots , z_{N} \in S^{1}, \mu$ be Lebesgue measure on $S^{1}$ ("arc length"). Prove that if

\mu (E)>2 \pi \left(1-\frac{1}{N}\right),

then a suitably rotated set $E$ contains all the points $z_{1}, \ldots , z_{N}$ , i.e., there exists a point $z_{0} \in S^{1}$ such that $z_{0} z_{k} \in E$ for $k=1, \ldots , N$ .

Problem VIII.3.2 from Макаров Б.М., Голузина М.Г., Лодкин А.А., Подкорытов А.Н. "Избранные задачи по вещественному анализу" [МГЛ+04]More problems in Section VIII.3 "Summable Functions"

Let each point of the interval $\left[0,1\right]$ belong to at least $k$ of the sets $E_{1}, \ldots , E_{N}$ . Prove that for some $n$ the inequality $\lambda \left(E_{n}\right) \geqslant \frac{k}{N}$ holds.

Problem 7.2.40 from Petrovic J.S. "Measure and Integral: Theory and Practice" [Pet25]More problems in Section 7.2 "Integration of Nonnegative Measurable Functions"

Suppose that every point in $[0,1]$ belongs to at least $k$ sets of the family of Lebesgue measurable sets $\left\{ E_{k}\right\}_{k=1}^{N}$ . Prove that for some $n \in \left\{ 1,2, \ldots , N\right\}$ , $m\left(E_{n}\right) \geq k / N$ .

Problem 8.241 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Section 1 "Lattice Points in Two and Three Dimensions"

Two lattice points $x,y$ and $x',y'$ are termed congruent mod $n$ , if

x\equiv x' \pmod n , \qquad y\equiv y' \pmod n .

Among any $kn^2+1$ distinct lattice points there are always $k+1$ that are congruent mod $n$ .

Problem 1.21 from Royden H.L., Fitzpatrick P.M. "Real Analysis" [RoFi23]More problems in Section 1.3 "Countable and Uncountable Sets"

Use an induction argument to establish the pigeonhole principle.

Problem 12.4 from Беклемишева Л.А., Беклемишев Д.В., Петрович А.Ю., Чубаров И.А. "Сборник задач по аналитической геометрии и линейной алгебре" [ББП+23]More problems in Subsection 12.1 "General properties of mappings (12.1-12.24)"

(1)(2)

Let $f: \mathcal{X} \rightarrow \mathcal{Y}, \left|\mathcal{X}\right| = m, \left|\mathcal{Y}\right| = n$ . Can the mapping $f$ be:

(1)

A surjection when $n > m$ ?

(2)

An injection when $n < m$ ?

Problem 1.76 from Balakrishnan V.K. "Schaum's Outline of Theory and Problems of Graph Theory" [Bal97]More problems in Chapter 1 "Graphs and Digraphs"

Show that in a simple graph, there are at least two vertices with equal degrees.

Problem 154 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21]More problems in Chapter 5 "Equivalence of Formulas"

(a)(b)(c)

(a)

Prove that among 20 formulas in the variables $x_{1}, x_{2}$ there will always be two that are equivalent.

(b)

Is it true that among 20 formulas in the variables $x_{1}, x_{2}$ there will always be three that are pairwise equivalent?

(c)

Suppose there are $k$ formulas in $n$ variables $x_{1}, \ldots , x_{n}$ . We need to choose several pairwise equivalent formulas. What number of such formulas can be guaranteed to be found?

Problem 1.3.1 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

(1)(2)(3)

(1)

If the sum of $n$ real numbers equals $S$ , then there is a summand not greater than $S/n$ , and also a summand not less than $S/n$ .

(2)

If the sum of $n$ integers is greater than $kn$ for some integer $k$ , then there is a summand not less than $k+1$ .

(3)

If the sum of $n$ integers is less than $kn$ for some integer $k$ , then there is a summand not greater than $k-1$ .

Remark.

Statement 1.3.1(1) is used in solving problems; see, for example, Problem 1.3.9. Its ``discrete analogue'', Statement 1.3.1(2), is called the pigeonhole principle and is often formulated as follows: for any distribution of $nk+1$ or more objects into $n$ boxes, some box will contain at least $k+1$ objects.

Methodologically, it would be more correct [MS, Glossary, entry estimate''] to call Sec.1.3 Estimates by contradiction''. However, we have chosen the title by which most readers will be able to form the clearest idea of the content of this section.

Problem 1.3.2 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

(1)(2)

A bag contains 32 red balls, 29 green balls, 45 blue, 17 yellow, and 30 each of white, black and gray. What is the smallest number of balls one must take so that among them there are certainly balls

(1)

of all 9 colors?

(2)

of 7 colors?

Problem 1.3.3 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

(1)(2)

(1)

Among the 7-digit numbers ending in 3 fives, there are at least 1200 numbers having the same remainder upon division by 7.

(2)

For each 4-digit number, the sum of the digits of its square was computed. Prove that there are at least 1200 numbers for which the computed sums give the same remainder upon division by 7.

Problem 1.3.4 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

(1)(2)

(1)

Among the numbers written using only ones, there is a number divisible by 1997.

(2)

Suppose $n$ integers are written in a row. Prove that one can select one or several consecutive ones among them whose sum is a multiple of $n$ .

Problem 1.3.5 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

(1)(2)

(1)

Among any $n$ real numbers there are two whose fractional parts differ by at most $\dfrac {1}{n-1}$ .

(2)

Integers are placed in a $10\times 10$ table, and any two numbers in cells adjacent by a side differ by at most 5. Prove that among these numbers there are two equal ones.

Problem 1.3.6 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

(1)(2)

Let $\alpha$ be an arbitrary irrational number.

(1)

For any positive integer $N$ there exist coprime $p,q\in \mathbb {Z}$ such that $0 < q \leqslant N$ and

\left|\alpha - \frac{p}{q}\right| \leqslant \frac{1}{qN}.

(2)

There exist infinitely many pairs of coprime numbers $p,q\in \mathbb {Z}$ for which

\left|\alpha - \frac{p}{q}\right| \leqslant \frac{1}{q^2}.

Remark.

Remark. In the formulation of Statement 1.3.6(2) one can get rid of coprimality, since for each fraction $\dfrac {p}{q}$ satisfying the inequality $\left|\alpha - \dfrac {p}{q}\right| \leqslant \dfrac {1}{q^2}$ , there exist only finitely many integers $k > 0$ such that $\left|\alpha - \dfrac {pk}{qk}\right| \leqslant \dfrac {1}{(qk)^2}$ .

Problem 1.3.7 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

The natural numbers from 1 to 101 are written in some order. Prove that this sequence contains either an increasing or a decreasing subsequence of length 11.

Remark.

A subsequence is what is obtained from a sequence by deleting some of its terms.

Problem 1.3.8 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 1.3 "The Pigeonhole Principle"

(1)(2)

There are 10 apples, each weighing at most 100 g, and two identical plates. Prove that one can put on the plates

(1)

several apples so that the weights on the plates differ by less than 1 g.

(2)

the same number of apples on each plate so that the weights on the plates differ by less than 2 g.

Here at least one apple must lie on the plates, but not all the apples have to lie on them (and in part (1) it is not required that each plate hold at least one apple).

Problem 6.2.2 from Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. "Элементы дискретной математики в задачах" [ГДИ+16]More problems in Section 6.2 "Independence and Existence Proofs"

(1)(2)

(1)

200 students from 10 groups, each of which has 20 students, stand in a circle. Prove that one can choose a leader in each group so that no two leaders stand next to each other.

(2)

The same for 1600 students from 100 groups, each of which has 16 students.

Problem 0.13 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 0.2 "Problems"

Show that every graph with two or more nodes contains two nodes that have equal degrees.

Problem 1.64 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 1.2 "Problems"

(a)(b)(c)(d)

Let $N$ be an NFA with $k$ states that recognizes some language $A$ .

(a)

Show that if $A$ is nonempty, $A$ contains some string of length at most $k$ .

(b)

Show, by giving an example, that part (a) is not necessarily true if you replace both $A$ 's by $\bar{A}$ .

(c)

Show that if $\bar{A}$ is nonempty, $\bar{A}$ contains some string of length at most $2^{k}$ .

(d)

Show that the bound given in part (c) is nearly tight; that is, for each $k$ , demonstrate an NFA recognizing a language $A_{k}$ where $\overline{A_{k}}$ is nonempty and where $\overline{A_{k}}$ 's shortest member strings are of length exponential in $k$ . Come as close to the bound in (c) as you can.

Problem 1.72 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 1.2 "Problems"

(a)(b)

Let $M_{1}$ and $M_{2}$ be DFAs that have $k_{1}$ and $k_{2}$ states, respectively, and then let $U=L\left(M_{1}\right) \cup L\left(M_{2}\right)$ .

(a)

Show that if $U \neq \emptyset$ , then $U$ contains some string $s$ , where $\left|s\right|<\max \left(k_{1}, k_{2}\right)$ .

(b)

Show that if $U \neq \Sigma^{*}$ , then $U$ excludes some string $s$ , where $\left|s\right|<k_{1} k_{2}$ .

Problem 2.35 from Sipser M. "Introduction to the Theory of Computation" [Sip13]More problems in Section 2.2 "Problems"

Let $G$ be a CFG in Chomsky normal form that contains $b$ variables. Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps, $L(G)$ is infinite.

References

[deSi04] de Souza P.N., Silva J. Berkeley Problems in Mathematics. 3rd ed., Springer, 2004.

[МГЛ+04] Макаров Б.М., Голузина М.Г., Лодкин А.А., Подкорытов А.Н. Избранные задачи по вещественному анализу. 2-е изд., Невский Диалект; БХВ-Петербург, 2004.

[Pet25] Petrovic J.S. Measure and Integral: Theory and Practice. CRC Press, 2025.

[PóSz98] Pólya G., Szegő G. Problems and Theorems in Analysis. Springer, 1998.

[RoFi23] Royden H.L., Fitzpatrick P.M. Real Analysis. 5th ed., Pearson, 2023.

[ББП+23] Беклемишева Л.А., Беклемишев Д.В., Петрович А.Ю., Чубаров И.А. Сборник задач по аналитической геометрии и линейной алгебре. Лань, 2023.

[Bal97] Balakrishnan V.K. Schaum's Outline of Theory and Problems of Graph Theory. McGraw-Hill, 1997.

[ДДК+21] Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. Задачник по дискретной математике. 2-е изд., Тверской государственный университет, 2021.

[ГДИ+16] Глибичук А.А., Дайняк А.Б., Ильинский Д.Г., Купавский А.Б., Райгородский А.М., Скопенков А.Б., Чернов А.А. Элементы дискретной математики в задачах. МЦНМО, 2016.

[Sip13] Sipser M. Introduction to the Theory of Computation. 3rd ed., Cengage Learning, 2013.