Let $n \geq 2$ be a positive integer. The set $M$ consists of $2n^2-3n+2$ positive rational numbers. Prove that there exists a subset $A$ of $M$ with $n$ elements with the following property: $\forall$ $2 \leq k \leq n$ the sum of any $k$ (not necessarily distinct) numbers from $A$ is not in $A$.
Problem
Source: 2022 Bulgarian Spring Math Competition, Problem 11.4
Tags: Combinatorial Number Theory, Subsets, number theory, combinatorics, Probabilistic Method, Bulgaria
Marinchoo
27.03.2022 11:46
If a set $S$ satisfies the property which we want for $A$ (but is not necessarily a subset of $M$), we will call it $\textit{sum-free}$. First, notice that if $B$ is $\textit{sum-free}$, then $B'=\{cx|x\in S\}$ is also $\textit{sum-free}$ for any $c>0$. Thus if we multiply all numbers in $M$ by the lcm of the denominators we will get a new set $M^{*}$ consisting only of positive integers (since we multiply a positive rational number by a $c>0$ to get an integer, this means that the new set $M$ consists of positive integers).
Let $p$ be a prime of the form $(2n-1)q-n+1$. Since $\gcd(n-1,2n-1)=1$, by Dirichlet's prime number theorem we know that infinitely many such prime numbers exist, so we can choose a big enough $q$ (for example, $q>\max_{x\in M^{*}} x$ will suffice). Now, notice that the set:
\[S=\{q,q+1, q+2\ldots ,2q-1\}\]is $\textit{sum-free}$. Indeed, if we look at the extremal cases, we notice that if $\sum$ denotes the sum of $k$ integers from the set $S$, then:
\[2q-1<q+q\leq \sum\leq n(2q-1)<p+q\]Now the key observation is that the sets $S_{t}=\{tx (\text{mod } p)|x\in S, 1\leq t\leq p-1\}$ are sum-free since we noted above that if $B$ is $\textit{sum-free}$, then also is $B'=\{cx|x\in B\}$ and the result follows from the fact that $S$ is $\textit{sum-free}$. Notice that $S\equiv S_{1}$ and now let's construct a $q\times (p-1)$ table (with $q$ columns and $p-1$ rows). In the $i$-th row we write the numbers from $S_{i}$, so that every cell contains a single number between $1$ and $q-1$ (we picked $q>\max_{x\in M^{*}} x$ earlier). Since $p$ is prime, that means that each column contains every residue modulo $p$. That is, if we have the numbers $xt (\text{mod }p)$ and $xs(\text{mod }p)$ in rows $t$ and $s$ respectively, then $q\leq x\leq 2q-1$, so $p\nmid x$ and $|t-s|\leq |(p-1)-1|<p$, so $xs-xt\not\equiv 0(\text{mod }p)$, thus every residue from $1$ to $p-1$ appears in every column. Thus, if for every number in $M^{*}$ we write a $1$ in the cells of the table which are congruent to it modulo $p$ (here since $p$ is huge, the numbers from $M^{*}$ are themselves residues mod $p$, but nevermind), we would have $|M^{*}|\cdot (q-1)$ ones since every number appears in every column once. However $|M^{*}|\cdot q=(2n^2-3n+2)q$. On the other hand, notice that the sets $S_{1},S_{2},\ldots ,S_{n-1}$ don't contain numbers from $M^{*}$ because $\min_{x\in S_{t}} x=tx (\text{mod }p)>q>\max_{x\in M^{*}} x$ and $\max_{x\in S_{t}} x=(2q-1)t \leq (2q-1)(n-1)<p<p+\min_{x\in M^{*}} x$. Thus, by the PHP we have a row with at least
\[\Bigg\lceil \frac{(2n^2-3n+2)q}{(p-1)-(n-1)}\Bigg\rceil=\Bigg\lceil \frac{(2n^2-3n+2)q}{(2n-1)(q-1)}\Bigg\rceil\quad 1\text{'s}\]Note that the numbers in this set form a $\textit{sum-free}$ subset $A$ of $M^{*}$ since they are a subset of some $\textit{sum-free}$ $S_{i}$. Now we only have to prove that:
\[\frac{(2n^2-3n+2)q}{(2n-1)(q-1)}>n-1\]\[\iff 2n^2q-3nq+2q>2n^2q-2n^2-nq+n-2nq+2n+q-1\]\[\iff q>-2n^2+3n-1\]which is obviously true even for small $q$, so we're done since
\[\frac{(2n^2-3n+2)q}{(2n-1)(q-1)}>n-1\Longrightarrow \Bigg\lceil \frac{(2n^2-3n+2)q}{(2n-1)(q-1)}\Bigg\rceil\geq n\]
dgrozev
27.03.2022 15:34
It is indeed a very nice problem! The best problem of this year's tournament, as I see the problems you've posted. Could you write its author, please? And is this the official solution?
Marinchoo
27.03.2022 16:03
dgrozev wrote: It is indeed a very nice problem! The best problem of this year's tournament, as I see the problems you've posted. Could you write its author, please? And is this the official solution? I completely agree, this is certainly a beautiful problem. I don't have the solutions or the names of the authors of each problem. I only have the problem statements and #2 is my solution (which I hope is correct) and not an official one. I may post the official solutions to the problems when they come out.
dgrozev
01.04.2022 17:16
The author of this problem is Aleksandar Ivanov. The main idea is to make the given numbers integers and work modulo $ p$ where $ p$ is a large (prime) number. If we manage to choose a large "sum-free" subset $ M'$ modulo $ p$ the same set $ M'$ will be sum-free. The plan follows as a whole the author's idea of the official solution. $\textbf{First observation}$: If $ M'$ is a "sum-free" set of integers modulo $ p$ the same holds for $ s\cdot M':=\{s\cdot m : m\in M\}$, where $ s$ is a natural number, and vise versa. $\textbf{Second observation}$: The set $ I:= \{i : i\in [0..p-1], \frac{p}{2n}\le i\le \frac{p}{n}\}$ is sum-free modulo $ p$. Indeed, summing up two or more (but at most $ n$) elements of $ I$ will result in a sum that is in the interval $ \left(\frac{p}{n},p-1\right]$. $\textbf{The key idea is}$ to find an integer $ s\in [1.. p-1]$ such that $ M_s:=s\cdot M$ has large number of elements in $ I$. Solution. We can assume all numbers in $ M$ are positive integers, otherwise they can be made such by multiplication by an appropriate integer. Let us take a prime number $ p$, greater than all the elements in $ M$. Further we consider $ M$ as a set of residues modulo $ p$. Denote by $ I$ the interval $ \displaystyle \left[\frac{p}{2n-1}, \frac{2p}{2n-1}\right].$ Note that the set $ M'$ of all integers inside $ I$ have the property that any sum of no more than $ n$ of them is not an element of $ M'$ modulo $ p$. For each $ a\in M$ let $ 1_{a, I}$ be the random variable that takes value $ 1$ if for a randomly taken integer $ s\in[1,p-1]$ we have $ s\cdot a\in I \pmod{p}$, and value $ 0$ otherwise. It holds $$ \displaystyle \mathbb{E}[1_{a,I}]> \frac{ \frac{2p}{2n-1}- \frac{p}{2n-1}-1 }{p-1}$$which yields $$ \displaystyle \mathbb{E}[1_{a,I}]>\frac{1}{2n-1}-\frac{1}{p}$$Let $ X$ be a random variable which equals $ \#\{a\in M : s\cdot a\in I \pmod{p}\}$ where $ s$ is a randomly taken integer in $ [1,p-1]$. Clearly, $X=\sum_{a\in M} 1_{a,I}.$ Using the linearity of expectation, we get $$ \displaystyle \mathbb{E}[X]=\sum_{a\in M}\mathbb{E}[1_{a,I}] > m\cdot \left(\frac{1}{2n-1}-\frac{1}{p}\right)$$Suppose we have already checked that $$ \displaystyle m\cdot \left(\frac{1}{2n-1}-\frac{1}{p}\right)> n-1 \qquad(1)$$It means $ \displaystyle \mathbb{E}[X]>n-1,$ therefore $X$ takes $ n$ as a value. Thus, there exists $ s\in [1..p-1]$ such that the set $ M'_s:=\{a\in M : s\cdot a\in I\}$ satisfies $ |M'_s|\ge n$. Hence, the elements of $ M'_s$ satisfy the requirement of the problem. It remains to check that $ (1)$ holds. Since the prime $ p$ can be chosen as large as we want, it is enough to check $$ \displaystyle m\cdot \left(\frac{1}{2n-1}\right)> n-1$$which is a matter of simple calculation. Comment. The restriction of numbers being positive is redundant. The same proof can be used, just omitting the word "positive". The official solution is like in $\#$2 (without the glitches and typos). Btw, no one managed to solve it at the competition - all the contestants scored only 1 point. The claim also holds for any real numbers. More details and comments can be found in my blog.
dgrozev
08.04.2022 19:30
Here is the proof of the general case, when all the numbers are real. The plan is to multiply all the numbers by some real number to make them all irrationals and then work modulo $ 1$. That is, we consider $ a\equiv b\pmod 1$ if $ a-b$ is integer. That said, we could think of $ M$ as a set of irrational numbers in $ [0,1)$ and points $ 0$ and $ 1$ being "glued". Let $ I$ be the interval $ \displaystyle \left(\frac{1}{2n-1}, \frac{2}{2n-1}\right).$ Note that it is impossible any sum of $ k$ terms in $ I$ ($ 2\le k\le n$) to be also in $ I$ modulo $ 1$. Thus, if we multiply all elements of $ M$ by some natural $ s\in\mathbb{N}$ modulo $ 1$ and if it happens (by chance) that at least $ n$ of the numbers $ s\cdot M:=\{sx : x\in M \}$ are in $ I$, we are done, because the corresponding terms of $ M$ would be "special sum-free" modulo $ 1$. So, there exists $ a\in \mathbb{R}$ such that all the numbers $ ax, x\in M$ are irrational. This is intuitive clear, one can see the proof in my blog. Further, we can assume $ M$ consists of irrational numbers. Let now $ N$ is sufficiently large positive integer, which will be determined later. Fix $ x\in M$ and look at the numbers $ \{kx\pmod 1 : k=1,2,\dots,N\}$. It is known that the infinite sequence $ \big( ka\pmod{1}\big)_{k=1}^{\infty}$ is uniformly distributed in $ [0,1]$ (Equidistribution theorem). Hence, $$ \displaystyle \frac{\#\{k : kx\in I\pmod 1, 1\le k\le N\}}{N}=|I| +o(1)\qquad (1)$$where $ o(1)$ denotes a value that tends to $ 0$ when $ N\to\infty$. As in the original problem, let $ 1_{x,I}$ be a random variable defined as follows. We take randomly $ k\in [1..N]$ and if $ kx\in I\pmod 1$ then $ 1_{x,I}$ is $ 1$ otherwise it is $ 0$. Usually, it's called indicator variable, because it indicates when $ kx\in I\pmod 1$. By $ (1)$ we get $$ \displaystyle \mathbb{E}[1_{x,I}]=\frac{1}{2n-1}+o(1).$$Let $ X$ be a random variable equal to the number of terms of $ k\cdot M=\{kx:x\in M\}$ that are inside $ I$ where $ k$ is a randomly taken integer in $ [1..N]$. Clearly $$ \displaystyle X=\sum_{x\in M}1_{x,I}.$$By the linearity of expectation we obtain \begin{align*} \displaystyle \mathbb{E}[X]&=\sum_{x\in M}\mathbb{E}[1_{x,I}]\\ \displaystyle \mathbb{E}[X]&= m\cdot \left(\frac{1}{2n-1}\right)+m\cdot o(1). \end{align*}where $ m=|M|=2n^2-3n+2$. It is a matter of calculation to check $$ \displaystyle m\left(\frac{1}{2n-1} \right)>n-1$$and since $ m\cdot o(1)\to 0$ as $ N\to \infty$, it yields $$ \mathbb{E}[X]>n-1.$$It implies that $ X$ takes a value $ n$ or greater, providing $ N$ is sufficiently large. That is, there exists $ k\in [1..N]$ such that $ \#\{x\in M : kx\in I \pmod 1\}\ge n$.
EthanWYX2009
31.08.2024 09:15
Nice problem but not so suitable to appear in contest. The key idea of probabilistic method and consider in $\mathbb F_p$ first came up in this problem, I don't really think people who haven't seen this before can solve the problem. Quote: (Erdos 1965?) Every set of $n$ integers, $A$, contains a sum -free subset of at least $\frac{n}{3}$. I also wrote it in my blog.