Maths Olympiad Prep

Library / /138 of 144

Combinatorics Difficulty 8.9 Shortlist Find the answer

Determine the greatest positive integer kk that satisfies the following property: The set of positive integers can be partitioned into kk subsets A1,A2,,AkA_1, A_2, \ldots, A_k such that for all integers n15n \geq 15 and all i{1,2,,k}i \in \{1, 2, \ldots, k\} there exist two distinct elements of AiA_i whose sum is n.n.

*

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

To find the greatest positive integer k k that satisfies the partition property, we must ensure that the positive integers can be divided into k k subsets A1,A2,,Ak A_1, A_2, \ldots, A_k such that for all integers n15 n \geq 15 and for each i{1,2,,k} i \in \{1, 2, \ldots, k\} , there are two distinct elements in Ai A_i whose sum is n n .

Let's analyze the problem:

1. Understanding the Partition Requirement:
- Each subset Ai A_i should contain two distinct elements whose sum equals n n for every n15 n \geq 15 .
- This requires diversity in each subset so that various sums n n can be obtained by choosing two elements from any subset.

2. **Finding Constraints on k k **:
- If k k is too large, it might not be possible to achieve the necessary sums with the limited numbers available in smaller subsets.
- If the number of subsets k k is small enough, each subset can incorporate a sufficient range of numbers to meet the summing requirement.

3. **Demonstrating a Working Value of k k **:
- For k=3 k = 3 , consider three subsets:
A1={1,4,7,10,}={1+3ttZ+}, A_1 = \{ 1, 4, 7, 10, \ldots \} = \{ 1 + 3t \mid t \in \mathbb{Z}^+ \},
A2={2,5,8,11,}={2+3ttZ+}, A_2 = \{ 2, 5, 8, 11, \ldots \} = \{ 2 + 3t \mid t \in \mathbb{Z}^+ \},
A3={3,6,9,12,}={3+3ttZ+}. A_3 = \{ 3, 6, 9, 12, \ldots \} = \{ 3 + 3t \mid t \in \mathbb{Z}^+ \}.
- These sets distribute the positive integers cyclically into three groups based on their remainder modulo 3.
- For any integer n15 n \geq 15 , it can be verified that there exist two numbers in each subset whose sum equals n n . For instance:
- Choose distinct integers a=3m+r a = 3m + r and b=3n+r b = 3n + r with r=1,2,3 r = 1, 2, 3 for subsets A1,A2, A_1, A_2, and A3 A_3 , respectively.

4. **Proving k>3 k > 3 Does Not Work**:
- Suppose k=4 k = 4 . Then we would need to find a regular way to partition the integers into four subsets while maintaining the sum property for each subset.
- However, constructing such a distribution generally fails for larger k k because the need to utilize higher integers to achieve every possible sum n15 n \geq 15 becomes impractical.

Therefore, the largest value of k k that permits the construction of such a partition is:

3 \boxed{3}
This solution satisfies the conditions of the problem, ensuring that every required sum can be found by adding two distinct elements from each subset of the partition.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.