There are $n \ge 3$ distinct positive real numbers. Show that there are at most $n-2$ different integer power of three that can be written as the sum of three distinct elements from these $n$ numbers.
Problem
Source:
Tags: algebra, Canada, P1
mira74
15.03.2020 02:24
Put them in order, each number, other than the first 2, has at most 1 triple where its the largest number and the sum is a power of 3
jj_ca888
15.03.2020 02:26
mira74 wrote:
Put them in order, each number, other than the first 2, has at most 1 triple where its the largest number and the sum is a power of 3
i did this lol pigeonhole finishes
cosmicgenius
15.03.2020 03:11
Assume for the sake of contradiction that $K$ is the smallest integer such that there exists a counterexample $S$ sized $K$. Now if each number in $S$ set is a summand in at least $2$ powers of $3$, given that $a+b+c=3^{\ell}$ be the sum that creates the largest sum that is a power of three, we must have $a, b, c < 3^{\ell - 1}$ since they are are added together to form another power $< 3^{\ell - 1}$, impossible. Thus there exists a number that is only part of $1$ power of $3$, i.e. we can remove it creating another counterexample of size $K-1$, contradiction.
jj_ca888
17.03.2020 03:48
FTSoC suppose that there are $k > n-2$ different integer powers of $3$ that can be written as the sum of three distinct elements from some set $S$ of $n$ positive reals. Suppose that these $k$ distinct powers of $3$ are produced by the $k$ distinct 3-element subsets $S_1, S_2, \ldots S_k$ of $S$.
Claim: No two triples $S_i, S_j$ with $i \neq j$ can have the same "greatest element".
Proof:Let $S_i = \{x_1, x_2, x_3\}$ and $S_i = \{y_1, y_2, y_3\}$. Since each triple $S_i$ produces a different multiple of $3$, let $x_1 + x_2 + x_3 = 3^{k_1}$ and $y_1 + y_2 + y_3 = 3^{k_2}$. WLOG let $x_1 < x_2 < x_3$, $y_1 < y_2 < y_2$, and $k_1 < k_2$. Since all elements of $S$ are positive, $x_3 < 3^{k_1}$. Since $y_3 > y_2 > y_1$, we have $y_3 > \frac13(y_1 + y_2 + y_3) = 3^{k_2 - 1}$. Since $k_2 > k_1$ and they are both integers, $k_2 - 1 \geq k_1$, hence the chain of inequalities:$$y_3 > 3^{k_2 - 1} \geq 3^{k_1} > x_3.$$so $y_3 \neq x_3$, as desired. $\square$
Note that only the 3rd largest to largest elements of $S$ can be greatest elements of a triple, hence $n - 2$ possible greatest elements. Since $k > n-2$, by pigeonhole, some two triples $S_n, S_m$, $n \neq m$ must have the same greatest element, contradiction.
Therefore, $k \leq n-2$ as desired.
Afo
10.10.2020 10:12
Nice problem. We'll interpret the sum as an unordered triple instead. We will prove the following claim which immediately implies the conclusion. Claim 1. For every two distinct unordered triple, the largest element is different. Proof. Assume otherwise. Let $L$ be the largest among two distinct unordered triple. Then there exists four numbers, each two are different, and each one is less than $L$ such that $$L+x+y=3^a$$$$L+p+q=3^b$$WLOG, $a>b$. However $$L+x+y =3^a = 3\times 3^{a-1} \ge 3\times 3^b=3L+3p+3q$$$$\implies x+y\ge 2L+3p+3q$$An obvious contradiction. Hence our assumption is false, and the claim is true. $\blacksquare$
mathtiger6
26.12.2020 09:08
Define a form as an integer power of three that is the sum of three distinct elements from our set of reals.
We proceed by induction.
Base case: We have $n = 3$. There is only one possible choice of $3$ distinct elements, so there is at most $n - 2 = 1$ form.
Inductive hypothesis: Suppose that, for any $n-1$ distinct positive reals, there are at most $n-3$ distinct forms.
Inductive step: Consider $a_1 < a_2 < \cdots < a_{n-1} < a_n$. The set $T = \{a_1, \ldots, a_{n-1}\}$ has at most $n-3$ forms; let its largest form be $3^k$.
We claim that $S = \{a_1,\ldots, a_n\}$ has at most $n-2$ forms; that is, it adds at most $1$ more distinct form to the forms from $T$. FTSOC, suppose it adds in at least $2$ more distinct forms.
Let the distinct elements $x,y \in T$ be such that they add in a new form. That is,$$x + y + a_n = 3^{j+k}$$for a positive integer $j$.Note $0 < x,y < 3^k$ so$$3^{j + k - 1} \leq 3^{j + k} - 2\cdot 3^k < a_n < 3^{j+k}.$$Taking arbitrary $z,w \in T$,$$3^{j + k - 1} < z + w + a_n < 3^{j + k} + 2\cdot 3^k < 3^{j+k+1}.$$This implies any form less than or equal to $3^{j + k - 1}$ cannot be achieved (if $a_n$ is one of the three distinct elements) and any form greater than or equal to $3^{j + k +1}$ cannot be achieved. Only one form, $3^{j+k}$ is achieved, so we have reached our contradiction.
By induction, we have proved the result. $\blacksquare$
heheXD1
10.03.2021 11:12
Afo wrote:
Nice problem. We'll interpret the sum as an unordered triple instead.
We will prove the following claim which immediately implies the conclusion.
Claim 1. For every two distinct unordered triple, the largest element is different.
Proof.
Assume otherwise. Let $L$ be the largest among two distinct unordered triple. Then there exists four numbers, each two are different, and each one is less than $L$ such that
$$L+x+y=3^a$$$$L+p+q=3^b$$WLOG, $a>b$. However
$$L+x+y =3^a = 3\times 3^{a-1} \ge 3\times 3^b=3L+3p+3q$$$$\implies x+y\ge 2L+3p+3q$$An obvious contradiction. Hence our assumption is false, and the claim is true. $\blacksquare$
What is the motivation for considering the largest element of each unordered triple?
L567
13.11.2021 05:50
Cute, say there are $k$ possible powers of three that can be written. Pick one of them, say $3^z = x+y+z$, at least one of these is such that $3^z > x \ge 3^{z-1}$, call this the dominating number of $3^z$ (If there are many such things, pick one arbitrarily). Now, note that each dominating number is sandwiched between different powers of three, so are all distinct. But for the smallest power of three representable, the other two numbers can't be dominating any other power of $3$. So there must be at least $k+2$ numbers, so $k \le n-2$, as desired. $\blacksquare$
Mogmog8
05.03.2022 07:20
Consider $x_1+x_2+a=3^k$ where $x_1<x_2<a,$ and $y_1+y_2+b=3^{\ell}$ where $y_1<y_2<b.$ We claim $a\neq b.$ Suppose the contrary and WLOG $k>\ell.$ Since $3^{\ell}\le 3^{k-1},$ $x_i\in(0,3^{k-1})$ and $y_i\in(0,3^{\ell-1}),$ $$2\cdot 3^{k-1}\le 3^k-3^{\ell}=x_1+x_2-y_1-y_2<2\cdot3^{k-1},$$a contradiction. Hence, the greatest element in each sum must be distinct. If we have a list $(x_1,x_2,x_3,\dots,x_n)$ ordered from least to greatest, $x_3,x_4,\dots,x_n$ could be the greatest elements, and they can be the greatest element only once, so there are at most $n-2$ sums. $\square$
Arslan
19.10.2022 10:51
In the solution presented by the Canadian Mathematical Society, it says the following: "Even if it was not asked to prove, we will now show that the optimal answer $n-2$ is reachable." So, in such kind of combinatorial/Number theoretical problems, how do we know that if it is necessary to give an example?
john0512
19.04.2023 02:44
We will use induction. Clearly, this is true for $n=3$. Now, suppose that there are $n+1$ numbers. Claim: The largest number out of these $n+1$, which we call $L$, can only contribute at most one power of 3. Suppose otherwise. Then there exist integers $a,b$ with $a<b$ for which there exists a triple containing $L$ with sum $3^a$ and another triple containing $L$ with sum $3^b$. Then, obviously $$L<3^a.$$However, since $L$ is by definition the largest number, $$L>\frac{1}{3}3^b.$$Thus, $$3^a>\frac{1}{3}3^b,$$which is clearly a contradiction since $b\geq a+1$. Hence, the largest number can only contribute at most one. Thus, by induction we are done.
chenghaohu
14.07.2023 00:05
Proof by induction. Base case: n=3 works, because there’s of course at most 1 power of 3 being made from the sum of 3 numbers. Inductive step: assume that n works, then we show that a(n+1) adds no more than 1 new integer power of 3. Assume for contradiction that there exists some 3^a and 3^b such that a(n+1) is involved in the formation of them, and a > b. Then we must have that a(n+1) is greater than or equal to 3^(b-1) and less than 3^(a-1), which cannot coexist, thus it must introduce less than or equal to 1 new term. Thus the induction hypothesis is true, and the problem is completed.
YaoAOPS
07.09.2023 18:08
Partition $S$ into subsets $S_i = S \cap [3^i, 3^{i+1})$. Claim: It is only possible for a $3$ element subset of $S$ to sum to $3^{i+1}$ only if $S_i$ is nonempty. Proof. Suppos that the set is empty. Then either the sum contains an element at least $3^{i+1}$ so it can not hold, or it contains elements at most $3^i$, so the sum is less than $3^{i+1}$ due to being distinct. $\blacksquare$ As such, there are at most $n$ possible ways to sum to a power of $3$. Since the bottom two elements of $S$ can't contribute to possible sums due to needing a larger element, this gives at most $n - 2$ ways.
InterLoop
01.05.2024 18:11
ook
Consider the maximum power generated, say $3^{a + 1}$. Then the maximum element of that tuple is $> 3^a$, and it is used only to create that one power of $3$. Delete it and induct.