Maths Olympiad Prep

Library / /83 of 144

Algebra Difficulty 8.3 Shortlist Find the answer

Let k2k\ge2 be an integer. Find the smallest integer nk+1n \ge k+1 with the property that there exists a set of nn distinct real numbers such that each of its elements can be written as a sum of kk other distinct elements of the set.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Let k2 k \geq 2 be an integer. We need to find the smallest integer nk+1 n \geq k+1 such that there exists a set S S of n n distinct real numbers, where each element of S S can be expressed as a sum of k k other distinct elements of S S .

To solve this problem, we consider the construction of such a set S S .

1. Understanding the Problem:
- For each element sS s \in S , we need k k distinct elements from S{s} S \setminus \{s\} that sum up to s s .

2. Minimum Size Construction:
- We start by proving that with n=k+4 n = k + 4 , such a set can indeed be constructed.
- Consider a construction where:
- Choose k+1 k + 1 elements as the base set: {a1,a2,,ak+1}\{ a_1, a_2, \ldots, a_{k+1} \} .
- Introduce an additional four elements: {b1,b2,b3,b4}\{ b_1, b_2, b_3, b_4 \} .
- We construct our set S S as:
S={a1,a2,,ak+1,b1,b2,b3,b4} S = \{ a_1, a_2, \ldots, a_{k+1}, b_1, b_2, b_3, b_4 \}

3. Illustrating the Construction:
- Arrange the elements such that:
- Each ai a_i is expressed as the sum of any k k of the other aj a_j 's and some b b 's if necessary.
- Each bi b_i can be expressed using a combination of a a 's and other b b 's.

4. Verification:
- By choosing specific numbers for each bi b_i , we ensure that each number in the constructed set can indeed be expressed as a sum of k k distinct others.
- For example, by choosing values and testing that the sum condition holds, we verify that each possibility works, fulfilling the problem's conditions.

5. Conclusion:
- Testing smaller n n for valid configurations will fail due to insufficient numbers to formulate each possible sum using k k distinct numbers.
- Therefore, the smallest n n for which such a configuration is possible indeed turns out to be n=k+4 n = k + 4 .

Thus, the smallest integer n n such that a set S S with the given conditions can be constructed is:
k+4 \boxed{k + 4}

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.