set with c+2a>3b

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VicKmath7

1388 posts

VicKmath7

#1 h Jul 12, 2022, 12:55 PM • 5 Y

Y by HA5x5, yshk, rstenetbg, deplasmanyollari, Funcshun840

Let $n$ be a positive integer. Given is a subset $A$ of $\{0,1,...,5^n\}$ with $4n+2$ elements. Prove that there exist three elements $a<b<c$ from $A$ such that $c+2a>3b$ .

Proposed by Dominik Burek and Tomasz Ciesla, Poland

This post has been edited 3 times. Last edited by VicKmath7, Dec 22, 2022, 4:09 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Orestis_Lignos

555 posts

Orestis_Lignos

#2 h Jul 12, 2022, 12:58 PM • 21 Y

Y by VicKmath7, David-Vieta, qwert159, Mathlover_1, agwwtl03, Llantas_Saguate, Quidditch, yshk, rama1728, Rebel_1, a_n, mathmax12, rstenetbg, ehuseyinyigit, Tellocan, Deadline, Infinityfun, lomta, nawuu, FredAlexander, Funcshun840

Assume otherwise. Then, if $A$ consists of $0 \leq x_1<x_2<\ldots<x_{4n+2} \leq 5^n$ , then $3x_{4n+1} \geq x_{4n+2}+2x_{4n}$ . Let $y_i=x_{4n+2}-x_i>0$ for all $i$ , and so the above relation rewrites as $y_{i+1} \leq \frac{2}{3}y_i$ . Hence, we easily obtain that $y_{4n+1} \leq (\frac{2}{3})^{4n} y_1$ .

However,

$1 \leq y_{4n+1} \leq (\frac{2}{3})^{4n}(x_{4n+2}-x_1) \leq (\frac{16}{81})^n(5^n-0)=(\frac{80}{81})^n<1,$

which gives the desired contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Assassino9931

1248 posts

Assassino9931

#3 h Jul 12, 2022, 1:00 PM • 5 Y

Y by solidgreen, rstenetbg, Mango247, FredAlexander, Funcshun840

Suppose the elements of $A$ are $a_1 < a_2 < \cdots < a_{4n+2}$ . Pick $c = a_{4n+2}$ (with the idea in mind that we do not win more if we do not pick the largest element of $A$ ) and aim for $a$ and $b$ to be consecutive in the above sequence (in any other case the difference $3b-2a$ shall be larger). If we prove that $c + 2a_i > 3a_{i+1}$ for at least one $i=1,2,\ldots,4n$ , the problem shall be solved. Suppose the contrary, i.e. $a_{i+1} \geq \frac{c+2a_i}{3}$ for all $i=1,2,\ldots,4n$ . Setting $a_i = b_i + c$ yields $b_{i+1} \geq \frac{2b_i}{3}$ and so $b_{4n+1} \geq \left(\frac{2}{3}\right)^{4n}b_1$ , whence $\left(\frac{2}{3}\right)^{4n}(c-a_1) \geq c - a_{4n+1}$ . In the latter the right-hand side is at least $1$ , while the left-hand one is less than $\left(\frac{2}{3}\right)^{4n} \cdot 5^n = \left(\frac{80}{81}\right)^{n} < 1$ , contradiction.

This post has been edited 1 time. Last edited by Assassino9931, Jul 12, 2022, 1:01 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

isaacmeng

113 posts

isaacmeng

#4 h Jul 12, 2022, 1:10 PM • 2 Y

Y by CoderNp, Sandro175

ISL 2021 A1. Let $n\in\mathbb Z$ and $A\subseteq\{0, 1, \dots, 5^n\}$ with $|A|=4n+2$ . Prove that there exist $a, b, c\in A$ such that $a<b<c$ and $c+2a>3b$ .

Solution. We choose elements of $A$ one by one from $\{0, 1, \dots, 5^n\}$ such that there are no $a, b, c\in A$ and $a<b<c$ such that $c+2a>3b$ . Consider the case when $0$ and $5^n$ are chosen at the moment. Take $a=0$ , $c=5^n$ , then all the numbers less than $\left[\frac{5^n}3\right]+1$ cannot be chosen, so the smallest number can be chosen is greater than $\frac13\cdot 5^n$ . Take $a$ be that number, which is greater than $\frac13\cdot 5^n$ and $c=5^n$ , then all the numbers less than $\left[\frac{5^n+\frac23\cdot 5^n}3\right]+1$ cannot be chosen, so the smallest number can be chosen this time is greater than $\frac59\cdot 5^n$ . The idea is to repeat this for $4n$ times.

Define a sequence by $a_1=\frac13$ and $a_{n+1}=\frac{2a_n+1}3$ for all $n\in\mathbb Z_+$ . It follows that the smallest number can be chosen in the $k^{\text{th}}$ is greater than $a_k\cdot 5^n$ .

Claim 1. We have $a_{4n}>\frac{5^n-1}{5^n}$ .

Proof. Induction. For the base case: $a_1=\frac13$ , $a_2=\frac59$ , $a_3=\frac{19}{27}$ , $a_4=\frac{65}{81}>\frac45$ . Assume that $a_{4k}>\frac{5^k-1}{5^k}$ . Then $\begin{align*}a_{4(k+1)}&=\frac{2\left(\frac{2\left(\frac{2\left(\frac{2a_{4k}+1}3\right)+1}3\right)+1}3\right)+1}3\\&=\frac{16a_{4k}+65}{81}\\&>\frac{16\cdot\frac{5^k-1}{5^k}+65}{81}\\&=\frac{81\cdot 5^k-16}{81\cdot 5^k}\\&>\frac{81\cdot 5^k-16-5^k}{81\cdot 5^k-5^k}\\&=\frac{5^{k+1}-1}{5^{k+1}}\end{align*}$ does the inductive step.

It follows from Claim 1 that the smallest number can be chosen in the last time, i.e. the $4n^{\text{th}}$ time, is greater than $\frac{5^n-1}{5^n}\cdot 5^n=5^n-1$ , but the only such number is available is $5^n$ , which is chosen in the beginning. This is a contradiction.

If the numbers $0$ or $5^n$ is not chosen, then repeat the argument by taking $a$ to be the minimal element of $A$ and $c$ the maximal element of $A$ . The contradiction above will still be induced as the range of 'available numbers' is even smaller than between $1$ and $5^n-1$ inclusive in above. Therefore, there is no way we can choose numbers such that there are no $a, b, c\in A$ and $a<b<c$ such that $c+2a>3b$ , the result follows.

This post has been edited 3 times. Last edited by isaacmeng, Jul 13, 2022, 9:07 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

DottedCaculator

7339 posts

DottedCaculator

#5 h Jul 12, 2022, 1:17 PM • 3 Y

Y by Mango247, Mango247, Mango247

Let $A=\{a_1,a_2,\ldots,a_{4n+2}\}$ with $a_1<a_2<\ldots<a_{4n+2}$ . If $a$ , $b$ , and $c$ do not exist, we must have that $a_{4n+2}+2a_i\leq3a_{i+1}$ for all $1\leq i\leq4n+1$ . We claim that $a_i\geq\left(1-\left(\frac23\right)^{i-1}\right)a_{4n+2}$ by induction on $i$ .

Base Case: $i=1$
Since $a_1\geq0$ , we have $a_1\geq\left(1-\left(\frac23\right)^{1-1}\right)a_{4n+2}=0$ .

Inductive Step:
We have
$\begin{align*} a_{i+1}\geq\frac13a_{4n+2}+\frac23a_i\\ &\geq\frac13a_{4n+2}+\frac23a_{4n+2}-\left(\frac23\right)^ia_{4n+2}\\ &=\left(1-\left(\frac23\right)^i\right)a_{4n+2}. \end{align*}$ Therefore, $a_{4n+1}\geq\left(1-\left(\frac23\right)^{4n}\right)a_{4n+2}>\left(1-\left(\frac15\right)^n\right)a_{4n+2}$ since $\left(\frac23\right)^4=\frac{16}{81}<\frac15$ . Since $a_{4n+2}\leq5^n$ , we have $a_{4n+1}>a_{4n+2}-\frac{a_{4n+2}}{5^n}\geq a_{4n+2}-1$ , which is impossible since $a_{4n+1}\leq a_{4n+2}-1$ . Therefore, this is a contradiction, so there must exist $a$ , $b$ , $c\in A$ such that $a<b<c$ and $c+2a>3b$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amuthup

779 posts

amuthup

#6 h Jul 12, 2022, 1:48 PM

Y by

Suppose for the sake of contradiction that $c+2a\le 3b$ for all $a,b,c\in A$ with $a<b<c.$

$\textbf{Claim: }$ If the elements of $A$ are $s_1<s_2<\dots<s_{4n+2},$ then $s_i\ge s_{4n+2}(1-(\tfrac{2}{3})^{i-1})$ for all $i.$

$\emph{Proof: }$ Induct on $i;$ the base case is true because $s_1\ge 0.$

For the inductive step, consider $s_k.$ Take $(a,b,c)=(s_{k-1},s_k,s_{4n+2});$ by our assumption, we have $s_{4n+2}+2s_{k-1}\ge 3s_k.$ Therefore,
$\begin{align*} s_k &\ge\frac{s_{4n+2}+2s_{k-1}}{3}\\ &\ge\frac{s_{4n+2}+2(s_{4n+2}(1-(\tfrac{2}{3})^{k-2}))}{3}\\ &=\frac{s_{4n+2}(3-2(\tfrac{2}{3})^{k-2})}{3}\\ &=s_{4n+2}(1-(\tfrac{2}{3})^{k-1}), \end{align*}$ as desired. $\blacksquare$

In particular, we have
$\begin{align*} s_{4n+1} &\ge s_{4n+2}(1-(\tfrac{2}{3})^{4n})\\ &=s_{4n+2}-(\tfrac{16}{81})^{n}s_{4n+2}\\ &>s_{4n+2}-(\tfrac{1}{5})^{n}5^n\\ &=s_{4n+2}-1. \end{align*}$ This is impossible, as $s_{4n+1}$ is an integer less than $s_{4n+2}.$

This post has been edited 1 time. Last edited by amuthup, Jul 12, 2022, 1:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

VicKmath7

1388 posts

VicKmath7

#7 h Jul 13, 2022, 7:07 AM

Y by

The idea is to plug in triples of the form $(a_i, a_{i+1}, a_{4n+2})$ (of course, let $a_1<...<a_{4n+2}$ ). Supposing otherwise for contradiction, we get $3a_{i+1} \geq 2a_i+a_{4n+2}$ , so if $d_i=a_i-a_{4n+2}$ , then $3d_{i+1} \geq 2d_i \iff \frac {d_{i+1}} {d_i} \geq \frac {2}{3}$ , so $d_{4n+1} \geq (\frac{2}{3})^{4n}d_1$ by multiplying them. Then $(5.(\frac{2}{3})^4)^n>(\frac{2}{3})^{4n}(a_{4n+2}-a_1) \geq a_{4n+2}- a_{4n+1}\geq 1$ , contradiction.

This post has been edited 1 time. Last edited by VicKmath7, Jul 13, 2022, 7:08 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lrjr24

967 posts

lrjr24

#8 h Jul 13, 2022, 5:37 PM

Y by

Order the elements $x_1 < x_2 < x_3 < \cdots < x_{4n+1} < x_{4n+2}$ . We claim that for some $1 \le i \le 4n$ , $(a_i,a_{i+1},a_{4n+2})$ satisfies the condition. Assume not. Let $d_i=x_{4n+2}-x_i$ . The condition becomes $d_{i+1} \le \frac{2}{3} d_i$ . This means that $d_{4n+1} \le \left( \frac{2}{3} \right) ^{4n} d_1$ . We have that $d_{4n+1} \ge 1$ and $d_1 \le 5^n$ . We get that $1 \le d_{4n+1} \le \left( \frac{2}{3} \right) ^{4n} d_1 \le \left( \frac{2}{3} \right) ^{4n} \cdot 5^n = \left( \frac{80}{81} \right) ^n,$ which is an obvious contradiction so we are done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

biomathematics

2566 posts

biomathematics

#9 h Jul 14, 2022, 3:09 PM

Y by

Let the elements in $A$ be $a_1 < a_2 < \ldots < a_{4n+2}$ . Suppose there exists a tuple $(i,j,k)$ of indices $i < j < k$ such that $a_{k} + 2a_{i} > 3a_j$ . Then note that $a_{4n+2} + 2a_{j-1} \ge a_k + 2a_i > 3a_j$ , so the tuple $(j-1,j,4n+2)$ also works.

Therefore, it is equivalent to show that for some $1 \le j \le 4n-1$ , we have $x_{4n+2} + 2x_{j-1} > 3x_j$ . Assume that this is not the case. Then for all $1 \le j \le 4n-1$ , we have $2(x_{j-1} - x_{4n+2}) \le 3(x_{j} - x_{4n+2}) \implies x_{4n+2}-x_j \le \frac{2}{3} (x_{4n+2}-x_{j-1})$ In particular, this means $x_{4n+2} - x_{4n+1} \le \left ( \frac{2}{3} \right )^{4n} (x_{4n+2} - x_1) \le \left ( \frac{2}{3} \right )^{4n} (5^n - 0) = \left ( \frac{80}{81} \right )^n < 1,$ a contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

asdf334

7585 posts

asdf334

#10 h Jul 14, 2022, 6:10 PM • 3 Y

Y by fuzimiao2013, Nikac12, ike.chen

A bit hastily written.

Let the elements of $A$ be $a_1<a_2<\dots<a_{4n+2}$ . Note that adding or subtracting any constant $C$ from each element in $A$ doesn't change whether it satisfies the condition in the problem; therefore, we may set $a_{4n+2}=5^n$ . Note that the condition is equal to $c-b>2(b-a)$ ; it suffices to show that we can't construct a set such that $a_{4n+2}-a_{i+1}\le 2(a_{i+1}-a_i)$ for all $1\le i\le 4n$ . Now let $a_{4n+2}-a_{4n+1}=d$ . Then
$a_{4n+1}-a_{4n}\ge \frac{d}{2}$ $a_{4n}-a_{4n-1}\ge \frac{3d}{4}$ $\vdots$ $\begin{align*} a_{i+1}-a_{i}&\ge \frac{a_{4n+2}-a_{i+1}}{2} \\ &=\frac{(a_{4n+2}-a_{4n+1})+(a_{4n+1}-a_{4n})+\dots+(a_{i+2}-a_{i+1})}{2} \\ &\ge \frac{d}{2}\cdot \left(\frac{3}{2}\right)^{4n-i}. \end{align*}$ Finally we obtain $5^n\ge a_{4n+2}-a_{1}\ge d\left(\frac{3}{2}\right)^{4n}\ge \left(\frac{81}{16}\right)^n>5^n$ which is a contradiction. We are done. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

awesomeming327.

1699 posts

awesomeming327.

#11 h Jul 15, 2022, 3:14 AM

Y by

Nice, I like it!

Let the numbers in $A$ be $a_1,a_2,\dots,a_{4n+2}$ , where $a_i<a_j$ if $i<j.$ Assume FTSOC that $3b\ge 2a+c$ for all $a,b,c\in A.$ Thus, we get that $a_2\ge \frac{2a_1+a_{4n+2}}{3}\ge \frac{1}{3}a_{4n+2}.$

Call a positive integer $1\le k\le 4n+1$ $r$ -good if we have $a_k\ge ra_{4n+2}.$ If $a_i$ is $r$ -good then $a_{i+1}$ is $\frac{2r+1}{3}$ -good. Note that $a_2$ is $1-\frac{2}{3}$ -good. If $a_i$ is $1-\left(\frac{2}{3}\right)^{i-1}$ -good then we see that $a_{i+1}$ is $1-\left(\frac{2}{3}\right)^i$ -good. Thus, by induction, $a_{4n+1}$ is $1-\left(\frac{2}{3}\right)^{4n}$ -good.

Hence, we have $a_{4n+1}\ge a_{4n+2}-a_{4n+2}\cdot \left(\frac{16}{81}\right)^n.$ We claim that it is forced to have $a_{4n+1}=a_{4n+2}.$ To do this, we show that $a_{4n+2}\left(\frac{16}{81}\right)^n< 1.$ This is true, since $a_{4n+2}\left(\frac{16}{81}\right)^n< \frac{a_{4n+2}}{5^n}\le 1.$ Thus, we reach a contradiction, so we're done.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

timon92

224 posts

timon92

#12 h Jul 16, 2022, 4:41 AM • 5 Y

Y by Quidditch, mijail, Lhaj3, Funcshun840, ademke

This problem was proposed by Burii and me

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mogmog8

1080 posts

Mogmog8

#13 h Jul 17, 2022, 3:54 AM • 1 Y

Y by centslordm

Let the subset contain elements $x_1<x_2<\dots<x_{4n+2}$ and let $c=x_{4n+2}.$ Suppose FTSOC that $x_{4n+2}+2a\le 3b$ for all $a<b,$ which implies $x_{4n+2}+2x_i\le 3x_{i+1}$ for all $1\le i\le 4n.$ We claim by induction that $x_j\ge x_{4n+2}(1-(2/3)^{j-1})$ for $j\ge 1.$ Indeed, $x_1\ge 0=x_{4n+2}(1-1)$ and $x_k\ge x_{4n+2}(1-(2/3)^{k-1})$ implies $x_{k+1}\ge \frac{x_{4n+2}+2x_k}{3}\ge x_{4n+2}\frac{1+1-2(2/3)^j}{3}=x_{4n+2}(1-(2/3)^k),$ completing the induction. Notice $x_{4n+1}\ge x_{4n+2}(1-(16/81)^n)>x_{4n+2}(1-(1/5)^n)=x_{4n+2}-x_{4n+2}(1/5)^n\ge x_{4n+2}-1$ since $1/5>16/81$ and $x_{4n+2}\le 5^n.$ Hence, $x_{4n+1}>x_{4n+2}-1$ so $x_{4n+1}\ge x_{4n+2},$ a contradiction. $\square$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MelonGirl

572 posts

MelonGirl

#14 h Jul 23, 2022, 2:54 AM

Y by

Suppose that $c+2a \leq 3b$ for all $a < b < c$ in $A.$ Then $a \leq \frac{3b - c}{2}.$
Then $A = \{a_1,\ldots,a_{4n+2}\}$ where $a_1 < \cdots < a_{4n+2},$ we have for all $k \leq 4n$ and considering the triple $(a_k, a_{k+1}, a_{4n+2}),$ that $a_k \leq \frac{3 a_{k+1} - a_{4n+2}}{2}.$

Thus, let $x = a_{4n+2} \leq 5^n, y = a_{4n+1} \leq x-1.$
Then $a_{4n} \leq \frac{3y-x}{2},$ and $a_{4n-1} \leq \frac{3 \left( \frac{3y-x}{2} - x \right)}{2} = \frac{9y-5x}{4},$ and $a_{4n-2} \leq \frac{3 \left( \frac{9y-5x}{4} \right) - x}{2} = \frac{27y-19x}{8},$ etc. We can easily see that in general we have by induction $a_{4n+1-m} \leq \frac{3^m y - (3^m - 2^m) x}{2^m}$ by induction, as $\frac{ 3 \left( \frac{3^j y - (3^j - 2^j) x}{2^j} \right) - x }{2} = \frac{ 3^{j+1} y - 3(3^j - 2^j)x - 2^j x }{2^{j+1}} = \frac{3^{j+1} y - (3^{j+1} - 2^{j+1}) x}{2^{j+1}}$

Thus, we get $a_1 \leq \frac{3^{4n} y - (3^{4n} - 2^{4n}) x}{2^{4n}} \leq \frac{3^{4n} (x-1) - (3^{4n} - 2^{4n}) x}{2^{4n}} = \frac{-3^{4n} + 2^{4n} x}{2^{4n}} = x - \frac{3^{4n}}{2^{4n}} \leq 5^n - \frac{3^{4n}}{2^{4n}} < 0$ where the last inequality holds for all $n \geq 1$ as $5^n < \frac{81^n}{16^n}$ follows from $80^n < 81^n.$ This is a contradiction. $\blacksquare$

This post has been edited 1 time. Last edited by MelonGirl, Jul 23, 2022, 3:04 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

SnowPanda

186 posts

SnowPanda

#16 h Aug 6, 2022, 5:34 PM • 2 Y

Y by Mango247, Mango247

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mr.Sharkman

498 posts

Mr.Sharkman

#41 h Apr 4, 2024, 5:15 PM

Y by

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

RedFireTruck

4221 posts

RedFireTruck

#42 h Apr 10, 2024, 9:55 PM

Y by

FTSOC assume there is no $a<b<c$ in $A$ such that $c+2a>3b$ . Then, $b-a\ge \frac{c-b}2$ for $a<b<c$ . Let the elements of $A$ be $\{x_1, x_2, \dots, x_{4n+1}, x_{4n+2}\}$ such that $x_1>x_2>\dots>x_{4n+1}>x_{4n+2}$ . Let $d=x_1-x_2\ge 1$ . Then $x_2-x_3\ge \frac{d}{2}$ so $x_1-x_3\ge \frac{3d}{2}$ . Then, $x_3-x_4\ge \frac{3d}{4}$ , so $x_1-x_4\ge \frac{9d}{4}$ . Therefore, $x_1-x_{4n+2}\ge(\frac32)^{4n}d\ge(\frac{81}{16})^nd\ge 5^n$ , which is impossible, as desired for our contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

de-Kirschbaum

196 posts

de-Kirschbaum

#43 h Apr 19, 2024, 2:23 AM

Y by

Assume for the sake of contradiction that this doesn't hold. So for any positive integer $n=k \geq 1$ , we have elements $x_0<x_1<...<x_{4k+1}$ such that $x_{4n}+2x_i \leq 3x_{i+1}$ . Thus we find that $3(x_{4k+1}-x_{i+1}) \leq 2(x_{4k+1}-x_i) \implies \frac{3}{2} (x_{4k+1}-x_{i+1}) \leq x_{4k+1}-x_i$ . Multiplying over all possible triples $(x_i, x_{i+1}, x_{4k+1})$ and dividing out common terms on both sides $x_{4k+1}-x_0 \geq (\frac{3}{2})^{4k}(x_{4k+1}-x_{4k}) = \frac{81}{16}^k (x_{4k+1}-x_{4k})$ . Note that $\frac{81}{16}^k (x_{4k+1}-x_{4k}) \geq 5^k \geq x_{4k+1}-x_0$ . Thus this is a contradiction and the problem statement holds.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Markas

105 posts

Markas

#44 h May 6, 2024, 8:50 AM

Y by

Suppose the elements of A are $a_1 < a_2 < \cdots < a_{4n+2}$ . Choose c = $a_{4n+2}$ , a = $a_i$ , b = $a_{i+1}$ . If we prove that $c + 2a_i > 3a_{i+1}$ for at least one i, we are ready. Suppose the opposite $\Rightarrow$ $a_{i+1} \geq \frac{c+2a_i}{3}$ , for all i. We set $a_i = b_i + c$ $\Rightarrow$ we get $b_{i+1} \geq \frac{2b_i}{3}$ $\Rightarrow$ $b_{4n+1} \geq \left(\frac{2}{3}\right)^{4n}b_1$ $\Rightarrow$ $\left(\frac{2}{3}\right)^{4n}(c-a_1) \geq c - a_{4n+1}$ . However $\left(\frac{2}{3}\right)^{4n}(c-a_1) \leq \left(\frac{2}{3}\right)^{4n} \cdot 5^n = \left(\frac{80}{81}\right)^{n} < 1$ . Also $c - a_{4n+1} \geq 1$ $\Rightarrow$ there is a contradiction $\Rightarrow$ we are ready.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sagnik123Biswas

420 posts

Sagnik123Biswas

#45 h Jun 21, 2024, 9:20 PM

Y by

Suppose that the elements of our subset are $x_1, x_2, x_3 \dots x_{4n+2}$ with $0 \leq x_1 < x_2 < x_3 \dots x_{4n} < x_{4n+1} < x_{4n+2} \leq 5^n$ . Define $d_i = x_{i+1} - x_{i}$ for $1 \leq i \leq 4n+1$ . Now assume for the sake of contradiction that there exist no $i, j, k$ such that $1 \leq i < j < k \leq 4n+2$ and $x_k + 2x_i > 3x_j$ . So it follows that for all $i, j, k$ such that $1 \leq i < j < k \leq 4n+2$ , we have $x_k + 2x_i \leq 3x_j \implies x_k - x_j \leq 2(x_j - x_i)$ .

So for $1 \leq a \leq 4n$ , we have that $2(x_{a+1} - x_{a}) \geq x_{4n+2} - x_{a+1}$ . It follows that $2d_{a} \geq d_{a+1} + \dots d_{4n+1}$

So it follows that $2d_{4n} \geq d_{4n+1}, 2d_{4n-1} \geq d_{4n} + d_{4n+1}, 2d_{4n-2} \geq d_{4n-1} + d_{4n} + d_{4n+1}, \dots, 2d_{1} \geq d_{2} + d_{3} \dots + d_{4n+1}$ .

So $d_{4n} \geq \frac{d_{4n+1}}{2}$ . Next, $d_{4n-1} \geq \frac{ \frac{d_{4n+1}}{2} + d_{4n+1} }{2} = \frac{3d_{4n+1}}{4}, d_{4n-2} \geq \frac{ \frac{3d_{4n+1}}{4} + \frac{d_{4n+1}}{2} + d_{4n+1} }{2} = \frac{9d_{4n+1}}{8}$ for $k \in \{0, 1, 2, \dots 4n-1 \}$ . We speculate that $d_{4n-k} \geq \frac{3^{k}}{2^{k+1}}d_{4n+1}$ . This can be proven through strong induction.

Base Case: Suppose $k = 0$ , then it follows that $2d_{4n} \geq d_{4n+1} \implies d_{4n} \geq \frac{d_{4n+1}}{2}$ which is consistent with our conjecture.

Inductive Step: Suppose that for some $0 \leq j \leq 4n-2$ we have that for all $0 \leq k \leq j$ , $d_{4n-k} \geq \frac{3^{k}d_{4n+1}}{2^{k+1}}$ . Now we know that $2d_{4n-(j+1)} \geq d_{4n-j} + d_{4n-(j-1)} + \dots d_{4n+1}$ . So $d_{4n-(j+1)} \geq \frac{d_{4n-j} + d_{4n-(j-1)} + \dots d_{4n+1}}{2} \geq \frac{d_{4n+1} + \sum_{k=0}^{j}\frac{3^{k}d_{4n+1}}{2^{k+1}} }{2} \geq \frac{d_{4n+1}}{2} (1 + \frac{1}{2}\frac{(\frac{3}{2})^{j+1} - 1 }{\frac{3}{2} - 1} ) \geq d_{4n+1}\frac{3^{j+1}}{2^{j+2}}$ . This completes the inductive step.

Now we have that $d_1 + d_2 + d_3 \dots d_{4n+1} \leq 5^n$ . But $d_1 + d_2 + d_3 \dots d_{4n+1} \geq d_{4n+1} + \sum_{k=0}^{4n-1}\frac{3^{k}}{2^{k+1}}d_{4n+1} = d_{4n+1}(1 + \frac{1}{2}\frac{(\frac{3}{2})^{4n}-1}{\frac{3}{2}-1}) = d_{4n+1}(\frac{3}{2})^{4n}$ . Since $d_{4n+1} \geq 1$ , it follows that $d_1 + d_2 + d_3 \dots d_{4n+1} \geq (\frac{3}{2})^{4n} = (\frac{81}{16})^n > 5^n$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Sammy27

81 posts

Sammy27

#46 h Jul 6, 2024, 10:49 PM • 1 Y

Y by Eka01

Solution

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ezpotd

1259 posts

ezpotd

#48 h Oct 1, 2024, 7:43 PM

Y by

Order the elements of $A$ as $a_1 \dots a_{4n + 2}$ . If no such triples exist, we have $a_{4n + 2} \le 3a_{i + 1} - 2a_i$ for all $i$ , or $3(a_{4n + 2} - a_{i + 1}) \le 2(a_{4n + 2} - a_i)$ , so letting $b_i = a_{4n + 2} - a_i$ , we have $3b_{i + 1} \le 2b_{i}$ , so $b_1 \ge (\frac 32)^{4n} b_{4n + 1} \ge (\frac 32)^{4n} > 5^n$ , so $a_{4n + 2} - a_{n} > 5^n$ , but this is impossible since the maximal difference between any two elements of $A$ is $5^n$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

L13832

262 posts

L13832

#49 h Oct 16, 2024, 4:51 AM

Y by

A nice problem
Storage

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pi271828

3365 posts

pi271828

#50 h Dec 9, 2024, 4:27 PM

Y by

Let $A = \{ a_1 < a_2 < \cdots < a_{4n+2} \}$ and $a_{4n+2} - a_{i} = d_i$ . Assume for contradiction that the given condition is never true. Applying the condition for contradiction on the triplet $(a_{i-1}, a_i, a_{4n+2})$ , we have $d_{i} < \tfrac{2}{3} \cdot d_{i-1}$ . Chaining inequalities, we have $\begin{align*} 5^n \cdot \left( \frac{2}{3}\right)^{4n} \ge \left( \frac{2}{3}\right)^{4n} \cdot d_1 > \cdots > d_{4n+1}\end{align*}$ implying that $d_{4n+1} = a_{4n+2} - a_{4n+1} < (\tfrac{80}{81})^n < 1$ , contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eg4334

631 posts

eg4334

#51 h Jan 12, 2025, 6:33 PM

Y by

Wasted too much time on global stuff and chaining the wrong inequalities in this one..

Let the numbers be $a_1 < a_2 < \dots < a_{4n+2}$ and assume FTSOC $c+2a \leq 3b$ . The entire idea of the problem is to write this as $\frac32 (c-b) \leq (c-a)$ . Now we let $c=a_{4n+2}$ and exploit the confinment of $5^n$ :
$\begin{align*} a_{4n+2} - a_1 &\geq \frac32 (a_{4n+2}-a_2) \\ &\geq \left( \frac32 \right)^2 (a_{4n+2}-a_3) \\ &\geq \ddots \\ &\geq \left( \frac32 \right)^{4n} (a_{4n+2} - a_{4n+1}) \end{align*}$ But using the miraculous fact that $\left( \frac32 \right)^{4n} = \left( \frac{81}{16} \right)^n > 5^n$ we get an obvious contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Saucepan_man02

1323 posts

Saucepan_man02

#52 h Feb 1, 2025, 7:30 AM

Y by

Ad-Hoc:

FTSOC assume the numbers $x_1 \le x_2 \cdots \le x_{4n+2}$ to be the elements of $A$ such that: $3x_{t+1} \ge x_{t+2}+2x_t$ . Let $y_k = x_{k+1}-x_k$ , and thus: $y_{k+1} \le \frac{2}{3} y_k$ . Spamming up: $y_{4n+1} \le (\tfrac{2}{3})^{4n} y_1$ .
Therefore: $1 \le y_{4n+1} \le (\tfrac{2}{3})^{4n} y_1 \le (\tfrac{2}{3})^{4n} (5^n) = (\frac{80}{81})^n < 1$ and thus, contradiction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Turtwig113

128 posts

Turtwig113

#53 h Mar 9, 2025, 4:12 PM

Y by

We rearrange the condition to $3(c-b)>2(c-a)$ . Note that letting $c$ be the largest element of $A$ is ideal, since any $c > b$ can be selected without needing to change $a$ and if the condition is satisfiable, it is clearly satisfiable with $c$ as the largest element of $A$ .

For this condition to never hold, consider the elements of $A$ as ordered from greatest to least as $c=a_0, a_1, a_2, a_3 \dots a_{4n+1}$ . Then, the sequence $b_i = a_0-a_i$ for $i \geq 1$ must have each term at least a factor of $3/2$ greater than the previous term. Since all elements of $A$ are distinct, $b_1 \geq 1$ and therefore $b_{4n+1} \geq (\frac{3}{2})^{4n}$ . However, $\left(\frac{3}{2}\right)^{4n} > 5^n,$ producing a contradiction, since this implies the difference between some two elements of $A$ would be more than $5^n$ . Therefore, the stated condition always holds.

This post has been edited 1 time. Last edited by Turtwig113, Mar 9, 2025, 4:13 PM
Reason: Typo

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Mapism

18 posts

Mapism

#54 h Mar 11, 2025, 5:35 PM

Y by

Let $A=\{a_1,a_2,...,a_{4n+2}\}$ where $0\le a_1< a_2< ...< a_{4n+2}\le 5^n$ . Suppose $c+2a\le 3b\ \ \forall a,b,c\in A$ such that $a<b<c$ . This is equivalent to $a_k+2a_i\le 3a_j\ \ \forall i<j<k$ . If we take any $i$ and let $j,k$ vary it is clear that $a_{4n+2}+2a_i\le 3a_{i+1}\ \ \forall i=1,2,...,4n$ is a necessary and sufficient condition.

Observe,
$a_{i+1}\ge \frac{a_{4n+2}}{3}+\frac{2}{3}a_i\ge ...\ge a_{4n+2}\left(1-\left(\frac{2}{3}\right)^i\right)+\left(\frac{2}{3}\right)^ia_1$ $a_{i}\le \frac{a_{4n+2}}{2}\ +\ \frac{3}{2}a_{i+1}\le ...\le a_{4n+2}\left(1-\left(\frac{3}{2}\right)^{4n+1-i}\right)\ +\ \left(\frac{3}{2}\right)^{4n+1-i}a_{4n+1}$ These imply
$a_{4n+2}\left(1-\left(\frac{3}{2}\right)^{4n-i}\right)+\left(\frac{3}{2}\right)^{4n-i}a_{4n+1}\ge a_{i+1}\ge a_{4n+2}\left(1-\left(\frac{2}{3}\right)^i\right)+\left(\frac{2}{3}\right)^ia_1,\ \ \forall i=2,...,4n$ $\left(\frac{3}{2}\right)^{4n-i}(a_{4n+2}-1)\ge \left(\frac{3}{2}\right)^{4n-i}a_{4n+1}-\left(\frac{2}{3}\right)^ia_1\ge a_{4n+2}\left(\left(\frac{3}{2}\right)^{4n-i}-\left(\frac{2}{3}\right)^i\right)$ $-\left(\frac{3}{2}\right)^{4n-i}\ge -\left(\frac{2}{3}\right)^ia_{4n+2}\implies 5^n\ge a_{4n+2}\ge \left(\frac{3}{2}\right)^{4n}=\left(\frac{81}{16}\right)^{n}>5^n$ Which clearly is a contradiction.

This post has been edited 4 times. Last edited by Mapism, Mar 12, 2025, 5:57 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

mananaban

36 posts

mananaban

#55 h Apr 1, 2025, 2:05 AM

Y by

Let $A = \{a_1, a_2, \cdots, a_{4n+2}\}$ , where $a_1 < a_2 < \cdots < a_{4n+2}$ .
Assume, FTSOC, that this $A$ violates the problem condition.

We may as well let $c=a_{4n+2}$ always. We also may as well set $b=a_{k+1}$ and $a=a_k$ for some $1 \leq k \leq 4n$ . From this, we get the relation
$c < 3a_{k+1} - 2a_k \implies a_{k+1} > \frac{2}{3} a_k + \frac{c}{3} \qquad \text{for all } 1 \leq k \leq 4n$ Now this implies that, since $a_1 \geq 0$ , $a_{k+1} > (1-\left(\tfrac{2}{3}\right)^k)c$ . This conclusion is from the manipulation
$a_{k+1} - c > \frac{2}{3} (a_k - c)$ to get $a_{k+1}-c > \left(\tfrac{2}{3}\right)^n (a_0-c) \geq -c \left(\tfrac{2}{3}\right)^n$ .

The critical inequality from where we derive the contradiction is
$c > a_{4n+1} > \left( 1 - \left(\frac{2}{3}\right)^{4n} \right) c$ Now I will show that
$\left( 1 - \left(\frac{2}{3}\right)^{4n} \right) c > c-1$
for $c \leq 5^n$ . This is true due to the amazing fact that $5 \cdot 2^4 < 3^4$ . In particular, this is equivalent to
$1 > \left(\frac{16}{81}\right)^n c,$ which is true since $(\tfrac{16}{81})^n c \leq (\tfrac{5 \cdot 16}{81})^n < 1$ .

This provides us with the bound
$c > a_{4n+1} > c-1$ which leaves $a_{4n+1}$ with no possible integer value, our desired contradiction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

akliu

1795 posts

akliu

#56 h Apr 2, 2025, 6:46 PM

Y by

For the sake of contradiction, assume there exists a sequence of numbers $a_k$ that doesn't satisfy the conditions but exists entirely within the bound $0 \leq a_1 < a_2 < \dots < a_{4n+2} \leq 5^n$ . We then have $a_{4n+2} + 2a_{4n} \leq 3a_{4n+1}$ , or $a_{4n+2} - a_{4n+1} \leq 2(a_{4n+1} - a_{4n})$ , in other words, $a_{4n+2} - a_{4n} \geq \frac{3}{2}(a_{4n+2} - a_{4n+1})$ . If we set $d_i = a_{4n+2} - a_i$ , we have $d_{i+1} \leq \frac{2}{3}d_i$ , giving us the inequality $d_{4n+1} \leq (\frac{16}{81})^n d_1$ (where $d_i$ is essentially the distance between the last term and term $i$ in sequence $a$ ). However, $d_1$ is at most $5^n$ and $d_{4n+1}$ is at least $1$ , meaning we have $1 < d_{4n+1} \leq (\frac{80}{81})^n < 1$ , giving us our desired contradiction.

Z K Y