Found problems: 31
The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.
An international society has its members from six different countries. The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.
Ten localities are served by two international airlines such that there exists a direct service (without stops) between any two of these localities and all airline schedules offer round-trip service between the cities they serve. Prove that at least one of the airlines can offer two disjoint round trips each containing an odd number of landings.
Given a graph with $n$ vertices and a positive integer $m$ that is less than $ n$, prove that the graph contains a set of $m+1$ vertices in which the difference between the largest degree of any vertex in the set and the smallest degree of any vertex in the set is at most $m-1.$
Given seven points in the plane, some of them are connected by segments such that:
[b](i)[/b] among any three of the given points, two are connected by a segment;
[b](ii)[/b] the number of segments is minimal.
How many segments does a figure satisfying [b](i)[/b] and [b](ii)[/b] have? Give an example of such a figure.
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.
The localities $P_1, P_2, \dots, P_{1983}$ are served by ten international airlines $A_1,A_2, \dots , A_{10}$. It is noticed that there is direct service (without stops) between any two of these localities and that all airline schedules offer round-trip flights. Prove that at least one of the airlines can offer a round trip with an odd number of landings.
In a group of mathematicians, every mathematician has some friends (the relation of friend is reciprocal). Prove that there exists a mathematician, such that the average of the number of friends of all his friends is no less than the average of the number of friends of all these mathematicians.
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]
Prove that a graph containing a copy of each possible tree on $n$ vertices as a subgraph has at least $n(\ln n - 2)$ edges.
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.$
An international society has its members from six different countries. The list of members contain $1978$ names, numbered $1, 2, \dots, 1978$. Prove that there is at least one member whose number is the sum of the numbers of two members from his own country, or twice as large as the number of one member from his own country.
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.$
155 birds $ P_1, \ldots, P_{155}$ are sitting down on the boundary of a circle $ C.$ Two birds $ P_i, P_j$ are mutually visible if the angle at centre $ m(\cdot)$ of their positions $ m(P_iP_j) \leq 10^{\circ}.$ Find the smallest number of mutually visible pairs of birds, i.e. minimal set of pairs $ \{x,y\}$ of mutually visible pairs of birds with $ x,y \in \{P_1, \ldots, P_{155}\}.$ One assumes that a position (point) on $ C$ can be occupied simultaneously by several birds, e.g. all possible birds.
From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1, \cdots, q$ (no ties). Let $m$ be the least integer larger than or equal to $2q/n$. Show that there are $m$ distinct teams that may be listed so that :
[b](i)[/b] each pair of consecutive teams on the list have one member in common and
[b](ii)[/b] the chain of teams on the list are in rank order.
[i]Alternative formulation.[/i]
Given a graph with $n$ vertices and $q$ edges numbered $1, \cdots , q$, show that there exists a chain of $m$ edges, $m \geq \frac{2q}{n}$ , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.
1990 mathematicians attend a meeting, every mathematician has at least 1327 friends (the relation of friend is reciprocal). Prove that there exist four mathematicians among them such that any two of them are friends.
Let $n \geq 2$ be an integer. Find the maximal cardinality of a set $M$ of pairs $(j, k)$ of integers, $1 \leq j < k \leq n$, with the following property: If $(j, k) \in M$, then $(k,m) \not \in M$ for any $m.$
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]
Let $X$ and $Y$ be two sets of points in the plane and $M$ be a set of segments connecting points from $X$ and $Y$ . Let $k$ be a natural number. Prove that the segments from $M$ can be painted using $k$ colors in such a way that for any point $x \in X \cup Y$ and two colors $\alpha$ and $\beta$ $(\alpha \neq \beta)$, the difference between the number of $\alpha$-colored segments and the number of $\beta$-colored segments originating in $X$ is less than or equal to $1$.
$n\ge 3$ guests met at a party. Some of them know each other but there is no quartet of different guests $a, b, c, d$ such that in pairs $\lbrace a, b \rbrace, \lbrace b, c \rbrace, \lbrace c, d \rbrace, \lbrace d, a \rbrace$ guests know each other but in pairs $\lbrace a, c \rbrace, \lbrace b, d \rbrace$ guests don't know each other. We say a nonempty set of guests $X$ is an [i]ingroup[/i], when guests from $X$ know each other pairwise and there are no guests not from $X$ knowing all guests from $X$. Prove that there are at most $\frac{n(n-1)}{2}$ different ingroups at that party.
In a simple graph with 300 vertices no two vertices of the same degree are adjacent (boo hoo hoo).
What is the maximal possible number of edges in such a graph?
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.
In the plane we are given a set $ E$ of 1991 points, and certain pairs of these points are joined with a path. We suppose that for every point of $ E,$ there exist at least 1593 other points of $ E$ to which it is joined by a path. Show that there exist six points of $ E$ every pair of which are joined by a path.
[i]Alternative version:[/i] Is it possible to find a set $ E$ of 1991 points in the plane and paths joining certain pairs of the points in $ E$ such that every point of $ E$ is joined with a path to at least 1592 other points of $ E,$ and in every subset of six points of $ E$ there exist at least two points that are not joined?
At a university dinner, there are 2017 mathematicians who each order two distinct entrées, with no two mathematicians ordering the same pair of entrées. The cost of each entrée is equal to the number of mathematicians who ordered it, and the university pays for each mathematician's less expensive entrée (ties broken arbitrarily). Over all possible sets of orders, what is the maximum total amount the university could have paid?
[i]Proposed by Evan Chen[/i]
From a collection of $n$ persons $q$ distinct two-member teams are selected and ranked $1, \cdots, q$ (no ties). Let $m$ be the least integer larger than or equal to $2q/n$. Show that there are $m$ distinct teams that may be listed so that :
[b](i)[/b] each pair of consecutive teams on the list have one member in common and
[b](ii)[/b] the chain of teams on the list are in rank order.
[i]Alternative formulation.[/i]
Given a graph with $n$ vertices and $q$ edges numbered $1, \cdots , q$, show that there exists a chain of $m$ edges, $m \geq \frac{2q}{n}$ , each two consecutive edges having a common vertex, arranged monotonically with respect to the numbering.