Let $ G$ be a simple graph with $ 2 \cdot n$ vertices and $ n^{2}+1$ edges. Show that this graph $ G$ contains a $ K_{4}-\text{one edge}$, that is, two triangles with a common edge.

The set $G$ is defined by the points $(x,y)$ with integer coordinates, $1 \le x \le 5$ and $1 \le y \le 5$. Determine the number of five-point sequences $(P_1, P_2, P_3, P_4, P_5)$ such that for $1 \le i \le 5$, $P_i = (x_i,i)$ is in $G$ and $|x_1 - x_2| = |x_2 - x_3| = |x_3 - x_4|=|x_4 - x_5| = 1$.

Given four colours and enough square plates $1\times 1$. We have to paint four edges of every plate with four different colours and combine plates, putting them with the edges of the same colour together. Describe all the pairs $m,n$, such that we can combine those plates in a $n\times m$ rectangle, that has every edge of one colour, and its four edges have different colours.

Let $A$ and $B$ be sets of positive integers with $|A|\ge 2$ and $|B|\ge 2$. Let $S$ be a set consisting of $|A|+|B|-1$ numbers of the form $ab$ where $a\in A$ and $b\in B$. Prove that there exist pairwise distinct $x,y,z\in S$ such that $x$ is a divisor of $yz$.

Let $n$ be an even integer greater than $2$. On the vertices of a regular polygon with n sides we can place red or blue chips. Two players, $A$ and $B$, play alternating turns of the next mode: each player, on their turn, chooses two vertices that have no tiles and places on one of them a red chip and in the other a blue chip. The goal of $A$ is to get three vertices consecutive with tiles of the same color. $B$'s goal is to prevent this from happening. To the beginning of the game there are no tiles in any of the vertices. Show that regardless of who starts to play, Player $B$ can always achieve his goal.

[b]p1.[/b] $17$ rooks are placed on an $8\times 8$ chess board. Prove that there must be at least one rook that is attacking at least $2$ other rooks. [b]p2.[/b] In New Scotland there are three kinds of coins: $1$ cent, $6$ cent, and $36$ cent coins. Josh has $99$ of the $36$-cent coins (and no other coins). He is allowed to exchange a $36$ cent coin for $6$ coins of $6$ cents, and to exchange a $6$ cent coin for $6$ coins of $1$ cent. Is it possible that after several exchanges Josh will have $500$ coins? [b]p3.[/b] Find all solutions $a, b, c, d, e, f, g, h, i$ if these letters represent distinct digits and the following multiplication is correct: $\begin{tabular}{ccccc} & & a & b & c \\ x & & & d & e \\ \hline & f & a & c & c \\ + & g & h & i & \\ \hline f & f & f & c & c \\ \end{tabular}$ [b]p4.[/b] Pinocchio rode a bicycle for $3.5$ hours. During every $1$-hour period he went exactly $5$ km. Is it true that his average speed for the trip was $5$ km/h? Explain your reasoning. [b]p5.[/b] Let $a, b, c$ be odd integers. Prove that the equation $ax^2 + bx + c = 0$ cannot have a rational solution. PS. You should use hide for answers. Collected [url=https://artofproblemsolving.com/community/c5h2760506p24143309]here[/url].

Let $n$ numbers all equal to $1$ be written on a blackboard. A move consists of replacing two numbers on the board with two copies of their sum. It happens that after $h$ moves all $n$ numbers on the blackboard are equal to $m.$ Prove that $h \leq \frac{1}{2}n \log_2 m.$

Let $k$ be a positive integer and $n_1, n_2, ..., n_k$ be non-negative integers. Points $P_1, P_2, ..., P_k$ lie on a circle in such a way that at point $P_i$ there are $n_i$ stones. Leandro wishes to change the position of some of these stones in order to accomplish his objective which is to have the same number of stones at each point of the circle. He does this by repeating as many times as necessary the following operation: if there exists a point on the circle with at least $k - 1$ stones, he can choose $k -1$ of these and distribute them by giving one to each of the remaining $k - 1$ points. For which values $n_1, n_2, ..., n_k$ can Leandro accomplish his objective? In the figure below there is a configuration of stones for $k = 4$. On the right is the initial division of stones, while on the left there is the configuration obtained from the initial one by choosing $k - 1 = 3$ stones from the top point on the circle and distributing one each to the other points. [figures missing]

Find all the positive integers $n$ for which there exists a Family $\mathcal{F}$ of three-element subsets of $S=\{1,2,...,n\}$ satisfying \[\text{(i) for any two different elements $a,b \in S$ there exists exactly one $A \in \mathcal{F}$ containing both $a$ and $b$;}\] \[\text{(ii) if $a,b,c,x,y,z$ are elements of $S$ such that $\{a,b,x\},\{a,c,y\},\{b,c,z\} \in \mathcal{F}$, then $\{x,y,z\} \in \mathcal{F} $ }.\]

Determine for which natural numbers $n$ it is possible to completely cover a board of $ n \times n$, divided into $1 \times 1$ squares, with pieces like the one in the figure, without gaps or overlays and without leaving the board. Each of the pieces covers exactly six boxes. Note: Parts can be rotated. [img]https://cdn.artofproblemsolving.com/attachments/c/2/d87d234b7f9799da873bebec845c721e4567f9.png[/img]

On a circle there are $2n+1$ points, dividing it into equal arcs ($n\ge 2$). Two players take turns to erase one point. If after one player's turn, it turned out that all the triangles formed by the remaining points on the circle were obtuse, then the player wins and the game ends. Who has a winning strategy: the starting player or his opponent?

Laura has $2010$ lamps connected with $2010$ buttons in front of her. For each button, she wants to know the corresponding lamp. In order to do this, she observes which lamps are lit when Richard presses a selection of buttons. (Not pressing anything is also a possible selection.) Richard always presses the buttons simultaneously, so the lamps are lit simultaneously, too. a) If Richard chooses the buttons to be pressed, what is the maximum number of different combinations of buttons he can press until Laura can assign the buttons to the lamps correctly? b) Supposing that Laura will choose the combinations of buttons to be pressed, what is the minimum number of attempts she has to do until she is able to associate the buttons with the lamps in a correct way?

There are 4 coins, 3 of which are real, which weigh the same, and one is fake, which differs in weight from the rest. Cup scales without weights are such that if equal weights are placed on their cups, then any of the cups can outweigh, but if the loads are different in mass, then the cup with a heavier load is sure to pull. How to definitely identify a counterfeit coin in three weighings and easily establish what is it or is it heavier than the others?

A convex $1993$-gon is divided into convex $7$-gons. Prove that there are $3$ neighbouring sides of the $1993$-gon belonging to one such $7$-gon. (A vertex of a $7$-gon may not be positioned on the interior of a side of the $1993$-gon, and two $7$-gons either have no common points, exactly one common vertex or a complete common side.) (A Kanel-Belov)

Points with integer coordinates in cartesian space are called lattice points. We color $2000$ lattice points blue and $2000$ other lattice points red in such a way that no two blue-red segments have a common interior point (a segment is blue-red if its two endpoints are colored blue and red). Consider the smallest rectangular parallelepiped that covers all the colored points. (a) Prove that this rectangular parallelepiped covers at least $500,000$ lattice points. (b) Give an example of a coloring for which the considered rectangular paralellepiped covers at most $8,000,000$ lattice points.

Let $n$ be an integer greater than $1$, and let $p$ be a prime divisor of $n$. A confederation consists of $p$ states, each of which has exactly $n$ airports. There are $p$ air companies operating interstate flights only such that every two airports in different states are joined by a direct (two-way) flight operated by one of these companies. Determine the maximal integer $N$ satisfying the following condition: In every such confederation it is possible to choose one of the $p$ air companies and $N$ of the $np$ airports such that one may travel (not necessarily directly) from any one of the $N$ chosen airports to any other such only by flights operated by the chosen air company.

The vertices of a regular $n + 1$-gon are denoted by $P_0,P_1,...,P_n$ in some order ($n \ge 2$). Each side of the polygon is assigned a natural number as follows: if the endpoints of the side are $P_i$ and $P_j$, then the assigned number equals $|i - j |$. Let S be the sum of all $n + 1$ assigned numbers. (a) Given $n$, what is the smallest possible value of $S$? (b) If $P_0$ is fixed, how many different assignments are there for which $S$ attains the smallest value?

Let $ m\geq n\geq 4$ be two integers. We call a $ m\times n$ board filled with 0's or 1's [i]good[/i] if 1) not all the numbers on the board are 0 or 1; 2) the sum of all the numbers in $ 3\times 3$ sub-boards is the same; 3) the sum of all the numbers in $ 4\times 4$ sub-boards is the same. Find all $ m,n$ such that there exists a good $ m\times n$ board.

A cube of edge length $3$ consists of $27$ unit cubes. Find the number of lines passing through exactly three centers of these $27$ cubes, as well as the number of those passing through exactly two such centers.

The cells of a square $2011 \times 2011$ array are labelled with the integers $1,2,\ldots, 2011^2$, in such a way that every label is used exactly once. We then identify the left-hand and right-hand edges, and then the top and bottom, in the normal way to form a torus (the surface of a doughnut). Determine the largest positive integer $M$ such that, no matter which labelling we choose, there exist two neighbouring cells with the difference of their labels at least $M$. (Cells with coordinates $(x,y)$ and $(x',y')$ are considered to be neighbours if $x=x'$ and $y-y'\equiv\pm1\pmod{2011}$, or if $y=y'$ and $x-x'\equiv\pm1\pmod{2011}$.) [i](Romania) Dan Schwarz[/i]

For a finite simple graph $G$, we define $G'$ to be the graph on the same vertex set as $G$, where for any two vertices $u \neq v$, the pair $\{u,v\}$ is an edge of $G'$ if and only if $u$ and $v$ have a common neighbor in $G$. Prove that if $G$ is a finite simple graph which is isomorphic to $(G')'$, then $G$ is also isomorphic to $G'$. [i]Mehtaab Sawhney and Zack Chroman[/i]

consider $n\geq 6$ points $x_1,x_2,\dots,x_n$ on the plane such that no three of them are colinear. We call graph with vertices $x_1,x_2,\dots,x_n$ a "road network" if it is connected, each edge is a line segment, and no two edges intersect each other at points other than the vertices. Prove that there are three road networks $G_1,G_2,G_3$ such that $G_i$ and $G_j$ don't have a common edge for $1\leq i,j\leq 3$. Proposed by Morteza Saghafian

The points of a circle are colored in green and yellow, such that every equilateral triangle inscribed in the circle has exactly 2 vertices colored in yellow. Prove that there exist a square inscribed in the circle which has at least 3 vertices colored in yellow.

Let $n$ be a positive integer. Each of the numbers $1,2,3,\ldots,100$ is painted with one of $n$ colors in such a way that two distinct numbers with a sum divisible by $4$ are painted with different colors. Determine the smallest value of $n$ for which such a situation is possible.

The vertices of the regular $n$-gon are marked. Two players play the following game: they, in turn, select a vertex and connect it by a segment to either the adjacent vertex or the center of the $n$-gon. The winner is a player if after his move it is possible to get any vertex from any other vertex moving along segments. For each integer $n\geqslant 3$ determine who has a winning strategy.