Found problems: 42
2000 China National Olympiad, 3
A test contains $5$ multiple choice questions which have $4$ options in each. Suppose each examinee chose one option for each question. There exists a number $n$, such that for any $n$ sheets among $2000$ sheets of answer papers, there are $4$ sheets of answer papers such that any two of them have at most $3$ questions with the same answers. Find the minimum value of $n$.
2007 IMO Shortlist, 7
Let $ \alpha < \frac {3 \minus{} \sqrt {5}}{2}$ be a positive real number. Prove that there exist positive integers $ n$ and $ p > \alpha \cdot 2^n$ for which one can select $ 2 \cdot p$ pairwise distinct subsets $ S_1, \ldots, S_p, T_1, \ldots, T_p$ of the set $ \{1,2, \ldots, n\}$ such that $ S_i \cap T_j \neq \emptyset$ for all $ 1 \leq i,j \leq p$
[i]Author: Gerhard Wöginger, Austria[/i]
1978 IMO Shortlist, 1
The set $M = \{1, 2, . . . , 2n\}$ is partitioned into $k$ nonintersecting subsets $M_1,M_2, \dots, M_k,$ where $n \ge k^3 + k.$ Prove that there exist even numbers $2j_1, 2j_2, \dots, 2j_{k+1}$ in $M$ that are in one and the same subset $M_i$ $(1 \le i \le k)$ such that the numbers $2j_1 - 1, 2j_2 - 1, \dots, 2j_{k+1} - 1$ are also in one and the same subset $M_j (1 \le j \le k).$
1998 IMO, 2
In a contest, there are $m$ candidates and $n$ judges, where $n\geq 3$ is an odd integer. Each candidate is evaluated by each judge as either pass or fail. Suppose that each pair of judges agrees on at most $k$ candidates. Prove that \[{\frac{k}{m}} \geq {\frac{n-1}{2n}}. \]
1990 IMO Longlists, 4
Given $ n$ countries with three representatives each, $ m$ committees $ A(1),A(2), \ldots, A(m)$ are called a cycle if
[i](i)[/i] each committee has $ n$ members, one from each country;
[i](ii)[/i] no two committees have the same membership;
[i](iii)[/i] for $ i \equal{} 1, 2, \ldots,m$, committee $ A(i)$ and committee $ A(i \plus{} 1)$ have no member in common, where $ A(m \plus{} 1)$ denotes $ A(1);$
[i](iv)[/i] if $ 1 < |i \minus{} j| < m \minus{} 1,$ then committees $ A(i)$ and $ A(j)$ have at least one member in common.
Is it possible to have a cycle of 1990 committees with 11 countries?
1972 Miklós Schweitzer, 1
Let $ \mathcal{F}$ be a nonempty family of sets with the following properties:
(a) If $ X \in \mathcal{F}$, then there are some $ Y \in \mathcal{F}$ and $ Z \in \mathcal{F}$ such that $ Y \cap Z =\emptyset$ and $ Y \cup Z=X$.
(b) If $ X \in \mathcal{F}$, and $ Y \cup Z =X , Y \cap Z=\emptyset$, then either $ Y \in \mathcal{F}$ or $ Z \in \mathcal{F}$.
Show that there is a decreasing sequence $ X_0 \supseteq X_1 \supseteq X_2 \supseteq ...$ of sets $ X_n \in \mathcal{F}$ such that \[ \bigcap_{n=0}^{\infty} X_n= \emptyset.\]
[i]F. Galvin[/i]
1979 IMO Longlists, 31
Let $R$ be a set of exactly $6$ elements. A set $F$ of subsets of $R$ is called an $S$-family over $R$ if and only if it satisfies the following three conditions:
(i) For no two sets $X, Y$ in $F$ is $X \subseteq Y$ ;
(ii) For any three sets $X, Y,Z$ in $F$, $X \cup Y \cup Z \neq R,$
(iii) $\bigcup_{X \in F} X = R$
1987 IMO Shortlist, 18
For any integer $r \geq 1$, determine the smallest integer $h(r) \geq 1$ such that for any partition of the set $\{1, 2, \cdots, h(r)\}$ into $r$ classes, there are integers $a \geq 0 \ ; 1 \leq x \leq y$, such that $a + x, a + y, a + x + y$ belong to the same class.
[i]Proposed by Romania[/i]
1979 IMO Shortlist, 16
Let $K$ denote the set $\{a, b, c, d, e\}$. $F$ is a collection of $16$ different subsets of $K$, and it is known that any three members of $F$ have at least one element in common. Show that all $16$ members of $F$ have exactly one element in common.
1979 IMO Longlists, 46
Let $K$ denote the set $\{a, b, c, d, e\}$. $F$ is a collection of $16$ different subsets of $K$, and it is known that any three members of $F$ have at least one element in common. Show that all $16$ members of $F$ have exactly one element in common.
2006 Romania Team Selection Test, 3
Let $n>1$ be an integer. A set $S \subset \{ 0,1,2, \ldots, 4n-1\}$ is called [i]rare[/i] if, for any $k\in\{0,1,\ldots,n-1\}$, the following two conditions take place at the same time
(1) the set $S\cap \{4k-2,4k-1,4k, 4k+1, 4k+2 \}$ has at most two elements;
(2) the set $S\cap \{4k+1,4k+2,4k+3\}$ has at most one element.
Prove that the set $\{0,1,2,\ldots,4n-1\}$ has exactly $8 \cdot 7^{n-1}$ rare subsets.
2002 IMO Shortlist, 5
Let $r\geq2$ be a fixed positive integer, and let $F$ be an infinite family of sets, each of size $r$, no two of which are disjoint. Prove that there exists a set of size $r-1$ that meets each set in $F$.
1988 IMO Longlists, 18
Let $ N \equal{} \{1,2 \ldots, n\}, n \geq 2.$ A collection $ F \equal{} \{A_1, \ldots, A_t\}$ of subsets $ A_i \subseteq N,$ $ i \equal{} 1, \ldots, t,$ is said to be separating, if for every pair $ \{x,y\} \subseteq N,$ there is a set $ A_i \in F$ so that $ A_i \cap \{x,y\}$ contains just one element. $ F$ is said to be covering, if every element of $ N$ is contained in at least one set $ A_i \in F.$ What is the smallest value $ f(n)$ of $ t,$ so there is a set $ F \equal{} \{A_1, \ldots, A_t\}$ which is simultaneously separating and covering?
1992 IMO Longlists, 39
Let $n \geq 2$ be an integer. Find the minimum $k$ for which there exists a partition of $\{1, 2, . . . , k\}$ into $n$ subsets $X_1,X_2, \cdots , X_n$ such that the following condition holds:
for any $i, j, 1 \leq i < j \leq n$, there exist $x_i \in X_1, x_j \in X_2$ such that $|x_i - x_j | = 1.$
1987 IMO Longlists, 56
For any integer $r \geq 1$, determine the smallest integer $h(r) \geq 1$ such that for any partition of the set $\{1, 2, \cdots, h(r)\}$ into $r$ classes, there are integers $a \geq 0 \ ; 1 \leq x \leq y$, such that $a + x, a + y, a + x + y$ belong to the same class.
[i]Proposed by Romania[/i]
1998 IMO Shortlist, 4
Let $U=\{1,2,\ldots ,n\}$, where $n\geq 3$. A subset $S$ of $U$ is said to be [i]split[/i] by an arrangement of the elements of $U$ if an element not in $S$ occurs in the arrangement somewhere between two elements of $S$. For example, 13542 splits $\{1,2,3\}$ but not $\{3,4,5\}$. Prove that for any $n-2$ subsets of $U$, each containing at least 2 and at most $n-1$ elements, there is an arrangement of the elements of $U$ which splits all of them.
2010 Contests, 3
In an exam every question is solved by exactly four students, every pair of questions is solved by exactly one student, and none of the students solved all of the questions. Find the maximum possible number of questions in this exam.
1991 IMO, 3
Let $ S \equal{} \{1,2,3,\cdots ,280\}$. Find the smallest integer $ n$ such that each $ n$-element subset of $ S$ contains five numbers which are pairwise relatively prime.
1967 IMO Longlists, 56
In a group of interpreters each one speaks one of several foreign languages, 24 of them speak Japanese, 24 Malaysian, 24 Farsi. Prove that it is possible to select a subgroup in which exactly 12 interpreters speak Japanese, exactly 12 speak Malaysian and exactly 12 speak Farsi.
1978 IMO Longlists, 1
The set $M = \{1, 2, . . . , 2n\}$ is partitioned into $k$ nonintersecting subsets $M_1,M_2, \dots, M_k,$ where $n \ge k^3 + k.$ Prove that there exist even numbers $2j_1, 2j_2, \dots, 2j_{k+1}$ in $M$ that are in one and the same subset $M_i$ $(1 \le i \le k)$ such that the numbers $2j_1 - 1, 2j_2 - 1, \dots, 2j_{k+1} - 1$ are also in one and the same subset $M_j (1 \le j \le k).$
2017 Romanian Master of Mathematics, 3
Let $n$ be an integer greater than $1$ and let $X$ be an $n$-element set. A non-empty collection of subsets $A_1, ..., A_k$ of $X$ is tight if the union $A_1 \cup \cdots \cup A_k$ is a proper subset of $X$ and no element of $X$ lies in exactly one of the $A_i$s. Find the largest cardinality of a collection of proper non-empty subsets of $X$, no non-empty subcollection of which is tight.
[i]Note[/i]. A subset $A$ of $X$ is proper if $A\neq X$. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.
1989 IMO Longlists, 68
Prove that in the set $ \{1,2, \ldots, 1989\}$ can be expressed as the disjoint union of subsets $ A_i, \{i \equal{} 1,2, \ldots, 117\}$ such that
[b]i.)[/b] each $ A_i$ contains 17 elements
[b]ii.)[/b] the sum of all the elements in each $ A_i$ is the same.
2017 Romanian Masters In Mathematics, 3
Let $n$ be an integer greater than $1$ and let $X$ be an $n$-element set. A non-empty collection of subsets $A_1, ..., A_k$ of $X$ is tight if the union $A_1 \cup \cdots \cup A_k$ is a proper subset of $X$ and no element of $X$ lies in exactly one of the $A_i$s. Find the largest cardinality of a collection of proper non-empty subsets of $X$, no non-empty subcollection of which is tight.
[i]Note[/i]. A subset $A$ of $X$ is proper if $A\neq X$. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.
1988 IMO, 2
Let $ n$ be an even positive integer. Let $ A_1, A_2, \ldots, A_{n \plus{} 1}$ be sets having $ n$ elements each such that any two of them have exactly one element in common while every element of their union belongs to at least two of the given sets. For which $ n$ can one assign to every element of the union one of the numbers 0 and 1 in such a manner that each of the sets has exactly $ \frac {n}{2}$ zeros?
1991 IMO Shortlist, 12
Let $ S \equal{} \{1,2,3,\cdots ,280\}$. Find the smallest integer $ n$ such that each $ n$-element subset of $ S$ contains five numbers which are pairwise relatively prime.