There are 1000 towns $A_{1},A_{2},\ldots ,A_{1000}$ with airports in a country and some of them are connected via flights. It's known that the $i$-th town is connected with $d_{i}$ other towns where $d_{1}\leq d_{2}\leq \ldots \leq d_{1000}$ and $d_{j}\geq j+1$ for every $j=1,2,\ldots 999-d_{999}$. Prove that if the airport of any town $A_{k}$ is closed, then we'd still be able to get from any town $A_{i}$ to any $A_{j}$ for $i,j\neq k$ (possibly by more than one flight).

Patrick tosses four four-sided dice, each numbered $1$ through $4$. What's the probability their product is a multiple of four?

A figure with area $1$ is cut out of paper. We divide this figure into $10$ parts and color them in $10$ different colors. Now, we turn around the piece of paper, divide the same figure on the other side of the paper in $10$ parts again (in some different way). Show that we can color these new parts in the same $10$ colors again (hereby, different parts should have different colors) such that the sum of the areas of all parts of the figure colored with the same color on both sides is $\geq \frac{1}{10}.$

Players $A$ and $B$ play a "paintful" game on the real line. Player $A$ has a pot of paint with four units of black ink. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length $p$. In every round, player $A$ picks some positive integer $m$ and provides $1/2^m $ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k/2^m$ to $(k+1)/2^m$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where the pot is empty and the interval $[0,1]$ is not completely blackened. Decide whether there exists a strategy for player $A$ to win in a finite number of moves.

Consider $4n$ points in the plane such that no three of them are collinear ($n\geq 1$). Show that the set of centroids of all the triangles formed by any three of these points contains at least $4n$ elements. [i]Radu Bumbăcea[/i]

Given right hexagon $H$ with side length $1$. On the sides of $H$ points $A_1$,$A_2$,$\ldots$,$A_k$ such that at least one of them is the midpoint of some side and for every $1 \leq i \leq k$ lines $A_{i-1}A_i$ and $A_iA_{i+1}$ form equal angles with the side, that contains the point $A_i$ (let $A_0=A_k$ and $A_{k+1}=A_1$. It is known that the length of broken line $A_1A_2\ldots A_kA_1$ is a positive integer Prove that $n$ is divisible by $3$ [i]M. Zorka[/i]

Republic has $n \geq 2$ cities, between some pairs of cities there are non-directed flight routes. From each city it is possible to get to any other city, and we will call the minimal number of flights required to do that the [i]distance[/i] between the cities. For every city consider the biggest distance to another city. It turned out that for every city this number is equal to $m$. Find all values $m$ can attain for given $n$

A checkered square $8 \times 8$ is divided into rectangles with two cells. Two rectangles are called adjacent if they share a segment of length 1 or 2. In each rectangle the amount of adjacent with it rectangles is written. Find the maximal possible value of the sum of all numbers in rectangles. [i]A. Voidelevich[/i]

Prove that :$$\sum_{k=0}^{58}C_{2017+k}^{58-k}C_{2075-k}^{k}=\sum_{p=0}^{29}C_{4091-2p}^{58-2p}$$

Let $ n$ be a nonzero positive integer. A set of persons is called a $ n$-balanced set if in any subset of $ 3$ persons there exists at least two which know each other and in each subset of $ n$ persons there are two which don't know each other. Prove that a $ n$-balanced set has at most $ (n \minus{} 1)(n \plus{} 2)/2$ persons.

$N$ children no two of the same height stand in a line. The following two-step procedure is applied: first, the line is split into the least possible number of groups so that in each group all children are arranged from the left to the right in ascending order of their heights (a group may consist of a single child). Second, the order of children in each group is reversed, so now in each group the children stand in descending order of their heights. Prove that in result of applying this procedure $N - 1$ times the children in the line would stand from the left to the right in descending order of their heights. [i](12 points)[/i]

Two infinite rows of evenly-spaced dots are aligned as in the figure below. Arrows point from every dot in the top row to some dot in the lower row in such a way that: [list][*]No two arrows point at the same dot. [*]Now arrow can extend right or left by more than 1006 positions.[/list] [img]https://cdn.artofproblemsolving.com/attachments/7/6/47abf37771176fce21bce057edf0429d0181fb.png[/img] Show that at most 2012 dots in the lower row could have no arrow pointing to them.

The King called two wizards. He ordered First Wizard to write down $100$ positive integers (not necessarily distinct) on cards without revealing them to Second Wizard. Second Wizard must correctly determine all these integers, otherwise both wizards will lose their heads. First Wizard is allowed to provide Second Wizard with a list of distinct integers, each of which is either one of the integers on the cards or a sum of some of these integers. He is not allowed to tell which integers are on the cards and which integers are their sums. If Second Wizard correctly determines all $100$ integers the King tears as many hairs from each wizard's beard as the number of integers in the list given to Second Wizard. What is the minimal number of hairs each wizard should sacrice to stay alive?

A $9\times 7$ rectangle is tiled with tiles of the two types: L-shaped tiles composed by three unit squares (can be rotated repeatedly with $90^\circ$) and square tiles composed by four unit squares. Let $n\ge 0$ be the number of the $2 \times 2 $ tiles which can be used in such a tiling. Find all the values of $n$.

In a country, there are $2018$ cities, some of which are connected by roads. Each city is connected to at least three other cities. It is possible to travel from any city to any other city using one or more roads. For each pair of cities, consider the shortest route between these two cities. What is the greatest number of roads that can be on such a shortest route?

Players $A$ and $B$ play a "paintful" game on the real line. Player $A$ has a pot of paint with four units of black ink. A quantity $p$ of this ink suffices to blacken a (closed) real interval of length $p$. In every round, player $A$ picks some positive integer $m$ and provides $1/2^m $ units of ink from the pot. Player $B$ then picks an integer $k$ and blackens the interval from $k/2^m$ to $(k+1)/2^m$ (some parts of this interval may have been blackened before). The goal of player $A$ is to reach a situation where the pot is empty and the interval $[0,1]$ is not completely blackened. Decide whether there exists a strategy for player $A$ to win in a finite number of moves.

Two players $A$ and $B$ play the following game taking alternate moves. In each move, a player writes one digit on the blackboard. Each new digit is written either to the right or left of the sequence of digits already written on the blackboard. Suppose that $A$ begins the game and initially the blackboard was empty. $B$ wins the game if ,after some move of $B$, the sequence of digits written in the blackboard represents a perfect square. Prove that $A$ can prevent $B$ from winning.

Let $n \ge 3$ be an integer, and consider a $n \times n$-board, divided into $n^2$ unit squares. For all $m \ge 1$, arbitrarily many $1\times m$-rectangles (type I) and arbitrarily many $m\times 1$-rectangles (type II) are available. We cover the board with $N$ such rectangles, without overlaps, and such that every rectangle lies entirely inside the board. We require that the number of type I rectangles used is equal to the number of type II rectangles used.(Note that a $1 \times 1$-rectangle has both types.) What is the minimal value of $N$ for which this is possible?

$(NET 4)$ A boy has a set of trains and pieces of railroad track. Each piece is a quarter of circle, and by concatenating these pieces, the boy obtained a closed railway. The railway does not intersect itself. In passing through this railway, the train sometimes goes in the clockwise direction, and sometimes in the opposite direction. Prove that the train passes an even number of times through the pieces in the clockwise direction and an even number of times in the counterclockwise direction. Also, prove that the number of pieces is divisible by $4.$

Alice and Bob play the following game: They start with non-empty piles of coins. Taking turns, with Alice playing first, each player choose a pile with an even number of coins and moves half of the coins of this pile to the other pile. The game ends if a player cannot move, in which case the other player wins. Determine all pairs $(a,b)$ of positive integers such that if initially the two piles have $a$ and $b$ coins respectively, then Bob has a winning strategy. Proposed by Dimitris Christophides, Cyprus

Consider a $1$-indexed array that initially contains the integers $1$ to $10$ in increasing order. The following action is performed repeatedly (any number of times): [code] def action(): Choose an integer n between 1 and 10 inclusive Reverse the array between indices 1 and n inclusive Reverse the array between indices n+1 and 10 inclusive (If n = 10, we do nothing) [/code] How many possible orders can the array have after we are done with this process?

There are $21$ towns. Each airline runs direct flights between every pair of towns in a group of five. What is the minimum number of airlines needed to ensure that at least one airline runs direct flights between every pair of towns?

The vertices of a regular $45$-gon are painted into three colors so that the number of vertices of each color is the same. Prove that three vertices of each color can be selected so that three triangles formed by the chosen vertices of the same color are all equal.

A rectangle $\mathcal{R}$ with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of $\mathcal{R}$ are either all odd or all even. [i]Proposed by Jeck Lim, Singapore[/i]

A [i]diameter[/i] of a finite planar set is any line segment of maximal Euclidean length having both end points in that set. A [i]lattice point[/i] in the Cartesian plane is one whose coordinates are both integral. Given an integer $n\geq 2$, prove that a set of $n$ lattice points in the plane has at most $n-1$ diameters.