Olympiad problems

2008 Miklós Schweitzer, 3

Tags: graph theory

A bipartite graph on the sets $\{ x_1,\ldots, x_n \}$ and $\{ y_1,\ldots, y_n\}$ of vertices (that is the edges are of the form $x_iy_j$) is called tame if it has no $x_iy_jx_ky_l$ path ($i,j,k,l\in\{ 1,\ldots, n\}$) where $j<l$ and $i+j>k+l$. Calculate the infimum of those real numbers $\alpha$ for which there exists a constant $c=c(\alpha)>0$ such that for all tame graphs $e\le cn^{\alpha}$, where $e$ is the number of edges and $n$ is half of the number of vertices. (translated by Miklós Maróti)

2022 Belarus - Iran Friendly Competition, 5

Tags: graph theory , combinatorics

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$

2013 USAMTS Problems, 1

Tags: graph theory

Alex is trying to open a lock whose code is a sequence that is three letters long, with each of the letters being one of $\text A$, $\text B$ or $\text C$, possibly repeated. The lock has three buttons, labeled $\text A$, $\text B$ and $\text C$. When the most recent $3$ button-presses form the code, the lock opens. What is the minimum number of total button presses Alex needs to guarantee opening the lock?

2012 France Team Selection Test, 1

Tags: group theory , abstract algebra , graph theory , combinatorics

Let $n$ and $k$ be two positive integers. Consider a group of $k$ people such that, for each group of $n$ people, there is a $(n+1)$-th person that knows them all (if $A$ knows $B$ then $B$ knows $A$). 1) If $k=2n+1$, prove that there exists a person who knows all others. 2) If $k=2n+2$, give an example of such a group in which no-one knows all others.

2023 China Team Selection Test, P7

Tags: combinatorics , graph theory

Given the integer $n\geq 2$ and a integer ${a}$, which is coprime with ${n}$. A country has ${n}$ islands $D_1$, $D_2$, $\cdots$, $D_n$. For any $1\leq i\neq j\leq n$, there is a one-way ferry $D_i$ to $D_j$ if and only if $ij\equiv ia\pmod n$. A tourist can initially fly to any of the islands, and then he can only take a one-way ferry. What is the maximum number of islands he can visit? [i]Created by Zhenhua Qu[/i]

1993 All-Russian Olympiad, 4

Tags: graph theory , combinatorics

In a family album, there are ten photos. On each of them, three people are pictured: in the middle stands a man, to the right of him stands his brother, and to the left of him stands his son. What is the least possible total number of people pictured, if all ten of the people standing in the middle of the ten pictures are different.

2014 Belarusian National Olympiad, 4

Tags: combinatorics , graph theory , path

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.

Russian TST 2018, P2

Tags: combinatorics , graph theory

There are $2^n$ airports, numbered with binary strings of length $n{}$. Any two stations whose numbers differ in exactly one digit are connected by a flight that has a price (which is the same in both directions). The sum of the prices of all $n{}$ flights leaving any station does not exceed 1. Prove that one can travel between any two airports by paying no more than 1.

2012 Romanian Masters In Mathematics, 1

Tags: induction , modular arithmetic , graph theory , combinatorics

Given a finite number of boys and girls, a [i]sociable set of boys[/i] is a set of boys such that every girl knows at least one boy in that set; and a [i]sociable set of girls[/i] is a set of girls such that every boy knows at least one girl in that set. Prove that the number of sociable sets of boys and the number of sociable sets of girls have the same parity. (Acquaintance is assumed to be mutual.) [i](Poland) Marek Cygan[/i]

1995 Miklós Schweitzer, 6

Tags: graph theory , combinatorics

Prove that every finite triangle-free graph can be embedded as an induced subgraph in a finite triangle-free graph of diameter 2.

2016 Nordic, 4

Tags: combinatorics , graph theory

King George has decided to connect the $1680$ islands in his kingdom by bridges. Unfortunately the rebel movement will destroy two bridges after all the bridges have been built, but not two bridges from the same island. What is the minimal number of bridges the King has to build in order to make sure that it is still possible to travel by bridges between any two of the $1680$ islands after the rebel movement has destroyed two bridges?

2010 Contests, 4

Tags: linear algebra , matrix , graph theory , combinatorics

Let $n$ be a positive integer. Find the smallest positive integer $k$ with the property that for any colouring nof the squares of a $2n$ by $k$ chessboard with $n$ colours, there are $2$ columns and $2$ rows such that the $4$ squares in their intersections have the same colour.

2011 Turkey Junior National Olympiad, 4

Tags: graph theory , combinatorics

Each student chooses $1$ math problem and $1$ physics problem among $20$ math problems and $11$ physics problems. No same pair of problem is selected by two students. And at least one of the problems selected by any student is selected by at most one other student. At most how many students are there?

2016 IMAR Test, 3

Tags: graph theory , graph , spanning tree , combinatorics , combinatorial geometry

Fix an integer $n \ge 2$, let $Q_n$ be the graph consisting of all vertices and all edges of an $n$-cube, and let $T$ be a spanning tree in $Q_n$. Show that $Q_n$ has an edge whose adjunction to $T$ produces a simple cycle of length at least $2n$.

2017 EGMO, 3

Tags: combinatorics , graph theory , vertex degree

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.

2007 IMO Shortlist, 6

Tags: algorithm , graph theory , combinatorics , clique number

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a [i]clique[/i] if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its [i]size[/i]. Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room. [i]Author: Vasily Astakhov, Russia[/i]

2021 Bangladeshi National Mathematical Olympiad, 9

Tags: combinatorics , graph theory , number theory

Cynthia loves Pokemon and she wants to catch them all. In Victory Road, there are a total of $80$ Pokemon. Cynthia wants to catch as many of them as possible. However, she cannot catch any two Pokemon that are enemies with each other. After exploring around for a while, she makes the following two observations: 1. Every Pokemon in Victory Road is enemies with exactly two other Pokemon. 2. Due to her inability to catch Pokemon that are enemies with one another, the maximum number of the Pokemon she can catch is equal to $n$. What is the sum of all possible values of $n$?

1993 China Team Selection Test, 3

Tags: graph theory , combinatorics

A graph $G=(V,E)$ is given. If at least $n$ colors are required to paints its vertices so that between any two same colored vertices no edge is connected, then call this graph ''$n-$colored''. Prove that for any $n \in \mathbb{N}$, there is a $n-$colored graph without triangles.

2010 Contests, 3

Tags: geometry , graph theory , combinatorics

Given an integer $n\ge 2$, given $n+1$ distinct points $X_0,X_1,\ldots,X_n$ in the plane, and a positive real number $A$, show that the number of triangles $X_0X_iX_j$ of area $A$ does not exceed $4n\sqrt n$.

1998 Korea Junior Math Olympiad, 2

Tags: graph theory , combinatorics

There are $6$ computers(power off) and $3$ printers. Between a printer and a computer, they are connected with a wire or not. Printer can be only activated if and only if at least one of the connected computer's power is on. Your goal is to connect wires in such a way that, no matter how you choose three computers to turn on among the six, you can activate all $3$ printers. What is the minimum number of wires required to make this possible?

2002 IMO Shortlist, 7

Tags: combinatorics , graph theory , extremal graph theory , extremal combinatorics

Among a group of 120 people, some pairs are friends. A [i]weak quartet[/i] is a set of four people containing exactly one pair of friends. What is the maximum possible number of weak quartets ?

the 12th XMO, Problem 4

Tags: graph theory , combinatorics

求最小的 $n,$ 使得对任意有 ${1000}$ 个顶点且每个顶点度均为 ${4}$ 的简单图 $G,$ 都一定可以从中取掉 ${n}$ 条边$,$ 使 ${G}$ 变为二部图$.$

2009 Saint Petersburg Mathematical Olympiad, 6

Tags: combinatorics , graph theory

Some cities in country are connected by road, and from every city goes $\geq 2008$ roads. Every road is colored in one of two colors. Prove, that exists cycle without self-intersections ,where $\geq 504$ roads and all roads are same color.

2016 Turkey Team Selection Test, 2

Tags: combinatorics , graph theory

In a class with $23$ students, each pair of students have watched a movie together. Let the set of movies watched by a student be his [i]movie collection[/i]. If every student has watched every movie at most once, at least how many different movie collections can these students have?

2016 Tournament Of Towns, 4

Tags: graph theory , combinatorics

30 masters and 30 juniors came onto tennis players meeting .Each master played with one master and 15 juniors while each junior played with one junior and 15 masters.Prove that one can find two masters and two juniors such that these masters played with each other ,juniors -with each other ,each of two masters played with at least one of two juniors and each of two juniors played with at least one of two masters.