Maths Olympiad Prep

Library / /23 of 61

Combinatorics Difficulty 6.3 National Olympiad Prove it Canada

Problem:

Let SS be a set of n3n \geq 3 positive real numbers. Show that the largest possible number of distinct integer powers of three that can be written as the sum of three distinct elements of SS is n2n-2.

Solution

Solution:

We will show by induction that for all n3n \geq 3, it holds that at most n2n-2 powers of three are sums of three distinct elements of SS for any set SS of positive real numbers with S=n|S|=n. This is trivially true when n=3n=3.

Let n4n \geq 4 and consider the largest element xSx \in S. The sum of xx and any two other elements of SS is strictly between xx and 3x3x. Therefore xx can be used as a summand for at most one power of three. By the induction hypothesis, at most n3n-3 powers of three are sums of three distinct elements of S{x}S \setminus \{x\}. This completes the induction.

Even if it was not asked to prove, we will now show that the optimal answer n2n-2 is reached. Observe that the set S={1,2,323,333,,3n3}S=\{1,2,3^{2}-3,3^{3}-3, \ldots, 3^{n}-3\} is such that 32,33,,3n3^{2}, 3^{3}, \ldots, 3^{n} can be expressed as sums of three distinct elements of SS. This makes use of the fact that each term of the form 3k33^{k}-3 can be used in exactly one sum of three terms equal to 3k3^{k}.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.