For a positive integer $n$ and a subset $S$ of $\{1, 2, \dots, n\}$, let $S$ be "$n$-good" if and only if for any $x$, $y\in S$ (allowed to be same), if $x+y\leq n$, then $x+y\in S$. Let $r_n$ be the smallest real number such that for any positive integer $m\leq n$, there is always a $m$-element "$n$-good" set, so that the sum of its elements is not more than $m\cdot r_n$. Prove that there exists a real number $\alpha$ such that for any positive integer $n$, $|r_n-\alpha n|\leq 2024.$
Problem
Source: 2024 CTST P14
Tags: combinatorics
dragon-YBW
24.03.2024 07:28
bump this
MathLover_ZJ
24.03.2024 09:09
It seems that $\alpha=2-\sqrt 2$... Sketch: For not-so-small $m$, find $r$ such that $\frac{n}{r+1}\leq m<\frac{n}{r}$. Let \[S=\{r+1,2(r+1),\ldots,(r+1)k\}\cup\{(r+1)(k-1)+1,(r+1)(k-2)+1,\ldots,(r+1)(2k-m)+1\}\],where $k=\lfloor\frac{n}{r+1}\rfloor$.Some calculations indicate that the average of numbers in $S$ is under $(2-\sqrt 2)n$ when $r=1$(reached when $m\approx\frac{n}{\sqrt 2}$) and under $\frac{7}{12} n$ when $r\geq 2$. On the other hand, when $m\approx\frac{n}{\sqrt 2}$, easy to see that the construction is almost optimal. (not sure if this is correct, however.)
R8kt
26.03.2024 00:33
The above answer is true. The main thing to exploit here is that if a number doesn’t exist in a set, the density of the numbers smaller than it is less than 1/2. So basically when m>n/2 we must have a lot of big numbers present.