Let $n$ and $k$ be arbitrary non-negative integers. Suppose we have drawn $2kn+1$ (different) diagonals of a convex $n$-gon. Show that there exists a broken line formed by $2k+1$ of these diagonals that passes through no point more than once. Prove also that this is not necessarily true when we draw only $kn$ diagonals.

$P$ is a convex polyhedron such that: [b](1)[/b] every vertex belongs to exactly $3$ faces. [b](1)[/b] For every natural number $n$, there are even number of faces with $n$ vertices. An ant walks along the edges of $P$ and forms a non-self-intersecting cycle, which divides the faces of this polyhedron into two sides, such that for every natural number $n$, the number of faces with $n$ vertices on each side are the same. (assume this is possible) Show that the number of times the ant turns left is the same as the number of times the ant turn right.

Each of the $50$ students in a class sent greeting cards to $25$ of the others. Prove that there exist two students who greeted each other.

An $ n \times n, n \geq 2$ chessboard is numbered by the numbers $ 1, 2, \ldots, n^2$ (and every number occurs). Prove that there exist two neighbouring (with common edge) squares such that their numbers differ by at least $ n.$

a.) There are $2n+1$ ($n>2$) batteries. We don't know which batteries are good and which are bad but we know that the number of good batteries is greater by $1$ than the number of bad batteries. A lamp uses two batteries, and it works only if both of them are good. What is the least number of attempts sufficient to make the lamp work? b.) The same problem but the total number of batteries is $2n$ ($n>2$) and the numbers of good and bad batteries are equal. [i]Proposed by Alexander Shapovalov[/i]

Let $G$ be a connected (simple) graph with $n$ vertices and at least $n$ edges. Prove that it is possible to color the vertices of $G$ red and blue, so that the following conditions hold: i. There is at least one vertex of each color, ii. There is an even number of edges connecting a red vertex to a blue vertex, and iii. If all such edges are deleted, one is left with two connected graphs.

Given a complete bipartite graph on $n,n$ vertices (call this $K_{n,n}$), we colour all its edges with $2$ colours , red and blue . What is the least value of $n$ such that for any colouring of the edges of the graph , there will exist at least one monochromatic $4$ cycle ?

$n(\geq 4)$ islands are connected by bridges to satisfy the following conditions: [list] [*]Each bridge connects only two islands and does not go through other islands. [*]There is at most one bridge connecting any two different islands. [*]There does not exist a list $A_1, A_2, \ldots, A_{2k}(k \geq 2)$ of distinct islands that satisfy the following: [center]For every $i=1, 2, \ldots, 2k$, the two islands $A_i$ and $A_{i+1}$ are connected by a bridge. (Let $A_{2k+1}=A_1$)[/center] [/list] Prove that the number of the bridges is at most $\frac{3(n-1)}{2}$.

For a tournament with $8$ vertices, if from any vertex it is impossible to follow a route to return to itself, we call the graph a [i]good[/i] graph. Otherwise, we call it a [i]bad[/i] graph. Prove that $(1)$ there exists a tournament with $8$ vertices such that after changing the orientation of any at most $7$ edges of the tournament, the graph is always a[i]bad[/i] graph; $(2)$ for any tournament with $8$ vertices, one can change the orientation of at most $8$ edges of the tournament to get a [i]good[/i] graph. (A tournament is a complete graph with directed edges.)

Let $n\ge 3$ be an integer and let $K_n$ be the complete graph on $n$ vertices. Each edge of $K_n$ is colored either red, green, or blue. Let $A$ denote the number of triangles in $K_n$ with all edges of the same color, and let $B$ denote the number of triangles in $K_n$ with all edges of different colors. Prove \[ B\le 2A+\frac{n(n-1)}{3}.\] (The [i]complete graph[/i] on $n$ vertices is the graph on $n$ vertices with $\tbinom n2$ edges, with exactly one edge joining every pair of vertices. A [i]triangle[/i] consists of the set of $\tbinom 32=3$ edges between $3$ of these $n$ vertices.) [i]Proposed by Ankan Bhattacharya[/i]

Find the maximal number of edges a connected graph $G$ with $n$ vertices may have, so that after deleting an arbitrary cycle, $G$ is not connected anymore.

Given two integers $h \geq 1$ and $p \geq 2$, determine the minimum number of pairs of opponents an $hp$-member parliament may have, if in every partition of the parliament into $h$ houses of $p$ member each, some house contains at least one pair of opponents.

In a sport competition, there are teams of two different countries, with $5$ teams in each country. Each team plays against two teams from each country, including the one itself belongs to, one game at home, one away. How many different ways can one choose the matches in this competition?

A set $P$ of $2002$ persons is given. The family of subsets of $P$ containing exactly $1001$ persons has the property that the number of acquaintance pairs in each such subset is the same. (It is assumed that the acquaintance relation is symmetric). Find the best lower estimation of the acquaintance pairs in the set $P$.

There are several gentlemen in the meeting of the Diogenes Club, some of which are friends with each other (friendship is mutual). Let's name a participant unsociable if he has exactly one friend among those present at the meeting. By the club rules, the only friend of any unsociable member can leave the meeting (gentlemen leave the meeting one at a time). The purpose of the meeting is to achieve a situation in which that there are no friends left among the participants. Prove that if the goal is achievable, then the number of participants remaining at the meeting does not depend on who left and in what order.

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$.

Here $G_{n}$ denotes a simple undirected graph with $n$ vertices, $K_{n}$ denotes the complete graph with $n$ vertices, $K_{n,m}$ the complete bipartite graph whose components have $m$ and $n$ vertices, and $C_{n}$ a circuit with $n$ vertices. The number of edges in the graph $G_{n}$ is denoted $e(G_{n})$. The edges of $K_{n}(n \geq 3)$ are colored with $n$ colors, and every color is used. Show that there is a triangle whose sides have different colors.

Flavian and Pavel play a game. Starting with Flavian, they take turns eliminating exactly one edge from a complete graph with $2024$ vertices. The first player to make a move that leaves no cycles loses. Determine who has a winning strategy. [i]Proposed by Pavel Ciurea[/i]

The vertices of a connected graph cannot be coloured with less than $n+1$ colours (so that adjacent vertices have different colours). Prove that $\dfrac{n(n-1)}{2}$ edges can be removed from the graph so that it remains connected. [i]V. Dolnikov[/i] [b]EDIT.[/b] It is confirmed by the official solution that the graph is tacitly assumed to be [b]finite[/b].

In a chess tournament there are $n>2$ players. Every two players play against each other exactly once. It is known that exactly $n$ games end as a tie. For any set $S$ of players, including $A$ and $B$, we say that $A$ [i]admires[/i] $B$ [i]in that set [/i]if i) $A$ does not beat $B$; or ii) there exists a sequence of players $C_1,C_2,\ldots,C_k$ in $S$, such that $A$ does not beat $C_1$, $C_k$ does not beat $B$, and $C_i$ does not beat $C_{i+1}$ for $1\le i\le k-1$. A set of four players is said to be [i]harmonic[/i] if each of the four players admires everyone else in the set. Find, in terms of $n$, the largest possible number of harmonic sets.

Let $G$ be a simple graph on the infinite vertex set $V=\{v_1, v_2, v_3,\ldots\}$. Suppose every subgraph of $G$ on a finite vertex subset is $10$-colorable, Prove that $G$ itself is $10$-colorable.

Suppose that $ \mathcal F$ is a family of subsets of $ X$. $ A,B$ are two subsets of $ X$ s.t. each element of $ \mathcal{F}$ has non-empty intersection with $ A, B$. We know that no subset of $ X$ with $ n \minus{} 1$ elements has this property. Prove that there is a representation $ A,B$ in the form $ A \equal{} \{a_1,\dots,a_n\}$ and $ B \equal{} \{b_1,\dots,b_n\}$, such that for each $ 1\leq i\leq n$, there is an element of $ \mathcal F$ containing both $ a_i, b_i$.

There are two airlines A and B and finitely many airports. For each pair of airports, there is exactly one airline among A and B whose flights operates in both directions. Each airline plans to develop world travel packages which pass each airport exactly once using only its flights. Let $a$ and $b$ be the number of possible packages which belongs to A and B respectively. Prove that $a-b$ is a multiple of $4$. The official statement of the problem has been changed. The above is the form which appeared during the contest. Now the condition 'the number of airports is no less than 4'is attached. Cite the following link. [url]https://artofproblemsolving.com/community/c6h2923697p26140823[/url]

An island has $10$ cities, where some of the possible pairs of cities are connected by roads. A [i]tour route[/i] is a route starting from a city, passing exactly eight out of the other nine cities exactly once each, and returning to the starting city. (In other words, it is a loop that passes only nine cities instead of all ten cities.) For each city, there exists a tour route that doesn't pass the given city. Find the minimum number of roads on the island.

Let $S$ be a finite set of points on a plane, where no three points are collinear, and the convex hull of $S$, $\Omega$, is a $2016-$gon $A_1A_2\ldots A_{2016}$. Every point on $S$ is labelled one of the four numbers $\pm 1,\pm 2$, such that for $i=1,2,\ldots , 1008,$ the numbers labelled on points $A_i$ and $A_{i+1008}$ are the negative of each other. Draw triangles whose vertices are in $S$, such that any two triangles do not have any common interior points, and the union of these triangles is $\Omega$. Prove that there must exist a triangle, where the numbers labelled on some two of its vertices are the negative of each other.