Splitting integers 1, 2, 3, … n to avoid least possible sum

Question

For each positive integer n, partition the integers 1, 2, 3, … 2n into two sets of n integers each. Let g(n) be the least integer such that there is such a partition in neither of whose parts there is a subset of numbers whose sum is g(n). (Thus g(5) = 11 because of {1,3,4,5,9} and {2,6,7,8,10}). Is anything known about g(n)?

Answer 1

Let me show that $g(n)$ grows quadratically (surely, it cannot grow faster). It follows from the following

Claim. Let $t$ be a sufficiently large integer, and let $A\subset\{1,2,\dots,2t-1\}$ be a subset of cardinality $|A|\geq t$. Then every integer $s\in[O(t\log t),t^2/2(1+o(1))]$ is a sum of some subset in $A$.

This easily implies that $g(n)\geq n^2/2(1+o(1))$, since for every $s\in [2n,n^2/2(1+o(1))]$ we may fins a suitable $t\leq n$; then the intersection of one of the partitioning sets with $[1,2t-1]$ will satisfy the condition of the Claim.

To prove the Claim, we start with some lemmas.

Lemma 1. Let $a<b<n$ be positive integers, and let $B\subset[0,n]$ be a set of integers with $|B|>\frac{a}{a+b}(n+b+1)$. Then $B$ contains two numbers whose difference lies in $[a,b]$.

Proof of Lemma 1. Assume the contrary. Let $b_1<\dots<b_k$ be all elements of $B$. Split them into blocks such that the neighboring numbers in a block differ by at most $b-a$. Each block $b_i<\dots<b_j$ `prohibits' the numbers in $[b_i+a,b_j+b]$ from entering $B$ (in particular, $b_j<b_i+a$). Moreover, the prohibited segments for different blocks do not intersect, and both blocks and prohibited segments lie in $[0,n+b]$. Finally, the lengths ratio of a block and its prohibited segment is at most $$ \frac{b_j-b_i+1}{b_j-b_i+1+(b-a)}=\left(1+\frac{b-a}{b_j-b_i+1}\right)^{-1} \leq \left(1+\frac{b-a}a\right)^{-1}=\frac ab. $$ Thus the blocks cannot cover more than $\frac a{a+b}$-th part of $[0,n+b]$, as required.

Lemma 2. Let $d_0,d_1,\dots,d_k$ be positive numbers with $d_1=1$, and $d_i\leq 1+\sum_{j<i}d_j$ for all $i\leq k$. Then every number from 1 to $\sum_i d_i$ is a sum of some of $d_i$'s.

Proof of Lemma 2. Induction on $k$; both the base and the step are clear.

Proof of the Claim. Let us add $0$ to $A$; this does not change the set of subset sums.

Now $A$ contains two integers with difference 1; call them $x_0<y_0$ and delete them from $A$. By Lemma 1, the remaining set contains two numbers with difference 1 or 2 (if $t$ is large enough), call them $x_1<y_1$ and delete them from $A$. Repeat the procedure in the following manner: on the $k$th step, we choose from the remaining set two numbers $x_{k+1}<y_{k+1}$ such that $$ \left\lfloor\left(\frac43\right)^k\right\rfloor\leq y_k-x_k\leq \left\lceil\left(\frac43\right)^{k+1}\right\rceil. $$ By Lemma 1, it is possible while $$ t+1-2k=|A|-2k\geq \frac37\left(2t+\left(\frac43\right)^k+1\right). $$ i.e. when $t\geq 3\left(\frac43\right)^k+14k+2$. Thus we may stop, say, at some $k_0$ of order $k_0\approx \log_{4/3}(t/4)$, and then add 20 more pairs $x_\ell<y_\ell$ with $(4/3)^{k_0}\leq x_\ell-y_\ell\leq (4/3)^{k_0+1}$ (recall that $t$ is sufficiently large).

Now denote $d_i=y_i-x_i$ for $i=0,\dots,k_0+20$. One can easily check that this sequence satisfies the conditions of Lemma 2, and that $\sum_i d_i\geq 2t$. Denote $B=A\setminus\{x_0,y_0,\dots,x_{k_0+20},y_{k_0+20}\}$.

Finally, we are ready to represent each $s$. Let us start collecting the subset by putting there all $y_i$'s; their number is of order $t\log t$, so the sum now does not exceed $s$. Then we add one by one the elements of $B$; the sum of elements in $B$ is at least $t^2/2(1+o(1))$, so at some moment the sum in a subset under collection will exceed $s$. Stop at this moment; the sum $s'$ in our subset now lies in $[s,s+2t-2]$, so there exists a set $\{i_1,\dots,i_m\}$ with $\sum_jd_{i_j}=s'-s$. Now one may replace $y_{i_j}$ by $x_{i_j}$ obtaining a desired subset.

Answer 2

As n gets larger, the quantity g(n) - 2n should grow, primarily because small sums can't be avoided by an even partition. An analysis that g(6) > 13 should illustrate the principle.

To attempt to avoid the sum 13 in a required partition of 1 through 12, note that if a+b =c and c+d=13, and all four numbers are distinct and in the set, placing a and b in one part and c in the other will not avoid the sum 13, as d placed in either part will produce the sum. One such tuplet is (1,2,3,10), and another is (1,3,4,9). The first tuplet witnessess that if 1 and 2 are in the same part, then 3 also must be in that part to hope avoiding a sum of 13. However, other considerations will show that 4 and 5 must be in that part. Similarly, using (2,3,5,8) will show that 2,3, and 5 must be together, and again other constraints will show that 13 cannot be avoided.

This suggests to me that the quantity g(n)-2n gets a (delayed) quadratic order of growth when n gets larger than 5, primarily because small sums can't be avoided in a bipartition.