Found problems: 175
Prove that every $1000$-element subset $M$ of the set $\{0,1,...,2001\}$ contains either a power of two or two distinct numbers whose sum is a power of two.
The set $S$ is a subset of $\{1, 2, \dots, 2025\}$ such that no two elements of $S$ differ by $2$ or by $7$. What is the largest number of elements that $S$ can have?
A positive integer $k$ is said to be [i]good [/i] if there exists a partition of $ \{1, 2, 3,..., 20\}$ into disjoint proper subsets such that the sum of the numbers in each subset of the partition is $k$. How many [i]good [/i] numbers are there?
Given is a set of $n\ge5$ people and $m$ commissions with $3$ persons in each. Let all the commissions be [i]nice[/i] if there are no two commissions $A$ and $B$, such that $\mid A\cap B\mid=1$. Find the biggest possible $m$ (as a function of $n$).
Let $ k,m,n$ be integers such that $ 1 < n \leq m \minus{} 1 \leq k.$ Determine the maximum size of a subset $ S$ of the set $ \{1,2,3, \ldots, k\minus{}1,k\}$ such that no $ n$ distinct elements of $ S$ add up to $ m.$
Let $p > 3$ be a given prime number. For a set $S \subseteq \mathbb{Z}$ and $a \in \mathbb{N}$ , define
$S_a = \{ x \in \{ 0,1, 2,...,p-1 \}$ | $(\exists_s \in S) x \equiv_p a \cdot s \}$ .
$(a)$ How many sets $S \subseteq \{ 1, 2,...,p-1 \} $ are there for which the sequence
$S_1 , S_2 , ..., S_{p-1}$ contains exactly two distinct terms?
$(b)$ Determine all numbers $k \in \mathbb{N}$ for which there is a set $ S \subseteq \{ 1, 2,...,p-1 \} $ such
that the sequence $S_1 , S_2 , ..., S_{p-1} $ contains exactly $k$ distinct terms.
[i]Proposed by Milan Basic and Milos Milosavljevic[/i]
Let $S = \{1,2,..., 2017\}$.
Find the maximal $n$ with the property that there exist $n$ distinct subsets of $S$ such that for no two subsets their union equals $S$.
Proposed by Gerhard Woeginger
Let $A_1,A_2,...,A_n$ be $n$ finite subsets of a set $X, n \ge 2$, such that
(i) $|A_i| \ge 2, 1 \le i \le n$,
(ii) $ |A_i \cap A_j | \ne 1, j \le i < j \le n$.
Prove that the elements of $A_1 \cup A_2 \cup ... \cup A_n$ may be colored with $2$ colors so that no $A_i$ is colored by the same color.
Is it possible to partition the set $A = \{1, 2, 3, ... , 32, 33\}$ into eleven subsets that contain three integers each, such that for every one of these eleven subsets, one of the integers is equal to the sum of the other two? If so, give such a partition, if not, prove that such a partition cannot exist.
Consider the set of natural numbers $ U = \{1,2,3, ..., 6024 \} $ Prove that for any partition of the $ U $ in three subsets with $ 2008 $ elements each, we can choose a number in each subset so that one of the numbers is the sum of the other two numbers.
Let $S = \{1, 2,..., 8\}$. How many ways are there to select two disjoint subsets of $S$?
Let $S = \{-17, -16, ..., 16, 17\}$. We call a subset $T$ of $S$ a good set if $-x \in T$ for all $x \in T$ and if $x, y, z \in T (x, y, z$ may be equal) then $x + y + z \ne 0$. Find the largest number of elements in a good set.
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.
What is the maximum number of subsets of size $5$, taken from the set $A=\{1,2,3,...,20\}$ such that any $2$ of them share exactly $1$ element.
Given the finite set $M$ with $m$ elements and $1986$ further sets $M_1,M_2,M_3,...,M_{1986}$, each of which contains more than $\frac{m}{2}$ elements from $M$ . Show that no more than ten elements need to be marked in order for any set $M_i$ ($i =1, 2, 3,..., 1986$) contains at least one marked element.
Consider the set of all $10$-digit numbers expressible with the help of figures $1$ and $2$ only. Divide it into two subsets so that the sum of any two numbers of the same subset is a number which is written with not less than two $3$’s.
We say that a subset \( T \) of \(\{1, 2, \dots, 2024\}\) is [b]kawaii[/b] if \( T \) has the following properties:
1. \( T \) has at least two distinct elements;
2. For any two distinct elements \( x \) and \( y \) of \( T \), \( x - y \) does not divide \( x + y \).
For example, the subset \( T = \{31, 71, 2024\} \) is [b]kawaii[/b], but \( T = \{5, 15, 75\} \) is not [b]kawaii[/b] because \( 15 - 5 = 10 \) divides \( 15 + 5 = 20 \).
What is the largest possible number of elements that a [b]kawaii [/b]subset can have?
Let $n \ge 1$ be a fixed positive integer. We consider all the sets $S$ which consist of sub-sequences of the sequence $0, 1,2, ..., n$ satisfying the following conditions:
i) If $(a_i)_{i=0}^k$ belongs to $S$, then $a_0 = 0$, $a_k = n$ and $a_{i+1} - a_i \le 2$ for all $0 \le i \le k - 1$.
ii) If $(a_i)_{i=0}^k$ and $(b_j)^h_{j=0}$ both belong to $S$, then there exist $0 \le i_0 \le k - 1$ and $0 \le j_0 \le h - 1$ such that $a_{i_0} = b_{j_0}$ and $a_{i_0+1} = b_{j_0+1}$.
Find the maximum value of $|S|$ (among all the above-mentioned sets $S$).
Let $m$ and $n$ be positive integers with $m > n \ge 2$. Set $S =\{1,2,...,m\}$, and set $T = \{a_1,a_2,...,a_n\}$ is a subset of $S$ such that every element of $S$ is not divisible by any pair of distinct elements of $T$. Prove that
$$\frac{1}{a_1}+\frac{1}{a_2}+ ...+ \frac{1}{a_n} < \frac{m+n}{m}$$
Find maximal value of positive integer $n$ such that there exists subset of $S=\{1,2,...,2001\}$ with $n$ elements, such that equation $y=2x$ does not have solutions in set $S \times S$
Let $ k,m,n$ be integers such that $ 1 < n \leq m \minus{} 1 \leq k.$ Determine the maximum size of a subset $ S$ of the set $ \{1,2,3, \ldots, k\minus{}1,k\}$ such that no $ n$ distinct elements of $ S$ add up to $ m.$
Let $A$ be a set, and let $P (A)$ be the powerset of all non-empty subsets of $A$. (For example, $A = \{1,2,3\}$, then $P (A) = \{\{1\},\{2\} ,\{3\},\{1,2\}, \{1,3\},\{2,3\}, \{1,2,3\}\}$.)
A subset $F$ of P $(A)$ is called [i]strong [/i] if the following is true:
If $B_1$ and $B_2$ are elements of $F$, then $B_1 \cup B_2$ is also an element of $F$.
Suppose that $F$ and $G$ are strong subsets of $P (A)$.
a) Is the union $F \cup G$ necessarily strong?
b) Is the intersection $F \cap G$ necessarily strong?
Let n be a natural number. Let $A_1, A_2, . . . , A_k$ be distinct $3$-element subsets of $\{1, 2, . . . , n\}$ such that $|A_i \cap A_j | \ne 1$ for all $1 \le i, j \le k$. Determine all $n$ for which there are $n$ such that these subsets exist.
[hide=original wording of last sentence]Bestimme alle n, fur die es n solche Teilmengen gibt.[/hide]
Given a finite set $S$, $P(S)$ denotes the set of all the subsets of $S$. For any $f:P(S)\rightarrow \mathbb{R}$ ,prove the following inequality:$$\sum_{A\in P(S)}\sum_{B\in P(S)}f(A)f(B)2^{\left| A\cap B \right|}\geq 0.$$
Let $M$ be the set of positive odd integers.
For every positive integer $n$, denote $A(n)$ the number of the subsets of $M$ whose sum of elements equals $n$.
For instance, $A(9) = 2$, because there are exactly two subsets of $M$ with the sum of their elements equal to $9$: $\{9\}$ and $\{1, 3, 5\}$.
a) Prove that $A(n) \le A(n + 1)$ for every integer $n \ge 2$.
b) Find all the integers $n \ge 2$ such that $A(n) = A(n + 1)$