Participants in a chess tournament played one game with each other. For each participant AAA, the number of points they earned was calculated (1 point for a win, 12\frac{1}{2}21 point for a draw, and 0 points for a loss). Additionally…
Consider an assembly of nnn people such that in any group of 4 people, there are either 3 who all know each other, or 3 who do not know each other. Show that it is possible to separate the assembly into two groups such that all members…
A group of 404640464046 friends will play a videogame tournament. For that, 202320232023 of them will go to one room which the computers are labeled with a1,a2,…,a2023a_1,a_2,\dots,a_{2023}a1,a2,…,a2023 and the other 202320232023 friends go to another room which the compute…
Form a sequence from the consecutive positive integers from 1 to nnn (where n>1n > 1n>1) in such a way that the sum of any two adjacent terms in the sequence is a perfect square. What is the smallest value of the positive integer nnn?
Twenty cities are connected by 172 airline routes. Prove that, using these airline routes, it is possible to travel from any city to any other city (possibly with layovers).
At a costume ball, there were 20 people. Each dance was between a boy and a girl. It turned out that ten people danced with three partners, two people (Sasha and Zhenya) danced with five partners, and the remaining eight danced with six par…
Show that every graph admits an acyclic orientation.
Let GGG be a graph. Show that it contains an independent set of vertices with a cardinality greater than or equal to ∑v∈V11+d(v)\sum_{v \in V} \frac{1}{1+d(v)}∑v∈V1+d(v)1
There are five monkeys and five ladders. At the top of each ladder, there is a banana. The ladders are connected by ropes, with each rope connecting two rungs on different ladders. No rung has more than one rope attached to it. Initially, e…
Anton colors a cell in a 4×504 \times 504×50 rectangle. He then repeatedly chooses an uncolored cell that is adjacent to at most one already colored cell. What is the maximum number of cells that can be colored?
A maze is a 10x10 grid square where some pairs of adjacent nodes are connected by a "wall" segment, such that it is possible to visit all grid cells by moving from one cell to an adjacent cell through the sides and without passing through w…
In a gathering of 2n2n2n people, if any two individuals have the same number of friends, then those two individuals do not share any common friends (friendship is mutual). What is the maximum number of pairs of friends in this gathering?
Show that among the participants of the Animath training this week, there are two who know the same number of other participants (assuming the "knowing each other" relationship is symmetric).
In the Thrice-Ninth Kingdom, there is only one type of transport - the magic carpet. 21 carpetlines extend from the capital, one from the city of Dalniy, and 20 from all other cities. Prove that it is possible to travel from the capital to…
A chess tournament was held among the actors of the Karabas Barabas theater. Each participant played with each of the others exactly once. For a win, one received one soldo, for a draw - half a soldo, and for a loss - nothing. It turned out…
Given 6 lines in space, where no three lines lie on the same plane. Prove that there exist three of these lines that satisfy one of the following three conditions: (1) They form a plane pairwise, (2) They are parallel to each other, (3) The…
In a directed graph with 201320132013 vertices, there is exactly one edge between any two vertices and for every vertex there exists an edge outwards this vertex. We know that whatever the arrangement of the edges, from every vertex we can reac…
Is it possible to write one of the 10 digits 0, 1, 2, ..., 9 at each vertex of a regular 45-gon, such that for any two different digits among these 10 digits, there exists an edge of the 45-gon with these two digits written at its endpoints…
Suppose GGG is a connected graph with kkk edges. Prove that it is possible to label the edges 1,2,…,k1, 2, \ldots, k1,2,…,k in such a way that at each vertex which belongs to two or more edges, the greatest common divisor of the integers la…
There are 242424 participants attended a meeting. Each two of them shook hands once or not. A total of 216216216 handshakes occured in the meeting. For any two participants who have shaken hands, at most 101010 among the rest 222222 participa…