Found problems: 19
2021 European Mathematical Cup, 4
Let $n$ be a positive integer. Morgane has coloured the integers $1,2,\ldots,n$. Each of them is coloured in exactly one colour. It turned out that for all positive integers $a$ and $b$ such that $a<b$ and $a+b \leqslant n$, at least two of the integers among $a$, $b$ and $a+b$ are of the same colour. Prove that there exists a colour that has been used for at least $2n/5$ integers. \\ \\
(Vincent Jugé)
2008 Korea Junior Math Olympiad, 4
Let $N$ be the set of positive integers. If $A,B,C \ne \emptyset$, $A \cap B = B \cap C = C \cap A = \emptyset$ and $A \cup B \cup C = N$, we say that $A,B,C$ are partitions of $N$. Prove that there are no partitions of $N, A,B,C$, that satis fy the following:
(i) $\forall a \in A, b \in B$, we have $a + b + 1 \in C$
(ii) $\forall b \in B, c \in C$, we have $b + c + 1 \in A$
(iii) $\forall c \in C, a \in A$, we have $c + a + 1 \in B$
Novosibirsk Oral Geo Oly VIII, 2022.6
Anton has an isosceles right triangle, which he wants to cut into $9$ triangular parts in the way shown in the picture. What is the largest number of the resulting $9$ parts that can be equilateral triangles?
A more formal description of partitioning. Let triangle $ABC$ be given. We choose two points on its sides so that they go in the order $AC_1C_2BA_1A_2CB_1B_2$, and no two coincide. In addition, the segments $C_1A_2$, $A_1B_2$ and $B_1C_2$ must intersect at one point. Then the partition is given by segments $C_1A_2$, $A_1B_2$, $B_1C_2$, $A_1C_2$, $B_1A_2$ and $C_1B_2$.
[img]https://cdn.artofproblemsolving.com/attachments/0/5/5dd914b987983216342e23460954d46755d351.png[/img]
2020 Canadian Mathematical Olympiad Qualification, 2
Given a set $S$, of integers, an [i]optimal partition[/i] of S into sets T, U is a partition which minimizes the value $|t - u|$, where $t$ and $u$ are the sum of the elements of $T$ and U respectively.
Let $P$ be a set of distinct positive integers such that the sum of the elements of $P$ is $2k$ for a positive integer $k$, and no subset of $P$ sums to $k$.
Either show that there exists such a $P$ with at least $2020$ different optimal partitions, or show that such a $P$ does not exist.
2022 Junior Balkan Mathematical Olympiad, 4
We call an even positive integer $n$ [i]nice[/i] if the set $\{1, 2, \dots, n\}$ can be partitioned into $\frac{n}{2}$ two-element subsets, such that the sum of the elements in each subset is a power of $3$. For example, $6$ is nice, because the set $\{1, 2, 3, 4, 5, 6\}$ can be partitioned into subsets $\{1, 2\}$, $\{3, 6\}$, $\{4, 5\}$. Find the number of nice positive integers which are smaller than $3^{2022}$.
2021 Indonesia TST, N
For every positive integer $n$, let $p(n)$ denote the number of sets $\{x_1, x_2, \dots, x_k\}$ of integers with $x_1 > x_2 > \dots > x_k > 0$ and $n = x_1 + x_3 + x_5 + \dots$ (the right hand side here means the sum of all odd-indexed elements). As an example, $p(6) = 11$ because all satisfying sets are as follows: $$\{6\}, \{6, 5\}, \{6, 4\}, \{6, 3\}, \{6, 2\}, \{6, 1\}, \{5, 4, 1\}, \{5, 3, 1\}, \{5, 2, 1\}, \{4, 3, 2\}, \{4, 3, 2, 1\}.$$ Show that $p(n)$ equals to the number of partitions of $n$ for every positive integer $n$.
2015 Junior Balkan Team Selection Tests - Romania, 3
Can we partition the positive integers in two sets such that none of the sets contains an infinite arithmetic progression of nonzero ratio ?
1987 IMO Shortlist, 11
Find the number of partitions of the set $\{1, 2, \cdots, n\}$ into three subsets $A_1,A_2,A_3$, some of which may be empty, such that the following conditions are satisfied:
$(i)$ After the elements of every subset have been put in ascending order, every two consecutive elements of any subset have different parity.
$(ii)$ If $A_1,A_2,A_3$ are all nonempty, then in exactly one of them the minimal number is even .
[i]Proposed by Poland.[/i]
2018 India PRMO, 22
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?
2022 JBMO Shortlist, C4
We call an even positive integer $n$ [i]nice[/i] if the set $\{1, 2, \dots, n\}$ can be partitioned into $\frac{n}{2}$ two-element subsets, such that the sum of the elements in each subset is a power of $3$. For example, $6$ is nice, because the set $\{1, 2, 3, 4, 5, 6\}$ can be partitioned into subsets $\{1, 2\}$, $\{3, 6\}$, $\{4, 5\}$. Find the number of nice positive integers which are smaller than $3^{2022}$.
2004 Junior Tuymaada Olympiad, 4
Given the disjoint finite sets of natural numbers $ A $ and $ B $, consisting of $ n $ and $ m $ elements, respectively. It is known that every natural number belonging to $ A $ or $ B $ satisfies at least one of the conditions $ k + 17 \in A $, $ k-31 \in B $. Prove that $ 17n = 31m $
2022 Novosibirsk Oral Olympiad in Geometry, 6
Anton has an isosceles right triangle, which he wants to cut into $9$ triangular parts in the way shown in the picture. What is the largest number of the resulting $9$ parts that can be equilateral triangles?
A more formal description of partitioning. Let triangle $ABC$ be given. We choose two points on its sides so that they go in the order $AC_1C_2BA_1A_2CB_1B_2$, and no two coincide. In addition, the segments $C_1A_2$, $A_1B_2$ and $B_1C_2$ must intersect at one point. Then the partition is given by segments $C_1A_2$, $A_1B_2$, $B_1C_2$, $A_1C_2$, $B_1A_2$ and $C_1B_2$.
[img]https://cdn.artofproblemsolving.com/attachments/0/5/5dd914b987983216342e23460954d46755d351.png[/img]
2009 Jozsef Wildt International Math Competition, W. 6
Prove that$$p (n)= 2+ \left (p (1) + \cdots + p\left ( \left [\frac {n}{2} \right ] + \chi_1 (n)\right ) + \left (p'_2(n) + \cdots + p' _{ \left [\frac {n}{2} \right ] - 1}(n)\right )\right )$$for every $n \in \mathbb {N}$ with $n>2$ where $\chi $ denotes the principal character Dirichlet modulo 2, i.e.$$ \chi _1 (n) = \begin{cases} 1 & \text{if } (n,2)=1 \\ 0 &\text{if } (n,2)>1 \end{cases} $$with $p (n) $ we denote number of possible partitions of $n $ and $p' _m(n) $ we denote the number of partitions of $n$ in exactly $m$ sumands.
1978 Romania Team Selection Test, 3
Let $ p $ be a natural number and let two partitions $ \mathcal{A} =\left\{ A_1,A_2,...,A_p\right\} ,\mathcal{B}=\left\{ B_1,B_2,...B_p\right\} $ of a finite set $ \mathcal{M} . $ Knowing that, whenever an element of $ \mathcal{A} $ doesn´t have any elements in common with another of $ \mathcal{B} , $ it holds that the number of elements of these two is greater than $ p, $ prove that $ \big| \mathcal{M}\big|\ge\frac{1}{2}\left( 1+p^2\right) . $ Can equality hold?
2015 Korea National Olympiad, 4
For positive integers $n, k, l$, we define the number of $l$-tuples of positive integers $(a_1,a_2,\cdots a_l)$ satisfying the following as $Q(n,k,l)$.
(i): $n=a_1+a_2+\cdots +a_l$
(ii): $a_1>a_2>\cdots > a_l > 0$.
(iii): $a_l$ is an odd number.
(iv): There are $k$ odd numbers out of $a_i$.
For example, from $9=8+1=6+3=6+2+1$, we have $Q(9,1,1)=1$, $Q(9,1,2)=2$, $Q(9,1,3)=1$.
Prove that if $n>k^2$, $\sum_{l=1}^n Q(n,k,l)$ is $0$ or an even number.
1987 IMO Longlists, 48
Find the number of partitions of the set $\{1, 2, \cdots, n\}$ into three subsets $A_1,A_2,A_3$, some of which may be empty, such that the following conditions are satisfied:
$(i)$ After the elements of every subset have been put in ascending order, every two consecutive elements of any subset have different parity.
$(ii)$ If $A_1,A_2,A_3$ are all nonempty, then in exactly one of them the minimal number is even .
[i]Proposed by Poland.[/i]
2021 Indonesia TST, N
For every positive integer $n$, let $p(n)$ denote the number of sets $\{x_1, x_2, \dots, x_k\}$ of integers with $x_1 > x_2 > \dots > x_k > 0$ and $n = x_1 + x_3 + x_5 + \dots$ (the right hand side here means the sum of all odd-indexed elements). As an example, $p(6) = 11$ because all satisfying sets are as follows: $$\{6\}, \{6, 5\}, \{6, 4\}, \{6, 3\}, \{6, 2\}, \{6, 1\}, \{5, 4, 1\}, \{5, 3, 1\}, \{5, 2, 1\}, \{4, 3, 2\}, \{4, 3, 2, 1\}.$$ Show that $p(n)$ equals to the number of partitions of $n$ for every positive integer $n$.
1988 Spain Mathematical Olympiad, 5
A well-known puzzle asks for a partition of a cross into four parts which are to be reassembled into a square. One solution is exhibited on the picture.
[img]https://cdn.artofproblemsolving.com/attachments/9/1/3b8990baf5e37270c640e280c479b788d989ba.png[/img]
Show that there are infinitely many solutions. (Some solutions split the cross into four equal parts!)
2003 Gheorghe Vranceanu, 4
Prove that among any $ 16 $ numbers smaller than $ 101 $ there are four of them that have the property that the sum of two of them is equal to the sum of the other two.