For a positive integer $n$, and a non empty subset $A$ of $\{1,2,...,2n\}$, call $A$ good if the set $\{u\pm v|u,v\in A\}$ does not contain the set $\{1,2,...,n\}$. Find the smallest real number $c$, such that for any positive integer $n$, and any good subset $A$ of $\{1,2,...,2n\}$, $|A|\leq cn$.
Problem
Source: 2015 China TST 2 Day 1 Q1
Tags: combinatorics, combinatorics proposed
19.03.2015 22:50
The answer is $c=6/5$.First,let's prove that $c>6/5-e$ for arbirtaly small $e$.Take $n=5*k$ and take $(1,2,...2k-1,6k+1,...10k)$.Now,the set ${u+-v}|u,v-A}$ doesn't contain $4k$.Now,for this set $c=(6k-1)/5k=6/5-1/5k$,which is less than some $6/5-e$ for arbirtaly large $k$(I assume $u,v$ can be equal).Now,the proof that $c>6/5$ doesn't work.Let $|Akn|$ be the cardinality of the largest subset of ${1,2,..2n}$ such that the set ${u+-v|u,v-A}$ doesn't contain $k$,so we will prove that $Akn/n<6/5$ for all $k<=n$.Let $2n=x*k+a$($k>1$ from condition). Case 1: $x=2m$.Group elements like this:$(2m*k+a,(2m-1)*k+a),...(2i*k+j,(2i-1)*k+j)$$Akn$ can have at most one element from each group).So,we are left with elements ${1,2,...a}$($a<k$).If $a<k/2$,then we can add all $a$ elements in $|Akn|$,so $c=2*(m*k+a)/(2*m*k+a)$,which is maximumum $a$ is maximum and $m$ is minimum,and plugg $m=1$ and $a=k/2$ we get that $c$ can't be bigger than $6/5$. When $a>k/2$,then we can pick at most $k/2$ elements,so it is optimal when $a=k/2$. Case 2: $x=2m+1$($m>0$).Group elements similar like in Case 1 and we are left with ${1,2,...k+a}$. If $a>k/2$,then just group elements $(k+a,a),...(k+1,1)$ and we get that we can pick at most $k$ elements,so it is optimal when $a=k/2$ and it is obvious that it is optimal when $m$ is minimum possible,so we get that $c$ is maximum $8/7$.Now,if $a<k/2$,group elements $(k+a,a),...(k+1,1)$ and we are left with $(k,....a+1)$,now group them like $(a+1,k-a-1),...(k/2,k/2)$,so we can pick at most $k$ elements,so it is optimal for $a=k/2$ and we again get $8/7$.
25.03.2015 04:54
My solution is very similar to junioragd's, but I think I can add motivation and help make his proof more readable. First, I will prove that $ c \ge \frac{6}{5}. $Let $ n = 5m $ for some $ m \in \mathbb{Z}^{+} $ and consider the set $ A = \{1, 2, 3, \dots, 2m - 1, 6m + 1, 6m + 2, \dots, 10m\}. $ First, it is clear that $ 4m \notin (A + A) \cup (A - A) $ so $ A $ is good as desired. Moreover, we have that $ \frac{|A|}{n} = \frac{6m - 1}{5m} $ so if we make $ m $ arbitrarily large we have that $ c \ge \frac{6}{5} $ as desired. How did I come up with this? Well, usually these kinds of extremal case sets are given by $ \{1, 2, 3, \dots, a, b, b + 1, \dots, 2n\} $ so by solving the equations $ 2a = 2n - b = b - a $ I found $ a, b $ such that $ \{1, 2, 3, \dots, n\} $ was mostly covered. The solutions were $ a = \frac{2n}{5} $ and $ b = \frac{6n}{5} $ which led to the above construction. Now, we want to prove that $ c = \frac{6}{5} $ is the smallest possible. The constructed example makes us want to look at sets which "miss" an element, so let $ A_k \subset \{1, 2, \dots, n\} $ be the largest set where $ k \notin (A_k + A_k) \cup (A_k - A_k) $ for $ k \in \{1, 2, \dots, n\}. $ Now let $ 2n = qk + r $ for some $ q, r \in \mathbb{N} $ such that $ r < k. $ Since $ k \le n $ we have that $ q > 1. $ Define $ B_i = \{i, i + k, i + 2k, \dots, i + qk\} $ for $ 1 \le i \le r $ and define $ B_i = \{i, i + k, i + 2k, \dots, i + (q - 1)k\} $ for $ r < i \le k. $ If $ i \in A_k, $ call $ B_i $ a good - otherwise, call it bad. Because $ k \notin (A_k + A_k) $ it is clear that less than $ \frac{k}{2} $ sets can be good. It is easy to compute that if $ i \le r $ then $ |A_k \cap B_i| \le \left\lfloor{\frac{q}{2}}\right\rfloor + 1 $ if $ B_i $ is good and $ |A_k \cap B_i| \le \left\lceil{\frac{q}{2}}\right\rceil $ if $ B_i $ is bad. Similarly, if $ i > r $ then $ |A_k \cap B_i| \le \left\lceil{\frac{q}{2}}\right\rceil $ if $ B_i $ is good and $ |A_k \cap B_i| \le \left\lfloor{\frac{q}{2}}\right\rfloor $ if $ B_i $ is bad. Now we proceed with casework on the parity of $ q $ and the size of $ r. $ Case 1: $ q = 2q' $ for some $ q' \in \mathbb{Z}^{+} $ and $ r \ge \frac{k}{2}. $ Here we have $ |A_k| \le \sum_{i = 1}^{k}|A_k \cap B_i| \le \frac{k}{2}(q' + 1) + \left(r - \frac{k}{2}\right)q' + (k - r)q' $ so $ \frac{2|A_k|}{2n} \le \frac{(2q' + 1)k}{2q'k + r} \le \frac{(2q' + 1)k}{2q'k + \frac{k}{2}} \le \frac{6}{5} $ since $ q' \ge 1. $ Case 2: $ q = 2q' $ for some $ q' \in \mathbb{Z}^{+} $ and $ r \le \frac{k}{2}. $ Here we have $ |A_k| \le \sum_{i = 1}^{k}|A_k \cap B_i| \le r(q' + 1) +(k - r)q' $ so $ \frac{2|A_k|}{2n} \le \frac{2q'k + 2r}{2q'k + r} = 1 + \frac{r}{2q'k + r} \le 1 + \frac{\frac{k}{2}}{2q'k + \frac{k}{2}} \le \frac{6}{5} $ since $ q' \ge 1. $ Case 3: $ q = 2q' + 1 $ for some $ q' \in \mathbb{Z}^{+} $ and $ r \ge \frac{k}{2}. $ Here we have $ |A_k| \le \sum_{i = 1}^{k}|A_k \cap B_i| \le k(q' + 1) $ so $ \frac{2|A_k|}{2n} \le \frac{2q'k + 2k}{(2q' + 1)k + r} \le \frac{2q'k + 2k}{(2q' + 1)k + \frac{k}{2}} \le \frac{8}{7} < \frac{6}{5} $ since $ q' \ge 1. $ Case 4: $ q = 2q' + 1 $ for some $ q' \in \mathbb{Z}^{+} $ and $ r \le \frac{k}{2}. $ We proceed exactly as in Case 3. Now we are done, because $ |A| \le \text{max}(|A_k|) \le \frac{6n}{5} $ as desired.
25.03.2015 17:30
We will prove that the smallest constant is $c = 6 / 5.$ First, let us show that $c \ge 6 / 5.$ We take $n = 10q + 1$ for $q \in \mathbb{N}_0$ and set $k = \tfrac{4n + 1}{5}.$ Observe that $k$ is an odd positive integer with $1 \le k \le n.$ Now, consider the set $A = A_1 \cup A_2 \cup A_3$ where \[A_1 = \left\{1, 2, \cdots , \frac{k - 1}{2}\right\}, \quad A_2 = \left\{2k + 1, 2k + 2, \cdots , 2k + \frac{k - 1}{2}\right\}, \quad A_3 = \left\{ k + \frac{k + 1}{2}, k + \frac{k + 3}{2}, \cdots , 2k\right\}.\] It is clear that $A$ is a subset of $\{1, 2, \cdots , 2n\}$ with \[|A| = \frac{k - 1}{2} + \left(k - \frac{k - 1}{2}\right) + \frac{k - 1}{2} = \frac{6}{5}n - \frac{1}{5}.\] Hence, if we take the limit as $q \to \infty$, it follows that $|A| > \epsilon n$ for any $\epsilon < 6 / 5.$ Therefore, to show that $c \ge 6 / 5$, it suffices to prove that $A$ is good. In particular, we will show that the set $B = \{u \pm v \mid u, v \in A\}$ does not contain the integer $k.$ First, it is clear that if $u, v \in A$ satisfy $u + v = k$, then $u, v \in A_1$ (since all elements of $A_2$ and $A_3$ are greater than $k$). However, this is impossible, since the greatest possible sum of two elements of $A_1$ is $\tfrac{k - 1}{2} + \tfrac{k - 3}{2} < k.$ Meanwhile, if $u, v \in A$ satisfy $u - v = k$, we must have $u \equiv v \pmod{k}.$ By breaking up $A$ into subsets modulo $k$, we find that \[A = \{1, 2k + 1\} \cup \{2, 2k + 2\} \cup \cdots \cup \left\{\frac{k - 1}{2}, 2k + \frac{k - 1}{2}\right\} \cup \left\{k + \frac{k + 1}{2}\right\} \cup \left\{k + \frac{k + 3}{2}\right\} \cup \cdots \cup \{2k\}.\] It is then easy to see that no $u, v \in A$ satisfy $u - v = k.$ Hence, $c \ge 6 / 5$, as desired. $\blacksquare$ Now, we will show that $|A| \le \tfrac{6}{5}n$ for any good set $A \subseteq \{1, 2, \cdots , 2n\}.$ Suppose, by way of contradiction, that there exists a good set $A \subseteq \{1, 2, \cdots , 2n\}$ with $|A| > \tfrac{6}{5}n.$ Then there must exist some integer $k \in \{1, 2, \cdots , n\}$ such that $k \not \in B$, where $B = \{u \pm v \mid u, v \in A\}.$ By the Division Algorithm, let us write $2n = mk + p$ where $m \in \mathbb{N}$ and $0 \le p < k.$ In particular, notice that \[2n = mk + p < (m + 1)k \le (m + 1)n \implies 2 < m + 1 \implies 2 \le m.\] Now, consider the sets $S_i = \{b \in B \mid b \equiv i \pmod{k}\}$ ($i = 1, 2, \cdots , k$). We will examine these sets in pairs: $(S_1, S_{k - 1}), (S_2, S_{k - 2}), \cdots.$ First, observe that the only sets that are not part of a pair are $S_k$ and $S_{k / 2}$ (if $k$ is even). We begin by proving that at most $\tfrac{m + 1}{2m + 1}$ of the elements in $S_k \cup S_{k / 2}$ are in $B$ (if $k$ is odd, simply ignore the set $S_{k / 2}$ in the following analysis; the same conclusion still holds). Observe that $S_k$ has precisely $m$ elements, and $S_{k / 2}$ has either $m$ or $m + 1$ elements. Within each of these sets, no two consecutive elements can both be in $B$, since then the difference of these two consecutive elements would equal $k$, a contradiction. Hence, at most $\left\lceil \tfrac{m}{2} \right\rceil$ of the elements in $S_k$ are in $B$, and at most $\left\lceil \tfrac{m + 1}{2} \right\rceil$ of the elements in $S_{k / 2}$ are in $B.$ It is then easy to see that at most $\tfrac{m + 1}{2m + 1}$ of the elements in $S_k \cup S_{k / 2}$ are in $B.$ Now, we prove a similar bound for the pairs of sets described earlier: Consider any pair $(S_i, S_{k - i}).$ Notice that at most $1 / 2$ of the elements of one of these sets can be in $B.$ This is because if more than $1 / 2$ of the elements of each of these sets are in $B$, then because no two consecutive elements in either of these sets can be in $B$, it would follow that $i \in S_i$ and $k - i \in S_{k - i}$ must be in $B.$ However, this is impossible, since then the sum of these two elements would equal $k$, a contradiction. Therefore, at most $1 / 2$ of the elements in one of these two sets must be in $B.$ Keeping in mind that $|S_i| = m, m + 1$, it’s not hard to see that at most $\tfrac{m + 1}{2m + 1}$ of the elements in $S_i \cup S_{k - i}$ are in $B.$ Therefore, since $B \subseteq S_1 \cup S_2 \cup \cdots \cup S_k$, it follows that $|B| \le \tfrac{m + 1}{2m + 1} |S_1 \cup S_2 \cup \cdots \cup S_k| = \frac{m + 1}{2m + 1}(2n).$ Because $\tfrac{m + 1}{2m + 1} = \tfrac{1}{2} + \tfrac{1}{4m + 2}$ is a decreasing function of $n$ over $\mathbb{N}$, it follows that $\tfrac{m + 1}{2m + 1}$ takes on its maximal value for $m = 2.$ Hence, $|B| \le \tfrac{2 + 1}{4 + 1}(2n) = \tfrac{6}{5}n.$ This is a clear contradiction, since we assumed that $|B| > \tfrac{6}{5}n$. Thus, the proof is complete. $\square$
21.10.2024 14:52
n=5, {2,3,4,8,9,10} is an easy example for c=6/5