Found problems: 149
2019 Canadian Mathematical Olympiad Qualification, 4
Let $n$ be a positive integer. For a positive integer $m$, we partition the set $\{1, 2, 3,...,m\}$ into $n$ subsets, so that the product of two different elements in the same subset is never a perfect square. In terms of $n$, fi nd the largest positive integer $m$ for which such a partition exists.
1974 Putnam, B6
For a set with $n$ elements, how many subsets are there whose cardinality is respectively $\equiv 0$ (mod $3$), $\equiv 1$ (mod $3$), $ \equiv 2$ (mod $3$)? In other words, calculate
$$s_{i,n}= \sum_{k\equiv i \;(\text{mod} \;3)} \binom{n}{k}$$
for $i=0,1,2$. Your result should be strong enough to permit direct evaluation of the numbers $s_{i,n}$ and to show clearly the relationship of $s_{0,n}, s_{1,n}$ and $s_{2,n}$ to each other for all positive integers $n$. In particular, show the relationships among these three sums for $n = 1000$.
2011 Korea Junior Math Olympiad, 8
There are $n$ students each having $r$ positive integers. Their $nr$ positive integers are all different. Prove that we can divide the students into $k$ classes satisfying the following conditions:
(a) $k \le 4r$
(b) If a student $A$ has the number $m$, then the student $B$ in the same class can't have a number $\ell$ such that $(m - 1)! < \ell < (m + 1)! + 1$
1999 Austrian-Polish Competition, 1
Find the number of $6$-tuples $(A_1,A_2,...,A_6)$ of subsets of $M = \{1,..., n\}$ (not necessarily different) such that each element of $M$ belongs to zero, three, or six of the subsets $A_1,...,A_6$.
2005 Singapore Senior Math Olympiad, 3
Let $S$ be a subset of $\{1,2,3,...,24\}$ with $n(S)=10$. Show that $S$ has two $2$-element subsets $\{x,y\}$ and $\{u,v\}$ such that $x+y=u+v$
2007 Indonesia TST, 4
Given a collection of sets $X = \{A_1, A_2, ..., A_n\}$. A set $\{a_1, a_2, ..., a_n\}$ is called a single representation of $X$ if $a_i \in A_i$ for all i. Let $|S| = mn$, $S = A_1\cup A_2 \cup ... \cup A_n = B_1 \cup B_2 \cup ... \cup B_n$ with $|A_i| = |B_i| = m$ for all $i$. Prove that $S = C_1 \cup C_2 \cup ... \cup C_n$ where for every $i, C_i $ is a single represenation for $\{A_j\}_{j=1}^n $and $\{B_j\}_{j=1}^n$.
1991 Spain Mathematical Olympiad, 2
Given two distinct elements $a,b \in \{-1,0,1\}$, consider the matrix $A$ .
Find a subset $S$ of the set of the rows of $A$, of minimum size, such that every other row of $A$ is a linear combination of the rows in $S$ with integer coefficients.
1994 Bulgaria National Olympiad, 6
Let $n$ be a positive integer and $A$ be a family of subsets of the set $\{1,2,...,n\},$ none of which contains another subset from A . Find the largest possible cardinality of $A$ .
2008 Postal Coaching, 4
Consider the set $A = \{1, 2, ..., n\}$, where $n \in N, n \ge 6$. Show that $A$ is the union of three pairwise disjoint sets, with the same cardinality and the same sum of their elements, if and only if $n$ is a multiple of $3$.
2007 Indonesia TST, 4
Given a collection of sets $X = \{A_1, A_2, ..., A_n\}$. A set $\{a_1, a_2, ..., a_n\}$ is called a single representation of $X$ if $a_i \in A_i$ for all i. Let $|S| = mn$, $S = A_1\cup A_2 \cup ... \cup A_n = B_1 \cup B_2 \cup ... \cup B_n$ with $|A_i| = |B_i| = m$ for all $i$. Prove that $S = C_1 \cup C_2 \cup ... \cup C_n$ where for every $i, C_i $ is a single represenation for $\{A_j\}_{j=1}^n $and $\{B_j\}_{j=1}^n$.
2012 India Regional Mathematical Olympiad, 4
Let $X=\{1,2,3,...,10\}$. Find the number of pairs of $\{A,B\}$ such that $A\subseteq X, B\subseteq X, A\ne B$ and $A\cap B=\{2,3,5,7\}$.
2001 Croatia Team Selection Test, 1
Consider $A = \{1, 2, ..., 16\}$. A partition of $A$ into nonempty sets $A_1, A_2,..., A_n$ is said to be good if none of the Ai contains elements $a, b, c$ (not necessarily distinct) such that $a = b + c$.
(a) Find a good partition $\{A_1, A_2, A_3, A_4\}$ of $A$.
(b) Prove that no partition $\{A_1, A_2, A_3\}$ of $A$ is good
1999 IMO Shortlist, 7
Let $p >3$ be a prime number. For each nonempty subset $T$ of $\{0,1,2,3, \ldots , p-1\}$, let $E(T)$ be the set of all $(p-1)$-tuples $(x_1, \ldots ,x_{p-1} )$, where each $x_i \in T$ and $x_1+2x_2+ \ldots + (p-1)x_{p-1}$ is divisible by $p$ and let $|E(T)|$ denote the number of elements in $E(T)$. Prove that
\[|E(\{0,1,3\})| \geq |E(\{0,1,2\})|\]
with equality if and only if $p = 5$.
2019 Purple Comet Problems, 16
Find the number of ordered triples of sets $(T_1, T_2, T_3)$ such that
1. each of $T_1, T_2$, and $T_3$ is a subset of $\{1, 2, 3, 4\}$,
2. $T_1 \subseteq T_2 \cup T_3$,
3. $T_2 \subseteq T_1 \cup T_3$, and
4. $T_3\subseteq T_1 \cup T_2$.
2010 Miklós Schweitzer, 3
Let $ A_i,i=1,2,\dots,t$ be distinct subsets of the base set $\{1,2,\dots,n\}$ complying to the following condition
$$ \displaystyle A_ {i} \cap A_ {k} \subseteq A_ {j}$$for any $1 \leq i <j <k \leq t.$ Find the maximum value of $t.$
Thanks @dgrozev
2012 Ukraine Team Selection Test, 12
We shall call the triplet of numbers $a, b, c$ of the interval $[-1,1]$ [i]qualitative [/i] if these numbers satisfy the inequality $1 + 2abc\ge a^2 + b^2 + c^2$. Prove that when the triples $a, b, c$, and $x, y, z$ are qualitative, then $ax, by, cz$ is also qualitative.
2022 Chile TST IMO, 1
The sets of rational numbers $A = \{a_1, \dots, a_5\}$ and $B = \{b_1, \dots, b_5\}$ both contain $0$ and satisfy the condition that
$$ \{a_i + b_j\}_{i,j} = \{0, 1, 2, \dots, 23, 24\}. $$
Determine these sets. (The set $\{a_i + b_j\}_{i,j}$ consists of all possible sums between an element of $A$ and an element of $B$)
1969 IMO Shortlist, 42
$(MON 3)$ Let $A_k (1 \le k \le h)$ be $n-$element sets such that each two of them have a nonempty intersection. Let $A$ be the union of all the sets $A_k,$ and let $B$ be a subset of $A$ such that for each $k (1\le k \le h)$ the intersection of $A_k$ and $B$ consists of exactly two different elements $a_k$ and $b_k$. Find all subsets $X$ of the set $A$ with $r$ elements satisfying the condition that for at least one index $k,$ both elements $a_k$ and $b_k$ belong to $X$.
2005 National Olympiad First Round, 24
There are $20$ people in a certain community. $10$ of them speak English, $10$ of them speak German, and $10$ of them speak French. We call a [i]committee[/i] to a $3$-subset of this community if there is at least one who speaks English, at least one who speaks German, and at least one who speaks French in this subset. At most how many commitees are there in this community?
$
\textbf{(A)}\ 120
\qquad\textbf{(B)}\ 380
\qquad\textbf{(C)}\ 570
\qquad\textbf{(D)}\ 1020
\qquad\textbf{(E)}\ 1140
$
2008 Indonesia TST, 1
Let $A$ be the subset of $\{1, 2, ..., 16\}$ that has $6$ elements. Prove that there exist $2$ subsets of $A$ that are disjoint, and the sum of their elements are the same.
2008 Indonesia TST, 2
Let $S = \{1, 2, 3, ..., 100\}$ and $P$ is the collection of all subset $T$ of $S$ that have $49$ elements, or in other words: $$P = \{T \subset S : |T| = 49\}.$$ Every element of $P$ is labelled by the element of $S$ randomly (the labels may be the same). Show that there exist subset $M$ of $S$ that has $50$ members such that for every $x \in M$, the label of $M -\{x\}$ is not equal to $x$
1991 Poland - Second Round, 5
$ P_1, P_2, \ldots, P_n $ are different two-element subsets of $ \{1,2,\ldots,n\} $. The sets $ P_i $, $ P_j $ for $ i\neq j $ have a common element if and only if the set $ \{i,j\} $ is one of the sets $ P_1, P_2, \ldots, P_n $. Prove that each of the numbers $ 1,2,\ldots,n $ is a common element of exactly two sets from $ P_1, P_2, \ldots, P_n $.
2022 Bulgarian Spring Math Competition, Problem 11.4
Let $n \geq 2$ be a positive integer. The set $M$ consists of $2n^2-3n+2$ positive rational numbers. Prove that there exists a subset $A$ of $M$ with $n$ elements with the following property: $\forall$ $2 \leq k \leq n$ the sum of any $k$ (not necessarily distinct) numbers from $A$ is not in $A$.
2004 Switzerland Team Selection Test, 1
Let $S$ be the set of all n-tuples $(X_1,...,X_n)$ of subsets of the set $\{1,2,..,1000\}$, not necessarily different and not necessarily nonempty. For $a = (X_1,...,X_n)$ denote by $E(a)$ the number of elements of $X_1\cup ... \cup X_n$. Find an explicit formula for the sum $\sum_{a\in S} E(a)$
2004 Korea Junior Math Olympiad, 2
For $n\geq3$ define $S_n=\{1, 2, ..., n\}$. $A_1, A_{2}, ..., A_{n}$ are given subsets of $S_n$, each having an even number of elements. Prove that there exists a set $\{i_1, i_2, ..., i_t\}$, a nonempty subset of $S_n$ such that
$$A_{i_1} \Delta A_{i_2} \Delta \ldots \Delta A_{i_t}=\emptyset$$
(For two sets $A, B$, we define $\Delta$ as $A \Delta B=(A\cup B)-(A\cap B)$)