Found problems: 801
2016 International Zhautykov Olympiad, 3
There are $60$ towns in $Graphland$ every two countries of which are connected by only a directed way. Prove that we can color four towns to red and four towns to green such that every way between green and red towns are directed from red to green
1987 IMO Shortlist, 2
At a party attended by $n$ married couples, each person talks to everyone else at the party except his or her spouse. The conversations involve sets of persons or cliques $C_1, C_2, \cdots, C_k$ with the following property: no couple are members of the same clique, but for every other pair of persons there is exactly one clique to which both members belong. Prove that if $n \geq 4$, then $k \geq 2n$.
[i]Proposed by USA.[/i]
2001 China Team Selection Test, 2.2
Given distinct positive integers \( g \) and \( h \), let all integer points on the number line \( OX \) be vertices. Define a directed graph \( G \) as follows: for any integer point \( x \), \( x \rightarrow x + g \), \( x \rightarrow x - h \). For integers \( k, l (k < l) \), let \( G[k, l] \) denote the subgraph of \( G \) with vertices limited to the interval \([k, l]\). Find the largest positive integer \( \alpha \) such that for any integer \( r \), the subgraph \( G[r, r + \alpha - 1] \) of \( G \) is acyclic. Clarify the structure of subgraphs \( G[r, r + \alpha - 1] \) and \( G[r, r + \alpha] \) (i.e., how many connected components and what each component is like).
2024 Turkey MO (2nd Round), 1
Let $n\ge3$ be a positive integer. Each edge of a complete graph $K_n$ is assigned a real number satisfying the following conditions:
$(i)$ For any three vertices, the numbers assigned to two of the edges among them are equal, and the number on the third edge is strictly greater.
$(ii) $ The weight of a vertex is defined as the sum of the numbers assigned to the edges emanating from that vertex. The weights of all vertices are equal.
Find all possible values of $n$.
2023 Kyiv City MO Round 1, Problem 5
In a galaxy far, far away there are $225$ inhabited planets. Between some pairs of inhabited planets there is a bidirectional space connection, and it is possible to reach any planet from any other (possibly with several transfers). The [i]influence[/i] of a planet is the number of other planets with which this planet has a direct connection. It is known that if two planets are not connected by a direct space flight, they have different influences. What is the smallest number of connections possible under these conditions?
[i]Proposed by Arsenii Nikolaev, Bogdan Rublov[/i]
2005 Junior Tuymaada Olympiad, 4
The organizers of a mathematical congress found that if they accomodate any participant in a room the rest can be accomodated in double rooms so that 2 persons living in each room know each other. Prove that every participant can organize a round table on graph theory for himself and an even number of other people so that each participant of the round table knows both his neigbours.
[i]Proposed by S. Berlov, S. Ivanov[/i]
2004 IMO Shortlist, 3
The following operation is allowed on a finite graph: Choose an arbitrary cycle of length 4 (if there is any), choose an arbitrary edge in that cycle, and delete it from the graph. For a fixed integer ${n\ge 4}$, find the least number of edges of a graph that can be obtained by repeated applications of this operation from the complete graph on $n$ vertices (where each pair of vertices are joined by an edge).
[i]Proposed by Norman Do, Australia[/i]
EGMO 2017, 4
Let $n\geq1$ be an integer and let $t_1<t_2<\dots<t_n$ be positive integers. In a group of $t_n+1$ people, some games of chess are played. Two people can play each other at most once. Prove that it is possible for the following two conditions to hold at the same time:
(i) The number of games played by each person is one of $t_1,t_2,\dots,t_n$.
(ii) For every $i$ with $1\leq i\leq n$, there is someone who has played exactly $t_i$ games of chess.
2020 Iranian Combinatorics Olympiad, 4
Given a graph with $99$ vertices and degrees in $\{81,82,\dots,90\}$, prove that there exist $10$ vertices of this graph with equal degrees and a common neighbour.
[i]Proposed by Alireza Alipour[/i]
2015 German National Olympiad, 3
To prepare a stay abroad, students meet at a workshop including an excursion. To promote interaction between the students, they are to be distributed to two busses such that not too many of the students in the same bus know each other.
Every student knows all those who know her. The number of such pairwise acquaintances is $k$.
Prove that it is possible to distribute the students such that the number of pairwise acquaintances in each bus is at most $\frac{k}{3}$.
2015 Bangladesh Mathematical Olympiad, 4
There are $36$ participants at a BdMO event. Some of the participants shook hands with each other. But no two participants shook hands with each other more than once. Each participant recorded the number of handshakes they made. It was found that no two participants with the same number of handshakes made, had shaken hands with each other. Find the maximum possible number of handshakes at the party with proof. (When two participants shake hands with each other, this will be counted as one handshake.)
2017 Harvard-MIT Mathematics Tournament, 6
Let $r$ be a positive integer. Show that if a graph $G$ has no cycles of length at most $2r$, then it has at most $|V|^{2016}$ cycles of length exactly $2016r$, where $|V|$ denotes the number of vertices in the graph $G$.
1987 Canada National Olympiad, 4
On a large, flat field $n$ people are positioned so that for each person the distances to all the other people are different. Each person holds a water pistol and at a given signal fires and hits the person who is closest. When $n$ is odd show that there is at least one person left dry. Is this always true when $n$ is even?
2015 Miklos Schweitzer, 2
Let $\{x_n\}$ be a Van Der Corput series,that is,if the binary representation of $n$ is $\sum a_{i}2^{i}$ then $x_n=\sum a_i2^{-i-1}$.Let $V$ be the set of points on the plane that have the form $(n,x_n)$.Let $G$ be the graph with vertex set $V$ that is connecting any two points $(p,q)$ if there is a rectangle $R$ which lies in parallel position with the axes and $R\cap V= \{p,q\}$.Prove that the chromatic number of $G$ is finite.
2016 Iran MO (3rd Round), 3
There are $24$ robots on the plane. Each robot has a $70^{\circ}$ field of view. What is the maximum number of observing relations?
(Observing is a one-sided relation)
2007 Junior Balkan Team Selection Tests - Romania, 3
At a party there are eight guests, and each participant can't talk with at most three persons. Prove that we can group the persons in four pairs such that in every pair a conversation can take place.
1974 Miklós Schweitzer, 2
Let $ G$ be a $ 2$-connected nonbipartite graph on $ 2n$ vertices. Show that the vertex set of $ G$ can be split into two classes of $ n$ elements such that the edges joining the two classes form a connected, spanning subgraph.
[i]L. Lovasz[/i]
1985 IMO Shortlist, 8
Let $A$ be a set of $n$ points in the space. From the family of all segments with endpoints in $A$, $q$ segments have been selected and colored yellow. Suppose that all yellow segments are of different length. Prove that there exists a polygonal line composed of $m$ yellow segments, where $m \geq \frac{2q}{n}$, arranged in order of increasing length.
2009 Kazakhstan National Olympiad, 3
In chess tournament participates $n$ participants ($n >1$). In tournament each of participants plays with each other exactly $1$ game. For each game participant have $1$ point if he wins game, $0,5$ point if game is drow and $0$ points if he lose game.
If after ending of tournament participant have at least $ 75 %
$ of maximum possible points he called $winner$ $of$ $tournament$.
Find maximum possible numbers of $winners$ $of$ $tournament$.
2021/2022 Tournament of Towns, P5
There were 20 participants in a chess tournament. Each of them played with each other twice: once as white and once as black. Let us say that participant $X{}$ is no weaker than participant $Y{}$ if $X{}$ has won at least the same number of games playing white as $Y{}$ and also has won at least the same number of games playing black as $Y{}$ . Do there exist for sure two participants $A{}$ and $B{}$ such that $A{}$ is not weaker than $B{}$?
[i]Boris Frenkin[/i]
2024 Bulgaria MO Regional Round, 9.4
Given is a $K_{2024}$ in which every edge has weight $1$ or $2$. If every cycle has even total weight, find the minimal value of the sum of all weights in the graph.
2017 CHMMC (Fall), 6
The country of Claredena has $5$ cities, and is planning to build a road system so that each of its cities has exactly one outgoing (unidirectional) road to another city.
Two road systems are considered equivalent if we can get from one road system the other by just changing the names of the cities. That is, two road systems are considered the same if given a relabeling of the cities, if in the first configuration a road went from city $C$ to city $D$, then in the second configuration there is road that goes from the city now labeled $C$ to the city now labeled $D$.
How many distinct, nonequivalent possibilities are there for the road system Claredena builds?
2022 239 Open Mathematical Olympiad, 4
The degrees of all vertices of a graph are not less than 100 and not more than 200. Prove that its vertices can be divided into connected pairs and triples.
2022 Saint Petersburg Mathematical Olympiad, 7
Given is a graph $G$ of $n+1$ vertices, which is constructed as follows: initially there is only one vertex $v$, and one a move we can add a vertex and connect it to exactly one among the previous vertices. The vertices have non-negative real weights such that $v$ has weight $0$ and each other vertex has a weight not exceeding the avarage weight of its neighbors, increased by $1$. Prove that no weight can exceed $n^2$.
2000 Moldova National Olympiad, Problem 5
An airline offer $2000$ two-way routes connecting $64$ towns in a country. Show that it is possible to reach any town from any other town using the offered routes.