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
15.03.2020 02:24
15.03.2020 02:26
mira74 wrote:
i did this lol pigeonhole finishes
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.
17.03.2020 03:48
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$
26.12.2020 09:08
10.03.2021 11:12
Afo wrote:
What is the motivation for considering the largest element of each unordered triple?
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$
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$
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?
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.
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.
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.
01.05.2024 18:11
ook