ILL 1971

The points $S(i, j)$ with integer Cartesian coordinates $0 < i \leq n, 0 < j \leq m, m \leq n$, form a lattice. Find the number of:

(a) rectangles with vertices on the lattice and sides parallel to the coordinate axes;

(b) squares with vertices on the lattice and sides parallel to the coordinate axes;

(c) squares in total, with vertices on the lattice.

Let us denote by $s(n)= \sum_{d|n} d$ the sum of divisors of a positive integer $n$ ( $1$ and $n$ included). If $n$ has at most $5$ distinct prime divisors, prove that $s(n) < \frac{77}{16} n.$ Also prove that there exists a natural number $n$ for which $s(n) < \frac{76}{16} n$ holds.

Let $a, b, c$ be positive real numbers, $0 < a \leq b \leq c$ . Prove that for any positive real numbers $x, y, z$ the following inequality holds: $$(ax+by+cz) \left( \frac xa + \frac yb+\frac zc \right) \leq (x+y+z)^2 \cdot \frac{(a+c)^2}{4ac}.$$

Let $x_n=2^{2^{n}}+1$ and let $m$ be the least common multiple of $x_2, x_3, \ldots, x_{1971}.$ Find the last digit of $m.$

Consider a sequence of polynomials $P_0(x), P_1(x), P_2(x), \ldots, P_n(x), \ldots$, where $P_0(x) = 2, P_1(x) = x$ and for every $n \geq 1$ the following equality holds: $$P_{n+1}(x) + P_{n-1}(x) = xP_n(x).$$

Prove that there exist three real numbers $a, b, c$ such that for all $n \geq 1,$ $$(x^2 - 4)[P_n^2(x) - 4] = [aP_{n+1}(x) + bP_n(x) + cP_{n-1}(x)]^2.$$

Let squares be constructed on the sides $BC,CA,AB$ of a triangle $ABC$ , all to the outside of the triangle, and let $A_1,B_1, C_1$ be their centers. Starting from the triangle $A_1B_1C_1$ one analogously obtains a triangle $A_2B_2C_2$ . If $S, S_1, S_2$ denote the areas of triangles $ABC,A_1B_1C_1,A_2B_2C_2$ , respectively, prove that $S = 8S_1 - 4S_2.$

In a triangle $ABC$ , let $H$ be its orthocenter, $O$ its circumcenter, and $R$ its circumradius. Prove that:(a) $|OH| = R \sqrt{1-8 \cos \alpha \cdot \cos \beta \cdot \cos \gamma}$ where $\alpha, \beta, \gamma$ are angles of the triangle $ABC;$ (b) $O \equiv H$ if and only if $ABC$ is equilateral.

The base of an inclined prism is a triangle $ABC$ . The perpendicular projection of $B_1$ , one of the top vertices, is the midpoint of $BC$ . The dihedral angle between the lateral faces through $BC$ and $AB$ is $\alpha$ , and the lateral edges of the prism make an angle $\beta$ with the base. If $r_1, r_2, r_3$ are exradii of a perpendicular section of the prism, assuming that in $ABC, \cos^2 A + \cos^2 B + \cos^2 C = 1, \angle A < \angle B < \angle C,$ and $BC = a$ , calculate $r_1r_2 + r_1r_3 + r_2r_3.$

In how many different ways can three knights be placed on a chessboard so that the number of squares attacked would be maximal?

Find all positive integers $n$ for which the number $1!+2!+3!+\cdots+n!$ is a perfect power of an integer.

A system of n numbers $x_1, x_2, \ldots, x_n$ is given such that $$x_1 = \log_{x_{n-1}} x_n, x_2 = \log_{x_{n}} x_1, \ldots, x_n = \log_{x_{n-2}} x_{n-1}.$$ Prove that $\prod_{k=1}^n x_k =1.$

Note that $8^3 - 7^3 = 169 = 13^2$ and $13 = 2^2 + 3^2.$ Prove that if the difference between two consecutive cubes is a square, then it is the square of the sum of two consecutive squares.

Let $ABCD$ be a convex quadrilateral whose diagonals intersect at $O$ at an angle $\theta$ . Let us set $OA = a, OB = b, OC = c$ , and $OD = d, c > a > 0$ , and $d > b > 0.$ Show that if there exists a right circular cone with vertex $V$ , with the properties:(1) its axis passes through $O$ , and**(2)** its curved surface passes through $A,B,C$ and $D,$ then $$OV^2=\frac{d^2b^2(c + a)^2 - c^2a^2(d + b)^2}{ca(d - b)^2 - db(c - a)^2}.$$

Show also that if $\frac{c+a}{d+b}$ lies between $\frac{ca}{db}$ and $\sqrt{\frac{ca}{db}},$ and $\frac{c-a}{d-b}=\frac{ca}{db},$ then for a suitable choice of $\theta$ , a right circular cone exists with properties **(1)**and (2).

Knowing that the system $$x + y + z = 3,$$ $$x^3 + y^3 + z^3 = 15,$$ $$x^4 + y^4 + z^4 = 35,$$

has a real solution $x, y, z$ for which $x^2 + y^2 + z^2 < 10$, find the value of $x^5 + y^5 + z^5$ for that solution.

We are given two mutually tangent circles in the plane, with radii $r_1, r_2$. A line intersects these circles in four points, determining three segments of equal length. Find this length as a function of $r_1$ and $r_2$ and the condition for the solvability of the problem.

Let $a_1, a_2, \ldots, a_n$ be positive numbers, $m_g = \sqrt[n]{(a_1a_2 \cdots a_n)}$ their geometric mean, and $m_a = \frac{(a_1 + a_2 + \cdots + a_n)}{n}$ their arithmetic mean. Prove that $$(1 + m_g)^n \leq (1 + a_1) \cdots(1 + a_n) \leq (1 + m_a)^n.$$

In a triangle $P_1P_2P_3$ let $P_iQ_i$ be the altitude from $P_i$ for $i = 1, 2,3$ ( $Q_i$ being the foot of the altitude). The circle with diameter $P_iQ_i$ meets the two corresponding sides at two points different from $P_i.$ Denote the length of the segment whose endpoints are these two points by $l_i.$ Prove that $l_1 = l_2 = l_3.$

Let $M$ be the circumcenter of a triangle $ABC.$ The line through $M$ perpendicular to $CM$ meets the lines $CA$ and $CB$ at $Q$ and $P,$ respectively. Prove that $$\frac{\overline{CP}}{\overline{CM}} \cdot \frac{\overline{CQ}}{\overline{CM}}\cdot \frac{\overline{AB}}{\overline{PQ}}= 2.$$

We are given an $n \times n$ board, where $n$ is an odd number. In each cell of the board either $+1$ or $-1$ is written. Let $a_k$ and $b_k$ denote them products of numbers in the $k^{th}$ row and in the $k^{th}$ column respectively. Prove that the sum $a_1 +a_2 +\cdots+a_n +b_1 +b_2 +\cdots+b_n$ cannot be equal to zero.

Find all integer solutions of the equation $$x^2+y^2=(x-y)^3.$$

Let $A, B,$ and $C$ denote the angles of a triangle. If $\sin^2 A + \sin^2 B + \sin^2 C = 2$ , prove that the triangle is right-angled.

Let $ABC,AA_1A_2,BB_1B_2, CC_1C_2$ be four equilateral triangles in the plane satisfying only that they are all positively oriented (i.e., in the counterclockwise direction). Denote the midpoints of the segments $A_2B_1,B_2C_1, C_2A_1$ by $P,Q,R$ in this order. Prove that the triangle $PQR$ is equilateral.

An infinite set of rectangles in the Cartesian coordinate plane is given. The vertices of each of these rectangles have coordinates $(0, 0), (p, 0), (p, q), (0, q)$ for some positive integers $p, q$ . Show that there must exist two among them one of which is entirely contained in the other.

Let $n \geq 2$ be a natural number. Find a way to assign natural numbers to the vertices of a regular $2n$ - gon such that the following conditions are satisfied:

(1) only digits $1$ and $2$ are used;

(2) each number consists of exactly $n$ digits;

(3) different numbers are assigned to different vertices;

(4) the numbers assigned to two neighboring vertices differ at exactly one digit.

A rhombus with its incircle is given. At each vertex of the rhombus a circle is constructed that touches the incircle and two edges of the rhombus. These circles have radii $r_1,r_2$ , while the incircle has radius $r$ . Given that $r_1$ and $r_2$ are natural numbers and that $r_1r_2=r$ , find $r_1,r_2,$ and $r$ .

Prove that the system of equations $$2yz+x-y-z=a, 2xz-x+y-z=a, 2xy-x-y+z=a,$$ $a$ being a parameter, cannot have five distinct solutions. For what values of $a$ does this system have four distinct integer solutions?

Determine whether there exist distinct real numbers $a, b, c, t$ for which:

(i) the equation $ax^2 + btx + c = 0$ has two distinct real roots $x_1, x_2,$

(ii) the equation $bx^2 + ctx + a = 0$ has two distinct real roots $x_2, x_3,$

(iii) the equation $cx^2 + atx + b = 0$ has two distinct real roots $x_3, x_1.$

Two half-lines $a$ and $b$ , with the common endpoint $O$ , make an acute angle $\alpha$ . Let $A$ on $a$ and $B$ on $b$ be points such that $OA=OB$ , and let $b$ be the line through $A$ parallel to $b$ . Let $\beta$ be the circle with centre $B$ and radius $BO$ . We construct a sequence of half-lines $c_1,c_2,c_3,\ldots$ , all lying inside the angle $\alpha$ , in the following manner: (i) $c_i$ is given arbitrarily; (ii) for every natural number $k$ , the circle $\beta$ intercepts on $c_k$ a segment that is of the same length as the segment cut on $b'$ by $a$ and $c_{k+1}$ . Prove that the angle determined by the lines $c_k$ and $b$ has a limit as $k$ tends to infinity and find that limit.

A square $2n\times 2n$ grid is given. Let us consider all possible paths along grid lines, going from the centre of the grid to the border, such that (1) no point of the grid is reached more than once, and (2) each of the squares homothetic to the grid having its centre at the grid centre is passed through only once. (a) Prove that the number of all such paths is equal to $4\prod_{i=2}^n(16i-9)$ . (b) Find the number of pairs of such paths that divide the grid into two congruent figures. (c) How many quadruples of such paths are there that divide the grid into four congruent parts?

Let $T_k = k - 1$ for $k = 1, 2, 3,4$ and $$T_{2k-1} = T_{2k-2} + 2^{k-2}, T_{2k} = T_{2k-5} + 2^k (k \geq 3).$$

Show that for all $k$, $$1 + T_{2n-1} = \left[ \frac{12}{7}2^{n-1} \right] \text{and} 1 + T_{2n} = \left[ \frac{17}{7}2^{n-1} \right],$$

where $[x]$ denotes the greatest integer not exceeding $x.$

The matrix $$A=\begin{pmatrix} a_{11} & \ldots & a_{1n} \\ \vdots & \ldots & \vdots \\ a_{n1} & \ldots & a_{nn} \end{pmatrix}$$

satisfies the inequality $\sum_{j=1}^n |a_{j1}x_1 + \cdots+ a_{jn}x_n| \leq M$ for each choice of numbers $x_i$ equal to $\pm 1$. Show that $$|a_{11} + a_{22} + \cdots+ a_{nn}| \leq M.$$

Let $S$ be a circle, and $\alpha =\{A_1,\ldots ,A_n\}$ a family of open arcs in $S$ . Let $N(\alpha )=n$ denote the number of elements in $\alpha$ . We say that $\alpha$ is a covering of $S$ if $\bigcup_{k=1}^n A_k\supset S$ . Let $\alpha=\{A_1,\ldots ,A_n\}$ and $\beta =\{B_1,\ldots ,B_m\}$ be two coverings of $S$ . Show that we can choose from the family of all sets $A_i\cap B_j,\ i=1,2,\ldots ,n,\ j=1, 2,\ldots ,m,$ a covering $\gamma$ of $S$ such that $N(\gamma )\le N(\alpha)+N(\beta)$ .

Let $A,B,C$ be three points with integer coordinates in the plane and $K$ a circle with radius $R$ passing through $A,B,C$ . Show that $AB\cdot BC\cdot CA\ge 2R$ , and if the centre of $K$ is in the origin of the coordinates, show that $AB\cdot BC\cdot CA\ge 4R$ .

Two congruent equilateral triangles $ABC$ and $A'B'C'$ in the plane are given. Show that the midpoints of the segments $AA',BB', CC'$ either are collinear or form an equilateral triangle.

Consider the set of grid points $(m,n)$ in the plane, $m,n$ integers. Let $\sigma$ be a finite subset and define $$S(\sigma)=\sum_{(m,n)\in\sigma}(100-|m|-|n|)$$ Find the maximum of $S$ , taken over the set of all such subsets $\sigma$ .

Let $L_i,\ i=1,2,3$ , be line segments on the sides of an equilateral triangle, one segment on each side, with lengths $l_i,\ i=1,2,3$ . By $L_i^{\ast}$ we denote the segment of length $l_i$ with its midpoint on the midpoint of the corresponding side of the triangle. Let $M(L)$ be the set of points in the plane whose orthogonal projections on the sides of the triangle are in $L_1,L_2$ , and $L_3$ , respectively; $M(L^{\ast})$ is defined correspondingly. Prove that if $l_1\ge l_2+l_3$ , we have that the area of $M(L)$ is less than or equal to the area of $M(L^{\ast})$ .

Show that for nonnegative real numbers $a,b$ and integers $n\ge 2$ , $$\frac{a^n+b^n}{2}\ge\left(\frac{a+b}{2}\right)^n$$ When does equality hold?

Let $A = (a_{ij})$ , where $i,j = 1,2,\ldots,n$ , be a square matrix with all $a_{ij}$ non-negative integers. For each $i,j$ such that $a_{ij} = 0$ , the sum of the elements in the $i$ th row and the $j$ th column is at least $n$ . Prove that the sum of all the elements in the matrix is at least $\frac {n^2}{2}$ .

Let $m$ and $n$ denote integers greater than $1$ , and let $\nu (n)$ be the number of primes less than or equal to $n$ . Show that if the equation $\frac{n}{\nu(n)}=m$ has a solution, then so does the equation $\frac{n}{\nu(n)}=m-1$ .

A broken line $A_1A_2 \ldots A_n$ is drawn in a $50 \times 50$ square, so that the distance from any point of the square to the broken line is less than $1$. Prove that its total length is greater than $1248.$

Natural numbers from $1$ to $99$ (not necessarily distinct) are written on $99$ cards. It is given that the sum of the numbers on any subset of cards (including the set of all cards) is not divisible by $100$. Show that all the cards contain the same number.

A sequence of real numbers $x_1,x_2,\ldots ,x_n$ is given such that $x_{i+1}=x_i+\frac{1}{30000}\sqrt{1-x_i^2},\ i=1,2,\ldots ,$ and $x_1=0$ . Can $n$ be equal to $50000$ if $x_n<1$ ?

The diagonals of a convex quadrilateral $ABCD$ intersect at a point $O$ . Find all angles of this quadrilateral if $\measuredangle OBA=30^{\circ},\measuredangle OCB=45^{\circ},\measuredangle ODC=45^{\circ}$ , and $\measuredangle OAD=30^{\circ}$ .

Suppose that the sides $AB$ and $DC$ of a convex quadrilateral $ABCD$ are not parallel. On the sides $BC$ and $AD$ , pairs of points $(M,N)$ and $(K,L)$ are chosen such that $BM=MN=NC$ and $AK=KL=LD$ . Prove that the areas of triangles $OKM$ and $OLN$ are different, where $O$ is the intersection point of $AB$ and $CD$ .

Prove the inequality $$\frac{a_1+ a_3}{a_1 + a_2} + \frac{a_2 + a_4}{a_2 + a_3} + \frac{a_3 + a_1}{a_3 + a_4} + \frac{a_4 + a_2}{a_4 + a_1} \geq 4,$$

where $a_i > 0, i = 1, 2, 3, 4.$

Denote by $x_n(p)$ the multiplicity of the prime $p$ in the canonical representation of the number $n!$ as a product of primes. Prove that $\frac{x_n(p)}{n}<\frac{1}{p-1}$ and $\lim_{n \to \infty}\frac{x_n(p)}{n}=\frac{1}{p-1}$ .

A set $M$ is formed of $\binom{2n}{n}$ men, $n=1,2,\ldots$ . Prove that we can choose a subset $P$ of the set $M$ consisting of $n+1$ men such that one of the following conditions is satisfied: $(1)$ every member of the set $P$ knows every other member of the set $P$ ; $(2)$ no member of the set $P$ knows any other member of the set $P$ .

Prove that the polynomial $x^4+\lambda x^3+\mu x^2+\nu x+1$ has no real roots if $\lambda, \mu , \nu$ are real numbers satisfying $$|\lambda |+|\mu |+|\nu |\le \sqrt{2}$$