Let a complete oriented graph on $n$ points be given. Show that the vertices can be enumerated as $v_1 , v_2 ,\ldots, v_n$ such that $v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n.$

In the figure we see the paths connecting the square of a city (point $P$) with the school (point $S$). In the square there are $k$ pupils starting to go to the school. They have the ability to move only to the right and up. If the pupils are free to choose any allowed path (in order to get to school), determine the minimum value of $k$ so that in any case at least two pupils follow the same path. [img]https://cdn.artofproblemsolving.com/attachments/e/2/b5d6c6db5942cb706428cb63af3ca15590727f.png[/img]

A directed graph (any two distinct vertices joined by at most one directed line) has the following property: If $x, u,$ and $v$ are three distinct vertices such that $x \to u$ and $x \to v$, then $u \to w$ and $v \to w$ for some vertex $w$. Suppose that $x \to u \to y \to\cdots \to z$ is a path of length $n$, that cannot be extended to the right (no arrow goes away from $z$). Prove that every path beginning at $x$ arrives after $n$ steps at $z.$

A straight one-mile stretch of highway, $40$ feet wide, is closed. Robert rides his bike on a path composed of semicircles as shown. If he rides at $5$ miles per hour, how many hours will it take to cover the one-mile stretch? Note: $1$ mile= $5280$ feet [asy]size(10cm); pathpen=black; pointpen=black; D(arc((-2,0),1,300,360)); D(arc((0,0),1,0,180)); D(arc((2,0),1,180,360)); D(arc((4,0),1,0,180)); D(arc((6,0),1,180,240)); D((-1.5,1)--(5.5,1)); D((-1.5,0)--(5.5,0),dashed); D((-1.5,-1)--(5.5,-1)); [/asy] $\textbf{(A) }\frac{\pi}{11}\qquad\textbf{(B) }\frac{\pi}{10}\qquad\textbf{(C) }\frac{\pi}{5}\qquad\textbf{(D) }\frac{2\pi}{5}\qquad \textbf{(E) }\frac{2\pi}{3}$

There are four houses, located on the vertices of a square. You want to draw a road network, so that you can go from any house to any other. Prove that the network formed by the diagonals is not the shortest. Find a shorter network.

For positive integers $m,n \geq 2$, let $S_{m,n} = \{(i,j): i \in \{1,2,\ldots,m\}, j\in \{1,2,\ldots,n\}\}$ be a grid of $mn$ lattice points on the coordinate plane. Determine all pairs $(m,n)$ for which there exists a simple polygon $P$ with vertices in $S_{m,n}$ such that all points in $S_{m,n}$ are on the boundary of $P$, all interior angles of $P$ are either $90^{\circ}$ or $270^{\circ}$ and all side lengths of $P$ are $1$ or $3$.

In a certain country there are $n$ cities. Some pairs of cities are connected by highways in such a way that for each two cities there is at most one highway connecting them. Assume that for a certain positive integer $k$, the total number of highways is greater than $\frac{nk}{2}$. Show that there exist $k+2$ distinct cities $C_1, C_2, \dots, C_{k+2}$ such that $C_i$ and $C_{i+1}$ are connected by a highway for $i=1, 2, \dots, k+1$. [i]Proposed by Oriol Solé[/i]

An ant is on the Cartesian plane. In a single move, the ant selects a positive integer $k$, then either travels [list] [*] $k$ units vertically (up or down) and $2k$ units horizontally (left or right); or [*] $k$ units horizontally (left or right) and $2k$ units vertically (up or down). [/list] Thus, for any $k$, the ant can choose to go to one of eight possible points. \\ Prove that, for any integers $a$ and $b$, the ant can travel from $(0, 0)$ to $(a, b)$ using at most $3$ moves.

How many paths are there from$ A$ to the line $BC$ if the path does not go through any vertex twice and always moves to the left? [img]https://cdn.artofproblemsolving.com/attachments/e/6/a4bc3a9decc06eaeed6f7e99cb58f7b2524471.jpg[/img]

An equilateral triangle of side $n$ has been divided into little equilateral triangles of side $1$ in the usual way. We draw a path over the segments of this triangulation, in such a way that it visits exactly once each one of the $\frac{(n+1)(n+2)}{2}$ vertices. What is the minimum number of times the path can change its direction? The figure below shows a valid path on a triangular board of side $4$, with exactly $9$ changes of direction. [asy] unitsize(30); pair h = (1, 0); pair v = dir(60); pair d = dir(120); for(int i = 0; i < 4; ++i) { draw(i*v -- i*v + (4 - i)*h); draw(i*h -- i*h + (4 - i)*v); draw((i + 1)*h -- (i + 1)*h + (i + 1)*d); } draw(h + v -- v -- (0, 0) -- 2*h -- 2*h + v -- h + 2*v -- 2*v -- 4*v -- 3*h + v -- 3*h -- 4*h, linewidth(2)); draw(3*h -- 4*h, EndArrow); fill(circle(h + v, 0.1)); [/asy] [i]Proposed by Oriol Solé[/i]

There are $k$ cities in Belarus and $k$ cities in Armenia, between some cities there are non-directed flights. From any Belarusian city there are exactly $n$ flights to Armenian cities, and for every pair of Armenian cities exactly two Belarusian cities have flights to both of the Armenian cities. a) Prove that from every Armenian city there are exactly $n$ flights to Belarusian cities. b) Prove that there exists a flight route in which every city is visited at most once and that consists of at least $\lfloor \frac{(n+1)^2}{4} \rfloor$ cities in each of the countries. [i]D. Gorovoy[/i]

Consider a checkered board $2m \times 2n$, $m, n \in \mathbb{Z}_{>0}$. A stone is placed on one of the unit squares on the board, this square is different from the upper right square and from the lower left square. A snail goes from the bottom left square and wants to get to the top right square, walking from one square to other adjacent, one square at a time (two squares are adjacent if they share an edge). Determine all the squares the stone can be in so that the snail can complete its path by visiting each square exactly one time, except the square with the stone, which the snail does not visit.

There are six ports on a lake. Is it possible to organize a series of routes satisfying the following conditions ? [i](i)[/i] Every route includes exactly three ports; [i](ii)[/i] No two routes contain the same three ports; [i](iii)[/i] The series offers exactly two routes to each tourist who desires to visit two different arbitrary ports.

Let $n$ be a posititve integer and let $M$ the set of all all integer cordinates $(a,b,c)$ such that $0 \le a,b,c \le n$. A frog needs to go from the point $(0,0,0)$ to the point $(n,n,n)$ with the following rules: $\cdot$ The frog can jump only in points of $M$ $\cdot$ The frog can't jump more than $1$ time over the same point. $\cdot$ In each jump the frog can go from $(x,y,z)$ to $(x+1,y,z)$, $(x,y+1,z)$, $(x,y,z+1)$ or $(x,y,z-1)$ In how many ways the Frog can make his target?

A rook stands in one cell of an infinite square grid. A different cell was colored blue and mines were placed in $n$ additional cells: the rook cannot stand on or pass through them. It is known that the rook can reach the blue cell in finitely many moves. Can it do so (for every $n$ and such a choice of mines, starting point, and blue cell) in at most [b](a)[/b] $1.99n+100$ moves? [b](b)[/b] $2n-2\sqrt{3n}+100$ moves? [b]Remark.[/b] In each move, the rook goes in a vertical or horizontal line.

A Magician and a Detective play a game. The Magician lays down cards numbered from $1$ to $52$ face-down on a table. On each move, the Detective can point to two cards and inquire if the numbers on them are consecutive. The Magician replies truthfully. After a finite number of moves, the Detective points to two cards. She wins if the numbers on these two cards are consecutive, and loses otherwise. Prove that the Detective can guarantee a win if and only if she is allowed to ask at least $50$ questions. [i]Proposed by Anant Mudgal[/i]

There are $N$ cities in a country, some of which are connected by two-way flights. No city is directly connected with every other city. For each pair $(A, B)$ of cities there is exactly one route using at most two flights between them. Prove that $N - 1$ is a square of an integer.

In the city of $\textrm{Las Cobayas}$, the houses are arranged in a rectangular grid of $3$ rows and $n\geq 2$ columns, as illustrated in the figure. $\textrm{Mich}$ plans to move there and wants to tour the city to visit some of the houses in a way that he visits at least one house from each column and does not visit the same house more than once. During his tour, $\textrm{Mich}$ can move between adjacent houses, that is, after visiting a house, he can continue his journey by visiting one of the neighboring houses to the north, south, east, or west, which are at most four. The figure illustrates one $\textrm{Mich´s}$ position (circle), and the houses to which he can move (triangles). Let $f(n)$ be the number of ways $\textrm{Mich}$ can complete his tour starting from a house in the first column and ending at a house in the last column. Prove that $f(n)$ is odd. [asy]size(200); draw((0,0)--(1,0)--(1,1)--(0,1)--cycle); draw((2,0)--(3,0)--(3,1)--(2,1)--cycle); draw((4,0)--(5,0)--(5,1)--(4,1)--cycle); draw((0,2)--(1,2)--(1,3)--(0,3)--cycle); draw((2,2)--(3,2)--(3,3)--(2,3)--cycle); draw((4,2)--(5,2)--(5,3)--(4,3)--cycle); draw((0,4)--(1,4)--(1,5)--(0,5)--cycle); draw((2,4)--(3,4)--(3,5)--(2,5)--cycle); draw((4,4)--(5,4)--(5,5)--(4,5)--cycle); fill(circle((0.5,2.5), 0.4), black); fill((0.1262,4.15)--(0.8738,4.15)--(0.5,4.7974)--cycle, black); fill((0.1262,0.15)--(0.8738,0.15)--(0.5,0.7974)--cycle, black); fill((2.1262,2.15)--(2.8738,2.15)--(2.5,2.7974)--cycle, black); fill(circle((6,0.5), 0.07), black); fill(circle((6.3,0.5), 0.07), black); fill(circle((6.6,0.5), 0.07), black); fill(circle((6,2.5), 0.07), black); fill(circle((6.3,2.5), 0.07), black); fill(circle((6.6,2.5), 0.07), black); fill(circle((6,4.5), 0.07), black); fill(circle((6.3,4.5), 0.07), black); fill(circle((6.6,4.5), 0.07), black); draw((8,0)--(9,0)--(9,1)--(8,1)--cycle); draw((10,0)--(11,0)--(11,1)--(10,1)--cycle); draw((8,2)--(9,2)--(9,3)--(8,3)--cycle); draw((10,2)--(11,2)--(11,3)--(10,3)--cycle); draw((8,4)--(9,4)--(9,5)--(8,5)--cycle); draw((10,4)--(11,4)--(11,5)--(10,5)--cycle); draw((0,-0.2)--(0,-0.5)--(5.5,-0.5)--(5.5,-0.8)--(5.5,-0.5)--(11,-0.5)--(11,-0.5)--(11,-0.2)); label("$n$", (5.22,-1.15), dir(0), fontsize(10)); label("$\textrm{West}$", (-2,2.5), dir(0), fontsize(10)); label("$\textrm{East}$", (11.1,2.5), dir(0), fontsize(10)); label("$\textrm{North}$", (4.5,5.7), dir(0), fontsize(10)); label("$\textrm{South}$", (4.5,-2), dir(0), fontsize(10)); draw((0.5,2.5)--(2,2.5)--(1.8,2.7)--(2,2.5)--(1.8,2.3)); draw((0.5,2.5)--(0.5,4)--(0.3,3.7)--(0.5,4)--(0.7,3.7)); draw((0.5,2.5)--(0.5,1)--(0.3,1.3)--(0.5,1)--(0.7,1.3)); [/asy]

Let $ABCDEFGH$ be a cube of sidelength $a$ and such that $AG$ is one of the space diagonals. Consider paths on the surface of this cube. Then determine the set of points $P$ on the surface for which the shortest path from $P$ to $A$ and from $P$ to $G$ have the same length $l.$ Also determine all possible values of $l$ depending on $a.$