2
$\begingroup$

Determine the greatest positive integer $k$ that satisfies the following property.
The set of positive integers can be partitioned into $k$ subsets $A_1,A_2,A_3,\ldots,A_k$ such that for all integers $n\ge 15$ and all $i\in\{1,2,\ldots,k\}$ there exist two distinct elements of $A_i$ such that their sum is $n$.

$\endgroup$
3
$\begingroup$

The greatest such number is $3$

First we are going to show that there exists a construction for $k = 3$ and then we are going to prove that $k \not\ge 4$

PART 1

We build the 3 sets $A_1,A_2\ and\ A_3$ as:

$$ \begin{align} \\&A_1 = \{1,2,3\} \cup \{3m\ |\ m \ge\ 4\} \\&A_2 = \{4,5,6\} \cup \{3m - 1\ |\ m \ge\ 4\} \\&A_3 = \{7,8,9\} \cup \{3m - 2\ |\ m \ge\ 4\} \end{align} $$

Here we easily see that,

  • all $n\ge13$ can be represented as the sum of two unique elements of $A_1$
  • all $n\ge15$ can be represented as the sum of two unique elements of $A_2$
  • all $n\ge17$ can be represented as the sum of two unique elements of $A_3$

So we are only left to see that $15\ and\ 16$ can be represented as the sum of two distinct elements of $A_3$ which is given by:

$$ \\15 = 7+8 \\16 = 7+9 $$

PART 2

Here we prove that $k \not\ge 4$

Let us assume that such a construction exists for $k \ge 4$. So let the sets $A_1,A_2,A_3...A_k$ satisfy the condition for $k \ge 4$

If $A_1,A_2,A_3...A_k$ satisfy the conditions, so does $A_1,A_2,A_3,A_4 \cup A_5 \cup A_6 \cup...\cup A_k$

Thus we assume that $k = 4$

$\therefore$ we assume the sets to be $A_1,A_2,A_3\ and\ A_4$

Now, we construct sets $B_1,B_2,B_3\ and\ B_4$ such that $B_i = A_i \cap \{1,2,3...,23\}$

Then $\forall i \in {1,2,3,4}$ each of the $10$ numbers $15,16,17...,24$ can be represented as the sum of two distinct numbers in $B_i$

$\therefore$ we must have $n = |B_i|$ such that $\binom{n}{2} \ge 10$

$\therefore\ |B_i| \ge 5\ \forall i \in \{1,2,3,4\}$ as $\binom{5}{2} = 10$

But we have $|B_1| + |B_2| + |B_3| + |B_4| = 23$ as we have done intersection with ${1,2,3,...23}$ and $B_1 \cap B_3 \cap B_3 \cap B_4 = \phi$

$\therefore \exists\ j \in \{1,2,3,4\}$ such that $|B_j| = 5$

Now let $B_j = \{x_1,x_2,x_3,x_4,x_5\}$

Now, the sums of two distinct elements of $A_j$ representing the numbers $15, 16, . . . , 24$ must exactly be equal to all the pairwise sums of the elements of $B_j$

Let the pairwise sum of all elements of $B_j$ be equal to $S$

$\therefore S = 4(x_1 + x_2 + x_3 + x_4 + x_5)$

Again, $S = 15 + 16 + 17 ... 24 = 195$

which gives $4(x_1 + x_2 + x_3 + x_4 + x_5) = 195$ which clearly is impossible.

Thus we have proved that $k \not \ge 4$

Thus, the anser is $k =3$

$\endgroup$
  • $\begingroup$ This looks good to me! (Except for that word "unique" in part 2, which doesn't look right.) $\endgroup$ – TonyK Feb 22 '15 at 11:58
  • $\begingroup$ Well the sum has to be of two unique numbers as we have assumed that to be true for all A_i and B_i is just a subset. $\endgroup$ – Crazy-Fool Feb 22 '15 at 12:00
  • $\begingroup$ I am sorry your answer is wrong. Answer is 195:( $\endgroup$ – Aditya Kumar Feb 22 '15 at 12:04
  • $\begingroup$ @AdityaKumar How do you know that ? $\endgroup$ – Crazy-Fool Feb 22 '15 at 12:08
  • 1
    $\begingroup$ @user211217 you are absolutely right. I confirmed it from my teacher:) $\endgroup$ – Aditya Kumar Feb 22 '15 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.