Found problems: 175
Let $S$ be a set consisting of $n$ elements, $F$ a set of subsets of $S$ consisting of $2^{n-1}$ subsets such that every three such subsets have a non-empty intersection.
a) Show that the intersection of all subsets of $F$ is not empty.
b) If you replace the number of sets from $2^{n-1}$ with $2^{n-1}-1$, will the previous answer change?
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.
Let $X= \{A_1, A_2, A_3, A_4\}$ be a set of four distinct points in the plane. Show that there exists a subset $Y$ of $X$ with the property that there is no (closed) disk $K$ such that $K\cap X = Y$.
Given an integer $m\ge 2$, find the smallest integer $k > m$ such that for any partition of the set $\{m,m + 1,..,k\}$ into two classes $A$ and $B$ at least one of the classes contains three numbers $a,b,c$ (not necessarily distinct) such that $a^b = c$.
Let $X$ be a subset of $R_{+}^{*}$ with $m$ elements.
Find $X$ such that the number of subsets with the same sum is maximum.
The set of all $10$-digit numbers may be represented as a union of two subsets: the subset $M$ consisting of all $10$-digit numbers, each of which may be represented as a product of two $5$-digit numbers, and the subset $N$ , containing the remaining $10$-digit numbers . Which of the sets $M$ and $N$ contains more elements?
(S. Fomin , Leningrad)
Let $m,n$ be positive integers with $m \le n$, and let $F$ be a family of $m$-element subsets of $\{1,2,...,n\}$ satisfying $A \cap B \ne \varnothing$ for all $A,B \in F$. Determine the maximum possible number of elements in $F$.
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$)
Given a positive integer $n$, show that the set $\{1,2,...,n\}$ can be partitioned into $m$ sets, each with the same sum, if and only if m is a divisor of $\frac{n(n + 1)}{2}$ which does not exceed $\frac{n + 1}{2}$.
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.
Assume that $M \subset N$ has the property that every two numbers $m,n$ of $M$ satisfy $|m-n| \ge mn/25$.
Prove that the set $M$ contains no more than $9$ elements.
Decide whether there exists such set M.
Determine for which $m$ there exist exactly $2^{15}$ subsets $X$ of $\{1,2,...,47\}$ with the following property: $m$ is the smallest element of $X$, and for every $x \in X$, either $x+m \in X$ or $x+m > 47$.
Let $S$ be the set $\{1, 2, ..., 10\}$. Let $A$ be a subset of $S$.
We arrange the elements of $A$ in increasing order, that is, $A = \{a_1, a_2, ...., a_k\}$ with $a_1 < a_2 < ... < a_k$.
Define [i]WSUM [/i] for this subset as $3(a_1 + a_3 +..) + 2(a_2 + a_4 +...)$ where the first term contains the odd numbered terms and the second the even numbered terms.
(For example, if $A = \{2, 5, 7, 8\}$, [i]WSUM [/i] is $3(2 + 7) + 2(5 + 8)$.)
Find the sum of [i]WSUMs[/i] over all the subsets of S.
(Assume that WSUM for the null set is $0$.)
Let $m,n$ be integers so that $m \ge n > 1$. Let $F_1,...,F_k$ be a collection of $n$-element subsets of $\{1,...,m\}$ so that $F_i\cap F_j$ contains at most $1$ element, $1 \le i < j \le k$. Show that $k\le \frac{m(m-1)}{n(n-1)} $
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$ .
For $ n\ge 2$, let $ S_1$, $ S_2$, $ \ldots$, $ S_{2^n}$ be $ 2^n$ subsets of $ A \equal{} \{1, 2, 3, \ldots, 2^{n \plus{} 1}\}$ that satisfy the following property: There do not exist indices $ a$ and $ b$ with $ a < b$ and elements $ x$, $ y$, $ z\in A$ with $ x < y < z$ and $ y$, $ z\in S_a$, and $ x$, $ z\in S_b$. Prove that at least one of the sets $ S_1$, $ S_2$, $ \ldots$, $ S_{2^n}$ contains no more than $ 4n$ elements.
[i]Proposed by Gerhard Woeginger, Netherlands[/i]
Given any set of $14$ (different) natural numbers, prove that for some $k$ ($1 \le k \le 7$) there exist two disjoint $k$-element subsets $\{a_1,...,a_k\}$ and $\{b_1,...,b_k\}$ such that $A =\frac{1}{a_1}+\frac{1}{a_2}+...+\frac{1}{a_k}$ and $B =\frac{1}{b_1}+\frac{1}{b_2}+...+\frac{1}{b_k}$ differ by less than $0.001$, i.e. $|A-B| < 0.001$
Let $\mathbf M\subseteq\mathbb R^2$ be a set with the following properties:
1) there is a pair $(a,b)\in\mathbf M$ such that $ab(a-b)\neq0,$
2) if $\left(x_1,y_1\right),\left(x_2,y_2\right)\in\mathbf M$ and $c\in\mathbb R$ then also \[\left(cx_1,cy_1\right),\left(x_1+x_2,y_1+y_2\right),\left(x_1x_2,y_1y_2\right)\in\mathbf M.\]
Show that in fact \[\mathbf M=\mathbb R^2.\]
Let $n \ge 3$ be a natural number.
Determine the number $a_n$ of all subsets of $\{1, 2,...,n\}$ consisting of three elements such that one of them is the arithmetic mean of the other two.
[i]Proposed by Walther Janous[/i]
Let $n \geq 2, n \in \mathbb{N}$ and $A_0 = (a_{01},a_{02}, \ldots, a_{0n})$ be any $n-$tuple of natural numbers, such that $0 \leq a_{0i} \leq i-1,$ for $i = 1, \ldots, n.$
$n-$tuples $A_1= (a_{11},a_{12}, \ldots, a_{1n}), A_2 = (a_{21},a_{22}, \ldots, a_{2n}), \ldots$ are defined by: $a_{i+1,j} = Card \{a_{i,l}| 1 \leq l \leq j-1, a_{i,l} \geq a_{i,j}\},$ for $i \in \mathbb{N}$ and $j = 1, \ldots, n.$ Prove that there exists $k \in \mathbb{N},$ such that $A_{k+2} = A_{k}.$
The numbers from$ 1$ to $2016$ are divided into three (disjoint) subsets $A, B$ and $C$, each one contains exactly $672$ numbers. Prove that you can find three numbers, each from a different subset, such that the sum of two of them is equal to the third.
[hide=original wording]Skaitļi no 1 līdz 2016 ir sadalīti trīs (nešķeļošās) apakškopās A, B un C, katranotām satur tieši 672 skaitļus. Pierādīt, ka var atrast trīs tādus skaitļus, katru no citas apakškopas, ka divu no tiem summa ir vienāda ar trešo.
[/hide]
A sequence $\{an\}$ of positive integers is defined by
\[a_n=\left[ n +\sqrt n + \frac 12 \right] , \qquad \forall n \in \mathbb N\]
Determine the positive integers that occur in the sequence.
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)$)
Let $p$ be an odd prime. Determine the number of nonempty subsets from $\{1, 2, \dots, p - 1\}$ for which the sum of its elements is divisible by $p$.
find all $k$ distinct integers $a_1,a_2,...,a_k$ such that there exists an injective function $f$ from reals to themselves such that for each positive integer $n$ we have
$$\{f^n(x)-x| x \in \mathbb{R} \}=\{a_1+n,a_2+n,...,a_k+n\}$$.