Let $N$ be a positive integer, and consider an $N \times N$ grid. A [i]right-down path[/i] is a sequence of grid cells such that each cell is either one cell to the right of or one cell below the previous cell in the sequence. A [i]right-up path[/i] is a sequence of grid cells such that each cell is either one cell to the right of or one cell above the previous cell in the sequence. Prove that the cells of the $N \times N$ grid cannot be partitioned into less than $N$ right-down or right-up paths. For example, the following partition of the $5 \times 5$ grid uses $5$ paths. [asy] size(4cm); draw((5,-1)--(0,-1)--(0,-2)--(5,-2)--(5,-3)--(0,-3)--(0,-4)--(5,-4),gray+linewidth(0.5)+miterjoin); draw((1,-5)--(1,0)--(2,0)--(2,-5)--(3,-5)--(3,0)--(4,0)--(4,-5),gray+linewidth(0.5)+miterjoin); draw((0,0)--(5,0)--(5,-5)--(0,-5)--cycle,black+linewidth(2.5)+miterjoin); draw((0,-1)--(3,-1)--(3,-2)--(1,-2)--(1,-4)--(4,-4)--(4,-3)--(2,-3)--(2,-2),black+linewidth(2.5)+miterjoin); draw((3,0)--(3,-1),black+linewidth(2.5)+miterjoin); draw((1,-4)--(1,-5),black+linewidth(2.5)+miterjoin); draw((4,-3)--(4,-1)--(5,-1),black+linewidth(2.5)+miterjoin); [/asy] [i]Proposed by Zixiang Zhou, Canada[/i]

Prove that there are infinitely many n’s for which there exists a partition of $\{1,2,...,3n\}$ into subsets $\{a_1,...,a_n\}, \{b_1,...,b_n\}, \{c_1,...,c_n\}$ such that $a_i +b_i = c_i$ for all $i$, and prove that there are infinitely many $n$’s for which there is no such partition.

Let $0<f(1)<f(2)<f(3)<\ldots$ a sequence with all its terms positive$.$ The $n-th$ positive integer which doesn't belong to the sequence is $f(f(n))+1.$ Find $f(240).$

Can we partition the positive integers in two sets such that none of the sets contains an infinite arithmetic progression of nonzero ratio ?

In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals $Q_{1}, \ldots, Q_{24}$ whose corners are vertices of the 100-gon, so that [list] [*] the quadrilaterals $Q_{1}, \ldots, Q_{24}$ are pairwise disjoint, and [*] every quadrilateral $Q_{i}$ has three corners of one color and one corner of the other color. [/list]

Let P be a set of 4n points in the plane such that none of the three points are collinear. Prove that if n is large enough, then the following two statements are equivalent. (i) P can be divided into n four-element subsets such that each subset forms the vertices of a convex quadrilateral. (ii) P can not be split into two sets A and B, each with an odd number of elements, so that each convex quadrilateral whose vertices are in P has an even number of vertices in A and B.

Let $n$ be a positive integer, and let $A$ be a subset of $\{ 1,\cdots ,n\}$. An $A$-partition of $n$ into $k$ parts is a representation of n as a sum $n = a_1 + \cdots + a_k$, where the parts $a_1 , \cdots , a_k $ belong to $A$ and are not necessarily distinct. The number of different parts in such a partition is the number of (distinct) elements in the set $\{ a_1 , a_2 , \cdots , a_k \} $. We say that an $A$-partition of $n$ into $k$ parts is optimal if there is no $A$-partition of $n$ into $r$ parts with $r<k$. Prove that any optimal $A$-partition of $n$ contains at most $\sqrt[3]{6n}$ different parts.

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]

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.

Let be a function $ s:\mathbb{N}^2\longrightarrow \mathbb{N} $ that sends $ (m,n) $ to the number of solutions in $ \mathbb{N}^n $ of the equation: $$ x_1+x_2+\cdots +x_n=m $$ [b]1)[/b] Prove that: $$ s(m+1,n+1)=s(m,n)+s(m,n+1) =\prod_{r=1}^n\frac{m-r+1}{r} ,\quad\forall m,n\in\mathbb{N} $$ [b]2)[/b] Find $ \max\left\{ a_1a_2\cdots a_{20}\bigg| a_1+a_2+\cdots +a_{20}=2007, a_1,a_2,\ldots a_{20}\in\mathbb{N} \right\} . $

Let $n_1, n_2$ be positive integers. Consider in a plane $E$ two disjoint sets of points $M_1$ and $M_2$ consisting of $2n_1$ and $2n_2$ points, respectively, and such that no three points of the union $M_1 \cup M_2$ are collinear. Prove that there exists a straightline $g$ with the following property: Each of the two half-planes determined by $g$ on $E$ ($g$ not being included in either) contains exactly half of the points of $M_1$ and exactly half of the points of $M_2.$

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]

$(HUN 3)$ In the plane $4000$ points are given such that each line passes through at most $2$ of these points. Prove that there exist $1000$ disjoint quadrilaterals in the plane with vertices at these points.

Find all positive integers $n$ such that the set $\{n,n+1,n+2,n+3,n+4,n+5\}$ can be partitioned into two subsets so that the product of the numbers in each subset is equal.

Determine for which positive integers $ k$ the set \[ X \equal{} \{1990, 1990 \plus{} 1, 1990 \plus{} 2, \ldots, 1990 \plus{} k\}\] can be partitioned into two disjoint subsets $ A$ and $ B$ such that the sum of the elements of $ A$ is equal to the sum of the elements of $ B.$

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.

We call a set of integers $\textit{special}$ if it has $4$ elements and can be partitioned into $2$ disjoint subsets $\{ a,b \}$ and $\{ c, d \}$ such that $ab - cd = 1$. For every positive integer $n$, prove that the set $\{ 1, 2, \dots, 4n \}$ cannot be partitioned into $n$ disjoint special sets. [i]Proposed by Mohsen Jamali, Iran[/i]

In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals $Q_{1}, \ldots, Q_{24}$ whose corners are vertices of the 100-gon, so that [list] [*] the quadrilaterals $Q_{1}, \ldots, Q_{24}$ are pairwise disjoint, and [*] every quadrilateral $Q_{i}$ has three corners of one color and one corner of the other color. [/list]

Prove that the set of positive integers cannot be partitioned into three nonempty subsets such that, for any two integers $x,y$ taken from two different subsets, the number $x^2-xy+y^2$ belongs to the third subset.

Show that there exists an integer $N$ such that for all $n \ge N$ a square can be partitioned into $n$ smaller squares.

Let $n_1, n_2$ be positive integers. Consider in a plane $E$ two disjoint sets of points $M_1$ and $M_2$ consisting of $2n_1$ and $2n_2$ points, respectively, and such that no three points of the union $M_1 \cup M_2$ are collinear. Prove that there exists a straightline $g$ with the following property: Each of the two half-planes determined by $g$ on $E$ ($g$ not being included in either) contains exactly half of the points of $M_1$ and exactly half of the points of $M_2.$

In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals $Q_{1}, \ldots, Q_{24}$ whose corners are vertices of the 100-gon, so that [list] [*] the quadrilaterals $Q_{1}, \ldots, Q_{24}$ are pairwise disjoint, and [*] every quadrilateral $Q_{i}$ has three corners of one color and one corner of the other color. [/list]

The Euclidian three-dimensional space has been partitioned into three nonempty sets $A_1,A_2,A_3$. Show that one of these sets contains, for each $d > 0$, a pair of points at mutual distance $d$.

$k > 1$ is fixed. Show that for $n$ sufficiently large for every partition of $\{1,2,\dots,n\}$ into $k$ disjoint subsets we can find $a \neq b$ such that $a$ and $b$ are in the same subset and $a+1$ and $b+1$ are in the same subset. What is the smallest $n$ for which this is true?

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.$