Search

Na kružnicu stavljamo crvene i plave kuglice. Na početku se na kružnici nalaze samo dvije crvene kuglice. Dozvoljeni su sljedeći potezi:

i) dodati jednu crvenu kuglicu i promijeniti boju svake od dviju njoj susjednih kuglica (crvenu u plavu i obratno);

ii) maknuti jednu crvenu kuglicu i promijeniti boju svake od dviju njoj susjednih kuglica.

Možemo li nizom takvih poteza postići da na kružnici bude

a) $2013$ crvenih i $2013$ plavih kuglica;

b) samo dvije plave kuglice?

Za skup $A \subseteq \mathbb{Z}$ kažemo da je prihvatljiv ako za svaka dva (ne nužno različita) broja $x, y \in A$ i za svaki $k \in \mathbb{Z}$ vrijedi $x^2 + kxy + y^2 \in A$.

Nađi sve parove $(m, n)$ cijelih brojeva različitih od nule za koje je $\mathbb{Z}$ jedini prihvatljivi skup koji sadrži $m$ i $n$.

($\mathbb{Z}$ je skup svih cijelih brojeva.)

Grupa ljudi različitih visina pleše mađarski narodni ples na otvaranju natjecanja MEMO 2013 u Veszprému. Kažemo da je čovjek prosječan ako je viši od jednog svog susjeda i niži od drugog. (Ljudi su raspoređeni u krug i svaki čovjek ima točno dva susjeda.)

Ako je ukupan broj ljudi $N$, odredi sve moguće vrijednosti broja prosječnih ljudi.

Dokaži da za svaki prirodni broj $n \geqslant 2$ postoje prirodni brojevi $a_1, a_2, \ldots, a_n$ takvi da je za sve $1 \leqslant i < j \leqslant n$

$$\frac{a_j + a_i}{a_j - a_i}$$

prirodan broj.

Skup $A \subset \mathbb{N}$ zovemo neprijateljskim ako za svaki par $(a,b)$ brojeva iz $A$ postoji $k \in \mathbb{N}_0$ takav da je $M(a,b) = 2^k$. Postoji li beskonačan skup $S \subset \mathbb{N}$ sa svojstvom da je skup svih mogućih zbrojeva dvaju različitih elemenata skupa $S$ neprijateljski skup?

Neka je $n \geqslant 3$ prirodan broj. Za prirodan broj $m \geqslant n + 1$ kažemo da je $n$-obojiv ako je $m$ kamenčića postavljenih na kružnici moguće obojati u $n$ boja tako da se među bilo kojih $n + 1$ uzastopnih kamenčića pojavljuje svih $n$ boja.

Dokaži da postoji konačno mnogo prirodnih brojeva $m \geqslant n + 1$ koji nisu $n$-obojivi i odredi najveći od njih.

Dokaži da za svaki prirodan broj $n > 10^6$ postoji višekratnik broja $n$ koji nije veći od $n^4$, čiji zapis u dekadskom brojevnom sustavu koristi najviše 4 različite znamenke.

Označimo s $\tau(k)$ broj pozitivnih djelitelja prirodnog broja $k$, a s $\varphi(k)$ broj prirodnih brojeva koji nisu veći od $k$, a relativno su prosti s $k$. Za prirodan broj $m$ kažemo da je lijep ako postoji prirodan broj $n$ takav da vrijedi

$$\frac{\tau(m)}{m} = \frac{\varphi(n)}{n}.$$

Postoji li beskonačno mnogo lijepih brojeva?

Za pozitivan racionalan broj $q$ kažemo da je sjajan ako za svaki pozitivan racionalan broj $x$ postoje cijeli broj $n \geqslant 0$ i cijeli brojevi $a_0, \ldots, a_n$ takvi da je

$$x = q^{a_0} \cdot (q + 1)^{a_1} \cdot \ldots \cdot (q + n)^{a_n}.$$

Odredi sve sjajne brojeve.

Neka je $k \geqslant 2$ prirodan broj. Odredi najmanji prirodni broj $n \geqslant k + 1$ takav da postoji skup od $n$ (različitih) realnih brojeva u kojem koji god broj da izaberemo možemo pronaći još $k$ drugih brojeva u skupu čiji je zbroj jednak izabranom broju.

Neka su $k$ i $\ell$ prirodni brojevi. Odredi najmanji prirodan broj $m$ za koji je moguće podijeliti kvadrat $ABCD$ na $m$ pravokutnika stranica paralelnih sa stranicama kvadrata tako da svaki pravac paralelan s $AB$ koji siječe unutrašnjost kvadrata siječe barem $k$ pravokutnika, a svaki pravac paralelan s $BC$ koji siječe unutrašnjost kvadrata siječe barem $\ell$ pravokutnika.

Construct a right triangle with given hypotenuse $c$ such that the median drawn to the hypotenuse is the geometric mean of the two legs of the triangle.

Two planes, $P$ and $Q$, intersect along the line $p$. The point $A$ is given in the plane $P$, and the point $C$ in the plane $Q$; neither of these points lies on the straight line $p$. Construct an isosceles trapezoid $ABCD$ (with $AB$ parallel to $CD$) in which a circle can be inscribed, and with vertices $B$ and $D$ lying in the planes $P$ and $Q$ respectively.

Construct triangle $ABC$, given $h_{a}, h_{b}$ (the altitudes from $A$ and $B$) and $m_{a}$, the median from vertex $A$.

Construct triangle $ABC$ if $AC = b$, $AB = c$ and $\measuredangle AMB = \omega$, where $M$ is the midpoint of segment $BC$ and $\omega < 90°$. Prove that a solution exists if and only if $$b \tan \frac{\omega}{2} \leq c < b.$$ In what case does the equality hold?

On the circle $K$ there are given three distinct points $A,B,C.$ Construct (using only straightedge and compasses) a fourth point $D$ on $K$ such that a circle can be inscribed in the quadrilateral thus obtained.

Let $A_0B_0C_0$ and $A_1B_1C_1$ be any two acute-angled triangles. Consider all triangles $ABC$ that are similar to $\triangle A_1B_1C_1$ (so that vertices $A_1, B_1, C_1$ correspond to vertices $A, B, C$, respectively) and circumscribed about triangle $A_0B_0C_0$ (where $A_0$ lies on $BC$, $B_0$ on $CA$, and $AC_0$ on $AB$). Of all such possible triangles, determine the one with maximum area, and construct it.

For each value of $k = 1, 2, 3, 4, 5$, find necessary and sufficient conditions on the number $a > 0$ so that there exists a tetrahedron with $k$ edges of length $a$, and the remaining $6 - k$ edges of length 1.

The real numbers $a_0, a_1, \ldots, a_n, \ldots$ satisfy the condition: $$1 = a_0 \leq a_1 \leq a_2 \leq \cdots \leq a_n \leq \cdots.$$

The numbers $b_1, b_2, \ldots, b_n, \ldots$ are defined by $$b_n = \sum_{k=1}^{n} \left(1 - \frac{a_{k-1}}{a_k}\right) \frac{1}{\sqrt{a_k}}.$$

(a) Prove that $0 \leq b_n < 2$ for all $n$.

(b) Given $c$ with $0 \leq c < 2$, prove that there exist numbers $a_0, a_1, \ldots$ with the above properties such that $b_n > c$ for large enough $n$.

Prove that for every natural number $m$, there exists a finite set $S$ of points in a plane with the following property: For every point $A$ in $S$, there are exactly $m$ points in $S$ which are at unit distance from $A$.

Given four distinct parallel planes, prove that there exists a regular tetrahedron with a vertex on each plane.

Determine whether or not there exists a finite set $M$ of points in space not lying in the same plane such that, for any two points $A$ and $B$ of $M$, one can select two other points $C$ and $D$ of $M$ so that lines $AB$ and $CD$ are parallel and not coincident.

On the sides of an arbitrary triangle $ABC$, triangles $ABR, BCP, CAQ$ are constructed externally with $\angle CBP = \angle CAQ = 45°$, $\angle BCP = \angle ACQ = 30°$, $\angle ABR = \angle BAR = 15°$. Prove that $\angle QRP = 90°$ and $QR = RP$.

Determine, with proof, whether or not one can find 1975 points on the circumference of a circle with unit radius such that the distance between any two of them is a rational number.

Let $n$ be a given integer $> 2$, and let $V_n$ be the set of integers $1 + kn$, where $k = 1, 2, \ldots$. A number $m \in V_n$ is called indecomposable in $V_n$ if there do not exist numbers $p, q \in V_n$ such that $pq = m$. Prove that there exists a number $r \in V_n$ that can be expressed as the product of elements indecomposable in $V_n$ in more than one way. (Products which differ only in the order of their factors will be considered the same.)

Is it possible to choose 1983 distinct positive integers, all less than or equal to $10^5$, no three of which are consecutive terms of an arithmetic progression? Justify your answer.

Let $n$ be an integer greater than or equal to 3. Prove that there is a set of $n$ points in the plane such that the distance between any two points is irrational and each set of three points determines a non-degenerate triangle with rational area.

Let $n$ be a positive integer and let $A_1$, $A_2$, \ldots, $A_{2n+1}$ be subsets of a set $B$. Suppose that

(a) Each $A_i$ has exactly $2n$ elements,

(b) Each $A_i \cap A_j$ ($1 \leq i < j \leq 2n + 1$) contains exactly one element, and

(c) Every element of $B$ belongs to at least two of the $A_i$.

For which values of $n$ can one assign to every element of $B$ one of the numbers $0$ and $1$ in such a way that $A_i$ has $0$ assigned to exactly $n$ of its elements?

Prove that the set $\{1,2,\ldots,1989\}$ can be expressed as the disjoint union of subsets $A_i$ ($i = 1, 2, \ldots, 117$) such that:

(i) Each $A_i$ contains 17 elements;

(ii) The sum of all the elements in each $A_i$ is the same.

Prove that for each positive integer $n$ there exist $n$ consecutive positive integers none of which is an integral power of a prime number.

Prove that there exists a convex 1990-gon with the following two properties:

(a) All angles are equal.

(b) The lengths of the 1990 sides are the numbers $1^2, 2^2, 3^2, \ldots, 1990^2$ in some order.

Suppose $G$ is a connected graph with $k$ edges. Prove that it is possible to label the edges $1, 2, \ldots, k$ in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers labeling those edges is equal to 1.

[A graph consists of a set of points, called vertices, together with a set of edges joining certain pairs of distinct vertices. Each pair of vertices $u, v$ belongs to at most one edge. The graph $G$ is connected if for each pair of distinct vertices $x, y$ there is some sequence of vertices $x = v_0, v_1, v_2, \ldots, v_m = y$ such that each pair $v_i, v_{i+1}$ ($0 \leq i < m$) is joined by an edge of $G$.]

An infinite sequence $x_0, x_1, x_2, \ldots$ of real numbers is said to be bounded if there is a constant $C$ such that $|x_i| \leq C$ for every $i \geq 0$.

Given any real number $a > 1$, construct a bounded infinite sequence $x_0, x_1, x_2, \ldots$ such that

$$|x_i - x_j||i - j|^a \geq 1$$

for every pair of distinct nonnegative integers $i, j$.

Does there exist a function $f: \mathbf{N} \to \mathbf{N}$ such that $f(1) = 2$, $f(f(n)) = f(n) + n$ for all $n \in \mathbf{N}$, and $f(n) < f(n + 1)$ for all $n \in \mathbf{N}$?

For any positive integer $k$, let $f(k)$ be the number of elements in the set $\{k + 1, k + 2, \ldots, 2k\}$ whose base 2 representation has precisely three 1s.

• (a) Prove that, for each positive integer $m$, there exists at least one positive integer $k$ such that $f(k) = m$.
• (b) Determine all positive integers $m$ for which there exists exactly one $k$ with $f(k) = m$.

Show that there exists a set $A$ of positive integers with the following property: For any infinite set $S$ of primes there exist two positive integers $m \in A$ and $n \notin A$ each of which is a product of $k$ distinct elements of $S$ for some $k \geq 2$.

Determine all integers $n > 3$ for which there exist $n$ points $A_1, \ldots, A_n$ in the plane, no three collinear, and real numbers $r_1, \ldots, r_n$ such that for $1 \leq i < j < k \leq n$, the area of $\triangle A_i A_j A_k$ is $r_i + r_j + r_k$.

An $n \times n$ matrix whose entries come from the set $S = \{1, 2, \ldots, 2n - 1\}$ is called a silver matrix if, for each $i = 1, 2, \ldots, n$, the $i$th row and the $i$th column together contain all elements of $S$. Show that

(a) there is no silver matrix for $n = 1997$;

(b) silver matrices exist for infinitely many values of $n$.

100 cards are numbered 1 to 100 (each card different) and placed in 3 boxes (at least one card in each box). How many ways can this be done so that if two boxes are selected and a card is taken from each, then the knowledge of their sum alone is always sufficient to identify the third box?

Can we find $N$ divisible by just 2000 different primes, so that $N$ divides $2^N + 1$? [$N$ may be divisible by a prime power.]

$A_1A_2A_3$ is an acute-angled triangle. The foot of the altitude from $A_i$ is $K_i$ and the incircle touches the side opposite $A_i$ at $L_i$. The line $K_1K_2$ is reflected in the line $L_1L_2$. Similarly, the line $K_2K_3$ is reflected in $L_2L_3$ and $K_3K_1$ is reflected in $L_3L_1$. Show that the three new lines form a triangle with vertices on the incircle.

$S$ is the set $\{1,2,3,\ldots,1000000\}$. Show that for any subset $A$ of $S$ with 101 elements we can find 100 distinct elements $x_i$ of $S$, such that the sets $\{a + x_i | a \in A\}$ are all pairwise disjoint.

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged in two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

Let $a_1, a_2, \ldots, a_n$ be distinct positive integers and let $M$ be a set of $n - 1$ positive integers not containing $s = a_1 + a_2 + \cdots + a_n$. A grasshopper is to jump along the real axis, starting at the point $0$ and making $n$ jumps to the right with lengths $a_1, a_2, \ldots, a_n$ in some order. Prove that the order can be chosen in such a way that the grasshopper never lands on any point in $M$.

In each of six boxes $B_{1}, B_{2}, B_{3}, B_{4}, B_{5}, B_{6}$ there is initially one coin. There are two types of operation allowed:

Type 1: Choose a nonempty box $B_{j}$ with $1 \leq j \leq 5$. Remove one coin from $B_{j}$ and add two coins to $B_{j+1}$.

Type 2: Choose a nonempty box $B_{k}$ with $1 \leq k \leq 4$. Remove one coin from $B_{k}$ and exchange the contents of (possibly empty) boxes $B_{k+1}$ and $B_{k+2}$.

Determine whether there is a finite sequence of such operations that results in boxes $B_{1}, B_{2}, B_{3}, B_{4}, B_{5}$ being empty and box $B_{6}$ containing exactly $2010^{2010^{2010}}$ coins. (Note that $a^{b^{c}} = a^{(b^{c})}$.)

Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal{S}$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal{S}$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal{S}$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal{S}$. This process continues indefinitely.

Show that we can choose a point $P$ in $\mathcal{S}$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal{S}$ as a pivot infinitely many times.

The liar's guessing game is a game played between two players $A$ and $B$. The rules of the game depend on two positive integers $k$ and $n$ which are known to both players.

At the start of the game $A$ chooses integers $x$ and $N$ with $1 \leq x \leq N$. Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. Player $B$ now tries to obtain information about $x$ by asking player $A$ questions as follows: each question consists of $B$ specifying an arbitrary set $S$ of positive integers (possibly one specified in some previous question), and asking $A$ whether $x$ belongs to $S$. Player $B$ may ask as many such questions as he wishes. After each question, player $A$ must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any $k + 1$ consecutive answers, at least one answer must be truthful.

After $B$ has asked as many questions as he wants, he must specify a set $X$ of at most $n$ positive integers. If $x$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that:

1. If $n \geq 2^k$, then $B$ can guarantee a win.
2. For all sufficiently large $k$, there exists an integer $n \geq 1.99^k$ such that $B$ cannot guarantee a win.

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC = BC$. We say that $\mathcal{S}$ is centre-free if for any three different points $A$, $B$ and $C$ in $\mathcal{S}$, there is no point $P$ in $\mathcal{S}$ such that $PA = PB = PC$.

(a) Show that for all integers $n \geqslant 3$, there exists a balanced set consisting of $n$ points.

(b) Determine all integers $n \geqslant 3$ for which there exists a balanced centre-free set consisting of $n$ points.

Find all positive integers $n$ for which each cell of an $n \times n$ table can be filled with one of the letters $I$, $M$ and $O$ in such a way that:

• in each row and each column, one third of the entries are $I$, one third are $M$ and one third are $O$; and
• in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are $I$, one third are $M$ and one third are $O$.

Note: The rows and columns of an $n \times n$ table are each labelled 1 to $n$ in a natural order. Thus each cell corresponds to a pair of positive integers $(i,j)$ with $1 \leq i,j \leq n$. For $n > 1$, the table has $4n - 2$ diagonals of two types. A diagonal of the first type consists of all cells $(i,j)$ for which $i + j$ is a constant, and a diagonal of the second type consists of all cells $(i,j)$ for which $i - j$ is a constant.

An integer $N \geqslant 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold:

(1) no one stands between the two tallest players,

(2) no one stands between the third and fourth tallest players,

$\vdots$

$(N)$ no one stands between the two shortest players.

Show that this is always possible.