Math Problems Vault

Problem 1.3.1

(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

(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

(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

(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

(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

(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

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

(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 1.3.9

(1)(2)

For any $n$ vectors $v_1,\ldots ,v_n$ of length 1 in the plane there exists a tuple $\varepsilon_1,\ldots ,\varepsilon_n = \pm 1$ such that

?

(1)

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \leqslant \sqrt{n}$ ,

(2)

$\left|\sum_{k=1}^{n}\varepsilon_kv_k\right| \geqslant \sqrt{n}$ .