2. Determine the largest possible number of non-empty, pairwise disjoint sets with the same sum of elements, into which the set can be divided:
a) $\{1,2, \ldots, 2017\}$,
b) $\{1,2, \ldots, 2018\}$.

If a set consists of a single number, we consider it as the sum of its elements.
SOLUTION. Let's first look at the sets with the smallest possible number of elements; we can probably have at most one one-element set - otherwise, those two one-element sets would not have the same sum of elements. The other sets are therefore at least two-element.

In part a), let's take the one-element set to be the one with the largest number, i.e., $\{2017\}$. All other sets will then be at least two-element and should have a sum of elements equal to 2017: the remaining numbers $1,2, \ldots, 2016$ can easily be divided into 1008 suitable sets $\{1,2016\},\{2,2015\}, \ldots,\{1008,1009\}$ with the desired sum of elements 2017.

According to the procedure just described, we can also divide the set $\{1,2, \ldots, 2018\}$ into 1009 sets $\{1,2018\},\{2,2017\}, \ldots,\{1009,1010\}$ with the same sum of elements equal to 2019.

Now we will show why in neither part a) nor b) can we create more than 1009 sets. Suppose there were at least 1010 such sets. Since at most one of them can be one-element and the others are at least two-element, the total number of all their elements would be at least $1+1009 \cdot 2=2019$, while we only have 2017 elements available in part a) and 2018 elements in part b).

Note. The sum of all numbers in part a) is $1009 \cdot 2017$ and in part b) $1009 \cdot 2019$. If we already guess that there should be 1009 sets, then the sum of elements in each individual set must be 2017 in part a) and 2019 in part b).

## GUIDING PROBLEMS:

N1. Find a formula for the sum of numbers $1+2+\ldots+n .[n(n+1) / 2]$

N2. Justify that if we divide 2000 pigeons into 1001 pigeonholes, there will be some pigeonhole that is either empty or contains only one pigeon. [If there were at least two pigeons in each pigeonhole, there would be at least $2 \cdot 1001=2002$ pigeons in total, which is a contradiction.]

D1. Into how many non-empty sets with the same sum can the set $\{1,2, \ldots, n\}$ be divided? [ $\lfloor (n+1) / 2\rfloor$, i.e., $(n+1) / 2$ if $n$ is odd, and $n / 2$ if $n$ is even]

D2. Into how many non-empty sets with sums of elements divisible by three can the set $\{1,2, \ldots, 3 m\}$ be divided? [An example of a division into $2 m$ sets is $m$ two-element sets $\{3 k-2,3 k-1\}$ and $m$ one-element sets $\{3 k\}$. We explain why a division into more than $2 m$ sets does not exist. In any suitable division, we can "peel off" any multiple of three from each multi-element set containing it as a one-element set, thus creating a more numerous division. Therefore, when looking for the relevant maximum, we can consider only divisions in which all $m$ multiples of three form one-element sets. Each of the other $2 m$ numbers then lies in some set with at least two elements, so there are at most $(3 m-m): 2=m$ multi-element sets.]

D3. Find a formula for the sum of numbers $1+3+5+\ldots+(2 n-1)$. $\left[n^{2}\right]$