ILL 1978

The set $M = \{1, 2, . . . , 2n\}$ is partitioned into $k$ nonintersecting subsets $M_1,M_2, \dots, M_k,$ where $n \ge k^3 + k.$ Prove that there exist even numbers $2j_1, 2j_2, \dots, 2j_{k+1}$ in $M$ that are in one and the same subset $M_i$ $(1 \le i \le k)$ such that the numbers $2j_1 - 1, 2j_2 - 1, \dots, 2j_{k+1} - 1$ are also in one and the same subset $M_j (1 \le j \le k).$

If $$f(x) = (x + 2x^2 +\cdots+ nx^n)^2 = a_2x^2 + a_3x^3 + \cdots+ a_{2n}x^{2n},$$ prove that $$a_{n+1} + a_{n+2} + \cdots + a_{2n} =\dbinom{n + 1}{2}\frac{5n^2 + 5n + 2}{12}$$

Find all numbers $\alpha$ for which the equation $$x^2 - 2x[x] + x -\alpha = 0$$ has two nonnegative roots. ( $[x]$ denotes the largest integer less than or equal to x.)

Two identically oriented equilateral triangles, $ABC$ with center $S$ and $A'B'C$, are given in the plane. We also have $A' \neq S$ and $B' \neq S$. If $M$ is the midpoint of $A'B$ and $N$ the midpoint of $AB'$, prove that the triangles $SB'M$ and $SA'N$ are similar.

Prove that for any triangle $ABC$ there exists a point P in the plane of the triangle and three points $A' , B'$ , and $C'$ on the lines $BC, AC$ , and $AB$ respectively such that $$AB \cdot PC'= AC \cdot PB'= BC \cdot PA'= 0.3M^2,$$ where $M = max\{AB,AC,BC\}$ .

Prove that for all $X > 1$ , there exists a triangle whose sides have lengths $P_1(X) = X^4+X^3+2X^2+X+1, P_2(X) = 2X^3+X^2+2X+1$ , and $P_3(X) = X^4-1$ . Prove that all these triangles have the same greatest angle and calculate it.

For two given triangles $A_1A_2A_3$ and $B_1B_2B_3$ with areas $\Delta_A$ and $\Delta_B$ , respectively, $A_iA_k \ge B_iB_k, i, k = 1, 2, 3$ . Prove that $\Delta_A \ge \Delta_B$ if the triangle $A_1A_2A_3$ is not obtuse-angled.

Let $T_1$ be a triangle having $a, b, c$ as lengths of its sides and let $T_2$ be another triangle having $u, v,w$ as lengths of its sides. If $P,Q$ are the areas of the two triangles, prove that $$16PQ \leq a^2(-u^2 + v^2 + w^2) + b^2(u^2 - v^2 + w^2) + c^2(u^2 + v^2 - w^2).$$

When does equality hold?

Show that for any natural number $n$ there exist two prime numbers $p$ and $q, p \neq q$ , such that $n$ divides their difference.

Find all natural numbers $n < 1978$ with the following property: If $m$ is a natural number, $1 < m < n$ , and $(m, n) = 1$ (i.e., $m$ and $n$ are relatively prime), then $m$ is a prime number.

The equation $x^3 + ax^2 + bx + c = 0$ has three (not necessarily distinct) real roots $t, u, v$ . For which $a, b, c$ do the numbers $t^3, u^3, v^3$ satisfy the equation $x^3 + a^3x^2 + b^3x + c^3 = 0$ ?

The satellites $A$ and $B$ circle the Earth in the equatorial plane at altitude $h$ . They are separated by distance $2r$ , where $r$ is the radius of the Earth. For which $h$ can they be seen in mutually perpendicular directions from some point on the equator?

Let $p(x, y)$ and $q(x, y)$ be polynomials in two variables such that for $x \ge 0, y \ge 0$ the following conditions hold: $(i) p(x, y)$ and $q(x, y)$ are increasing functions of $x$ for every fixed $y$ . $(ii) p(x, y)$ is an increasing and $q(x)$ is a decreasing function of $y$ for every fixed $x$ . $(iii) p(x, 0) = q(x, 0)$ for every $x$ and $p(0, 0) = 0$ . Show that the simultaneous equations $p(x, y) = a, q(x, y) = b$ have a unique solution in the set $x \ge 0, y \ge 0$ for all $a, b$ satisfying $0 \le b \le a$ but lack a solution in the same set if $a < b$ .

Prove that for every positive integer $n$ coprime to $10$ there exists a multiple of $n$ that does not contain the digit $1$ in its decimal representation.

Prove that for any positive integers $x, y, z$ with $xy-z^2 = 1$ one can find non-negative integers $a, b, c, d$ such that $x = a^2 + b^2, y = c^2 + d^2, z = ac + bd$. Set $z = (2q)!$ to deduce that for any prime number $p = 4q + 1$, $p$ can be represented as the sum of squares of two integers.

Given a natural number $n$ , prove that the number $M(n)$ of points with integer coordinates inside the circle $(O(0, 0),\sqrt{n})$ satisfies $$\pi n - 5\sqrt{n} + 1<M(n) < \pi n+ 4\sqrt{n} + 1$$

We consider three distinct half-lines $Ox, Oy, Oz$ in a plane. Prove the existence and uniqueness of three points $A \in Ox, B \in Oy, C \in Oz$ such that the perimeters of the triangles $OAB,OBC,OCA$ are all equal to a given number $2p > 0.$

Let $O$ be the center of a circle. Let $OU,OV$ be perpendicular radii of the circle. The chord $PQ$ passes through the midpoint $M$ of $UV$ . Let $W$ be a point such that $PM = PW$ , where $U, V,M,W$ are collinear. Let $R$ be a point such that $PR = MQ$ , where $R$ lies on the line $PW$ . Prove that $MR = UV$ .

Alternative version: A circle $S$ is given with center $O$ and radius $r$ . Let $M$ be a point whose distance from $O$ is $\frac{r}{\sqrt{2}}$ . Let $PMQ$ be a chord of $S$ . The point $N$ is defined by $\overrightarrow{PN} =\overrightarrow{MQ}$ . Let $R$ be the reflection of $N$ by the line through $P$ that is parallel to $OM$ . Prove that $MR =\sqrt{2}r$ .

A circle touches the sides $AB,BC, CD,DA$ of a square at points $K,L,M,N$ respectively, and $BU, KV$ are parallel lines such that $U$ is on $DM$ and $V$ on $DN$ . Prove that $UV$ touches the circle.

Let $x$ and $y$ be two integers not equal to $0$ such that $x+y$ is a divisor of $x^2+y^2$ . And let $\frac{x^2+y^2}{x+y}$ be a divisor of $1978$ . Prove that $x = y$ .

German IMO Selection Test 1979, problem 2

Let $S$ be the set of all the odd positive integers that are not multiples of $5$ and that are less than $30m$, $m$ being an arbitrary positive integer. What is the smallest integer $k$ such that in any subset of $k$ integers from $S$ there must be two different integers, one of which divides the other?

Consider a polynomial $P(x) = ax^2 + bx + c$ with $a > 0$ that has two real roots $x_1, x_2$ . Prove that the absolute values of both roots are less than or equal to $1$ if and only if $a + b + c \ge 0, a -b + c \ge 0$ , and $a - c \ge 0$ .

For every integer $d \geq 1$, let $M_d$ be the set of all positive integers that cannot be written as a sum of an arithmetic progression with difference $d$, having at least two terms and consisting of positive integers. Let $A = M_1$, $B = M_2 \setminus \{2 \}, C = M_3$. Prove that every $c \in C$ may be written in a unique way as $c = ab$ with $a \in A, b \in B.$

Determine the sixth number after the decimal point in the number $(\sqrt{1978} +\lfloor\sqrt{1978}\rfloor)^{20}$

Let $c, s$ be real functions defined on $\mathbb{R}\setminus\{0\}$ that are nonconstant on any interval and satisfy $$c\left(\frac{x}{y}\right)= c(x)c(y) - s(x)s(y)\text{ for any }x \neq 0, y \neq 0$$ Prove that: $(a) c\left(\frac{1}{x}\right) = c(x), s\left(\frac{1}{x}\right) = -s(x)$ for any $x = 0$ , and also $c(1) = 1, s(1) = s(-1) = 0$ ; $(b) c$ and $s$ are either both even or both odd functions (a function $f$ is even if $f(x) = f(-x)$ for all $x$ , and odd if $f(x) = -f(-x)$ for all $x$ ). Find functions $c, s$ that also satisfy $c(x) + s(x) = x^n$ for all $x$ , where $n$ is a given positive integer.

Given a nonconstant function $f : \mathbb{R}^+ \longrightarrow\mathbb{R}$ such that $f(xy) = f(x)f(y)$ for any $x, y > 0$ , find functions $c, s : \mathbb{R}^+ \longrightarrow \mathbb{R}$ that satisfy $c\left(\frac{x}{y}\right) = c(x)c(y)-s(x)s(y)$ for all $x, y > 0$ and $c(x)+s(x) = f(x)$ for all $x > 0$ .

Let the polynomials $$P(x) = x^n + a_{n-1}x^{n-1 }+ \cdots + a_1x + a_0,$$ $$Q(x) = x^m + b_{m-1}x^{m-1} + \cdots + b_1x + b_0,$$ be given satisfying the identity $P(x)^2 = (x^2 - 1)Q(x)^2 + 1$ . Prove the identity $$P'(x) = nQ(x).$$

Let $\mathcal{C}$ be the circumcircle of the square with vertices $(0, 0), (0, 1978), (1978, 0), (1978, 1978)$ in the Cartesian plane. Prove that $\mathcal{C}$ contains no other point for which both coordinates are integers.

A sequence $(a_n)^{\infty}_0$ of real numbers is called convex if $2a_n\le a_{n-1}+a_{n+1}$ for all positive integers $n$ . Let $(b_n)^{\infty}_0$ be a sequence of positive numbers and assume that the sequence $(\alpha^nb_n)^{\infty}_0$ is convex for any choice of $\alpha > 0$ . Prove that the sequence $(\log b_n)^{\infty}_0$ is convex.

A function $f : I \to \mathbb R$, defined on an interval $I$, is called concave if $f(\theta x + (1 - \theta)y) \geq \theta f(x) + (1 - \theta)f(y)$ for all $x, y \in I$ and $0 \leq \theta \leq 1$. Assume that the functions $f_1, \ldots , f_n$, having all nonnegative values, are concave. Prove that the function $(f_1f_2 \cdots f_n)^{1/n}$ is concave.

A sequence $(a_n)_0^N$ of real numbers is called concave if $2a_n\ge a_{n-1} + a_{n+1}$ for all integers $n, 1 \le n \le N - 1$ . $(a)$ Prove that there exists a constant $C >0$ such that $$\left( \sum_{n=0}^{N}a_n\right)^2\ge C(N - 1) \sum_{n=0}^{N}a_n^2\:\:\:\:\:(1)$$ for all concave positive sequences $(a_n)^N_0$ $(b)$ Prove that $(1)$ holds with $C = \frac{3}{4}$ and that this constant is best possible.

The integers $1$ through $1000$ are located on the circumference of a circle in natural order. Starting with $1$ , every fifteenth number (i.e., $1, 16, 31, \cdots$ ) is marked. The marking is continued until an already marked number is reached. How many of the numbers will be left unmarked?

Simplify $$\frac{1}{\log_a(abc)}+\frac{1}{\log_b(abc)}+\frac{1}{\log_c(abc)},$$ where $a, b, c$ are positive real numbers.

Given a circle, construct a chord that is trisected by two given noncollinear radii.

$A$ is a $2m$ -digit positive integer each of whose digits is $1$ . $B$ is an $m$ -digit positive integer each of whose digits is $4$ . Prove that $A+B +1$ is a perfect square.

If $C^p_n=\frac{n!}{p!(n-p)!} (p \ge 1)$ , prove the identity $$C^p_n=C^{p-1}_{n-1} + C^{p-1}_{n-2} + \cdots + C^{p-1}_{p} + C^{p-1}_{p-1}$$ and then evaluate the sum $$S = 1\cdot 2 \cdot 3 + 2 \cdot 3 \cdot 4 + \cdots + 97 \cdot 98 \cdot 99.$$

$A,B,C,D,E$ are points on a circle $O$ with radius equal to $r$ . Chords $AB$ and $DE$ are parallel to each other and have length equal to $x$ . Diagonals $AC,AD,BE, CE$ are drawn. If segment $XY$ on $O$ meets $AC$ at $X$ and $EC$ at $Y$ , prove that lines $BX$ and $DY$ meet at $Z$ on the circle.

If $p$ is a prime greater than $3$ , show that at least one of the numbers $$\frac{3}{p^2} , \frac{4}{p^2} , \cdots, \frac{p-2}{p^2}$$ is expressible in the form $\frac{1}{x} + \frac{1}{y}$ , where $x$ and $y$ are positive integers.

In $ABC$ with $\angle C = 60^{\circ}$ , prove that $$\frac{c}{a} + \frac{c}{b} \ge2.$$

If $r > s >0$ and $a > b > c$ , prove that $$a^rb^s + b^rc^s + c^ra^s \ge a^sb^r + b^sc^r + c^sa^r.$$

Given the expression $$P_n(x) =\frac{1}{2^n}\left[(x +\sqrt{x^2 - 1})^n+(x-\sqrt{x^2 - 1})^n\right],$$ prove: $(a) P_n(x)$ satisfies the identity $$P_n(x) - xP_{n-1}(x) + \frac{1}{4}P_{n-2}(x) \equiv 0.$$ $(b) P_n(x)$ is a polynomial in $x$ of degree $n.$

Prove that it is possible to place $2n(2n + 1)$ parallelepipedic (rectangular) pieces of soap of dimensions $1 \times 2 \times (n + 1)$ in a cubic box with edge $2n + 1$ if and only if $n$ is even or $n = 1$.

Remark. It is assumed that the edges of the pieces of soap are parallel to the edges of the box.

Let $A,B,C,D$ be four arbitrary distinct points in space. $(a)$ Prove that using the segments $AB +CD, AC +BD$ and $AD +BC$ , it is always possible to construct a triangle $T$ that is non-degenerate and has no obtuse angle. $(b)$ What should these four points satisfy in order for the triangle $T$ to be right-angled?

A variable tetrahedron $ABCD$ has the following properties: Its edge lengths can change as well as its vertices, but the opposite edges remain equal $(BC = DA, CA = DB, AB = DC)$ ; and the vertices $A,B,C$ lie respectively on three fixed spheres with the same center $P$ and radii $3, 4, 12$ . What is the maximal length of $PD$ ?

Find the relations among the angles of the triangle $ABC$ whose altitude $AH$ and median $AM$ satisfy $\angle BAH =\angle CAM$ .

Let $p$ be a prime and $A = \{a_1, \ldots , a_{p-1} \}$ an arbitrary subset of the set of natural numbers such that none of its elements is divisible by $p$. Let us define a mapping $f$ from $\mathcal P(A)$ (the set of all subsets of $A$) to the set $P = \{0, 1, \ldots, p - 1\}$ in the following way:

$(i)$ if $B = \{a_{i_{1}}, \ldots , a_{i_{k}} \} \subset A$ and $\sum_{j=1}^k a_{i_{j}} \equiv n \pmod p$, then $f(B) = n,$

$(ii)$ $f(\emptyset) = 0$, $\emptyset$ being the empty set.

Prove that for each $n \in P$ there exists $B \subset A$ such that $f(B) = n.$

Determine all the triples $(a, b, c)$ of positive real numbers such that the system $$ax + by -cz = 0,$$ $$a \sqrt{1-x^2}+b \sqrt{1-y^2}-c \sqrt{1-z^2}=0,$$

is compatible in the set of real numbers, and then find all its real solutions.

Let $p, q$ and $r$ be three lines in space such that there is no plane that is parallel to all three of them. Prove that there exist three planes $\alpha, \beta$ , and $\gamma$ , containing $p, q$ , and $r$ respectively, that are perpendicular to each other $(\alpha\perp\beta, \beta\perp\gamma, \gamma\perp \alpha).$