Unread post
by **ahmedittihad** » Mon Feb 20, 2017 3:59 pm

Solution to problem 2

We will show that $k=3$ is the greatest we can achieve.

Construction for $k=3$,

We let,

the first three terms of $A_1 = \{7,8,9\}$. The next terms are in the form of $3n+1$ where $n=\{3,4,5....\}$.

the first three terms of $A_2 = \{4,5,6\}$. The next terms are in the form of $3n+2$ where $n=\{3,4,5...\}$.

the first three terms of $A_3 = \{1,2,3\}$. The next terms are in the form of $3n$ where $n=\{4,5,6....\}$.

This construction indeed covers all integers more than $14$.

Now, we show that $k=3$ is the best we can do,

Assume that there is a partition for $k=4$.

We will add elements to $A_1$ to make sums of $15$, $16$, $17$....

To get $15$ in a partition, we need $A_1=\{a_1, 15-a_1\}$.

To get $16$ in a partition, we need \begin{align*}

A_1=&\{a_1, a_1+1, 15-a_1\}\\

\text{ or }&\{a_1, 15-a_1, 16-a_1\}

\end{align*}

To get $17$ in a partition, we need \begin{align*}

A_1=&\{a_1, a_1+1, 15-a_1, 16-a_1\}\\

\text{ or }&\{a_1, a_1+1, 15-a_1, 17-a_1\}\\

\text{ or }&\{a_1, a_1+1, a_1+2, 15-a_1\}\\

\text{ or }&\{a_1, 15-a_1, 16-a_1, 17-a_1\}\\

\text{ or }&\{a_1, a_1+2, 15-a_1, 16-a_1\}

\end{align*}

As there are $4$ partitions, all the numbers from $1$ to $16$ are used to get sum of $15, 16, 17$.

From casework, we get that the only possibility of $$\{A_1, A_2, A_3, A_4\}=\{\{1, 14, 15, 16\}, \{2, 3, 4, 13\}, \{5, 10, 11, 12\}, \{6, 7, 8, 9\}\}$$.

Here, we cannot add any numbers to the partitions to make them have sum $18$. We get a contradiction.

Frankly, my dear, I don't give a damn.