Stay ahead of learning milestones! Enroll in a class over the summer!

G
Topic
First Poster
Last Poster
k a May Highlights and 2025 AoPS Online Class Information
jlacosta   0
May 1, 2025
May is an exciting month! National MATHCOUNTS is the second week of May in Washington D.C. and our Founder, Richard Rusczyk will be presenting a seminar, Preparing Strong Math Students for College and Careers, on May 11th.

Are you interested in working towards MATHCOUNTS and don’t know where to start? We have you covered! If you have taken Prealgebra, then you are ready for MATHCOUNTS/AMC 8 Basics. Already aiming for State or National MATHCOUNTS and harder AMC 8 problems? Then our MATHCOUNTS/AMC 8 Advanced course is for you.

Summer camps are starting next month at the Virtual Campus in math and language arts that are 2 - to 4 - weeks in duration. Spaces are still available - don’t miss your chance to have an enriching summer experience. There are middle and high school competition math camps as well as Math Beasts camps that review key topics coupled with fun explorations covering areas such as graph theory (Math Beasts Camp 6), cryptography (Math Beasts Camp 7-8), and topology (Math Beasts Camp 8-9)!

Be sure to mark your calendars for the following upcoming events:
[list][*]May 9th, 4:30pm PT/7:30pm ET, Casework 2: Overwhelming Evidence — A Text Adventure, a game where participants will work together to navigate the map, solve puzzles, and win! All are welcome.
[*]May 19th, 4:30pm PT/7:30pm ET, What's Next After Beast Academy?, designed for students finishing Beast Academy and ready for Prealgebra 1.
[*]May 20th, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 1 Math Jam, Problems 1 to 4, join the Canada/USA Mathcamp staff for this exciting Math Jam, where they discuss solutions to Problems 1 to 4 of the 2025 Mathcamp Qualifying Quiz!
[*]May 21st, 4:00pm PT/7:00pm ET, Mathcamp 2025 Qualifying Quiz Part 2 Math Jam, Problems 5 and 6, Canada/USA Mathcamp staff will discuss solutions to Problems 5 and 6 of the 2025 Mathcamp Qualifying Quiz![/list]
Our full course list for upcoming classes is below:
All classes run 7:30pm-8:45pm ET/4:30pm - 5:45pm PT unless otherwise noted.

Introductory: Grades 5-10

Prealgebra 1 Self-Paced

Prealgebra 1
Tuesday, May 13 - Aug 26
Thursday, May 29 - Sep 11
Sunday, Jun 15 - Oct 12
Monday, Jun 30 - Oct 20
Wednesday, Jul 16 - Oct 29

Prealgebra 2 Self-Paced

Prealgebra 2
Wednesday, May 7 - Aug 20
Monday, Jun 2 - Sep 22
Sunday, Jun 29 - Oct 26
Friday, Jul 25 - Nov 21

Introduction to Algebra A Self-Paced

Introduction to Algebra A
Sunday, May 11 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Wednesday, May 14 - Aug 27
Friday, May 30 - Sep 26
Monday, Jun 2 - Sep 22
Sunday, Jun 15 - Oct 12
Thursday, Jun 26 - Oct 9
Tuesday, Jul 15 - Oct 28

Introduction to Counting & Probability Self-Paced

Introduction to Counting & Probability
Thursday, May 15 - Jul 31
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Wednesday, Jul 9 - Sep 24
Sunday, Jul 27 - Oct 19

Introduction to Number Theory
Friday, May 9 - Aug 1
Wednesday, May 21 - Aug 6
Monday, Jun 9 - Aug 25
Sunday, Jun 15 - Sep 14
Tuesday, Jul 15 - Sep 30

Introduction to Algebra B Self-Paced

Introduction to Algebra B
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Sunday, May 11 - Nov 9
Tuesday, May 20 - Oct 28
Monday, Jun 16 - Dec 8
Friday, Jun 20 - Jan 9
Sunday, Jun 29 - Jan 11
Monday, Jul 14 - Jan 19

Paradoxes and Infinity
Mon, Tue, Wed, & Thurs, Jul 14 - Jul 16 (meets every day of the week!)

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Jun 1 - Nov 23
Tuesday, Jun 10 - Nov 18
Wednesday, Jun 25 - Dec 10
Sunday, Jul 13 - Jan 18
Thursday, Jul 24 - Jan 22

Intermediate Counting & Probability
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Tuesday, Jun 10 - Aug 26

Calculus
Tuesday, May 27 - Nov 11
Wednesday, Jun 25 - Dec 17

Group Theory
Thursday, Jun 12 - Sep 11

Contest Preparation: Grades 6-12

MATHCOUNTS/AMC 8 Basics
Friday, May 23 - Aug 15
Monday, Jun 2 - Aug 18
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

MATHCOUNTS/AMC 8 Advanced
Sunday, May 11 - Aug 10
Tuesday, May 27 - Aug 12
Wednesday, Jun 11 - Aug 27
Sunday, Jun 22 - Sep 21
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Problem Series
Friday, May 9 - Aug 1
Sunday, Jun 1 - Aug 24
Thursday, Jun 12 - Aug 28
Tuesday, Jun 17 - Sep 2
Sunday, Jun 22 - Sep 21 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Monday, Jun 23 - Sep 15
Tues & Thurs, Jul 8 - Aug 14 (meets twice a week!)

AMC 10 Final Fives
Sunday, May 11 - Jun 8
Tuesday, May 27 - Jun 17
Monday, Jun 30 - Jul 21

AMC 12 Problem Series
Tuesday, May 27 - Aug 12
Thursday, Jun 12 - Aug 28
Sunday, Jun 22 - Sep 21
Wednesday, Aug 6 - Oct 22

AMC 12 Final Fives
Sunday, May 18 - Jun 15

AIME Problem Series A
Thursday, May 22 - Jul 31

AIME Problem Series B
Sunday, Jun 22 - Sep 21

F=ma Problem Series
Wednesday, Jun 11 - Aug 27

WOOT Programs
Visit the pages linked for full schedule details for each of these programs!


MathWOOT Level 1
MathWOOT Level 2
ChemWOOT
CodeWOOT
PhysicsWOOT

Programming

Introduction to Programming with Python
Thursday, May 22 - Aug 7
Sunday, Jun 15 - Sep 14 (1:00 - 2:30 pm ET/10:00 - 11:30 am PT)
Tuesday, Jun 17 - Sep 2
Monday, Jun 30 - Sep 22

Intermediate Programming with Python
Sunday, Jun 1 - Aug 24
Monday, Jun 30 - Sep 22

USACO Bronze Problem Series
Tuesday, May 13 - Jul 29
Sunday, Jun 22 - Sep 1

Physics

Introduction to Physics
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
May 1, 2025
0 replies
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

Find instructions and a list of contests to add here: https://artofproblemsolving.com/community/c40244h1064480_contests_to_add
1 reply
dcouchman
Sep 9, 2019
v_Enhance
Apr 5, 2023
k i Zero tolerance
ZetaX   49
N May 4, 2019 by NoDealsHere
Source: Use your common sense! (enough is enough)
Some users don't want to learn, some other simply ignore advises.
But please follow the following guideline:


To make it short: ALWAYS USE YOUR COMMON SENSE IF POSTING!
If you don't have common sense, don't post.


More specifically:

For new threads:


a) Good, meaningful title:
The title has to say what the problem is about in best way possible.
If that title occured already, it's definitely bad. And contest names aren't good either.
That's in fact a requirement for being able to search old problems.

Examples:
Bad titles:
- "Hard"/"Medium"/"Easy" (if you find it so cool how hard/easy it is, tell it in the post and use a title that tells us the problem)
- "Number Theory" (hey guy, guess why this forum's named that way¿ and is it the only such problem on earth¿)
- "Fibonacci" (there are millions of Fibonacci problems out there, all posted and named the same...)
- "Chinese TST 2003" (does this say anything about the problem¿)
Good titles:
- "On divisors of a³+2b³+4c³-6abc"
- "Number of solutions to x²+y²=6z²"
- "Fibonacci numbers are never squares"


b) Use search function:
Before posting a "new" problem spend at least two, better five, minutes to look if this problem was posted before. If it was, don't repost it. If you have anything important to say on topic, post it in one of the older threads.
If the thread is locked cause of this, use search function.

Update (by Amir Hossein). The best way to search for two keywords in AoPS is to input
[code]+"first keyword" +"second keyword"[/code]
so that any post containing both strings "first word" and "second form".


c) Good problem statement:
Some recent really bad post was:
[quote]$lim_{n\to 1}^{+\infty}\frac{1}{n}-lnn$[/quote]
It contains no question and no answer.
If you do this, too, you are on the best way to get your thread deleted. Write everything clearly, define where your variables come from (and define the "natural" numbers if used). Additionally read your post at least twice before submitting. After you sent it, read it again and use the Edit-Button if necessary to correct errors.


For answers to already existing threads:


d) Of any interest and with content:
Don't post things that are more trivial than completely obvious. For example, if the question is to solve $x^{3}+y^{3}=z^{3}$, do not answer with "$x=y=z=0$ is a solution" only. Either you post any kind of proof or at least something unexpected (like "$x=1337, y=481, z=42$ is the smallest solution). Someone that does not see that $x=y=z=0$ is a solution of the above without your post is completely wrong here, this is an IMO-level forum.
Similar, posting "I have solved this problem" but not posting anything else is not welcome; it even looks that you just want to show off what a genius you are.

e) Well written and checked answers:
Like c) for new threads, check your solutions at least twice for mistakes. And after sending, read it again and use the Edit-Button if necessary to correct errors.



To repeat it: ALWAYS USE YOUR COMMON SENSE IF POSTING!


Everything definitely out of range of common sense will be locked or deleted (exept for new users having less than about 42 posts, they are newbies and need/get some time to learn).

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
Something nice
KhuongTrang   33
N 2 minutes ago by NguyenVanHoa29
Source: own
Problem. Given $a,b,c$ be non-negative real numbers such that $ab+bc+ca=1.$ Prove that

$$\sqrt{a+1}+\sqrt{b+1}+\sqrt{c+1}\le 1+2\sqrt{a+b+c+abc}.$$
33 replies
+1 w
KhuongTrang
Nov 1, 2023
NguyenVanHoa29
2 minutes ago
Geometry hard
Lukariman   2
N 2 minutes ago by Primeniyazidayi
Given triangle ABC inscribed in circle (O). The bisector of angle A intersects (O) at D. Let M, N be the midpoints of AB, AC respectively. OD intersects BC at P and AD intersects MN at S. The circle circumscribed around triangle MPS intersects BC at Q different from P. Prove that QA is tangent to (O).
2 replies
Lukariman
43 minutes ago
Primeniyazidayi
2 minutes ago
help!!!!!!!!!!!!
Cobedangiu   3
N 3 minutes ago by sqing
help
3 replies
Cobedangiu
Mar 23, 2025
sqing
3 minutes ago
Inequality
nguyentlauv   1
N 4 minutes ago by NguyenVanHoa29
Source: Own
Let $a,b,c$ be positive real numbers such that $ab+bc+ca=3$ and $k\ge 0$, prove that
$$\frac{\sqrt{a+1}}{b+c+k}+\frac{\sqrt{b+1}}{c+a+k}+\frac{\sqrt{c+1}}{a+b+k} \geq \frac{3\sqrt{2}}{k+2}.$$
1 reply
nguyentlauv
Yesterday at 12:19 PM
NguyenVanHoa29
4 minutes ago
Great similarity
steven_zhang123   3
N 17 minutes ago by Lil_flip38
Source: a friend
As shown in the figure, there are two points $D$ and $E$ outside triangle $ABC$ such that $\angle DAB = \angle CAE$ and $\angle ABD + \angle ACE = 180^{\circ}$. Connect $BE$ and $DC$, which intersect at point $O$. Let $AO$ intersect $BC$ at point $F$. Prove that $\angle ACE = \angle AFC$.
3 replies
steven_zhang123
43 minutes ago
Lil_flip38
17 minutes ago
AD=BE implies ABC right
v_Enhance   117
N 2 hours ago by cj13609517288
Source: European Girl's MO 2013, Problem 1
The side $BC$ of the triangle $ABC$ is extended beyond $C$ to $D$ so that $CD = BC$. The side $CA$ is extended beyond $A$ to $E$ so that $AE = 2CA$. Prove that, if $AD=BE$, then the triangle $ABC$ is right-angled.
117 replies
v_Enhance
Apr 10, 2013
cj13609517288
2 hours ago
Geometry
gggzul   6
N 3 hours ago by Captainscrubz
In trapezoid $ABCD$ segments $AB$ and $CD$ are parallel. Angle bisectors of $\angle A$ and $\angle C$ meet at $P$. Angle bisectors of $\angle B$ and $\angle D$ meet at $Q$. Prove that $ABPQ$ is cyclic
6 replies
gggzul
Yesterday at 8:22 AM
Captainscrubz
3 hours ago
Geometry
Lukariman   5
N 3 hours ago by Lukariman
Given circle (O) and point P outside (O). From P draw tangents PA and PB to (O) with contact points A, B. On the opposite ray of ray BP, take point M. The circle circumscribing triangle APM intersects (O) at the second point D. Let H be the projection of B on AM. Prove that $\angle HDM$ = 2∠AMP.
5 replies
Lukariman
Yesterday at 12:43 PM
Lukariman
3 hours ago
Aime type Geo
ehuseyinyigit   4
N 5 hours ago by ehuseyinyigit
Source: Turkish First Round 2024
In a scalene triangle $ABC$, let $M$ be the midpoint of side $BC$. Let the line perpendicular to $AC$ at point $C$ intersect $AM$ at $N$. If $(BMN)$ is tangent to $AB$ at $B$, find $AB/MA$.
4 replies
ehuseyinyigit
Monday at 9:04 PM
ehuseyinyigit
5 hours ago
n variables with n-gon sides
mihaig   1
N 5 hours ago by mihaig
Source: Own
Let $n\geq3$ and let $a_1,a_2,\ldots, a_n\geq0$ be reals such that $\sum_{i=1}^{n}{\frac{1}{2a_i+n-2}}=1.$
Prove
$$\frac{24}{(n-1)(n-2)}\cdot\sum_{1\leq i<j<k\leq n}{a_ia_ja_k}\geq3\sum_{i=1}^{n}{a_i}+n.$$
1 reply
mihaig
Apr 25, 2025
mihaig
5 hours ago
Centroid, altitudes and medians, and concyclic points
BR1F1SZ   3
N Today at 5:48 AM by EeEeRUT
Source: Austria National MO Part 1 Problem 2
Let $\triangle{ABC}$ be an acute triangle with $BC > AC$. Let $S$ be the centroid of triangle $ABC$ and let $F$ be the foot of the perpendicular from $C$ to side $AB$. The median $CS$ intersects the circumcircle $\gamma$ of triangle $\triangle{ABC}$ at a second point $P$. Let $M$ be the point where $CS$ intersects $AB$. The line $SF$ intersects the circle $\gamma$ at a point $Q$, such that $F$ lies between $S$ and $Q$. Prove that the points $M,P,Q$ and $F$ lie on a circle.

(Karl Czakler)
3 replies
BR1F1SZ
Monday at 9:45 PM
EeEeRUT
Today at 5:48 AM
area of O_1O_2O_3O_4 <=1, incenters of right triangles outside a square
parmenides51   2
N Today at 4:35 AM by Solilin
Source: Thailand Mathematical Olympiad 2012 p4
Let $ABCD$ be a unit square. Points $E, F, G, H$ are chosen outside $ABCD$ so that $\angle AEB =\angle BF C = \angle CGD = \angle DHA = 90^o$ . Let $O_1, O_2, O_3, O_4$, respectively, be the incenters of $\vartriangle ABE, \vartriangle BCF, \vartriangle CDG, \vartriangle DAH$. Show that the area of $O_1O_2O_3O_4$ is at most $1$.
2 replies
parmenides51
Aug 17, 2020
Solilin
Today at 4:35 AM
Geo metry
TUAN2k8   3
N Today at 4:34 AM by TUAN2k8
Help me plss!
Given an acute triangle $ABC$. Points $D$ and $E$ lie on segments $AB$ and $AC$, respectively. Lines $BD$ and $CE$ intersect at point $F$. The circumcircles of triangles $BDF$ and $CEF$ intersect at a second point $P$. The circumcircles of triangles $ABC$ and $ADE$ intersect at a second point $Q$. Point $K$ lies on segment $AP$ such that $KQ \perp AQ$. Prove that triangles $\triangle BKD$ and $\triangle CKE$ are similar.
3 replies
TUAN2k8
Yesterday at 10:33 AM
TUAN2k8
Today at 4:34 AM
China South East Mathematical Olympiad 2013 problem 2
s372102   3
N Today at 2:11 AM by AGCN
$\triangle ABC$, $AB>AC$. the incircle $I$ of $\triangle ABC$ meet $BC$ at point $D$, $AD$ meet $I$ again at $E$. $EP$ is a tangent of $I$, and $EP$ meet the extension line of $BC$ at $P$. $CF\parallel PE$, $CF\cap AD=F$. the line $BF$ meet $I$ at $M,N$, point $M$ is on the line segment $BF$, the line segment $PM$ meet $I$ again at $Q$. Show that $\angle ENP=\angle ENQ$
3 replies
s372102
Aug 10, 2013
AGCN
Today at 2:11 AM
Wot n' Minimization
y-is-the-best-_   25
N May 2, 2025 by john0512
Source: IMO SL 2019 A3
Let $n \geqslant 3$ be a positive integer and let $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a strictly increasing sequence of $n$ positive real numbers with sum equal to 2. Let $X$ be a subset of $\{1,2, \ldots, n\}$ such that the value of
\[
\left|1-\sum_{i \in X} a_{i}\right|
\]is minimised. Prove that there exists a strictly increasing sequence of $n$ positive real numbers $\left(b_{1}, b_{2}, \ldots, b_{n}\right)$ with sum equal to 2 such that
\[
\sum_{i \in X} b_{i}=1.
\]
25 replies
y-is-the-best-_
Sep 23, 2020
john0512
May 2, 2025
Wot n' Minimization
G H J
Source: IMO SL 2019 A3
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
y-is-the-best-_
16 posts
#1 • 3 Y
Y by centslordm, megarnie, Mango247
Let $n \geqslant 3$ be a positive integer and let $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a strictly increasing sequence of $n$ positive real numbers with sum equal to 2. Let $X$ be a subset of $\{1,2, \ldots, n\}$ such that the value of
\[
\left|1-\sum_{i \in X} a_{i}\right|
\]is minimised. Prove that there exists a strictly increasing sequence of $n$ positive real numbers $\left(b_{1}, b_{2}, \ldots, b_{n}\right)$ with sum equal to 2 such that
\[
\sum_{i \in X} b_{i}=1.
\]
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
MarkBcc168
1595 posts
#2 • 2 Y
Y by centslordm, WTFrrrrrrrf
Comment

Solution
This post has been edited 1 time. Last edited by MarkBcc168, Sep 23, 2020, 6:42 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
dgrozev
2463 posts
#3 • 2 Y
Y by parmenides51, centslordm
This problem (with slightly different wording) had appeared here in this forum, as being given at some TST. I commented it in my blog without knowing it's from ISL 2019.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
rcorreaa
238 posts
#4 • 1 Y
Y by centslordm
Wow, I apparently have solved an A3. Hope it isn't a fakesolve! :P

Firstly, observe that the condition of $
\left|1-\sum_{i \in X} a_{i}\right|
= \delta$ being minimal is equivalent to $$
\frac{\left|\sum_{i \in X^C} a_i -\sum_{i \in X} a_{i}\right|}{2} $$be minimal. Then, assume WLOG that $\sum_{i \in X^C} a_i > \sum_{i \in X} a_{i}$ (if the equality ocurred, we would be done). Also, for any strictly increasing sequence of $n$ positive real numbers $(c_1,c_2,...,c_n)$, let $$\Delta_{(c_1,c_2,...,c_n)}= \left|\sum_{i \in X^C} c_i -\sum_{i \in X} c_{i}\right|$$We want to prove that there exists a strictly increasing sequence of $n$ positive real numbers $(b_1,b_2,...,b_n)$ such that $$\Delta_{(b_1,b_2,...,b_n)}=0$$
Now, observe that since $\frac{\Delta_{(a_1,a_2,...,a_n)}}{2}$ is minimal, for all $a_y \in X^C$ and $a_x \in X$ (they exist, since $\Delta_{(a_1,a_2,...,a_n)}>0$, we have that $$\frac{\Delta_{(a_1,a_2,...,a_n)}}{2} < a_y-a_x \qquad(\star)$$otherwise we could place $a_y$ in $X$ and $a_x$ in $X^C$ and $\frac{\Delta_{(a_1,a_2,...,a_n)}}{2}$ would decrease and would be greater than $0$, by assumption, and we would have a better choice for $X$, a contradiction!

Then, take $x_0 \in X, y_0 \in X^C$ with $a_{x_0} < a_{y_0}$ such that $a_{y_0}-a_{x_0}=M$ is minimal. From $(\star)$, $ \delta= \frac{\Delta_{(a_1,a_2,...,a_n)}}{2} < M$. Thus, if we choose $b_i=a_i+\frac{\delta}{|X|}$ for all $i \in X$ and $b_i=a_i-\frac{\delta}{|X^C|}$, the order of the terms in $b_i \in X$ is the same of $a_i \in X$, as well as the order of the terms in $b_i \in X^C$ is the same of $a_i \in X^C$. Furthermore, $b_y-b_x < M$, from $(\star)$, so we don't have issues with an index $i \in X$ sweeping with and index $j \in X^C$ in the new choice of sequence (the sequence keeps strictly increasing). Hence, this new sequence satisfies $\Delta_{(b_1,b_2,...,b_n)}=0$, $\sum_{i=1}^n b_i = \sum_{i=1}^n a_i = 2$ and $\sum_{i \in X} b_{i}=1$ by construction.

Therefore, we are done.

$\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Tintarn
9042 posts
#6 • 2 Y
Y by centslordm, sabkx
We solve the problem by characterizing all sets $X$ which can occur.
To this end, write $Y=X^c$ for the complement and $X>Y$ ("$X$ majorizes $Y$") if for every $k$, the set $X$ contains at least as many indices larger than $k$ as does $Y$. Similarly, define $Y>X$. (Note that we do not at all need to have either $X>Y$ or $Y>X$.)
Now if $X>Y$ it is clear that $\sum_{i \in X} b_i>1$. Similarly, if $Y>X$ it is clear that $\sum_{i \in X} b_i<1$.
So we better prove that such sets $X$ cannot occur.
Indeed, let us prove the following two facts:
1) If $X>Y$, then $X$ can not be a minimizing set as in the problem statement.
2) If we do not have $X>Y$, then we can find $b_i$ such that $\sum_{i \in X} b_i<1$.
Before we prove 1) and 2), let us see how this finishes the problem.
From 1) we get that the set $X$ from the problem must have neither $X>Y$ nor $Y>X$. Then from 2) we get a sequence $b_i$ such that $\sum_{i  \in X} b_i<1$ and a sequence $c_i$ such that $\sum_{i \in X} c_i>1$. Taking a convex linear combination (which will still be strictly increasing and have total sum equal to $2$) we find a sequence with sum over $X$ exactly $1$.
Finally, let us see how to prove 1) and 2):
Proof of 1): Indeed, write $X=\{x_1,\dots,x_k\}$ and $Y=\{y_1,\dots,y_m\}$ with the elements in decreasing order. So $x_1 >y_1, x_2 > y_2$ etc. So $\sum_{i \in Y} a_i<1<\sum_{i \in Y} x_i$. But if $k \ge 2$ and $m \ge 1$ the set $M=\{y_1,x_2,\dots,x_k\}$ will have a sum strictly between the two sums, hence $X$ can not be a minimizing set. So we must have $X=\{n\}$ or $X=\{1,2,\dots,n\}$ both of which are easily seen to be only possibly minimizing if $n \le 2$ (so this is where our proof uses $n \ge 3$). Done.
Proof of 2): So for some $k$ the set $X$ contains less than half of the indices from $\{k+1,\dots,n\}$. Choose $c_i=0$ for $i \le k$ and $c_i=\frac{2}{n-k}$ for $i>k$. This is an increasing sequence with $\sum_{i \in X} c_i<1$. Now just perturb $c_i$ to a sequence $b_i$ by a sufficiently small $\varepsilon$ to make it strictly increasing and still have $\sum_{i \in X} b_i<1$. Done.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jj_ca888
2726 posts
#7 • 7 Y
Y by mijail, samrocksnature, centslordm, sabkx, Mango247, Mango247, Mango247
Ok. I realize that this problem isn't particularly hard; it's just really annoying.

Split $a_1, \ldots , a_n$ into $X = \{x_1, \ldots , x_k\}$ and $Y = \{y_1, \ldots , y_{\ell}\}$ where $k + \ell = n$. Denote the sum of all $x_i$ as $1 + \epsilon$ and the sum of all $y_i$ as $1 - \epsilon$. If $\epsilon$ is ever $0$, then we are done. So WLOG $\epsilon > 0$.

Note that $\epsilon \leq x_i - y_j$ for all $i, j$ (where $x_i > y_j$ at least). If otherwise, then we may send $y_j$ to $X$ and $x_i$ to $Y$ and obtain a smaller $\epsilon '$ since\[1 - \epsilon < \sum Y' = (1 - \epsilon) + (x_i - y_j) \leq 1.\]In fact, we may further assume $\epsilon < x_i - y_j$ since if equality occurs, then after the swap, $\epsilon ' = 0$.

Similarly, with this swapping argument, we obtain that all $x_i$ are greater than $\epsilon$.

Now we construct a sequence $b_1, \ldots , b_n$ that satisfies the requirements. Let $S$ be the set of indices $i$ for which $a_i$ is a $x$ term and $T$ be the set of indices $j$ for which $a_j$ is a $y$ term. Clearly $|S| = k$ and $|T| = \ell$. I claim that the following sequence, defined by\begin{align*}b_i = a_i - \tfrac{\epsilon}{k} \text{  }\forall i \in S\\b_i = a_i + \tfrac{\epsilon}{\ell} \text{  }\forall i \in T\end{align*}works. Indeed, check that $\sum b_i = \sum a_i + {\epsilon} - {\epsilon} = 2$. and $\sum_{i \in S} b_i = (1 + \epsilon) - \epsilon = 1$.

It remains to check that this sequence is strictly increasing. If $b_m, b_{m+1}$ are either both in $S$ or both in $T$, then it clearly follows that $b_m < b_{m+1}$ since $a_m < a_{m+1}$. If $b_m \in S$ and $b_{m+1} \in T$, then also $b_{m+1} - b_m = (a_{m+1} - a_m) + \tfrac{\epsilon}{k} + \tfrac{\epsilon}{\ell} > 0$.

Now, if $b_m \in T$ and $b_{m+1} \in S$, then\[b_{m+1} - b_m = (x_i - y_j) - (\tfrac{\epsilon}{k} + \tfrac{\epsilon}{\ell}) \geq (x_i - y_j) - \epsilon > 0\]by our first note, along with using the fact that $\tfrac{1}{k} + \tfrac{1}{\ell} \leq \tfrac{1}{2} + \tfrac{1}{2n - 4} \leq 1$ for $n \geq 3$ unless $k$ or $\ell$ is $1$.

If $k = 1$, then the only $x$ term has value $1 + \epsilon > 1$ which is bad since then the next largest term is a $y$-term and has value $< 1$, contradicting minimality of $\epsilon$.

If $\ell = 1$, then the only $y$ term has value $1 - \epsilon$. The sum of the $n - 1$ remaning terms is $1 + \epsilon$. The sum of the smallest $n - 2$ terms is $> (n-2)\epsilon$, so the largest $x$ term is $< 1 + (3 - n)\epsilon = 1$. So if $x_{max} >$ the only $y$ term, we get a contradiction since their difference is $< \epsilon$. Thus, the $y$ term is the largest $a_i$, meaning that $b_m \in T$ and $b_{m+1} \in S$ is impossible.

So indeed, this sequence $b_i$ works. $\blacksquare$
This post has been edited 12 times. Last edited by jj_ca888, Oct 18, 2020, 3:42 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
alexiaslexia
110 posts
#8 • 3 Y
Y by centslordm, Kingsbane2139, sabkx
"No way an A3 could be THAT hard ..." $\Rightarrow$ me during the test, when I finally did it for 2.5x the average time other TST takers needed. Set-theory oriented solution in a completely different flavor: (first idea akin to the third solution from the official Shortlist).
For notational purposes let $[n]$ be the set $\{ 1,2,\ldots,n\}$.
Denote $a_{i+1} - a_i = d_i$, and $a_1$ be $d_0$. Note that the objective is equivalent to finding a sequence $\{b_i, 1 \leq i \leq n\}$ so that
\[ \sum_{i\in X} b_i = \sum_{j \in [n]-X} b_j \]and also that the problem statement is equivalent to $X$ satisfying
\[ \left| \sum_{i\in X} a_i - \sum_{j \in [n]-X} a_j \right| \]being the lowest possible among all set $X \subseteq [n]$, with the real numbrers $a_i$ fixed.
$\textcolor{green}{\textbf{\text{Main idea.}}}$ Bash for the win! We directly compute the terms
\[ S_d = \sum_{j\in Y} a_j - \sum_{i \in X} a_i = \sum_{i = 0}^{n-1} c_id_i \]in terms of $d_i$ (here, we let $Y = [n] - X$ for simplicity). Without Loss of Generality we can assume $X$ to be the set with the smaller sum.
\[
\begin{tabular}{cccccccccccc}
$a_i|\,\, i\in X$=&0&&$a_1$&&&&$a_3$\\
$a_j|\,\, j\in Y$=&&&&&$a_2$&&&&$a_4$&&$a_5$ \\
&&\kern-2\tabcolsep\upbracefill\kern-2\tabcolsep&&\kern-2\tabcolsep\upbracefill\kern-2\tabcolsep&&\kern-2\tabcolsep\upbracefill\kern-2\tabcolsep&&\kern-2\tabcolsep\upbracefill\kern-2\tabcolsep&&\kern-2\tabcolsep\upbracefill\kern-2\tabcolsep \\
&&$d_0$&&$d_1$&&$d_2$&&$d_3$&&$d_4$ \\[3pt]
&&&&&&&&&&\text{Y-block} 
\end{tabular}
\]For example, when $X = \{1,3\}$ and $Y = \{2,4,5\}$, $S_d$ (the letters $S_d$ represents the sum of "differences" $d_i$) = $1 \cdot d_0+ 2 \cdot d_1 + 1 \cdot d_2 + 2 \cdot d_3 + 1 \cdot d_4$.
Note that if not all coefficients $c_i$ is of "unified" sign, e.g. there exists a positive and negative coefficient, we can $\textbf{easily}$ set the $d_i$ so that
\[ \sum_{i; c_i > 0} |c_i|d_i = \sum_{j; c_j<0} |c_j|d_j \](one way to do it is to set all $d_i$ in the $LHS$ to be $1$, all $d_j$ except one on the $RHS$ to be $\frac{0.001}{n^2}$ and adjust the one not yet filled accordingly.) In these cases, setting $b_i$ equal to the new $d_0+\cdots + d_{i-1}$ fulfills the objective.
So let all $c_i$ be positive or $0$, as these are the exceptional cases where we would like to investigate further (and ultimately, prove that these cases do not exist by the statement given in the problem.) Before we continue, we present a simple, but central observation.
$\textcolor{blue}{\textbf{\text{Observation.}}}$ Let $i \in X$ and $i+1 \in Y$. If $X' = X \cup \{i+1\} - \{i\}$, then $S_d' = S_d - 2d_i$.
$\textcolor{blue}{\textbf{\text{Proof.}}}$ Obvious [Just note that $S_d' = S_d - (a_{i+1} - a_{i}) + (a_{i} - a_{i+1})].$
$\rule{25 cm}{3pt}$
We have two different finishes from here.
$\textcolor{red}{\textbf{\text{Finish 1: Polished, after redoing the problem.}}}$ Divide the indices into $\textit{blocks}$ of $X$ and $Y$. For example, in the set $X = \{1,4,6\}$ and $Y = \{2,3,5,7\}$, set the $Y-$blocks to be $\{2,3\}, \{5\}$ and $\{7\}$. Define an $X-Y$ transitional index to be the last index in any $X$- block, and say the $X-Y$ transitional index of an $X-$block to be its final index. (this is another way of categorizing the indices in which we can make a switch in the above $\textcolor{blue}{\textbf{\text{Observation.}}}$). We claim the following:
$\textbf{Claim 1.}$ Each $X-Y$ transitional index $i$ has coefficient $c_i$ at least $1$.
$\textbf{Proof 1.}$ Consider the coefficient $c_{i+1}$ of $d_{i+1}$. Then, we can be sure that $c_{i} = c_{i+1} +1 \geq 0+1 = 1$. Here we use the observation that $c_i$ is the difference between "the amount of indices in $Y$" and "the amount of indices in $X$" greater than $i$.

$\textbf{Claim 2.}$ There are at most one $X-Y$ transitional index.
$\textbf{Proof 2.}$ If $i$ and $j$ are $X-Y$ transitional indices, then
\[ S_d(X) \geq c_id_i + c_jd_j \geq 1 \cdot d_i + 1 \cdot d_j \]Consider $X'(i)$ and $X'(j)$ after switching $i$ with $i+1$, or $j$ with $j+1$ respectively. Then, one of $S_d(X'(i)) \geq d_i - d_j$ and $S_d(X'(j)) \geq d_j-d_i$ is at least $0$, but less than $S_d$.
$\rule{25cm}{0.5pt}$
These two claims greatly delimit the possible configurations of $X$, as we can just let $X$ to be an interval $[i,j] \in [n]$ or a collection of two intervals $[a,b], [c,d]$ where $0<a<b<c<d = n$. However, the second case can also be easily ruled out as $X$ does not contain the largest number $a_n$.
On the first case, if $|X| > n-j$; i.e. there are more terms in $X$ rather than the ending $Y-$block, then the coefficient of $d_{i-1}$ is negative. Otherwise we can be sure that the $X-$ block is kind of small.
First subcase: if the ending $Y-$ block's size is $2$ or greater: then we know that $d_j$ is at least 2. Then consider $X'$ obtaining from switching $j$ with $j+1$.
Second subcase: ending $Y-$ block's size is $1$. Then, the size of the $X-$ block is also 1, and a little experimentation yields that choosing $X = \{n\}$ contradicts the $\textbf{original}$ problem statement. (While the value of $a_n$ alone can certainly be BIG, it cannot be BIG enough to overrun the initial difference)
(Note: configurations with no $X-Y$ transitional indices may be dealt with in the same way as post $\#2$ does it)

$\rule{25 cm}{3pt}$
$\textcolor{red}{\textbf{\text{Finish 2: Original 3 hour solution "Y-block maniac".}}}$ We refer to $Y-X$ transitional indices to be the last index in a (particular) $Y-$ block. We claim the following:
$\textbf{Claim 3.}$ The length of any $Y-$ block aside from the first one is exactly $1$.
$\textbf{Proof 3.}$ Let a $Y-$ block has length $l \geq 2$. Consider the transitional index of that block $t$. Now, using a similar principle to $\textbf{Claim 1}$ above we get $c_{t-l} = c_t+l \geq 0+l = l \geq 2$. Letting $X'$ with switching indices $t-l$ and $t-l+1$ and using the initial $\textcolor{blue}{\textbf{\text{Observation}}}$, a contradiction takes place.
$\rule{25cm}{0.5pt}$
This claim also delimits the possibilities of $X-$ blocks preceding each $Y-$ block, as each block must have length at least $1$. It is illogical for any $X-$ block to have length $2$ or more: as the leftmost coefficient of said block will inevitably be negative.
If we have $2$ or more $X-$ blocks, we now pick two which are $\{i\}$ and $\{j\}$. Let the index with the smaller "difference" be $i$ (i.e. $d_i \leq d_j$). Then there is an easy switch of index $i$ and $i+1$ which yields a contradiction.
The case where the only $X-$ block available is of length $1$ is handled similarly to $\textcolor{red}{\textbf{\text{Finish 1}}}$.
Motivation: This MUST hold; proceed onwards despite unyielding cases!
This post has been edited 6 times. Last edited by alexiaslexia, Nov 12, 2020, 6:28 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
TheUltimate123
1740 posts
#9 • 4 Y
Y by centslordm, sabkx, channing421, eulerleonhardfan
Solved with nukelauncher.

We will show there exists an increasing sequence \((b_1,\ldots,b_n)\) satisfying \[\sum_{i\in X}b_i=\sum_{i\notin X}b_i.\]This clearly suffices by scaling.

Assume without loss of generality that \(\sum_{i\in X}a_i<1\), since otherwise we replace \(X\) with \(\{1,\ldots,n\}\setminus X\). Then if \(n\in X\), we win automatically by letting \(b_i=a_i\) for \(i\le n-1\) and varying \(b_n\ge a_n\). Henceforth \(n\notin X\).

Claim: We have \[\sum_{i\in X}a_{i+1}>2-\sum_{i\in X}a_i.\]
Proof. Since \(\sum_{i\in X}a_{i+1}\) is greater than \(\sum_{i\in X}a_i\) but farther from 1 than \(\sum_{i\in X}a_i\), we have \(\sum_{i\in X}a_{i+1}\ge2-\sum_{i\in X}a_i\).

Suppose that equality holds. Evidently there is some \(i\in X\) with \(i+1\notin X\); then replacing \(i\) with \(i+1\) in \(X\) yields a sum closer to 1 than \(\sum_{i\in X}a_i\), contradiction. \(\blacksquare\)

Consider the sequence \((c_1,\ldots,c_n)\) defined by \(c_i=a_{i+1}\) for \(i\in X\) and \(c_i=a_i\) otherwise.

Claim: We have \[\sum_{i\in X}c_i>\sum_{i\notin X}c_i.\]
Proof. By the first claim, \[\sum_{i\in X}c_i=\sum_{i\in X}a_{i+1}>2-\sum_{i\in X}a_i=\sum_{i\notin X}a_i=\sum_{i\notin X}c_i,\]proving the claim. \(\blacksquare\)

Finally, we have \[\sum_{i\in X}a_i<\sum_{i\notin X}a_i\quad\text{and}\quad\sum_{i\in X}c_i>\sum_{i\notin X}c_i.\]We are free to vary \(a_i\le b_i<c_i\) for \(i\in X\), so evidently there is an increasing sequence \((b_1,\ldots,b_n)\) satisfying \[\sum_{i\in X}b_i=\sum_{i\notin X}b_i,\]and 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.
goodar2006
1347 posts
#10 • 2 Y
Y by centslordm, Acclab
Is this solution correct? :huh:

Note that since the $a_{i}$'s sum to $2$, set $\bar{X} = \{1, 2, \ldots, n\} - X$ also satisfies the problem's minimization condition. Therefore, WLOG we can assume that $\sum_{i \in X} a_{i} = 1 - \epsilon$, where $\epsilon > 0$. We consider two cases:

Case 1: There is an index $j$, $1 \le j \le n -1$, such that $a_{j} \in X$ and $a_{j + 1} \in \bar{X}$. In this case, we have $a_{j + 1} - a_{j} \ge 2\epsilon$. Otherwise, adding $j + 1$ to $X$ and removing $j$ from it yields a new set $X ^ {\prime}$ closer to $1$ than $X$, contradicting the problem's minimization condition. Therefore, we can define $b_{j} = a_{j} + \epsilon$, $b_{j + 1} = a_{j + 1} - \epsilon$, and $b_{k} = a_{k}$ for every other $1 \le k \le n$.

Case 2: $j > k$ for every $j \in X$ and $k \in \bar{X}$. Note that in this case $a_{1} \in \bar{X} \ge 2\epsilon$. Otherwise, adding $1$ to $X$ yields a new set $X ^ {\prime}$ closer to $1$ than $X$, contradicting the problem's minimization condition. Therefore, we can define $b_{n} = a_{n} + \epsilon$, $b_{1} = a_{1} - \epsilon$, and $b_{k} = a_{k}$ for every other $2 \le k \le n - 1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Afo
1002 posts
#12 • 1 Y
Y by centslordm
Solution.

Let $|X|=p$. Let $X_1,...,X_p$ be the elements of $X$ in increasing order. WLOG
$$a_{X_1}+...+a_{X_p}=1+s$$where $s>0$. The main idea is to show that $(a_{X_1}-s)+a_{X_2}+..+a_{X_p}=1$ works. We finish the problem by proving three things.

1. $a_{X_1}-s$ is positive.
2. We need to show that the order is still preserved: $a_{X_1}-s>a_{X_1-1}$. Note that if $X_1=1$, we're done. We assume that $X_1 \ge 2$.
3. To make the sum $2$, we show that there is an $i \notin X$, such that $a_i+s<a_{i+1}$ (Again, to preserve the order).

Claim 1. $a_{X_1}-s$ is positive
Proof.
Because of the minimality condition,
$$a_{X_2}+..+a_{X_p}=s+1-a_{X_1} \leq 1-s$$$$2s\leq a_{X_1} \implies a_{X_1}-s>0$$Claim 2. $a_{X_1}-s>a_{X_1-1}$
Proof.
$$a_{X_2}+..+a_{X_p}+a_{X_1-1}=s+1-a_{X_1}+a_{X_1-1}\leq 1-s$$$$2s\leq a_{X_1}-a_{X_1-1} \implies a_{X_1}-s>a_{X_1-1}$$Claim 3. Point 3, above..
Proof.
let $a_i$ be the largest value such that $i \notin X$. If $a_i=a_n$, then just add $a_i$ by $s$. Otherwise, $a_{i+1} \in X$. Similar to Claim 2, we have that $a_{i+1}-a_i \ge 2s \implies a_i+s < a_{i+1}$.
This post has been edited 3 times. Last edited by Afo, Mar 23, 2021, 1:24 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mano
46 posts
#13 • 1 Y
Y by centslordm
In my opinion not that hard for an A3, but the amount of intimidating notation makes solvng the problem and writing up the solution considerably harder.
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
pad
1671 posts
#14 • 1 Y
Y by centslordm
Let $\sum_{i\in X} a_i = 1-\varepsilon$. WLOG $\varepsilon>0$, since the complement sums to $1+\varepsilon$.

Lemma 1: Suppose $i \in X$ and $j \not \in X$, and $i<j$. Then $a_j-a_i \ge 2\varepsilon$.

Proof: We know $a_i<a_j$ since the sequence is increasing. Suppose instead that $0<a_j-a_i< 2\varepsilon$. Then add $j$ to $X$ and remove $i$, so the new sum is $1-\varepsilon+a_j-a_i < 1+\varepsilon$. Now this new set is closer to $1$ than the original $X$ was, contradicting minimality. $\blacksquare$

Lemma 2: Suppose $j\not \in X$. Then $a_j \ge 2\varepsilon$.

Proof: If $a_j < 2\varepsilon$, then adding $j$ to $X$ makes the new sum between in the range $(1-\varepsilon, 1+\varepsilon)$, contradicting minimality. $\blacksquare$

Suppose there exists an index $i$ for which $a_i \in X$ and $a_{i+1} \not \in X$. By Lemma 1, $a_{i+1} - a_i \ge 2\varepsilon$. Create a new sequence where we increase $a_i$ by $\varepsilon$ and decrease $a_{i+1}$ by $\varepsilon$. This change preserves the strictly increasing property and all positive property, so we have a new sequence in which the $X$-indexed elements sum to $(1-\varepsilon)+\varepsilon=1$, finishing. (Technically, the change could make $a_i$ and $a_{i+1}$ equal, so increase $a_i$ by $\delta \ll \varepsilon$ less than $\varepsilon$ and increase some other $X$-indexed element by $\delta$, where $\delta$ is small enough so that this preserves strictly increasing.)

Else, we must have $X=\{k+1,\ldots,n\}$ for some $k\ge 1$. This guarantees that $a_1\not \in X$ and $a_n\in X$, so simply remove $\varepsilon$ from $a_1$ and add $\varepsilon$ onto $a_n$. This new sequence sums to $(1-\varepsilon)+\varepsilon=1$. It preserves all positive since $a_1 \ge 2\varepsilon>\varepsilon$ by Lemma 2, and it obviously preserves the strictly increasing property.

Remarks
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cmsgr8er
434 posts
#15 • 1 Y
Y by wzs26843545602
Note that either $S = \sum_{i\in X} a_i = 1 \pm \varepsilon,$ but since the sum is two let us WLOG consider $1-\varepsilon.$ Suppose for the sake of contradiction that no such sequence of $b_i$ exists.

Claim: For some integer $1\le k\le n,$ $a_1, a_2,\dots, a_k\not\in X$ and $a_{k+1}, \dots, a_n \in X.$

Proof. Suppose not. Consider $X$ such that $T = \sum_{i\in X} i$ is maximal. Then there must be some $i,j$ with $i<j$ and $a_j\not\in X$ and $a_i\in X.$ Note that $a_j-a_i\ne 2\varepsilon$ otherwise we could replace $i$ with $j$ in $X,$ contradicting maximality of $T$.

Moreover, if $a_j-a_i<2\varepsilon$ then replacing $i$ with $j$ in $X$ contradicts minimality of $S.$ As a result, $a_j-a_i > 2\varepsilon,$ so setting $b_i = a_i + \varepsilon$ and $b_j = a_j-\varepsilon$ and $b_k = a_k$ for $k\ne i,j$ gives a valid sequence of $b,$ contradiction. $\blacksquare$

Claim: For all $i\not\in X,$ $a_i \ge 2\varepsilon.$

Proof. If otherwise then add $i$ in $X,$ contradicting minimality. $\blacksquare$

Finally set,
\begin{align*}
b_i = a_i - \frac{\varepsilon}{k}  &\qquad 1\le i\le k  \\
b_i = a_i + \frac{\varepsilon}{n-k}  &\qquad k+1\le i\le n,
\end{align*}Whereby for $1\le i\le k,$ $b_i = a_i-\varepsilon/k \ge \varepsilon(2-1/k) > 0,$ giving a valid sequence for $b.$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
uvuvwevwevwe
12 posts
#16
Y by
I think I have quite a simple sketch of the solution but I have not worked it out on paper, so it might be a fake-solve.

Sketch:
We wish to prove the contrapositive of the statement. i.e. If the desired $\{ b_i \}$ does not exist then the first absolute sum is not minimised.
Lemma: The set $X$ satisfies the second condition iff $X$ neither majorizes $Y$ or be majorized by $Z$, where
$$Y=\{n, n-2, n-4, \dots ,2 \}, Z=\{n-1, n-3, n-5, \dots 1\} $$$$Y=\{n, n-2, n-4, \dots 1\}, Z=\{ n-1, n-3, n-5, \dots 2\}$$for even and odd $n$ respectively. Note that if $|A| > |B|$ then $B$ cannot majorize $A$, but $A$ can majorize $B$.

If $X$ majorizes $Y$, then
\[
\sum_{i \in X} a_{i} > \sum_{i \in Y} a_{i} > 1 \implies \left|1-\sum_{i \in X} a_{i}\right| > \left|1-\sum_{i \in Y} a_{i}\right|
\]If $X$ is majorized by $Z$, then
\[
\sum_{i \in X} a_{i} < \sum_{i \in Z} a_{i} < 1 \implies \left|1-\sum_{i \in X} a_{i}\right| > \left|1-\sum_{i \in Z} a_{i}\right|
\]which will imply that the first sum is not minimised anyways. Contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CANBANKAN
1301 posts
#17 • 1 Y
Y by sabkx
The idea is to characterize all possible $X$. I am minimizing $$|\sum_{i\in [n]\backslash X} a_i - \sum_{i\in X} a_i|$$
If $X=\{x_1,\cdots,x_t\}$ and there exists $z_j\in [n]\backslash X$ such that $z_j>x_j$, then I should swap $(z_i,x_i)$ to reduce that absolute value. There is a similar condition for $[n]\backslash X$ (*)

Now, our goal is to construct $c_1<c_2<\cdots<c_n, d_1<\cdots<d_n$ such that

$$\sum\limits_{i\in [n]\backslash X} c_i - \sum\limits_{i\in X} c_i  < 0 < \sum\limits_{i\in [n]\backslash X} d_i - \sum\limits_{i\in X} d_i $$
Then let $-A=\sum\limits_{i\in [n]\backslash X} c_i - \sum\limits_{i\in X} c_i$, $B=\sum\limits_{i\in [n]\backslash X} d_i - \sum\limits_{i\in X} d_i$, then setting $$b_1:b_2:\cdots:b_n = Bc_1+Ad_1 : Bc_2+Ad_2 : \cdots : Bc_n+Ad_n$$works

WLOG $n\in [n]\backslash X$, then set $d_j=j$ for all $1\le j\le n-1$ and $d_n=10^{10^n}$

It remains to construct $c_i$. Let $X=\{x_1,\cdots,x_t\}, [n]\backslash X=\{y_1,\cdots,y_{n-t}\}$, and consider the smallest integer $j$ such that $x_{t-j}>y_{n-t-j}$. It must exist by (*), then consider the following construction: for all $k>x_{t-j}, c_k=10^{10^n}+k\epsilon^2 10^{-10^n}$

$x_{t-j}=10^{10^n}, y_{n-t-j}=10$ and for all $k<y_{n-t-j}$, $c_k=k\epsilon^2 10^{-10^n}$

Check this works.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Number1048576
91 posts
#18
Y by
solution
This post has been edited 1 time. Last edited by Number1048576, Jun 25, 2022, 2:51 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1714 posts
#19
Y by
Let the elements of $X$ be $c_1$, $c_2$, $c_3$, $\dots$, $c_i$. Without loss of generality, we can assume that \[a_{c_1}+a_{c_2}+a_{c_3}+\dots+a_{c_i}=1+d > 1\]If $d=0$ we are already done by making the sequence $a$ the same as the sequence $b$.

Now, we will show that we can decrease a variable in $a_X$ by $s$, increase a variable not in $a_X$ by $s$, and maintain the relation $0<a_1<a_2<\dots < a_{n-1}<a_n$. Let us decrease $a_{c_j}$ by $d$, then we will show that $a_{c_j} - d > a_{c_j-1}$. Clearly, \[a_{c_1}+\dots+a_{c_{j-1}}+a_{c_j-1}+a_{c_{j+1}}+\dots+c_i\ge 1-d\]due to minimality. Now, we have $a_{c_j}-a_{c_j-1}\ge 2d$ which means we can subtract $d$ from $a_{c_j}$ without getting into any trouble. The same applies to adding $d$ to a non-$a_X$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
asdf334
7585 posts
#20
Y by
Idea is somewhat similar to 2022 USAJMO 2.

Essentially, if there exist sequences $(b_1,b_2,\dots,b_n)$ and $(c_1,c_2,\dots,c_n)$ where the second condition has the first sum less and the second sum greater, some sort of smoothing argument that changes $b_i$ to $c_i$ will give a correct value. Then $X$ must be majorized by its complement (WLOG) and we can find some better subset than $X$ by replacing an element of $X$ with the corresponding element in $X^C$. Done.

Example
This post has been edited 1 time. Last edited by asdf334, Mar 11, 2023, 2:15 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
198 posts
#21
Y by
Hopefully, it isn't fakesolve.

WLOG, we can assume $\sum_{i \in X} a_i < 1$. Let $\varepsilon = 1 - \sum_{i \in X} a_i$.Let $i_1 < i_2 < \dots < i_k$ be the elements of $X$. We split the problem into two cases:

Case 1: $n \in X$.

If there exists $s$ such that $i_{s + 1} > i_s + 1$, then $i_s + 1 \not\in X$, which means that $\sum_{j \in X \backslash \{i_s\} \cup \{i_s + 1\}} a_j \ge 1 + \varepsilon$, thus $a_{i_s + 1} \ge a_{i_s} + 2\varepsilon$, so replacing $a_n \to a_n + \varepsilon$ and $a_{i_s + 1} \to a_{i_s + 1} - \varepsilon$ works.

If there doesn't exists such $s$, then $X = \{n, n - 1, n - 2, \dots, n - k + 1 \}$. Then we can easily scale it.

Case 2: $n \not\in X$.

Let $m = i_k$. Then considering $X \backslash \{m\} \cup \{m+1\}$, we get $a_{m+1} - a_m \ge 2\varepsilon$. If $a_{m+1} > a_m + 2\varepsilon$, then replacing $a_{m+1} \to a_{m+1} - \varepsilon$ and $a_m \to a_m + \varepsilon$ works. Thus we may assume $a_{m+1} - a_m = 2\varepsilon$.

If there exists $k \neq j \in X$, then replace $a_{m+1} \to a_{m+1} - \varepsilon$ and $a_m \to a_m + \varepsilon_1$ and $a_j \to a_j + \varepsilon - \varepsilon_1$ and take $\varepsilon_1$ such that $a_{j+1} > a_j + \varepsilon - \varepsilon_1$.

Otherwise, since $n \ge 3$, there exists $j$ different from $k, k + 1$ and $j \not\in X$. Then replace $a_m \to a_m + \epsilon$ and $a_{m+1} \to a_{m+1} - \varepsilon_1$ and $a_j \to a_j - (\varepsilon - \varepsilon_1)$ and take $\varepsilon_1$ such that $\varepsilon - \varepsilon_1$ is close to $0$. Then it works perfectly.

Hence, in all cases, we can scale the sequence $(a_i)_{1 \le i \le n}$, so we're done. $\blacksquare$
This post has been edited 1 time. Last edited by thdnder, Aug 10, 2024, 4:32 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
vsamc
3789 posts
#22
Y by
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
asdf334
7585 posts
#24
Y by
Obviously redefine $X$ to be a subset of $\{a_1,\dots,a_n\}$. Let $s=\displaystyle{\sum_{i\in X}i}<1$ and let $Y$ be the complement of $X$.
Suppose there exist $y\in Y$ and $x\in X$ where $y>x$. Then consider set $X'$ formed by removing $x$ and adding $y$. Clearly
\[s-x+y\ge 2-s\implies y-x\ge 2-2s.\]Now if there exist $y\in Y$ and $x\in X$ where $y>x$ at all, then there must exist $i$ such that $a_{i+1}\in Y$ and $a_i\in X$. Consider the sequence $b$ where
  • If $j\not\in \{i,i+1\}$ then $b_j:=a_j$.
  • We have $b_i:=a_i+(1-s)$ and $b_{i+1}:=a_{i+1}-(1-s)$.
This works provided that $a_{i+1}-a_i\ne 2-2s$. In this case set $b_i=a_i+(1-s)-\epsilon$ instead and increase some other element in $X$ by $\epsilon$.
Now suppose that there do not exist $y\in Y$ and $x\in X$ such that $y>x$. In this case divide all values by $2-s$ so that the sum of values in $Y$ is $1$. Now increase the largest value in $X$ by
\[1-\frac{s}{2-s}=\frac{2-2s}{2-s}\]and we are done. $\blacksquare$
This post has been edited 1 time. Last edited by asdf334, Apr 27, 2024, 12:35 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
HamstPan38825
8860 posts
#25
Y by
Giving explicit constructions is too hard :(

We will characterize all sets $X$ that could possibly satisfy the given condition, then show that such a sequence $\{b_i\}$ exists for all such sets $X$. We say that a set $X$ dominates a set $Y$ if we can assign a distinct $f(y) \in X$ for each $y \in Y$ such that $f(y) > y$ for all $y$.

Claim. [First Part] For any sequence $\{a_i\}$, the given value can only be minimized when neither $X$ nor $X^c$ dominate each other.

Proof. Assume otherwise, and suppose $X^c$ dominates $X$. Let $\sum_{i \in X} a_i = 1-\varepsilon$ for $\varepsilon > 0$.

If $|X| = 1$, assume for the sake of contradiction that $i < n$. It follows that $1-\varepsilon = a_i < a_n \leq 1+\varepsilon$, so $a_n$ is closer to $1$ than $a_i$, contradiction.

Suppose that $|X| \geq 2$. It follows that for every index $i \in S$, the difference $a_{f(i)} - a_i$ is at least $2\varepsilon$, as otherwise, by replacing $i$ with $f(i)$ in $X$ we get a sum closer to $1$. Hence \[\sum_{j \in X^c} a_j - \sum_{i \in X} a_i \geq 2\varepsilon |X| > 2\varepsilon\]yields a contradiction. $\blacksquare$

Claim. [Second Part] If neither $X$ nor $X^c$ dominates the other, then we can find such a sequence $\{b_i\}$.

Proof. Let $|X| = r$. It suffices to construct a sequence $\{b_i\}$ such that $\sum_{i \in X} b_i = \sum_{j \in X^c} b_j$, as we can scale by a suitable amount. Thus, we will instead construct a sequence $(c_1, c_2, \dots, c_n)$ with $c_i > 0$ for each $i$ such that
\[\sum_{i=0}^{r-1} i \sum_{j=x_i}^{x_{i+1}} c_j = \sum_{i=0}^{r-1} (n-r-i) \sum_{j = y_i}^{y_{i+1}} c_j\]where $\{x_i\}$ is the increasing sequence of all indices in $X$ and $\{y_i\}$ is the increasing sequence of all indices in $X^c$. Then, taking $b_i = c_1+c_2+\cdots+c_i$ for each $i$ does the trick. (Here $c_i$ is just the difference sequence of $b_i$.)

Notice that every $c_i$ appears $f(i)$ times in the LHS sum, where $f(i)$ denotes the number of elements in $X$ at least $a_i$. This element is then counted $n-i+1 - f(i)$ times in the RHS sum, as it is counted $n-i+1$ times total. So it suffices to demonstrate such a sequence $\{c_i\}$ with $c_i > 0$ satisfying only the condition \[\sum_{i=1}^n c_i(2f(i) - n+i-1) = 0.\]There obviously exists such a $\{c_i\}$ as long as $2f(i) - n+i-1 > 0$ and $2f(j) - n+j-1 < 0$ for some $i, j$. Assume for the sake of contradiction that $2f(i) \leq n-i+1$ for all $i$; the other case is analogous, say by swapping $X$ with $X^c$. We will arrive at a contradiction by inductively pairing off every index $x_i \in X$ with a $y_j \in X^c$ with $x_i \leq y_j$.

For our base case, notice that for $i=n$, the inequality reads $2f(n) \leq 1$, i.e. $f(n) = 0$, so $n \not \in X$. So we can pair $x_r$ with $y_{n-r} = n$. For the inductive step, for $i = x_j$ the inequality reads $f\left(x_j\right) \leq \frac{n-x_j + 1}2$. In particular, there are at least $\frac{n-x_j + 1}2$ elements $y_i$ among $x_j + 1, \dots, n$. Because there are only at most $\frac{n-x_j-1}2$ elements $x_i$ among these which we have paired off with an equal number of $y_j$, there exists at least $\frac{n-x_j+1}2 - \frac{n-x_j-1}2 = 1$ unpaired $y_\ell$, which we can pair with our $x_j$, completing the induction.

Thus we can create a pairing $(x_i, y_j)$ for all $x_i \in X$, which contradicts the assumption. It follows that such a sequence $\{c_i\}$ must exist, completing the problem.
This post has been edited 1 time. Last edited by HamstPan38825, Jun 17, 2024, 7:11 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Acclab
33 posts
#27
Y by
Why do everyone's solution include majorization? I find the construction the same as @goodar2006, which I think is quite intuitive.

Call $X$ good if there is $a_n$ satisfying the constraint so $ | \sum_{i \in X} a_i - 1 | $ is minimised. We wish to modify $a_n$ while keeping its stricty monoticity and sum, so that $\sum_{i \in X} a_i=1$. Since $X$ is good if and only if its complement $\bar{X}$ is, we can assume without loss of generality that $\sum_{i \in X} a_i < 1$.

Heuristic


The rigorous way of writing the solution follows:
Pick $k$ so $k \in X$ but $k \notin X$, we claim $a_k + (1-s) < a_{k+1} - (1-s)$, where $s = \sum_{i \in X} a_i$. Indeed, let $X' = X + \{k+1\} - \{k\}$, then by minimality we have $|s - a_k + a_{k+1} - 1| \geq |s - 1| = 1-s$. This simplifies to $a_{k+1}-(1-s) \geq a_k+(1-s)$. So we can let $b_k = a_k+1-s$, $b_{k+1} = a_{k+1}-(1-s)$ and $b_m=a_m$ otherwise. This keeps the monoticity except when equality is a held, but in this case we can decrease $a_k$ by some $\epsilon$ and then add to any other $a_i$ with $i \in X$. This is unless $X$ only has one element (which is why $n = 2$ is excluded). If this is the case, we have two cases:

1. $X = \{1\}$. Then $2 - (a_3 + ...) = a_1 + a_2 > 2 - a_1 \implies a_3 \leq a_3+...<a_1$, a contradiction.

2. $X = \{m\}$ for some $m \geq 2$. If $a_m \leq \frac{1}{2}$, then $a_1 + a_m < 1$ which is closer to $1$ than $a_m$, contradiction. If $a_m > \frac{1}{2}$, then $a_1 + a_m > 2 - a_m \implies 2-(a_1+a_m) < a_m$. L.H.S. is the sum of all $a_i$ except $i=1,m$, so this it must be the case that $m = n$. In this case, we can still indeed construct $b_i$ so $b_n = 1$ while keeping $0<b_1 < b_2 < ... < b_n$.

If we cannot pick such $k$ describe above, then $X = \{m, m+1, ..., n\}$ for some $m$ (X = $\phi$ is not possible). By using the minimality on the set $X = X + \{ a_1 \}$ we have that $a_1 - (1-s) \geq 1-s > 0$, so we can subtract $1-s$ from $a_1$ and add to $a_n$, keeping the positivity, strict monoticity and giving the desired sum.
This post has been edited 1 time. Last edited by Acclab, Jul 14, 2024, 2:38 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Acclab
33 posts
#28 • 1 Y
Y by goodar2006
goodar2006 wrote:
Is this solution correct? :huh:

Note that since the $a_{i}$'s sum to $2$, set $\bar{X} = \{1, 2, \ldots, n\} - X$ also satisfies the problem's minimization condition. Therefore, WLOG we can assume that $\sum_{i \in X} a_{i} = 1 - \epsilon$, where $\epsilon > 0$. We consider two cases:

Case 1: There is an index $j$, $1 \le j \le n -1$, such that $a_{j} \in X$ and $a_{j + 1} \in \bar{X}$. In this case, we have $a_{j + 1} - a_{j} \ge 2\epsilon$. Otherwise, adding $j + 1$ to $X$ and removing $j$ from it yields a new set $X ^ {\prime}$ closer to $1$ than $X$, contradicting the problem's minimization condition. Therefore, we can define $b_{j} = a_{j} + \epsilon$, $b_{j + 1} = a_{j + 1} - \epsilon$, and $b_{k} = a_{k}$ for every other $1 \le k \le n$.

Case 2: $j > k$ for every $j \in X$ and $k \in \bar{X}$. Note that in this case $a_{1} \in \bar{X} \ge 2\epsilon$. Otherwise, adding $1$ to $X$ yields a new set $X ^ {\prime}$ closer to $1$ than $X$, contradicting the problem's minimization condition. Therefore, we can define $b_{n} = a_{n} + \epsilon$, $b_{1} = a_{1} - \epsilon$, and $b_{k} = a_{k}$ for every other $2 \le k \le n - 1$.

I think this is almost correct except when an equality case occurs (in your case 1, "closer to $1$ than $X$" is almost true, but it could be the case that they are both equidistant).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
maromex
184 posts
#29
Y by
Let $S_n = \{1, 2, 3, \ldots n\}$. Then \[
\left|1-\sum_{i \in S_n \backslash X} a_{i}\right| = \left|1 - (2 - \sum_{i \in X} a_i)\right| = \left|1 - \sum_{i \in X} a_i \right|
\]Both $S_n \backslash X$ and $X$ achieve the minimum value. Also, $(1 - \sum\limits_{i \in S_n \backslash X} a_i) + (1 - \sum\limits_{i \in X} a_i) = 2 - \sum\limits_{i \in S} a_i = 0$, which implies at least one of these addends is nonnegative. We may assume without loss of generality that $1 - \sum\limits_{i \in X} a_i \ge 0 \quad (1)$. Also, let $\epsilon = 1 - \sum\limits_{i \in X} a_i$. The value of $\epsilon$ only depends on the values in sequence $\{a_n\}$.

We will proceed by induction. Let $k$ be the largest element of $X$.

-- Base case: Goal holds for $k = n$

Our approach is to scale all terms before $a_n$ by scalar $s_1$ and scale $a_n$ by scalar $s_2$ for the construction of $\{ b_n \}$. For the condition $\sum\limits_{i \in X} b_i = 1$ to hold, we must have \[ s_1(1 - \epsilon - a_n) + s_2a_n = 1 \tag{1.1} \]For the sum of terms to be 2, we must have \[ s_1(2 - a_n) + s_2a_n = 2 \tag{1.2} \]Take (1.2) - (1.1) to get $$s_1(1 + \epsilon) = 1$$Thus, $$s_1 = \frac{1}{1 + \epsilon}$$Solving for $s_2$ in (1.2) gives $$s_2 = \frac{1}{a_n}(2 - \frac{2-a_n}{1+ \epsilon}) = \frac{1}{a_n}(\frac{2\epsilon + a_n}{1 + \epsilon}) = s_1 + \frac{2\epsilon}{a_n(1 + \epsilon)} > s_1$$Thus $s_2a_n > s_1a_{n-1} > s_1a_{n-2} > s_1a_{n-3} > \ldots$ We construct $\{ b_n \}$ with $b_i = s_1a_i \quad\forall i < n$, and $b_n = s_2a_n$. This sequence satisfies all of the requirements by construction.

-- Induction case: If the goal holds for $k = m$, it also holds for $k = m-1$ for all $2 \le m \le n$

We assume the goal holds for $k = m$. For the case where $k = m-1$, observe that \[ \sum\limits_{i \in (X \backslash \{a_{m-1}\}) \cup \{a_m\}} a_i = a_m - a_{m-1} + \sum\limits_{i \in X} a_i \tag{2.1}\]Also, it is given that the minimum value of $\left|1-\sum\limits_{i \in T} a_{i}\right|$ is achieved when $T = X$. Thus, we must have \[ \left| 1 - \sum\limits_{i \in (X \backslash \{ a_{m-1} \}) \cup \{ a_m \}} a_i \right| \ge \left| 1 - \sum\limits_{i \in X} a_i\right| \]After application of (1) and (2.1), this is equivalent to \[ \left| 1 - a_m + a_{m-1} - \sum\limits_{i \in X} a_i  \right| \ge 1 - \sum\limits_{i \in X} a_i \tag{2.2} \]Observe that $a_m > a_{m-1}$ because $\{a_n \}$ is strictly increasing. This means $ 1 - a_m + a_{m-1} + \sum\limits_{i \in X} a_i < 1 - \sum\limits_{i \in X} a_i$. This shows that for (2.2) to hold true, $1 - a_m + a_{m-1} + \sum\limits_{i \in X} a_i$ cannot be positive. We may transform (2.2) as follows: \[ 1 - a_m + a_{m-1} - \sum\limits_{i \in X} a_i \le \sum\limits_{i \in X} a_i - 1\]\[ - a_m + a_{m-1} \le 2\sum\limits_{i \in X} a_i - 2\]\[ - a_m + a_{m-1} \le -2\epsilon\]\[ a_m \ge a_{m-1}  +2\epsilon \tag{2.3}\]Now, if equality holds, that implies \[ \left| 1 - \sum\limits_{i \in (X \backslash \{ a_{m-1} \}) \cup \{ a_m \}} a_i \right| = \left| 1 - \sum\limits_{i \in X} a_i\right| \]This means that the minimum value of $\left|1 - \sum\limits_{i \in T} a_i \right|$ is achieved by $T = (X \backslash \{ a_{m-1} \}) \cup \{ a_m \}$. Applying the inductive hypothesis on $(X \backslash \{ a_{m-1} \}) \cup \{ a_m \}$ finishes for the equality case.

If equality does not hold for (2.3), we have $a_m > a_{m-1} + 2\epsilon \quad (2.4)$. Then we may construct $\{b_n \}$ with $b_i = a_i \quad\forall i \notin \{ m, m-1 \}$, $b_{m-1} = a_{m-1} + \epsilon$, and $b_m = a_m - \epsilon$. The sum of terms is 2 by construction. The sequence is strictly increasing due to (2.4), and otherwise by construction. We may use the definition of $\epsilon$ to get $\sum\limits_{i \in X} a_i = 1 - \epsilon$. Observe that $\sum\limits_{i \in X} b_i = \epsilon + \sum\limits_{i \in X} a_i = 1$, as the only difference between the sums is the $+ \epsilon$ for $b_{m-1}$. Thus, $\{b_n \}$ satisfies all of the requirements.
This post has been edited 2 times. Last edited by maromex, Apr 4, 2025, 1:59 AM
Reason: fixed some syntax issues alright latex PLEASE WORK
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
john0512
4187 posts
#30
Y by
OMG SO GOOD

We say that a subset $S$ of $[n]$ is dominating if, for all $i$, at least as many of the last $i$ numbers are in $S$ as not in $S$. Similarly, we say that $S$ is dominated if $[n]\backslash S$ is dominating.

Main Claim: There exists a strictly increasing sequence $b_i$ with sum $2$ and $\sum_{i\in S}b_i=1$ if and only if $S$ is neither dominating nor dominated.

If $S$ is dominating, then we can match $S$ to elements $[n]\backslash S$ such that in every pair the former element is larger, so it has sum greater than $1$, similarly if $S$ is dominated, it has sum less than $1$.

Consider if $S$ is neither. Assume the largest element does not belong in $S$ (otherwise flip it). Then, $\sum_{i\in S}b_i$ can be arbitrarily small by letting $a_n$ be close to $2$. However, since $S$ is not dominated, there is some $k$ where the last $k$ elements have a majority in $S$. By setting the first $n-k$ elements close to $0$ and the last $k$ close to $\frac{2}{k}$, we can obtain a sum greater than $1$. Thus by IVT a sum of $1$ is attainable.

Thus, it remains to show that the closest subset sum to $1$ cannot be achieved by a dominating subset. Consider a dominating matching
$$(x_1,y_1),(x_2,y_2),\dots,(x_k,y_k)$$with $x_i>y_i$ for all $i$ (pad the dominated subset with zeroes if it runs out).

Let $d_i=x_i-y_i>0$. Clearly $k\geq 2$ since a dominating subset must contain at least half of the elements. Thus, flipping a single $d_i$ to negative will clearly decrease $|\sum d_i|$, since all of the $d_i$ pointing in the same sign will maximize it. Thus, by swapping one of the pairs we obtain a closer to equal distribution, contradicting minimality. We are done.
This post has been edited 1 time. Last edited by john0512, May 2, 2025, 6:12 PM
Z K Y
N Quick Reply
G
H
=
a