A convex $n$-vertex polygon is partitioned into triangles by nonintersecting diagonals . The following operation, called perestroyka (=reconstruction) , is allowed: two triangles $ABD$ and $BCD$ with a common side may be replaced by the triangles $ABC$ and $ACD$. By $P(n)$ denote the smallest number of perestroykas needed to transform any partitioning into any other one. Prove that (a) $P ( n ) \ge n - 3$ (b) $P (n) \le 2n - 7$ (c) $P(n) \le 2n - 10$ if $n \ge 13$ . ( D.Fomin , based on ideas of W. Thurston , D . Sleator, R. Tarjan)

There are $n$ points in the plane so that no two pairs are equidistant. Each point is connected to the nearest point by a segment. Show that no point is connected to more than five points.

A square of side $n$ ($n$ natural) is divided into $n^2$ squares of side $1$. Each pair of "horizontal" boundary lines and each pair of "vertical" boundary lines enclose a rectangle (a square is also considered a rectangle). A rectangle has a length and a width; the width is less than or equal to the length. (a) Prove that there are $8$ rectangles of width $n - 1$. (b) Determine the number of rectangles with width $n -k$ ($0\le k \le n -1,k$ integer). (c) Determine a formula for $1^3 + 2^3 +...+ n^3$.

A cube is assembled with $27$ white cubes. The larger cube is then painted black on the outside and disassembled. A blind man reassembles it. What is the probability that the cube is now completely black on the outside? Give an approximation of the size of your answer.

Each point in the plane with integer coordinates is colored red or blue such that the following two properties hold. For any two red points, the line segment joining them does not contain any blue points. For any two blue points that are distance $2$ apart, the midpoint of the line segment joining them is blue. Prove that if three red points are the vertices of a triangle, then the interior of the triangle does not contain any blue points.

Six ducklings swim on the surface of a pond, which is in the shape of a circle with radius $5$ m. Show that at every moment, two of the ducklings swim on the distance of at most $5$ m from each other.

Call a convex polyhedron a [i]footballoid [/i] if it has the following properties. (1) Any face is either a regular pentagon or a regular hexagon. (2) All neighbours of a pentagonal face are hexagonal (a [i]neighbour [/i] of a face is a face that has a common edge with it). Find all possibilities for the number of pentagonal and hexagonal faces of a footballoid.

Let $A$ be an infinite set of points in the plane such that inside each circle there are only a finite number of points of $A$, with the following properties: $\bullet$ $(0, 0)$ belongs to $A$. $\bullet$ If $(a, b)$ and $(c, d)$ belong to $A$, then $(a-c, b-d)$ belongs to $A$. $\bullet$ There is a value of $\alpha$ such that by rotating the set $A$ with center at $(0, 0)$ and angle $\alpha$, the set $A$ is obtained again. Prove that $\alpha$ must be equal to $\pm 60^{\circ}$ or $\pm 90^{\circ}$ or $\pm 120^{\circ}$ or $\pm 180^{\circ}$.

Let $f(n)$ be the least number of distinct points in the plane such that for each $k = 1, 2, \cdots, n$ there exists a straight line containing exactly $k$ of these points. Find an explicit expression for $f(n).$ [i]Simplified version.[/i] Show that $f(n)=\left[\frac{n+1}{2}\right]\left[\frac{n+2}{2}\right].$ Where $[x]$ denoting the greatest integer not exceeding $x.$

Three different points were randomly selected from the vertices of the regular $2n$-gon. Let $ p_n $ be the probability of the event that the triangle with vertices at the selected points is acute-angled. Calculate $ \lim_{n\to \infty} p_n $. Attention. We assume that all choices of three different points are equally likely.

In four-dimensional space, the $24$-cell of sidelength $\sqrt{2}$ is the convex hull of (smallest convex set containing) the $24$ points $(\pm 1, \pm 1, 0, 0)$ and its permutations. Find the four-dimensional volume of this region.

In the $43$ dimension Euclidean space the convex hull of finite set $S$ contains polyhedron $P$. We know that $P$ has $47$ vertices. Prove that it is possible to choose at most $2021$ points in $S$ such that the convex hull of these points also contain $P$, and this is sharp.

There are several settlements on the bank of the Big Round Lake. Some of them are connected with the regular direct ship lines. Two settlements are connected if and only if two next (counterclockwise) to each ones are not connected. Prove that you can move from the arbitrary settlement to another arbitrary settlement, having used not more than three ships.

On the Cartesian coordinate system $Oxy$, consider a sequence of points $A_n(x_n, y_n)$ in which $(x_n)^{\infty}_{n=1}$,$(y_n)^{\infty}_{n=1}$ are two sequences of positive numbers satisfing the following conditions: $$x_{n+1} =\sqrt{\frac{x_n^2+x_{n+2}^2}{2}}, y_{n+1} =\big( \frac{\sqrt{y_n}+\sqrt{y_{n+2}}}{2} \big)^2 \,\, \forall n \ge 1 $$ Suppose that $O, A_1, A_{2016}$ belong to a line $d$ and $A_1, A_{2016}$ are distinct. Prove that all the points $A_2, A_3,. .. , A_{2015}$ lie on one side of $d$.

Sebastian has a certain number of rectangles with areas that sum up to 3 and with side lengths all less than or equal to $1$. Demonstrate that with each of these rectangles it is possible to cover a square with side $1$ in such a way that the sides of the rectangles are parallel to the sides of the square. [b]Note:[/b] The rectangles can overlap and they can protrude over the sides of the square.

The centre of a circle is the origin of $N$ vectors whose ends divide the circle in $N$ equal arcs . Some of the vectors are blue and some are red . We calculate the sum of the angles formed between each pair consisting of a red vector and a blue vector (the angle being measured anticlockwise from red to blue) and divide this sum by the total number of such angles . Prove that the "mean angle" thus obtained is $180^o$. (V. P roizvolov)

Show that no matter how $15$ points are plotted within a circle of radius $2$ (circle border included), there will be a circle with radius $1$ (circle border including) which contains at least three of the $15$ points.

The plan of the castle in Baranow Sandomierski can be presented as the graph with $16$ vertices on the picture. A night guard plans a closed round along the edges of this graph. (a) How many rounds passing through each vertex exactly once are there? The directions are irrelevant. (b) How many non-selfintersecting rounds (taking directions into account) containing each edge of the graph exactly once are there? [img]https://cdn.artofproblemsolving.com/attachments/1/f/27ca05fc689fd8d873130db9d8cc52acf49bb4.png[/img]

Let $S$ be a set of $n$ points in the plane such that for any two points $(a, b), (c, d) \in S$, we have that $| a - c | \cdot | b - d | \ge 1$. Show that [list] [*] (a) If $S = \{ Q_1, Q_2, Q_3\}$ such that for any point $Q_i$ in $S$, this point doesn't lie in the axis-aligned rectangle with corners as the other two points, show that the area of $\triangle Q_1Q_2Q_3$ is at least $\frac{\sqrt{5}}{2}$. [*] (b) If all points in $S$ lie in an axis-aligned square with sidelength $a$, then $|S| \le \frac{a^2}{\sqrt{5}} + 2a + 1$. [/list]

We have $n$ guinea pigs placed on the vertices of a regular polygon with $n$ sides inscribed in a circumference, one guinea pig in each vertex. Each guinea pig has a direction assigned, such direction is either "clockwise" or "anti-clockwise", and a velocity between $1 km/h$, $2km/h$,..., and $n km/h$, each one with a distinct velocity, and each guinea pig has a counter starting from $0$. They start moving along the circumference with the assigned direction and velocity, everyone at the same time, when 2 or more guinea pigs meet a point, all of the guinea pigs at that point follow the same direction of the fastest guinea pig and they keep moving (with the same velocity as before); each time 2 guinea pigs meet for the first time in the same point, the fastest guinea pig adds 1 to its counter. Prove that, at some moment, for each $1\leq i\leq n$ we have that the $i-$th guinea pig has $i-1$ in its counter.

Consider $4n$ points in the plane, with no three points collinear. Using these points as vertices, we form $\binom{4n}{3}$ triangles. Show that there exists a point $X$ of the plane that belongs to the interior of at least $2n^3$ of these triangles.

The points of the plane have been colored by $2013$ different colors. We say that a triangle $\vartriangle ABC$ has the color $X$ if its three vertices $A,B,C$ has the color $X$. Prove that there are innitely many triangles with the same color and the same area.

Determine all integers $m$ for which the $m \times m$ square can be dissected into five rectangles, the side lengths of which are the integers $1,2,3,\ldots,10$ in some order.

We call a set of cells on a checkered plane [i]rook-connected[/i] if from any of its cells one can get to any other by moving along the cells of this set by moving the rook (the rook is allowed to fly through fields that do not belong to our set). Prove that a [i]rook-connected[/i] set of $100$ cells can be divided into pairs of cells, lying in one row or in one column.

A square is divided into $25$ small squares, equal to each other, drawing lines parallel to the sides of the square. Some are drawn diagonals of small squares so that there are no two diagonals with a common point. What is the maximum number of diagonals that can be traced?