Found problems: 429
100 people from 50 countries, two from each countries, stay on a circle. Prove that one may partition them onto 2 groups in such way that neither no two countrymen, nor three consecutive people on a circle, are in the same group.
Given $n$ points in the plane, show that the largest distance determined by these points cannot occur more than $n$ times.
If $x^5 - x ^3 + x = a,$ prove that $x^6 \geq 2a - 1$.
Let $r,g,b$ be non negative integers and $\Gamma$ be a connected graph with $r+g+b+1$ vertices. Its edges are colored in red green and blue. It turned out that $\Gamma $ contains
A spanning tree with exactly $r$ red edges.
A spanning tree with exactly $g$ green edges.
A spanning tree with exactly $b$ blue edges.
Prove that $\Gamma$ contains a spanning tree with exactly $r$ red edges, $g$ green edges and $b$ blue edges.
The country has $n \ge 3$ airports, some pairs of which are connected by bidirectional flights. Every day, the government closes the airport with the strictly highest number of flights going out of it. What is the maximum number of days this can continue?
[i]Proposed by Fedir Yudin[/i]
A directed graph has each vertex with outdegree 2. Prove that it is possible to split the vertices into 3 sets so that for each vertex $v$, $v$ is not simultaneously in the same set with both of the vertices that it points to.
[i]David Yang.[/i]
[hide="Stronger Version"]See [url=http://www.artofproblemsolving.com/Forum/viewtopic.php?f=42&t=492100]here[/url].[/hide]
Alice has a map of Wonderland, a country consisting of $n \geq 2$ towns. For every pair of towns, there is a narrow road going from one town to the other. One day, all the roads are declared to be “one way” only. Alice has no information on the direction of the roads, but the King of Hearts has offered to help her. She is allowed to ask him a number of questions. For each question in turn, Alice chooses a pair of towns and the King of Hearts tells her the direction of the road connecting those two towns.
Alice wants to know whether there is at least one town in Wonderland with at most one outgoing road. Prove that she can always find out by asking at most $4n$ questions.
Solve the equation $\frac{1}{\sin x}+\frac{1}{\cos x}=\frac 1p$ where $p$ is a real parameter.
Discuss for which values of $p$ the equation has at least one real solution and determine the number of solutions in $[0, 2\pi)$ for a given $p.$
There are $ n$ students; each student knows exactly $d $ girl students and $d $ boy students ("knowing" is a symmetric relation). Find all pairs $ (n,d) $ of integers .
Let $T$ be a triangulation of a $100$-gon.We construct $P(T)$ by copying the same $100$-gon and drawing a diagonal if it was not drawn in $T$ an there is a quadrilateral with this diagonal and two other vertices so that all the sides and diagonals(Except the one we are going to draw) are present in $T$.Let $f(T)$ be the number of intersections of diagonals in $P(T)$.Find the minimum and maximum of $f(T)$.
Ivan is playing Lego with $4n^2$ $1 \times 2$ blocks. First, he places $2n^2$ $1 \times 2$ blocks to fit a $2n \times 2n$ square as the bottom layer. Then he builds the top layer on top of the bottom layer using the remaining $2n^2$ $1 \times 2$ blocks. Note that the blocks in the bottom layer are connected to the blocks above it in the top layer, just like real Lego blocks. He wants the whole two-layered building to be connected and not in seperate pieces.
Prove that if he can do so, then the four $1\times 2$ blocks connecting the four corners of the bottom layer, must be all placed horizontally or all vertically.
[i]Proposed by Ivan Chan Kai Chin[/i]
Let $m$ and $n$ be fixed positive integers. Tsvety and Freyja play a game on an infinite grid of unit square cells. Tsvety has secretly written a real number inside of each cell so that the sum of the numbers within every rectangle of size either $m$ by $n$ or $n$ by $m$ is zero. Freyja wants to learn all of these numbers.
One by one, Freyja asks Tsvety about some cell in the grid, and Tsvety truthfully reveals what number is written in it. Freyja wins if, at any point, Freyja can simultaneously deduce the number written in every cell of the entire infinite grid (If this never occurs, Freyja has lost the game and Tsvety wins).
In terms of $m$ and $n$, find the smallest number of questions that Freyja must ask to win, or show that no finite number of questions suffice.
[i]Nikolai Beluhov[/i]
You are given $N$ such that $ n \ge 3$. We call a set of $N$ points on a plane acceptable if their abscissae are unique, and each of the points is coloured either red or blue. Let's say that a polynomial $P(x)$ divides a set of acceptable points either if there are no red dots above the graph of $P(x)$, and below, there are no blue dots, or if there are no blue dots above the graph of $P(x)$ and there are no red dots below. Keep in mind, dots of both colors can be present on the graph of $P(x)$ itself. For what least value of k is an arbitrary set of $N$ points divisible by a polynomial of degree $k$?
Let $n\geqslant 2$ be a positive integer. Paul has a $1\times n^2$ rectangular strip consisting of $n^2$ unit squares, where the $i^{\text{th}}$ square is labelled with $i$ for all $1\leqslant i\leqslant n^2$. He wishes to cut the strip into several pieces, where each piece consists of a number of consecutive unit squares, and then [i]translate[/i] (without rotating or flipping) the pieces to obtain an $n\times n$ square satisfying the following property: if the unit square in the $i^{\text{th}}$ row and $j^{\text{th}}$ column is labelled with $a_{ij}$, then $a_{ij}-(i+j-1)$ is divisible by $n$.
Determine the smallest number of pieces Paul needs to make in order to accomplish this.
Let $m,n,a_1,a_2,\dots,a_n$ be positive integers and $r$ be a real number. Prove that the equation
\[\lfloor a_1x\rfloor+\lfloor a_2x\rfloor+\cdots+\lfloor a_nx\rfloor=sx+r\]
has exactly $ms$ solutions in $x$, where $s=a_1+a_2+\cdots+a_n+\frac1m$.
[i]Linus Tang[/i]
In a school with $2022$ students, either a museum trip or a nature trip is organized every day during a holiday. No student participates in the same type of trip twice, and the number of students attending each trip is different. If there are no two students participating in the same two trips together, find the maximum number of trips held.
Let $n\geq 3$ be a fixed integer. Each side and each diagonal of a regular $n$-gon is labelled with a number from the set $\left\{1;\;2;\;...;\;r\right\}$ in a way such that the following two conditions are fulfilled:
[b]1.[/b] Each number from the set $\left\{1;\;2;\;...;\;r\right\}$ occurs at least once as a label.
[b]2.[/b] In each triangle formed by three vertices of the $n$-gon, two of the sides are labelled with the same number, and this number is greater than the label of the third side.
[b](a)[/b] Find the maximal $r$ for which such a labelling is possible.
[b](b)[/b] [i]Harder version (IMO Shortlist 2005):[/i] For this maximal value of $r$, how many such labellings are there?
[hide="Easier version (5th German TST 2006) - contains answer to the harder version"]
[i]Easier version (5th German TST 2006):[/i] Show that, for this maximal value of $r$, there are exactly $\frac{n!\left(n-1\right)!}{2^{n-1}}$ possible labellings.[/hide]
[i]Proposed by Federico Ardila, Colombia[/i]
An integer $n \geq 3$ is given. We call an $n$-tuple of real numbers $(x_1, x_2, \dots, x_n)$ [i]Shiny[/i] if for each permutation $y_1, y_2, \dots, y_n$ of these numbers, we have
$$\sum \limits_{i=1}^{n-1} y_i y_{i+1} = y_1y_2 + y_2y_3 + y_3y_4 + \cdots + y_{n-1}y_n \geq -1.$$
Find the largest constant $K = K(n)$ such that
$$\sum \limits_{1 \leq i < j \leq n} x_i x_j \geq K$$
holds for every Shiny $n$-tuple $(x_1, x_2, \dots, x_n)$.
There are 20 students in a high school class, and each student has exactly three close friends in the class. Five of the students have bought tickets to an upcoming concert. If any student sees that at least two of their close friends have bought tickets, then they will buy a ticket too.
Is it possible that the entire class buys tickets to the concert?
(Assume that friendship is mutual; if student $A$ is close friends with student $B$, then $B$ is close friends with $A$.)
On a flat plane in Camelot, King Arthur builds a labyrinth $\mathfrak{L}$ consisting of $n$ walls, each of which is an infinite straight line. No two walls are parallel, and no three walls have a common point. Merlin then paints one side of each wall entirely red and the other side entirely blue.
At the intersection of two walls there are four corners: two diagonally opposite corners where a red side and a blue side meet, one corner where two red sides meet, and one corner where two blue sides meet. At each such intersection, there is a two-way door connecting the two diagonally opposite corners at which sides of different colours meet.
After Merlin paints the walls, Morgana then places some knights in the labyrinth. The knights can walk through doors, but cannot walk through walls.
Let $k(\mathfrak{L})$ be the largest number $k$ such that, no matter how Merlin paints the labyrinth $\mathfrak{L},$ Morgana can always place at least $k$ knights such that no two of them can ever meet. For each $n,$ what are all possible values for $k(\mathfrak{L}),$ where $\mathfrak{L}$ is a labyrinth with $n$ walls?
For each prime $p$, construct a graph $G_p$ on $\{1,2,\ldots p\}$, where $m\neq n$ are adjacent if and only if $p$ divides $(m^{2} + 1-n)(n^{2} + 1-m)$. Prove that $G_p$ is disconnected for infinitely many $p$
In a company of people some pairs are enemies. A group of people is called [i]unsociable[/i] if the number of members in the group is odd and at least $3$, and it is possible to arrange all its members around a round table so that every two neighbors are enemies. Given that there are at most $2015$ unsociable groups, prove that it is possible to partition the company into $11$ parts so that no two enemies are in the same part.
[i]Proposed by Russia[/i]
Let $k$ be a positive integer. Two players $A$ and $B$ play a game on an infinite grid of regular hexagons. Initially all the grid cells are empty. Then the players alternately take turns with $A$ moving first. In his move, $A$ may choose two adjacent hexagons in the grid which are empty and place a counter in both of them. In his move, $B$ may choose any counter on the board and remove it. If at any time there are $k$ consecutive grid cells in a line all of which contain a counter, $A$ wins. Find the minimum value of $k$ for which $A$ cannot win in a finite number of moves, or prove that no such minimum value exists.
Let $n$ be a positive integer. Define a chameleon to be any sequence of $3n$ letters, with exactly $n$ occurrences of each of the letters $a, b,$ and $c$. Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon $X$ , there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$ using fewer than $3n^2/2$ swaps.
In a certain city, age is reckoned in terms of real numbers rather than integers. Every two citizens $x$ and $x'$ either know each other or do not know each other. Moreover, if they do not, then there exists a chain of citizens $x = x_0, x_1, \ldots, x_n = x'$ for some integer $n \geq 2$ such that $ x_{i-1}$ and $x_i$ know each other. In a census, all male citizens declare their ages, and there is at least one male citizen. Each female citizen provides only the information that her age is the average of the ages of all the citizens she knows. Prove that this is enough to determine uniquely the ages of all the female citizens.