ILL 1974

We consider the division of a chess board $8 \times 8$ in p disjoint rectangles which satisfy the conditions:

a) every rectangle is formed from a number of full squares (not partial) from the 64 and the number of white squares is equal to the number of black squares.

b) the numbers $\ a_{1}, \ldots, a_{p}$ of white squares from $p$ rectangles satisfy $a_1, , \ldots, a_p.$ Find the greatest value of $p$ for which there exists such a division and then for that value of $p,$ all the sequences $a_{1}, \ldots, a_{p}$ for which we can have such a division.

Moderator says: see https://artofproblemsolving.com/community/c6h58591

Let ${u_n}$ be the Fibonacci sequence, i.e., $u_0=0,u_1=1,u_n=u_{n-1}+u_{n-2}$ for $n>1$ . Prove that there exist infinitely many prime numbers $p$ that divide $u_{p-1}$ .

Let $ABCD$ be an arbitrary quadrilateral. Let squares $ABB_1A_2, BCC_1B_2, CDD_1C_2, DAA_1D_2$ be constructed in the exterior of the quadrilateral. Furthermore, let $AA_1PA_2$ and $CC_1QC_2$ be parallelograms. For any arbitrary point $P$ in the interior of $ABCD$ , parallelograms $RASC$ and $RPTQ$ are constructed. Prove that these two parallelograms have two vertices in common.

Let $K_a,K_b,K_c$ with centres $O_a,O_b,O_c$ be the excircles of a triangle $ABC$ , touching the interiors of the sides $BC,CA,AB$ at points $T_a,T_b,T_c$ respectively. Prove that the lines $O_aT_a,O_bT_b,O_cT_c$ are concurrent in a point $P$ for which $PO_a=PO_b=PO_c=2R$ holds, where $R$ denotes the circumradius of $ABC$ . Also prove that the circumcentre $O$ of $ABC$ is the midpoint of the segment $PI$ , where $I$ is the incentre of $ABC$ .

A straight cone is given inside a rectangular parallelepiped $B$ , with the apex at one of the vertices, say $T$ , of the parallelepiped, and the base touching the three faces opposite to $T .$ Its axis lies at the long diagonal through $T.$ If $V_1$ and $V_2$ are the volumes of the cone and the parallelepiped respectively, prove that $$V_1 \leq \frac{\sqrt 3 \pi V_2}{27}.$$

Prove that the product of two natural numbers with their sum cannot be the third power of a natural number.

Let $p$ be a prime number and $n$ a positive integer. Prove that the product $${N=\frac{1}{p^{n^2}}} \prod_{i=1;2 \nmid i}^{2n-1} \biggl[ \left( (p-1)! \right) \binom{p^2 i}{pi}\biggr]$$ Is a positive integer that is not divisible by $p.$

Let $x, y, z$ be real numbers each of whose absolute value is different from $\frac{1}{\sqrt 3}$ such that $x + y + z = xyz$. Prove that $$\frac{3x - x^3}{1-3x^2} + \frac{3y - y^3}{1-3y^2} + \frac{3z -z^3}{1-3z^2} = \frac{3x - x^3}{1-3x^2} \cdot \frac{3y - y^3}{1-3y^2} \cdot \frac{3z - z^3}{1-3z^2}$$

Solve the following system of linear equations with unknown $x_1,x_2 \ldots, x_n \ (n \geq 2)$ and parameters $c_1,c_2, \ldots , c_n:$ $$2x_1 -x_2 = c_1;$$$$-x_1 +2x_2 -x_3 = c_2;$$$$-x_2 +2x_3 -x_4 = c_3;$$$$\cdots \cdots \cdots$$$$-x_{n-2} +2x_{n-1} -x_n = c_{n-1};$$$$-x_{n-1} +2x_n = c_n.$$

A regular octagon $P$ is given whose incircle $k$ has diameter $1$ . About $k$ is circumscribed a regular $16$ -gon, which is also inscribed in $P$ , cutting from $P$ eight isosceles triangles. To the octagon $P$ , three of these triangles are added so that exactly two of them are adjacent and no two of them are opposite to each other. Every $11$ -gon so obtained is said to be $P'$ . Prove the following statement: Given a finite set $M$ of points lying in $P$ such that every two points of this set have a distance not exceeding $1$ , one of the $11$ -gons $P'$ contains all of $M$ .

Given a line $p$ and a triangle $\Delta$ in the plane, construct an equilateral triangle one of whose vertices lies on the line $p$ , while the other two halve the perimeter of $\Delta.$

A circle $K$ with radius $r$ , a point $D$ on $K$ , and a convex angle with vertex $S$ and rays $a$ and $b$ are given in the plane. Construct a parallelogram $ABCD$ such that $A$ and $B$ lie on $a$ and $b$ respectively, $SA+SB=r$ , and $C$ lies on $K$ .

Prove that $2^{147} - 1$ is divisible by $343$ .

Let $n$ and $k$ be natural numbers and $a_1,a_2,\ldots ,a_n$ be positive real numbers satisfying $a_1+a_2+\cdots +a_n=1$ . Prove that $$\dfrac {1} {a_1^{k}}+\dfrac {1} {a_2^{k}}+\cdots +\dfrac {1} {a_n^{k}} \ge n^{k+1}.$$

A pack of $2n$ cards contains $n$ different pairs of cards. Each pair consists of two identical cards, either of which is called the twin of the other. A game is played between two players $A$ and $B$ . A third person called the dealer shuffles the pack and deals the cards one by one face upward onto the table. One of the players, called the receiver, takes the card dealt, provided he does not have already its twin. If he does already have the twin, his opponent takes the dealt card and becomes the receiver. $A$ is initially the receiver and takes the first card dealt. The player who first obtains a complete set of $n$ different cards wins the game. What fraction of all possible arrangements of the pack lead to $A$ winning? Prove the correctness of your answer.

Show that there exists a set $S$ of $15$ distinct circles on the surface of a sphere, all having the same radius and such that $5$ touch exactly $5$ others, $5$ touch exactly $4$ others, and $5$ touch exactly $3$ others.

[General Problem: http://www.artofproblemsolving.com/Forum/viewtopic.php?f=46&t=384764]

Let $A_r,B_r, C_r$ be points on the circumference of a given circle $S$. From the triangle $A_rB_rC_r$, called $\Delta_r$, the triangle $\Delta_{r+1}$ is obtained by constructing the points $A_{r+1},B_{r+1}, C_{r+1}$ o n $S$ such that $A_{r+1}A_r$ is parallel to $B_rC_r$, $B_{r+1}B_r$ is parallel to $C_rA_r$, and $C_{r+1}C_r$ is parallel to $A_rB_r$. Each angle of $\Delta_1$ is an integer number of degrees and those integers are not multiples of $45$. Prove that at least two of the triangles $\Delta_1,\Delta_2, \ldots ,\Delta_{15}$ are congruent.

Prove that there exists, for $n \geq 4$ , a set $S$ of $3n$ equal circles in space that can be partitioned into three subsets $s_5, s_4$ , and $s_3$ , each containing $n$ circles, such that each circle in $s_r$ touches exactly $r$ circles in $S.$

For which natural numbers $n$ do there exist $n$ natural numbers $a_i\ (1\le i\le n)$ such that $\sum_{i=1}^n a_i^{-2}=1$ ?

Let $M$ be a nonempty subset of $\mathbb Z^+$ such that for every element $x$ in $M,$ the numbers $4x$ and $\lfloor \sqrt x \rfloor$ also belong to $M.$ Prove that $M = \mathbb Z^+.$

Prove that the squares with sides $\frac{1}{1}, \frac{1}{2}, \frac{1}{3},\ldots$ may be put into the square with side $\frac{3}{2}$ in such a way that no two of them have any interior point in common.

Let $a_i, b_i$ be coprime positive integers for $i = 1, 2, \ldots , k$, and $m$ the least common multiple of $b_1, \ldots , b_k$. Prove that the greatest common divisor of $a_1 \frac{m}{b_1} , \ldots, a_k \frac{m}{b_k}$ equals the greatest common divisor of $a_1, \ldots , a_k.$

Let $f : \mathbb R \to \mathbb R$ be of the form $f(x) = x + \epsilon \sin x,$ where $0 < |\epsilon| \leq 1.$ Define for any $x \in \mathbb R,$ $$x_n=\underbrace{f \ o \ \ldots \ o \ f}_{n \text{ times}} (x).$$ Show that for every $x \in \mathbb R$ there exists an integer $k$ such that $\lim_{n\to \infty } x_n = k\pi.$

Let $g(k)$ be the number of partitions of a $k$ -element set $M$ , i.e., the number of families $\{ A_1,A_2,\ldots ,A_s\}$ of nonempty subsets of $M$ such that $A_i\cap A_j=\emptyset$ for $i\not= j$ and $\bigcup_{i=1}^n A_i=M$ . Prove that, for every $n$ , $$n^n\le g(2n)\le (2n)^{2n}$$

Let $C_1$ and $C_2$ be circles in the same plane, $P_1$ and $P_2$ arbitrary points on $C_1$ and $C_2$ respectively, and $Q$ the midpoint of segment $P_1P_2.$ Find the locus of points $Q$ as $P_1$ and $P_2$ go through all possible positions. Alternative version. Let $C_1, C_2, C_3$ be three circles in the same plane. Find the locus of the centroid of triangle $P_1P_2P_3$ as $P_1, P_2,$ and $P_3$ go through all possible positions on $C_1, C_2$ , and $C_3$ respectively.

Let $M$ be a finite set and $P=\{ M_1,M_2,\ldots ,M_l\}$ a partition of $M$ (i.e., $\bigcup_{i=1}^k M_i, M_i\not=\emptyset, M_i\cap M_j =\emptyset$ for all $i,j\in\{1,2, \ldots ,k\} ,i\not= j)$ . We define the following elementary operation on $P$ : Choose $i,j\in\{1,2,\ldots ,k\}$ , such that $i=j$ and $M_i$ has a elements and $M_j$ has $b$ elements such that $a\ge b$ . Then take $b$ elements from $M_i$ and place them into $M_j$ , i.e., $M_j$ becomes the union of itself and a $b$ -element subset of $M_i$ , while the same subset is subtracted from $M_i$ (if $a=b$ , $M_i$ is thus removed from the partition). Let a finite set $M$ be given. Prove that the property "for every partition $P$ of $M$ there exists a sequence $P=P_1,P_2,\ldots ,P_r$ such that $P_{i+1}$ is obtained from $P_i$ by an elementary operation and $P_r=\{M\}$ " is equivalent to "the number of elements of $M$ is a power of $2$ ."

Let $y^{\alpha}=\sum_{i=1}^n x_i^{\alpha}$ where $\alpha \neq 0, y > 0, x_i > 0$ are real numbers, and let $\lambda \neq \alpha$ be a real number. Prove that $y^{\lambda} > \sum_{i=1}^n x_i^{\lambda}$ if $\alpha (\lambda - \alpha) > 0,$ and $y^{\lambda} < \sum_{i=1}^n x_i^{\lambda}$ if $\alpha (\lambda - \alpha) < 0.$

Let $a_1,a_2,\ldots ,a_n$ be $n$ real numbers such that $0<a\le a_k\le b$ for $k=1,2,\ldots ,n$ . If $m_1=\frac{1}{n}(a_1+a_2+\cdots+a_n)$ and $m_2=\frac{1}{n}(a_1^2+a_2^2+\cdots + a_n^2)$ , prove that $m_2\le\frac{(a+b)^2}{4ab}m_1^2$ and find a necessary and sufficient condition for equality.

Let a be a real number such that $0 < a < 1$ , and let $n$ be a positive integer. Define the sequence $a_0, a_1, a_2, \ldots, a_n$ an recursively by $$a_0 = a, a_{k+1} = a_k +\frac 1n a_k^2 \text{ for } k = 0, 1, \ldots, n - 1.$$ Prove that there exists a real number $A$ , depending on $a$ but independent of $n$ , such that $$0 < n(A - a_n) < A^3.$$

Consider infinite diagrams

$n_{00} \ n_{01} \ n_{02} \ldots$ $n_{10} \ n_{11} \ n_{12} \ldots$ $n_{20} \ n_{21} \ n_{22} \ldots$ $\vdots \vdots \vdots$

where all but a finite number of the integers $n_{ij} , i = 0, 1, 2, \ldots, j = 0, 1, 2, \ldots ,$ are equal to $0$ . Three elements of a diagram are called adjacent if there are integers $i$ and $j$ with $i \geq 0$ and $j \geq 0$ such that the three elements are**(i)** $n_{ij}, n_{i,j+1}, n_{i,j+2},$ or**(ii)** $n_{ij}, n_{i+1,j}, n_{i+2,j} ,$ or**(iii)** $n_{i+2,j}, n_{i+1,j+1}, n_{i,j+2}.$ An elementary operation on a diagram is an operation by which three adjacent elements $n_{ij}$ are changed into $n_{ij}'$ in such a way that $|n_{ij}-n_{ij}'|=1.$ Two diagrams are called equivalent if one of them can be changed into the other by a finite sequence of elementary operations. How many inequivalent diagrams exist?

If $p$ and $q$ are distinct prime numbers, then there are integers $x_0$ and $y_0$ such that $1 = px_0 + qy_0.$ Determine the maximum value of $b - a$ , where $a$ and $b$ are positive integers with the following property: If $a \leq t \leq b$ , and $t$ is an integer, then there are integers $x$ and $y$ with $0 \leq x \leq q - 1$ and $0 \leq y \leq p - 1$ such that $t = px + qy.$

Consider the binomial coefficients $\binom{n}{k}=\frac{n!}{k!(n-k)!}\ (k=1,2,\ldots n-1)$. Determine all positive integers $n$ for which $\binom{n}{1},\binom{n}{2},\ldots ,\binom{n}{n-1}$ are all even numbers.

Let $a, b$ , and $c$ denote the three sides of a billiard table in the shape of an equilateral triangle. A ball is placed at the midpoint of side $a$ and then propelled toward side $b$ with direction defined by the angle $\theta$ . For what values of $\theta$ will the ball strike the sides $b, c, a$ in that order?

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 $n$ be a positive integer, $n \geq 2$ , and consider the polynomial equation $$x^n - x^{n-2} - x + 2 = 0.$$ For each $n,$ determine all complex numbers $x$ that satisfy the equation and have modulus $|x| = 1.$

Through the circumcenter $O$ of an arbitrary acute-angled triangle, chords $A_1A_2,B_1B_2, C_1C_2$ are drawn parallel to the sides $BC,CA,AB$ of the triangle respectively. If $R$ is the radius of the circumcircle, prove that $$A_1O \cdot OA_2 + B_1O \cdot OB_2 + C_1O \cdot OC_2 = R^2.$$

In a certain language words are formed using an alphabet of three letters. Some words of two or more letters are not allowed, and any two such distinct words are of different lengths. Prove that one can form a word of arbitrary length that does not contain any non-allowed word.

An $(n^2+n+1) \times (n^2+n+1)$ matrix of zeros and ones is given. If no four ones are vertices of a rectangle, prove that the number of ones does not exceed $(n + 1)(n^2 + n + 1).$

We are given $n$ mass points of equal mass in space. We define a sequence of points $O_1,O_2,O_3,\ldots$ as follows: $O_1$ is an arbitrary point (within the unit distance of at least one of the $n$ points); $O_2$ is the centre of gravity of all the $n$ given points that are inside the unit sphere centred at $O_1$; $O_3$ is the centre of gravity of all of the $n$ given points that are inside the unit sphere centred at $O_2$; etc. Prove that starting from some $m$, all points $O_m,O_{m+1},O_{m+2},\ldots$ coincide.

The sum of the squares of five real numbers $a_1, a_2, a_3, a_4, a_5$ equals $1$. Prove that the least of the numbers $(a_i - a_j)^2$, where $i, j = 1, 2, 3, 4,5$ and $i \neq j$, does not exceed $\frac{1}{10}.$

Outside an arbitrary triangle $ABC$ , triangles $ADB$ and $BCE$ are constructed such that $\angle ADB=\angle BEC=90^{\circ}$ and $\angle DAB=\angle EBC=30^{\circ}$ . On the segment $AC$ the point $F$ with $AF=3FC$ is chosen. Prove that $\angle DFE=90^{\circ}$ and $\angle FDE=30^{\circ}$ .

Given two points $A,B$ outside of a given plane $P,$ find the positions of points $M$ in the plane $P$ for which the ratio $\frac{MA}{MB}$ takes a minimum or maximum.

Determine an equation of third degree with integral coefficients having roots $\sin \frac{\pi}{14}, \sin \frac{5 \pi}{14}$ and $\sin \frac{-3 \pi}{14}.$

Let $m$ and $n$ be natural numbers with $m>n$ . Prove that $$2(m-n)^2(m^2-n^2+1)\ge 2m^2-2mn+1$$

There are $n$ points on a flat piece of paper, any two of them at a distance of at least $2$ from each other. An inattentive pupil spills ink on a part of the paper such that the total area of the damaged part equals $\frac 32$ . Prove that there exist two vectors of equal length less than $1$ and with their sum having a given direction, such that after a translation by either of these two vectors no points of the given set remain in the damaged area.

A fox stands in the centre of the field which has the form of an equilateral triangle, and a rabbit stands at one of its vertices. The fox can move through the whole field, while the rabbit can move only along the border of the field. The maximal speeds of the fox and rabbit are equal to $u$ and $v$ , respectively. Prove that: (a) If $2u>v$ , the fox can catch the rabbit, no matter how the rabbit moves. (b) If $2u\le v$ , the rabbit can always run away from the fox.