Every subset of size k has sum at most N/2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

orl

3647 posts

orl

#1 h Apr 20, 2006, 5:58 PM • 7 Y

Y by Aritra12, Adventure10, megarnie, TheHawk, Mango247, WiseTigerJ1, PikaPika999

For a given positive integer $k$ find, in terms of $k$ , the minimum value of $N$ for which there is a set of $2k + 1$ distinct positive integers that has sum greater than $N$ but every subset of size $k$ has sum at most $\tfrac{N}{2}.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

amirhtlusa

2176 posts

amirhtlusa

#2 h Apr 20, 2006, 10:23 PM • 4 Y

Y by Adventure10, TheHawk, WiseTigerJ1, PikaPika999

hint1
2

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

rem

1434 posts

rem

#3 h Apr 20, 2006, 11:05 PM • 5 Y

Y by Adventure10, TheHawk, Mango247, WiseTigerJ1, PikaPika999

amirhtlusa wrote:

hint1
2

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

pleurestique

867 posts

pleurestique

#4 h Apr 21, 2006, 7:55 PM • 4 Y

Y by Adventure10, TheHawk, Mango247, WiseTigerJ1

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\}$

This post has been edited 2 times. Last edited by pleurestique, Apr 21, 2006, 10:15 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

fuzzylogic

719 posts

fuzzylogic

#5 h Apr 21, 2006, 9:02 PM • 3 Y

Y by Adventure10, Mango247, WiseTigerJ1

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

carpo

142 posts

carpo

#6 h Apr 22, 2006, 4:41 AM • 3 Y

Y by Adventure10, Mango247, WiseTigerJ1

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.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ravi B

3083 posts

Ravi B

#7 h Apr 23, 2006, 4:10 PM • 5 Y

Y by Adventure10, TheHawk, WiseTigerJ1, and 2 other users

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*}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

epitomy01

240 posts

epitomy01

#8 h Apr 24, 2006, 1:34 AM • 3 Y

Y by A_Math_Lover, Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

123456789

1327 posts

123456789

#9 h Sep 6, 2008, 10:41 PM • 2 Y

Y by Adventure10, Mango247

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ravi B

3083 posts

Ravi B

#11 h Sep 22, 2008, 12:25 AM • 2 Y

Y by Adventure10 and 1 other user

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Temperal

1563 posts

Temperal

#13 h May 20, 2009, 1:34 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

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

Click to reveal hidden text

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Bugi

1857 posts

Bugi

#14 h Jul 21, 2010, 9:55 PM • 3 Y

Y by Justwait, Adventure10, Mango247

A little bit different

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

codyj

723 posts

codyj

#15 h Apr 3, 2015, 6:52 PM • 1 Y

Y by Adventure10

$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\}$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ABCDE

1963 posts

ABCDE

#16 h Apr 4, 2016, 4:58 PM • 2 Y

Y by Adventure10, Mango247

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$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

v_Enhance

6872 posts

v_Enhance

#17 h Apr 1, 2019, 8:26 PM • 8 Y

Y by pad, Illuzion, v4913, Adventure10, Mango247, vrondoS, two_steps, MS_asdfgzxcvb

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

brainfertilzer

1831 posts

brainfertilzer

#41 h Apr 30, 2023, 10:54 PM

Y by

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$ .
comment

This post has been edited 1 time. Last edited by brainfertilzer, Apr 30, 2023, 10:55 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

huashiliao2020

1292 posts

huashiliao2020

#42 h Aug 8, 2023, 12:22 AM

Y by

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kamatadu

473 posts

kamatadu

#43 h Aug 15, 2023, 4:13 PM • 1 Y

Y by HoripodoKrishno

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. :stretcher:

This post has been edited 1 time. Last edited by kamatadu, Aug 15, 2023, 4:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

eibc

599 posts

eibc

#45 h Aug 23, 2023, 1:25 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

joshualiu315

2513 posts

joshualiu315

#46 h Dec 22, 2023, 8:53 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

lelouchvigeo

179 posts

lelouchvigeo

#47 h Jan 3, 2024, 6:50 AM

Y by

Easy question
Answer

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Shreyasharma

673 posts

Shreyasharma

#48 h Feb 4, 2024, 10:25 PM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

793 posts

shendrew7

#49 h Feb 17, 2024, 9:21 PM

Y by

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

megarnie

5576 posts

megarnie

#50 h Feb 22, 2024, 1:24 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ywgh1

139 posts

Ywgh1

#51 h Mar 21, 2024, 5:50 PM

Y by

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.

This post has been edited 5 times. Last edited by Ywgh1, Nov 2, 2024, 1:38 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

blueprimes

326 posts

blueprimes

#53 h Jul 30, 2024, 10:00 PM

Y by

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.

This post has been edited 1 time. Last edited by blueprimes, Aug 6, 2024, 1:05 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ItsBesi

141 posts

ItsBesi

#54 h Aug 30, 2024, 4:46 PM

Y by

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$

This post has been edited 2 times. Last edited by ItsBesi, Sep 1, 2024, 10:13 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Namura

9 posts

Namura

#55 h Feb 20, 2025, 3:42 AM

Y by

Similar solution
Click to reveal hidden text

This post has been edited 1 time. Last edited by Namura, Feb 20, 2025, 3:43 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Ihatecombin

55 posts

Ihatecombin

#56 h Feb 20, 2025, 12:27 PM • 1 Y

Y by PikaPika999

The answer is $N = 2k^3+3k^2 + 3k$ , with the set $\{k^2+1,k^2+1,\dots,k^2+2k+1\}$ . This can be easily checked to work, we shall prove it is the minimum.
Order the elements, notice that we must have
$(k+2)a_{k+2} + a_{k+3} + \cdots + a_{2k+1} - \frac{(k+1)(k+2)}{2} \geq a_1 + a_2 + \dots a_{2k+1} \geq N+1$ We also obtain
$a_{k+2} + a_{k+3} + \cdots + a_{2k+1} \leq \frac{N}{2} \Longrightarrow N \geq 2(a_{k+2} + a_{k+3} + \cdots + a_{2k+1})$ By adding the two inequalities above, we obtain
$ka_{k+2} - \frac{(k+1)(k+2)}{2} \geq a_{k+3} + \cdots + a_{2k+1} + 1 \geq (k-1)a_{k+2} + \frac{(k-1)(k)}{2} + 1$ Whence we must have
$a_{k+2} \geq \frac{(k+1)(k+2)}{2} + \frac{(k-1)(k)}{2} + 1 = k^2 + k + 2$ Since we must have
$a_{k+2} + a_{k+3} + \cdots + a_{2k+1} \leq \frac{N}{2}$ The minimality of $N$ immediately follows.