Prove that for each vertex of a polyhedron it is possible to attach a natural number so that for each pair of vertices with a common edge, the attached numbers are not relatively prime (i.e. they have common divisors), and with each pair of vertices without a common edge the attached numbers are relatively prime. (Note: there are infinitely many prime numbers.)

We have a white table with $2$ rows and $5$ columns , and would like to colour all cells of the table according to the following rules: $\bullet$ We must colour the cell in the bottom left corner first. $\bullet$ After that, we can only colour a cell if some adjacent cell has already been coloured. (Two cells are adjacent if they share an edge.) How many different orders are there for colouring all $10$ squares (following these rules)?

Consider some graph $G$ with $2019$ nodes. Let's define [i]inverting[/i] a vertex $v$ the following process: for every other vertex $u$, if there was an edge between $v$ and $u$, it is deleted, and if there wasn't, it is added. We want to minimize the number of edges in the graph by several [i]invertings[/i] (we are allowed to invert the same vertex several times). Find the smallest number $M$ such that we can always make the number of edges in the graph not larger than $M$, for any initial choice of $G$. [i]Proposed by Arsenii Nikolaev, Anton Trygub (Ukraine)[/i]

Several identical square sheets of paper are laid out on a rectangular table so that their sides are parallel to the edges of the table (sheets may overlap). Prove that you can stick a few pins in such a way that each sheet will be attached to the table exactly by one pin.

The board has a natural number greater than $1$. At each step, Igor writes the number $n +\frac{n}{p}$ instead of the number $n$ on the board , where $p$ is some prime divisor of $n$. Prove that if Igor continues to rewrite the number infinite times, then he will choose infinitely times the number $3$ as a prime divisor of $p$. [hide=original wording]На доске записано какое-то натуральное число, большее 1. На каждом шагу Игорь переписывает имеющееся на доске число n на число n +n/p, где p - это какой-нибудь простой делитель числа n. Доказать, что если Игорь будет продолжать переписывать число бесконечно долго, то он бесконечно много раз выберет в качестве простого делителя p число 3.[/hide]

A frog started from the origin of the coordinate plane and made $3$ jumps. Each time, the frog jumped a distance of $5$ units and landed on a point with integer coordinates. How many different position possibilities end of the frog there?

p1. Circle $M$ is the incircle of ABC, while circle $N$ is the incircle of $ACD$. Circles $M$ and $N$ are tangent at point $E$. If side length $AD = x$ cm, $AB = y$ cm, $BC = z$ cm, find the length of side $DC$ (in terms of $x, y$, and $z$). [img]https://cdn.artofproblemsolving.com/attachments/d/5/66ddc8a27e20e5a3b27ab24ff1eba3abee49a6.png[/img] p2. The address of the house on Jalan Bahagia will be numbered with the following rules: $\bullet$ One side of the road is numbered with consecutive even numbers starting from number $2$. $\bullet$ The opposite side is numbered with an odd number starting from number $3$. $\bullet$ In a row of even numbered houses, there is some land vacant house that has not been built. $\bullet$ The first house numbered $2$ has a neighbor next door. When the RT management ordered the numbers of the house, it is known that the cost of making each digit is $12.000$ Rp. For that, the total cost to be incurred is $1.020.000$ Rp. It is also known that the cost of all even-sided house numbers is $132.000$ Rp. cheaper than the odd side. When the land is empty later a house has been built, the number of houses on the even and odd sides is the same. Determine the number of houses that are now on Jalan Bahagia . p3. Given the following problem: Each element in the set $A = \{10, 11, 12,...,2008\}$ multiplied by each element in the set $B = \{21, 22, 23,...,99\}$. The results are then added together to give value of $X$. Determine the value of $X$. Someone answers the question by multiplying $2016991$ with $4740$. How can you explain that how does that person make sense? p4. Let $P$ be the set of all positive integers between $0$ and $2008$ which can be expressed as the sum of two or more consecutive positive integers . (For example: $11 = 5 + 6$, $90 = 29 + 30 + 31$, $100 = 18 + 19 +20 + 21 + 22$. So $11, 90, 100$ are some members of $P$.) Find the sum of of all members of $P$. p5. A four-digit number will be formed from the numbers at $0, 1, 2, 3, 4, 5$ provided that the numbers in the number are not repeated, and the number formed is a multiple of $3$. What is the probability that the number formed has a value less than $3000$?

Let $G$ be a graph on $n\geq 6$ vertices and every vertex is of degree at least 3. If $C_{1}, C_{2}, \dots, C_{k}$ are all the cycles in $G$, determine all possible values of $\gcd(|C_{1}|, |C_{2}|, \dots, |C_{k}|)$ where $|C|$ denotes the number of vertices in the cycle $C$.

Compute the number of nonempty subsets $S \subseteq\{-10,-9,-8, . . . , 8, 9, 10\}$ that satisfy $$|S| +\ min(S) \cdot \max (S) = 0.$$

For any integer $n\geq1$, we consider a set $P_{2n}$ of $2n$ points placed equidistantly on a circle. A [i]perfect matching[/i] on this point set is comprised of $n$ (straight-line) segments whose endpoints constitute $P_{2n}$. Let $\mathcal{M}_{n}$ denote the set of all non-crossing perfect matchings on $P_{2n}$. A perfect matching $M\in \mathcal{M}_{n}$ is said to be [i]centrally symmetric[/i], if it is invariant under point reflection at the circle center. Determine, as a function of $n$, the number of centrally symmetric perfect matchings within $\mathcal{M}_{n}$. [i]Proposed by Mirko Petrusevski[/i]

Place 2005 points on the circumference of a circle. Two points $P,Q$ are said to form a pair of neighbours if the chord $PQ$ subtends an angle of at most 10 degrees at the centre. Find the smallest number of pairs of neighbours.

Given $12$ segments, it is known that they can be divided into $4$ groups of $3$ segments each in such a way that a triangle can be formed from the segments of each triplet. Is it always possible to divide these $12$ segments into $3$ groups of $4$ segments each in such a way that a quadrilateral can be formed from the segments of each quartet? [i]Proposed by Mykhailo Shtandenko[/i]

For a permutation $\pi$ of $\{1,2,3,\ldots,n\}$, let $\text{Inv}(\pi)$ be the number of pairs $(i,j)$ with $1 \leq i < j \leq n$ and $\pi(i) > \pi(j)$. [list=1] [*] Given $n$, what is $\sum \text{Inv}(\pi)$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$? [*] Given $n$, what is $\sum \left(\text{Inv}(\pi)\right)^2$ where the sum ranges over all permutations $\pi$ of $\{1,2,3,\ldots,n\}$?[/list] [i]Brian Hamrick.[/i]

[b]p1.[/b] Arrange the whole numbers $1$ through $15$ in a row so that the sum of any two adjacent numbers is a perfect square. In how many ways this can be done? [b]p2.[/b] Prove that if $p$ and $q$ are prime numbers which are greater than $3$ then $p^2 - q^2$ is divisible by $24$. [b]p3.[/b] If a polyleg has even number of legs he always tells truth. If he has an odd number of legs he always lies. Once a green polyleg told a dark-blue polyleg ”- I have $8$ legs. And you have only $6$ legs!” The offended dark-blue polyleg replied ”-It is me who has $8$ legs, and you have only $7$ legs!” A violet polyleg added ”-The dark-blue polyleg indeed has $8$ legs. But I have $9$ legs!” Then a stripped polyleg started ”None of you has $8$ legs. Only I have $8$ legs!” Which polyleg has exactly $8$ legs? [b][b]p4.[/b][/b] There is a small puncture (a point) in the wall (as shown in the figure below to the right). The housekeeper has a small flag of the following form (see the figure left). Show on the figure all the points of the wall where you can hammer in a nail such that if you hang the flag it will close up the puncture. [img]https://cdn.artofproblemsolving.com/attachments/a/f/8bb55a3fdfb0aff8e62bc4cf20a2d3436f5d90.png[/img] [b]p5.[/b] Assume $ a, b, c$ are odd integers. Show that the quadratic equation $ax^2 + bx + c = 0$ has no rational solutions. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n\geq1$ be an integer and let $t_1<t_2<\dots<t_n$ be positive integers. In a group of $t_n+1$ people, some games of chess are played. Two people can play each other at most once. Prove that it is possible for the following two conditions to hold at the same time: (i) The number of games played by each person is one of $t_1,t_2,\dots,t_n$. (ii) For every $i$ with $1\leq i\leq n$, there is someone who has played exactly $t_i$ games of chess.

We consider dissections of regular $n$-gons into $n - 2$ triangles by $n - 3$ diagonals which do not intersect inside the $n$-gon. A [i]bicoloured triangulation[/i] is such a dissection of an $n$-gon in which each triangle is coloured black or white and any two triangles which share an edge have different colours. We call a positive integer $n \ge 4$ [i]triangulable[/i] if every regular $n$-gon has a bicoloured triangulation such that for each vertex $A$ of the $n$-gon the number of black triangles of which $A$ is a vertex is greater than the number of white triangles of which $A$ is a vertex. Find all triangulable numbers.

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

Let $S$ denote $\{1, \dots , 100\}$, and let $f$ be a permutation of $S$ such that for all $x\in S$, $f(x)\ne x$. Over all such $f$, find the maximum number of elements $j$ that satisfy $\underbrace{f(\dots(f(j))\dots)}_{\text{j times}}=j$. [i]Proposed by Hari Desikan[/i]

For each positive integer $n$, let $f(n)$ denote the smallest possible value of $$|A_1 \cup A_2 \cup \dots \cup A_n|$$ where $A_1, A_2, A_3 \dots A_n$ are sets such that $A_i \not\subseteq A_j$ and $|A_i| \neq |A_j|$ whenever $i \neq j$. Determine $f(n)$ for each positive integer $n$.

Let $a$ and $b$ be distinct positive integers. The following infinite process takes place on an initially empty board. [list=i] [*] If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by $a$ and the other by $b$. [*] If no such pair exists, we write two times the number $0$. [/list] Prove that, no matter how we make the choices in $(i)$, operation $(ii)$ will be performed only finitely many times. Proposed by [I]Serbia[/I].

In a rectangle with sides of length 20 and 25 there are 120 squares of side length 1. Prove that there is a circle with a diameter of 1 contained in this rectangle and having no points in common with any of these squares.

Let $S$ be the set of [b]lattice[/b] points whose both coordinates are positive integers no larger than $2022$. i.e., $S=\{(x, y) \mid x, y\in \mathbb{N}, \, 1\leq x, y\leq 2022\}$. We put a card with one gold side and one black side on each point in $S$. We call a rectangle [i]"good"[/i] if: (i) All of its sides are parallel to the axes and have positive integer coordinates no larger than $2022$. (ii) The cards on its top-left and bottom-right corners are showing gold, and the cards on its top-right and bottom-left corners are showing black. Each [i]"move"[/i] consists of choosing a good rectangle and flipping all cards simultaneously on its four corners. Find the maximum possible number of moves one can perform, or show that one can perform infinitely many moves. [i]Proposed by CSJL[/i]

We say that $ n$ squares in a $ n\times n$ board are scattered if no two of them are in the same row or column.In every square of this board is witten a natural number so that the sum of numbrs in $ n$ scattered squares is always the same and no row or no column contains two equal numbers .It turned out that the numbers on the main diagonal are arranged in the increasing order ,and that their product is the smallest among all products of $ n$ scattered numbers .Prove that scattered numbers with the greatest product are exactly those on the other diagonal.

There is a $8\times 8$ table, drawn in a plane and painted in a chess board fashion. Peter mentally chooses a square and an interior point in it. Basil can draws any polygon (without self-intersections) in the plane and ask Peter whether the chosen point is inside or outside this polygon. What is the minimal number of questions suffcient to determine whether the chosen point is black or white?

The chromatic number $\chi$ of an (infinite) plane is the smallest number of colors with which we can color the points on the plane in such a way that no two points of the same color are one unit apart. Prove that $4 \leq \chi \leq 7$.