amirhtlusa wrote:

It's easier to group the integers and find the (k+1)st integer. Then you can just say the k integers larger than it must be consecutive, and u are done.

let $a_1 < a_2 < ... < a_{k+1} < a_{k+2} < ... < a_{2k+1}$ be distinct positive integers such that they sum to more than $N$ and any subset of $k$ of them has sum at most $N/2$. let $a_{k+2} = L$. we may then assume that $(a_1, ..., a_{k+1}) = (L-(k+1), ..., L - 1)$. (if not, replacing them with these numbers still produces a set satisfying the above conditions, because the $k$ largest elements remain unchanged.) Let $a_{k+2} +...+ a_{2k+1} = \frac{N}{2} - r$, where $r \geq 0$. Then because $\sum a_i > N$, we must have $\frac{N}{2} + r + 1 \leq a_1 + ... +a_{k+1} = L(k+1) - \frac{(k+1)(k+2)}{2} = S$ (**) Note also that $L = a_{k+2},\ L \leq a_{k+3} - 1,\ \cdots,\ L \leq a_{2k+1} - (k-1)$, so we get $S \leq a_{k+2} (k+1) - \frac{(k+1)(k+2)}{2}$, $S \leq (a_{k+3} - 1)(k+1) - \frac{(k+1)(k+2)}{2}$, ... $S \leq (a_{2k+1} - (k-1))(k+1) - \frac{(k+1)(k+2)}{2}$, and adding we get $kS \leq (k+1)(a_{k+2} + ... + a_{2k+1}) - \frac{(k+1)(k-1)k}{2} - \frac{k(k+1)(k+2)}{2}$, from which $S \leq \frac{k+1}{k}(\frac{N}{2}-r)-\frac{(k+1)(k-1)}{2} - \frac{(k+1)(k+2)}{2}$. together with (**) this gives $\frac{N}{2} + r + 1 \leq \frac{k+1}{k}(\frac{N}{2}-r)-\frac{(k+1)(k-1)}{2} - \frac{(k+1)(k+2)}{2}$; $\frac{(k+1)(k-1)}{2} + \frac{(k+1)(k+2)}{2} + r + r\frac{k+1}{k} + 1\leq \frac{N}{2k}$; $N \geq k(k+1)(k-1) + k(k+1)(k+2) + 2k = 2k^3+3k^2+3k$. equality is achieved when the $a_i$ are consecutive and their sum is exactly $2k^3+3k^2+3k+1$... i.e., when the numbers are $\{k^2+1, ..., k^2+2k+1\}$

Let $a_1 < ... <a_k< a_{k+1} < a_{k+2} < ... < a_{2k+1}$ be distinct positive integers such that they sum to more than $N$ and any subset of $k$ of them has sum at most $\frac{N}{2}$. It's clear that $a_{i+1} - a_i\ge 1$, so $a_{i+j} - a_i\ge j$. By assumption, we have, $(a_1 +\cdots+a_k)+ a_{k+1} +(a_{k+2} +\cdots+ a_{2k+1}) \ge N+1$ $= 2\cdot \frac{N}{2} + 1 \ge 2(a_{k+2} +\cdots+ a_{2k+1})+1$ So, $a_{k+1}\ge (a_{k+2} +\cdots+ a_{2k+1}) - (a_1 +\cdots+a_k) + 1$ $=(a_{k+2}-a_1) + \cdots+ (a_{2k+1} - a_k)+1 \ge k(k+1)+1=k^2+k+1$ Therefore, $\frac{N}{2} \ge a_{k+2} +\cdots+ a_{2k+1} =(a_{k+2}-a_{k+1}) + \cdots+ (a_{2k+1} - a_{k+1})+k a_{k+1}$ $\ge (1+\cdots+k) + k(k^2+k+1)$ That is, $N\geq k(k+1)+ 2k(k^2+k+1)= 2k^3+3k^2+3k$. For $N= 2k^3+3k^2+3k$, it's easy to verify that $k^2+1,\ldots, k^2+2k+1$ has sum $N+1$ and the sum of the last $k$ of them (which is the largest) is $\frac{N}{2}$.

Let the elements of our set $\{a_1, a_2, \ldots , a_{2k+1}\}$ be strictly increasing. Call the "upper bound", UB, $\left(\displaystyle\sum_{i=1}^{2k+1}a_i\right)-1$, and call the "lower bound", LB, $2\displaystyle\sum_{i=k+2}^{2k+1}a_i$. Now suppose we have a set with a valid $N$, i.e. $LB \le N \le UB$. Then if we increase $a_i$ by 1, where $i \le k$, then LB is unaffected and UB increases by 1, so we still have a valid $N$. If we decrease $a_i$ by 1, where $i \ge k+2$, then UB decreases by 1 and LB decreases by 2. So we still have a valid $N$ value, say $N'$, and $N' = N - 2 < N$. So we "crunch" our set around $a_{k+1}$ to get a set of consecutive integers, with a valid $N$-value less than or equal to the original. So our minimum $N$ will be found among sets of consecutive integers. Now we look at the set $\{1, 2, \ldots , 2k+1\}$, where $UB = (1 + 2 + \ldots + 2k+1) - 1 = \frac{(2k+1)(2k+2)}{2} - 1 = 2k^2 + 3k$, and $\\ LB = 2\left[(k+2) + (k+3) + \ldots + (2k+1)\right] \\ = 2\left[k(k+2) + (1 + 2 + \ldots + (k-1))\right] \\ = 2k^2 + 4k + k(k-1) \\ = 3k^2 + 3k.$ Call a "bump" to process of increasing each element of our set by 1. Through bumping our set $\{1, 2, \ldots , 2k+1\}$ we will get all sets of consecutive integers. A bump increases UB by $2k+1$, and increases LB by $2k$. Thus a bump increases UB by $1$ relative to LB. Since originally $LB - UB = (3k^2 + 3k) - (2k^2 + 3k) = k^2$, we must perform at least $k^2$ bumps to satisfy $UB \ge LB$. We will find our minimum $N$ after $k^2$ bumps, when $N = LB = (3k^2 + 3k) + k^2(2k) = 2k^3 + 3k^2 + 3k.$

Here's another proof, which resembles fuzzylogic's. Let $a_1$, $a_2$, $\ldots$, $a_{2k+1}$ be the $2k+1$ integers in increasing order. Then we have \begin{eqnarray*} N & = & 2k + (4k+2) \frac{N}{2} - 2k(N+1) \\ & \geq & 2k + (4k+2) \sum_{i=k+2}^{2k+1} a_i - 2k \sum_{i=1}^{2k+1} a_i \\ & = & 2k + (2k+2) \sum_{i=k+2}^{2k+1} a_i - 2k \sum_{i=1}^{k+1} a_i \\ & = & 2k + (2k+2) \sum_{i=k+2}^{2k+ 1} (a_i - a_{k+1}) + 2k \sum_{i=1}^{k+1} (a_{k+1} - a_i) \\ & \geq & 2k + (2k+2) \sum_{i=k+2}^{2k+1} (i - (k+1)) + 2k \sum_{i=1}^{k+1} (k+1 - i) \\ & = & 2k + (2k+2) \frac{k(k+1)}{2} + 2k \frac{k(k+1)}{2} \\ & = & 2k^3 + 3k^2 + 3k \, . \end{eqnarray*}

I thought this problem was just too easy. let {a_1,a_2 .. a_(2k+1)}be a satisfactory set of numbers with a_i < a_j iff i<j. it is evident that N+1 =< a_1 ... + a _(2k+1) and N/2 >= a_(k+2) .. + a_2k+1 therefore: 2 ( a_(k+2) .. + a_(2k+1) ) +1 <= a_1 + .. + a_(2k+1) <--> a_(k+2) .. + a_(2k+1) + 1 <= a_1 + (a_2 + ... a_(k+1)) <--> a_1 >= [a_(k+2) - a_2] + .. + [ a_(2k+1) - a_(k+1) ] + 1 = k + k .. + 1 = k^2 + 1 so it follows a_t >= k^2 + t; the conclusion follows easily N/2 >= (k^2 + k + 2) .. + (k^2 + 2k + 1) --> N>= 2k^3 + 3k^2 + 3k, and the fact that {k^2 + 1 ... (k+1)^2 } works finishes off the problem.

How did you guys find the example sequence? Guess and check?

I'm not sure if this is what you are asking, but after playing with the problem for awhile, you can guess that the minimal set of $ 2k + 1$ integers is a set of consecutive integers. So the set is $ \{ a, a + 1, \ldots, a + 2k \}$ for some integer $ a$. Then use the hypotheses to figure out the best value of $ a$. That is how you can guess the minimal set. You still need a rigorous argument to settle the problem.

I think this solution is more intuitive than some of the above (it's essentially the same idea, just phrased a bit differently).

$X:=a_1+a_2+\dots+a_k$, $Y:=a_{k+1}+a_{k+2}+\dots+a_{2k+1}$. $X\ge ka_k+\frac{k(k-1)}2$ and $Y\le(k+1)a_{k+1}-\frac{k(k+1)}2$ so \[\frac{N}2\ge X\ge ka_k+\frac{k(k-1)}2\ge k(a_{k+1}+1)+\frac{k(k-1)}2\ge k\left(\frac{Y}{k+1}+\frac{k}2+1\right)+\frac{k(k-1)}2\ge k\left(\frac{N/2+1}{k+1}+\frac{k}2+1\right)+\frac{k(k-1)}2\] so $N\ge k(2k^2+3k+3)$ with equality at $\{k^2+1,k^2+2,\dots,k^2+2k+1\}$

Let the positive integers be $a_1<a_2<\ldots<a_{2k+1}$. The condition then becomes $a_1+a_2+\ldots+a_{2k+1}>N$ and $\frac{N}{2}\geq a_{k+2}+a_{k+3}+\ldots+a_{2k+1}$ so $a_1+a_2+\ldots+a_{k+1}>N\geq2(a_{k+2}+a_{k+3}+\ldots+a_{2k+1})$, or $a_1+a_2+\ldots+a_{k+1}>a_{k+2}+a_{k+3}+\ldots+a_{2k+1}$. This condition is equivalent because by setting $N=2(a_{k+2}+a_{k+3}+\ldots+a_{2k+1})$. Now, note that by decreasing $a_i$ by 1 where $k+2\leq i\leq 2k+1$ (if possible), the condition still holds but we decrease the value of $N$. Hence, $a_{k+1},a_{k+2},\ldots,a_{2k+1}$ are consecutive for the minimal $N$. We now have $ka_{k+1}+\frac{k(k+1)}{2}=a_{k+2}+a_{k+3}+\ldots+a_{2k+1}<a_1+a_2+\ldots+a_{k+1}\leq(k+1)a_{k+1}-\frac{k(k+1)}{2}$, so $a_{k+1}>k(k+1)$, which means that $a_{k+1}\geq k^2+k+1$. Hence, $N=2(a_{k+2}+a_{k+3}+\ldots+a_{2k+1})=2ka_{k+1}+k(k+1)\geq 2k(k^2+k+1)+k(k+1)=2k^3+3k^2+3k$. Equality holds when $a_i=k^2+i$, so the minimum possible value of $N$ is $2k^3+3k^2+3k$.

The answer is $N = k(2k^2+3k+3)$ given by \[ S = \left\{ k^2+1, k^2+2, \dots, k^2+2k+1 \right\}. \] To show this is best possible, let the set be $S = \{ a_0 < a_1 < \dots < a_{2k} \}$ so that the hypothesis becomes \begin{align*} N + 1 &\le a_0 + a_1 + \dots + a_{2k} \\ N/2 &\ge a_{k+1} + \dots + a_{2k}. \end{align*}Subtracting twice the latter from the former gives \begin{align*} a_0 &\ge 1 + (a_{k+1}-a_1) + (a_{k+2}-a_2) + \dots + (a_{2k} - a_k) \\ &\ge 1 + \underbrace{k + k + \dots + k}_{k \text{ terms}} \\ &= 1 + k^2. \end{align*}Now, we have \begin{align*} N/2 &\ge a_{k+1} + \dots + a_{2k} \\ &\ge (a_0 + (k+1)) + (a_0 + (k+2)) + \dots + (a_0 + 2k) \\ &= k \cdot a_0 + \left( (k+1) + \dots + 2k \right) \\ &\ge k(k^2+1) + k \cdot \frac{3k+1}{2} \end{align*}so $N \ge k(2k^2+3k+3)$. Remark: The exact value of $N$ is therefore very superficial. From playing with these concrete examples we find out we are essentially just trying to find an increasing set $S$ obeying \[ a_0 + a_1 + \dots + a_k > a_{k+1} + \dots + a_{2k} \qquad (\star) \]and indeed given a sequence satisfying these properties one simply sets $N = 2(a_{k+1} + \dots + a_{2k})$. Therefore we can focus almost entirely on $a_i$ and not $N$. Remark: It is relatively straightforward to figure out what is going on based on the small cases. For example, one can work out by hand that $\{2,3,4\}$ is optimal for $k=1$ $\{5,6,7,8,9\}$ is optimal for $k=2$, $\{10,11,12,13,14,15,16\}$ is optimal for $k=3$. In all the examples, the $a_i$ are an arithmetic progression of difference $1$, so that $a_j - a_i \ge j-i$ is a sharp for all $i<j$, and thus this estimate may be used freely without loss of sharpness; applying it in $(\star)$ gives a lower bound on $a_0$ which is then good enough to get a lower bound on $N$ matching the equality cases we found empirically.

Let the $k$ smallest numbers be $a_1<\dots< a_k$, the $k$ largest numbers be $b_1< \dots< b_k$, and the median be $M$. Note that for all $i=1,2,\dots, k$, the inequality $b_i \ge a_i + (k+1)$ holds. Furthermore, since $\sum_{i=1}^{k} b_i \le N/2$ but the entire sum is greater than $N$, we have $M+ \sum_{i=1}^{k} a_i > \sum_{i=1}^{k} b_i$. Combining these observations, we deduce that $M>k(k+1$). Thus, we have \begin{align*} \frac{N}{2} \ge \sum_{i=1}^{k} b_i &\ge (k^2+k+2) + (k^2+k+3) + \dots + (k^2 + 2k + 1) \\ &=\frac{2k^3 + 3k^2 + 3k}{2} \end{align*}Hence, $N \ge 2k^3 + 3k^2 + 3k$. This can be achieved by the set of consecutive numbers $\{k^2+1, \dots, k^2+2k+1\}$, so this is indeed the minimal $N$. $\Box$

We claim the minimum value of $N$ is $\boxed{k(2k^2+3k+3)}$. To see that this is achieved, consider the set \[\{k^2+1,k^2+2,\ldots,k^2+2k+1\}.\]Now suppose we have a set \[\{a_1>a_2>\cdots>a_{2k}>a_{2k+1}\}\]that works. We see that $a_1+\cdots+a_k\le N/2$ and $a_1+\cdots+a_{2k+1}=N$, so \[2(a_1+\cdots+a_k)\le N<a_1+\cdots+a_{2k+1},\]so \[a_1+\cdots+a_k<a_{k+1}+\cdots+a_{2k+1}.\]Thus, \[(a_{k+1}+1)+\cdots+(a_{k+1}+k)<a_{k+1}+(a_{k+1}-1)+\cdots+(a_{k+1}-k),\]so \[ka_{k+1}+\frac{k(k+1)}{2}<(k+1)a_{k+1}-\frac{k(k+1)}{2},\]so $a_{k+1}\ge k^2+k+1$. Thus, \[a_1+\cdots+a_k\ge ka_{k+1}+\frac{k(k+1)}{2}=\frac{k}{2}(2k^2+3k+3),\]so $N\ge k(2k^2+3k+3)$, as desired.

We claim that the minimum value of $N$ is $N=k(2k^2+3k+3)$. We will first show that equality is achievable. Indeed, consider the set $\{k^2+1, k^2+2, \ldots, k^2+2k+1\}$. Let $a_1,\ldots,a_{2k+1}$ be the set, WLOG sorted in strictly increasing order. Then \[ a_{k+2}+\cdots+a_{2k+1} \le \frac{N}{2} \]and \[ a_1+\cdots+a_{2k+1} > N,\]so \[ a_1+\cdots+a_{k+1} > \frac{N}{2} \ge a_{k+2}+\cdots+a_{2k+1}. \]Let $b_i = a_i - a_1$. Then \begin{align*} &\qquad a_1+(a_1+b_2)+\cdots + (a_1+b_{k+1}) > (a_1+b_{k+2}) + \cdots+(a_1+b_{2k+1}) \\ &\implies (k+1)a_1 + (b_2+\cdots+b_{k+1}) > ka_1+(b_{k+2}+\cdots+b_{2k+1}) \\ &\implies a_1 > (b_{k+2}+\cdots+b_{2k+1}) - (b_2+\cdots+b_{k+1}). \end{align*}Since $\{a_i\}$ is strictly increasing, $1\le b_2<b_3<\cdots<b_{2k+1}$. So $b_i\ge i-1$ for $i=2,\ldots,2k+1$. Thus, $b_{k+1} \le b_{k+2}-1$, and $b_{k+1} - i \ge b_{k+1-i}$. Therefore, \begin{align*} b_2+\cdots+b_{k+1} &\le (b_{k+1}) + (b_{k+1}-1) + \cdots + (b_{k+1}-(k-1)) \\ &= kb_{k+1} - \frac{k(k-1)}{2} \\ &\le k(b_{k+2}-1) - \frac{k(k-1)}{2} \\ &= kb_{k+2} - \frac{k(k+1)}{2}. \end{align*}Similarly, $b_{k+2} \ge k+1$, and $k+1\le b_{k+2} < b_{k+3} <\cdots < b_{2k+1}$, so \begin{align*} b_{k+2}+\cdots+b_{2k+1} &\ge b_{k+2}+(b_{k+2}+1) +\cdots + (b_{k+2}+(k-1)) \\ &= kb_{k+2} + \frac{k(k-1)}{2}. \end{align*}Hence, \begin{align*} a_1 &> (b_{k+2} + \cdots+b_{2k+1}) - (b_2+\cdots+b_{k+1}) \\ &\ge kb_{k+2} + \frac{k(k-1)}{2} - kb_{k+2} + \frac{k(k+1)}{2} \\ &= k^2. \end{align*}Therefore, $a_k \ge k^2+1$. Finally, \begin{align*} \frac{N}{2} &\ge a_{k+2}+\cdots+a_{2k+1} \\ &= (a_1+b_{k+2}) + \cdots+(a_1+b_{2k+1}) \\ &= ka_1 + (b_{k+2} + \cdots+b_{2k+1} ) \\ &\ge k(k^2+1) + ((k+1)+\cdots+2k) \\ &= \frac{k(2k^2+3k+3)}{2} \\ \implies N&\ge k(2k^2+3k+3). \end{align*}

Let the numbers be $a_1 < a_2 < \cdots < a_k < a_{k+1} < \cdots < a_{2k+1}.$ The conditions are $a_{k+2}+\cdots+a_{2k+1} \leq N/2,$ and $a_1+\cdots+a_{2k+1}>N.$ Thus, $a_1+\cdots+a_{k+1}>N-(a_{k+2}+\cdots+a_{2k+1}) \geq N - N/2=N/2\geq a_{k+2}+\cdots+a_{2k+1}.$ If $b_i=a_{i+1}-a_1$ for $1 \leq i \leq k,$ we have $a_{k+j} \geq a_j + k = a_1+b_{j-1}+k$ for $2 \leq j \leq k+1.$ Then the inequality becomes $(k+1)a_1+(b_1+\cdots+b_k)>ka_1 + (b_1+b_2+\cdots b_k)+k\cdot k \implies a_1 > k^2$ Thus, $a_1+\cdots+a_{2k+1} \geq (k^2+1)+(k^2+2)+\cdots (k^2+2k+1)=2k^3+3k^2+3k+1,$ which is achieved exactly at $\{k^2+1,k^2+2,\ldots,k^2+2k+1\},$ giving the smallest $N=\boxed{2k^3+3k^2+3k}.$

REDACTED

We claim that the answer is $2k^3+3k^2+3k$. This can be achieved by taking $k^2+1$ through $(k+1)^2.$ Note that we essentially want to minimize the total sum while satisfying $$\text{Sum~of~k~largest}\leq \frac{(\text{Sum~of~all})-1}{2}.$$ Claim: In the optimal case, the set consists of consecutive positive integers. We say that the set has a inconsecutivity at index $i$ if the $i$th largest element is more than 1 larger than the $i+1$th largest element. Suppose FTSOC that an optimal set has an inconsecutivity at index $i$ for some $1\leq i \leq 2k.$ We will show that we can construct a better set. Case 1: $i\leq k$. Then, we can decrease each of the first $i$ elements by 1, which looking back at our inequality $$\text{Sum~of~k~largest}\leq \frac{(\text{Sum~of~all})-1}{2},$$will decrease the left side by $i$ but the right side by only $i/2$, so this inequality stays true but we have a more optimal set, contradiction. Case 2: $i>k$. Then, we can still decrease each of the first $i$ elements by 1. The LHS of that inequality will decrease $k$, but the right side decreases by at most $k$ (since $i\leq 2k$ and "Sum of all" decreases by $i$), so the inequality stays true and we have a more optimal set, also contradiction. Therefore, optimally, our set consists of consecutive positive integers. It is then easy to see that $k^2+1$ through $(k+1)^2$ is the smallest that works, so we are done.

We claim the answer is $N=2k^3+3k^2+3k,$ which works if we consider the set $\{k^2+1,k^2+2,\dots,k^2+(2k+1)\}.$ For the bound, we let $x_1<x_2\dots<x_{2k+1}$ be our integers. Notice $x_i\le x_{i+k}+k$ so \[x_2+x_3+\dots+x_{k+1}+k^2\le x_{k+2}+x_{k+3}+\dots+x_{2k+1}\]so \[N-x_1<x_2+x_3+\dots+x_{2k+1}\le N/2+N/2-k^2\le N-k^2.\]Therefore, $x_1>k^2$ and $N\ge (k^2+1)+(k^2+2)+\dots+(k^2+2k+1)=2k^3+3k^2+3k.$ $\square$

Feels very superficial for USAMO2 or even USAMO 1/4. The idea is to do some kind of smoothing argument as follows: Claim. It is optimal to have the $k$ largest elements of $S$ be consecutive integers. Proof. Suppose that we have a working subset $S$ that achieves a minimum value of $N$ that does not satisfy the conditions. Sort the elements of $S$ as $a_1 < a_2 < \cdots < a_{2k+1}$. Suppose there exists an index $k+2 \leq i \leq 2k+1$ such that $a_{i+1} > a_i + 1$. Then, we can shift $a_{i+1}$ down by $1$. Then, notice that the set $\{a_{k+2}, a_{k+3}, \cdots, a_{2k + 1}\}$ still has maximal sum out of all subsets; in particular, every subset has sum at most $\frac N2 - 1$. Furthermore, because the original $2k+1$ elements summed to at least $N$, this new set sums to at least $N-1$. Thus, choosing the constant $N-2$ in place of $N$ works in this case, so $N$ is not minimal, contradiction. $\blacksquare$ Now, the sum of the terms $a_1$ through $a_{k+1}$ must exceed the sum of the terms $a_{k+2}$ through $A_{2k+1}$ by the condition. Let $n = a_{k+2}$; then, we have the inequality $$n+(n+1)+(n+2)+\cdots+(n+k-1) \leq \sum_{i=1}^{k+1} a_i \leq (n-k-1) + (n-k) + \cdots + (n-1),$$or $$(2n-k-2)(k+1) \geq (2n+k-1)k.$$This simplifies to $n \geq k^2+k+1$, so the total sum $$\sum_{i=1}^{2k+1} a_i \geq k^2+(k^2+1) + \cdots + (k+1)^2 =2k^3+3k^2+3k.$$Equality clearly holds.

Let the set $S$ contain integers $a_1 > a_2 > \cdots > a_{2k+1}\ge 1$. Note that every subset of $S$ with size $k$ having sum at most $\tfrac{N}{2}$ is equivalent to the assertion \[ \quad a_1 + a_2 + \dots + a_k\le \frac{N}{2}.\]Now, we have \[ (k+1)a_k - \frac{(k+1)(k+2)}{2} = (a_k- 1) + \dots + (a_k- (k+1))\ge a_{k+1} + \dots + a_{2k+1} > \frac{N}{2},\]and \[ \frac{N}{2}\ge a_1 + \dots + a_k \ge a_k + (a_k + 1) + \dots + (a_k + (k-1)) = ka_k + \frac{(k-1)k}{2}.\]It follows that \[(k+1)a_k - \frac{(k+1)(k+2)}{2} > ka_k + \frac{(k-1)k}{2}\implies a_k > k^2 + k + 1.\]Hence, \[ N\ge 2ka_k + k^2 - k \ge 2k(k^2 +k + 2) + k^2 - k = \boxed{2k^3 + 3k^2 + 3k}.\]A construction for this $N$ is $a_k = k^2 + k + 2$ and $a_{k + i} = k^2 + k + 2 - i$ for each $i = -k+1, \dots, k+1$.

Very nice problem! The answer is $N=2k^3+3k^2+3k$ with the integers $k^2+1,k^2+2,\dots,k^2+(2k+1)$. WLOG $x_1<x_2<\dots<x_{2k+1}$. The key is to see that $$x_i\le x_{i+k}+k\implies x_2+x_3+\dots+x_{k+1}+k^2\le x_{k+2}+x_{k+3}+\dots+x_{2k+1}\le\frac N2$$$$\implies N-x_1<(x_2+x_3+\dots+x_{k+1})+(x_{k+2}+\dots+x_{2k+1})\le\frac N2-k^2+\frac N2\le N-k^2.$$$$\implies x_1>k^2\implies N\ge (k^2+1)+(k^2+2)+\dots+(k^2+2k+1)=2k^3+3k^2+3k.\blacksquare$$

I claim that the value of $N=k(2k^2+3k+3)$ works. First we prove the bound, then we give the construction. Firstly, $a_1,a_2,\ldots a_{2k+1}$ denote the elements of the set that satisfy the problem conditions. Also, WLOG let $a_1\ge a_2\ge \cdots\ge a_{2k+1}$. Now note that the condition for the sum of every subset of size $k$ being most $\dfrac{N}{2}$ is equivalent to $a_1+a_2+\cdots+a_k\le \dfrac{N}{2}$ due to the ordering we imposed. Now from this bound, we have that $\dfrac{N}{2}\ge a_1+\cdots+a_k\ge (a_k+(k-1))+(a_k+(k-2))+\cdots+(a_k)=ka_k+\dfrac{(k-1)k}{2}\implies a_k\le \dfrac{N-k^2+k}{2k}$. We also had that the sum was greater than $N$ which gives the following. \begin{align*} N&<a_1+a_2+\cdots+a_k+a_{k+1}+a_{k+2}+\cdots+a_{2k+1}\\ &\le (a_1+a_2+\cdots+a_k)+(a_k-1)+(a_k-2)+\cdots+(a_k-(k+1))\\ &\le \dfrac{N}{2}+(k+1)a_k - \dfrac{(k+1)(k+2)}{2} .\end{align*} Now finally using the bound we got for $a_k$ that we got earlier with our current bound (along with some painful algebraic calculations), we get that $N\ge k(2k^2+3k+3)$. So this proves our minimality. Now we provide the construction. Consider the following sequence.\[k^2+1,k^2+2,\ldots,k^2+2k+1.\]We can check that this actually satisfies our condition and we are done.

The answer is $\boxed{N = 2k^3 + 3k^2 + 3k}$. This can be achieved with the set $\{k^2 + 1, k^2 + 2, \ldots, k^2 + 2k + 1\}$. We will now show this is is indeed the minimal $N$. Claim: The minimum $N$ occurs when all of the elements of the set are consecutive. Proof: Let $x_1 < x_2 < \cdots < x_{2k + 1}$ be the elements of a set satisfying the condition, i.e. there is some (not necessarily minimal) $N'$ such that $x_1 + x_2 + \cdots + x_{2k + 1} > N'$ and $x_{k + 2} + x_{k + 3} + \cdots + x_{2k + 1} \le \tfrac{N'}{2}$. Let $d_1 = x_2 - x_1, d_2 = x_3 - x_2, \ldots, d_{2k} = x_{2k + 1} - x_{2k}$. Note that $d_1, d_2, \ldots, d_{2k} \ge 1$. If $d_i > 1$ for some $i$, then consider when happens when we shift $x_{i + 1}, x_{i + 2}, \ldots, x_{2k + 1}$ down by $d_i - 1$. We see that: If $i \ge k + 1$, then the sum of the $k$ largest elements and the sum of all of the elements both decrease by $(d_i - 1)(2k + 1 - i)$. Since $\tfrac{N'}{2} - (d_i - 1)(2k + 1 - i) < \tfrac{1}{2}(N' - (d_i - 1)(2k + 1 - i))$, this new set still satisfies the conditions If $i \le k$, then the sum of the $k$ largest elements decreases by $(d_i - 1)k$, while the sum of all elements decreases by $(d_i - 1)(2k + 1 - i)$. But $\tfrac{N'}{2} - (d_i - 1)k < \tfrac{1}{2}(N' - (d_i - 1)(2k + 1 - i))$, so this new set also satisfies the condition. Therefore, we can see in order to achieve the minimal $N$, all of the differences have to be $1$, which proves the claim. Thus, we can now set $x_i = x_1 + i - 1$ for $2 \le i \le 2k + 1$. Then we get $$(x_1 + k + 1) + (x_1 + k + 2) + \cdots + (x_1 + 2k) \le \tfrac{N}{2} < \tfrac{1}{2}(x_1 + (x_1 + 1) + \cdots + (x_1 + 2k)).$$This simplifies to $x_1 > k^2$, so $N \ge 2((k^2 + k + 2) + (k^2 + k + 3) + \cdots + (k^2 + 2k + 1)) = 2k^3 + 3k^2 + 3k$, as desired.

The answer is $N = \boxed{2k^3+3k^2+3k}$, which can be achieved with the set $\{k^2+1, k^2+2, \dots, k^2+2k+1\}$. WLOG let $x_1<x_2<\dots<x_{2k+1}$. Notice \[x_i + k \le x_{i+k} \implies \sum_{i=2}^{k+1} x_i+k^2 \le \sum_{i=k+2}^{2k+1} x_i \le N/2\]\[\implies N-x_1< (N/2-k^2)+N/2 = N-k^2.\] Hence, $x_1>k^2$, so by setting $x_1=k^2+1$, and taking the rest as consecutive integers, we show that $2k^3+3k^2+3k$ is the minimum.

Easy question

Based upon smaller cases we conjecture that we need consecutive integers. Thus we want to make use of the inequality $x_i + 1 \leq x_{i+1}$ due to the sharpness principle, and force equality to hold. Order the list in increasing order and denote the smallest element by $x_0$ and for all other elements, represent them as $x_i = x_0 + c_i$. Then, \begin{align*} kx_0 + \sum_{i = k+1}^{2k} c_i &\leq \frac{N}{2}\\ (2k+1)x_0 + \sum_{i=1}^{2k} c_i &> N \end{align*}Then subtracting twice of the first equation from the second we find, \begin{align*} x_0 &> \sum_{i=1}^k (c_{k+i} + c_i) > \sum_{i=1}^{k} k = k^2 \end{align*}Thus $x_0$ is at least $k^2 + 1$. Then $N$ satisfies, \begin{align*} \frac{N}{2} &\geq k \cdot (k^2+1) + \sum_{i=k+1}^{2k} i\\ \iff N &\geq 2k^3 + 3k^2 + 3k \end{align*}Thus we must have $\boxed{N \geq 2k^3 + 3k^2 + 3k}$. It is easy to see that when equality holds, it works so we are done.

Our desired condition is equivalent to \begin{align*} &a_1 + a_2 + \ldots + a_{k+1} > a_{k+2} + a_{k+3} + \ldots + a_{2k+1} \\ \implies &a_1 > (a_{k+2}-a_2) + (a_{k+3}-a_3) + \ldots + (a_{2k+1}-a_{k+1}) \ge k^2. \end{align*} Thus the minimal value of $a_1$ is $k^2+1$. Note that the optimal value of $N$ is just twice the sum of the largest $k$ numbers in the set, so the $2k+1$ consecutive integers $\{k^2+1, k^2+2, \ldots, k^2+2k+1\}$ does the trick. This gives us our answer of $\boxed{2k^3+3k^2+3k}$.

The answer is $N = 2 \left(k(k^2 +1) + (2k+1)k - \frac{k(k+1)}{2} \right) = 2k^3 + 3k^2 + 3k$, which is achievable by $\{k^2 + 1, k^2 + 2, \ldots, k^2 + 2k +1 \}$. Now we prove the bound. For a given $k$, let a good set (ordered in increasing order) be any set of distinct positive integers where the sum of the last $k$ elements is less than the sum of the first $k + 1$ elements, and let a super set be a good set where the sum of the last $k$ elements is minimal. It's clear that the set of positive integers achieving $N$ must be good, and the smallest possible value of $N$ for that good set is equal to twice the sum of the last $k$ elements. Claim: There exists a super set where all the elements are consecutive (they form an arithmetic sequence with common difference $1$). Proof: If the last $k$ elements are not all consecutive in a super set, then if the smallest of these last $k$ elements (the $k+1$th element) is $x$, then the last element must be greater than $x + k$, but we can change the last $k$ elements into $x, x + 1, \ldots x + (k-1)$ (preserving goodness), so the original set was not super. Therefore the last $k$ elements must be consecutive. Now no matter what the first $k+1$ elements are, consider changing them into $x - (k+1), x - k, \ldots, x - 1$. As they were originally all distinct and under $x$, this doesn't decrease their sum, so the set stays good. Moreover, the set also stays super as the sum of the last $k$ elements is unaffected. This super set we constructed has elements $x - (k+1), x - k, \ldots, x + (k-1)$, which means it has consecutive elements, as desired. $\square$ The smallest value of $N$ is twice the sum of the last $k$ elements in any super set. Consider the unique super set that has consecutive elements, starting from $a_1$. The sum of the first $k+1$ elements is $(k+1) a_1 +\frac{k(k+1)}{2}$ and the sum of the last $k$ elements is $k a_1 + (2k+1) k - \frac{k(k+1)}{2}$. Hence, we have \[ (k+1) a_1 +\frac{k(k+1)}{2} > k a_1 + (2k+1) k - \frac{k(k+1)}{2} \implies a_1 > k^2 \] Hence the sum of the last $k$ elements is at least $k(k^2 + 1) + (2k+1) k - \frac{k(k+1)}{2}$, so \[N \ge 2 \left( k (k^2 + 1) + (2k+1) k - \frac{k(k+1)}{2} \right) ,\]as desired.

First of all, assume WLOG that $$a_1 < a_2 < \dots < a_{2k+1}$$. And note that \[a_{j}-a_i \geq j-i.\]By problem condition we have that \[ a_1+a_2+ \dots +a_{2k+1} \geq N+1 \geq 2(a_{k+2}+a_{k+3}+ \dots + a_{2k+1})+1.\]Subtracting we get that \[a_1 \geq (a_{k+2}-a_2)+ (a_{k+3}-a_3)+ \dots +(a_{2k+1}-a_{k+1})+1\]\[ \geq \underbrace{k + k + \dots + k}_{k \text{ terms}} +1 \]\[ =k^2+1\]Which follows from the fact we stated above. From which we deduce that our set is \[ {k^2+1,k^2+2, \dots , k^2+2k+1}\]Which means that \[ N \leq 2((k^2+1)+(k^2+2)+ \dots + k^2+2k+1)-1\]\[= 2k^3+3k^2+3k \]As desired.

Out of the set of $2k + 1$ integers, let $A$ be the sum of the $k$ smallest, $B$ the sum of the $k$ largest, and $m$ the middle element. Note that $B \le \frac{N}{2}$, so $A + B + m \ge N + 1 \implies A + m \ge \frac{N}{2} + 1 \ge B + 1$. Now clearly $$\frac{1}{2} k(2m - k - 1) = (m - 1) + (m - 2) + \dots + (m - k) \ge A$$and $$B \ge (m + 1) + (m + 2) + \dots + (m + k) = \frac{1}{2} k(2m + k + 1).$$Therefore $$\frac{1}{2} k(2m - k - 1) + m \ge \frac{1}{2} k(2m + k) + 1 \implies k(2m - k - 1) + 2m \ge k(2m + k + 1) + 2$$$$\implies 2mk - k^2 - k + 2m \ge 2mk + k^2 + k + 2 \implies m \ge k^2 + k + 1.$$Now $N \ge 2B = k(2m + k + 1) \ge k(2k^2 + 3k + 3) = 2k^3 + 3k^2 + 3k$ as desired. Attainability can be demonstrated with the set of positive integers betwee $k^2 + 1$ and $k^2 + 2k + 1$ inclusive.

I don't know why it took me so long to solve it. Also my solution is similar to others. $\textbf{Answer:}$ $N=2k^3+3k^2+3k$. $\textbf{Solution:}$ Let $S$ be the set with $2k+1$ distinct positive integers $\iff \lvert S \lvert=2k+1$ $S=\{a_1,a_2, \dots, a_{2k+1} \}$. WLOG $a_1<a_2< \dots < a_{2k+1}$. So $\boxed{a_{i+j} \geq a_i +j} ...(*)(\because a_1 \leq a_2 +1 \leq \dots \leq a_{2k+1} +2k+1) $ Now from the two conditions we have: $\boxed{N<a_1+a_2+\dots+a_{2k+1}}$ $...(1)$ $a_{k+2}+a_{k+3}+\dots+a_{2k+1} \leq \frac{N}{2} \implies \boxed{ 2\cdot (a_{k+2}+a_{k+3}+\dots+a_{2k+1}) \leq N}$ $...(2)$ Combining $(1)$ and $(2)$ we get: $2(a_{k+2}+a_{k+3}+\dots+a_{2k+1}) \stackrel{(2)}{\leq} N \stackrel{(1)}{<} a_1+a_2+\dots+ a_{2k+1}$ $\implies 2(a_{k+2}+a_{k+3}+\dots+a_{2k+1}) < a_1+a_2+\dots+a_{2k+1}$ $\implies (2a_{k+2}+2a_{k+3}+\dots+2a_{2k+1})-(a_2+a_3+ \dots + a_{2k+1}) < a_1$ $\implies 2a_{k+2}+2a_{k+3}+\dots+2a_{2k+1}-a_2 - a_3 - \dots - a_{2k+1} <a_1$ $\implies a_{k+2}+a_{k+3}+\dots+a_{2k+1} - a_2 - a_3 - \dots - a_{k+1} < a_1$ $\implies (a_{k+2}-a_2)+(a_{k+3}-a_3)+\dots+ (a_{2k+1}-a_{k+1}) < a_1$ $...(3)$ Combining $(*)$ with $(3)$ we get the following: $(k+a_2-a_2)+(k+a_3-a_3)+ \dots + (k +a_{k+1}-a_{k+1}) \stackrel{(*)}{\leq} (a_{k+2}-a_2)+(a_{k+3}-a_3)+\dots+ (a_{2k+1}-a_{k+1}) \stackrel{(3)}{<} a_1$ $\implies \underbrace{k + k + \dots + k}_{k \text{ terms}} \leq (a_{k+2}-a_2)+(a_{k+3}-a_3)+\dots+ (a_{2k+1}-a_{k+1}) <a_1 $ $\implies k^2 \leq (a_{k+2}-a_2)+(a_{k+3}-a_3)+\dots+ (a_{2k+1}-a_{k+1}) <a_1$ $\implies k^2 < a_1 \iff a_1 >k^2 \implies $ $$\boxed{a_1 \geq k^2+1} ...(@)$$ Again from $(2)$ we have: $N \geq 2 \cdot (a_{k+2}+a_{k+3}+ \dots +a_{2k+1}) \stackrel{(*)}{\geq} 2 \cdot (((a_1+(k+1))+(a_1 +(k+2))+ \dots + (a_1+2k))=$ $=2 \cdot (a_1+k+1+a_1+k+2+ \dots + a_1+2k)=2 \cdot (a_1+k+1+a_1+k+2+ \dots + a_1+k+k)=$ $=2 \cdot ( \underbrace{a_1 + a_1 + \dots + a_1}_{k \text{ terms}} +\underbrace{k + k + \dots + k}_{k \text{ terms}} + 1+2+\dots + k)=$ $=2 \cdot(k \cdot a_1 + k \cdot k +\frac{k \cdot (k+1)}{2})=2 \cdot k \cdot a_1 + 2k^2 + k \cdot (k+1)=$ $=2 \cdot k \cdot a_1 + 2k^2+k^2+k \stackrel{(@)}{\geq} 2 \cdot k \cdot (k^2+1)+k^2+k=2k^3+2k+3k^2+k \implies $ $$\boxed{N \geq 2k^3+3k^2+3k}$$ So now we just show that $N=2k^3+3k^2+3k$ works. By picking $(a_1,a_2, \dots a_{2k+1})=(k^2+1,k^2+2, \dots k^2+2k+1).$ We see that $N=2k^3+3k^2+3k$ clearly works and satisfies both conditions. $\blacksquare$