[/quote]
,
,
,
be positive real numbers with 
.
Where 
with circumcenter 
and orthocenter 
.
meets 
at 
respectively.
as the circumcenter of 
.
again at 
,
.
again at 
,
and circumcircle of 
,
.
as the intersection of 
and 
meets circumcircle of 
.
and circumcircle of 
add up to zero. Find the maximum of 
in term of 
'
'
.
for which 
is a perfect square.
![\[ a^2 + b^2 + c^2 \geq \sqrt 3 abc. \]](http://latex.artofproblemsolving.com/6/c/7/6c779e29d3ae8516bae06fe2e9a7414869940027.png)
be real numbers such that 
.
.
grid has 
cells painted such that the following condition holds:
.
,
that intersects arc 
of circle 
,
, that doesn't contain 
,
.
and 
lies on circle 
is perpendicular on line 
.
,
,
by the recurrence![\[
a_{n+1} = a_n^2 + 1
\]](http://latex.artofproblemsolving.com/3/1/1/3114595ded8c8961d611afaab9ad19e254973001.png)
Prove that there is no natural number 
such that![\[
\prod_{k=1}^{n} \left( a_k^2 + a_k + 1 \right)
\]](http://latex.artofproblemsolving.com/a/4/f/a4f88ee7e3d4e53e369319f74cd9b12be26c9681.png)
is a perfect square.
be distinct real numbers such that![\[
a + b + c + \frac{1}{abc} = \frac{19}{2}
\]](http://latex.artofproblemsolving.com/5/1/e/51eef77358db2b6c98f0fb0fb4e30db837a03642.png)
Find the maximum possible value of 
.
be a real numbers such that 
P
Where 
with 
be the intersection of 
Let 
meet again 
at 
Called 
Prove that 
and 
Prove that
Let 
Prove that
.
Let 
.
Y by centslordm, megarnie, Mango247
Let 
be a positive integer and let 
be a strictly increasing sequence of 
positive real numbers with sum equal to 2. Let 
be a subset of 
such that the value of
![\[
\left|1-\sum_{i \in X} a_{i}\right|
\]](//latex.artofproblemsolving.com/2/5/1/2515e074de1782f38453e1fce8ab7c2ec7cfe4c0.png)
is minimised. Prove that there exists a strictly increasing sequence of positive real numbers 
with sum equal to 2 such that
![\[
\sum_{i \in X} b_{i}=1.
\]](//latex.artofproblemsolving.com/3/7/4/37410820fc4c546f11d57212cfce53a7ec4941e3.png)
be a positive integer and let 
be a strictly increasing sequence of 
positive real numbers with sum equal to 2. Let 
be a subset of 
such that the value of![\[
\left|1-\sum_{i \in X} a_{i}\right|
\]](http://latex.artofproblemsolving.com/2/5/1/2515e074de1782f38453e1fce8ab7c2ec7cfe4c0.png)
is minimised. Prove that there exists a strictly increasing sequence of positive real numbers 
with sum equal to 2 such that![\[
\sum_{i \in X} b_{i}=1.
\]](http://latex.artofproblemsolving.com/3/7/4/37410820fc4c546f11d57212cfce53a7ec4941e3.png)
and 
.
and 
.
(by taking complement). The first claim is.
and 
,![$b-a\notin(0,\delta]$](http://latex.artofproblemsolving.com/2/2/2/222b7f6f78d8087f906ac5b11b0cb6ad47645ef8.png)
.
(note : 
from strictly increasing condition). The new sum is![$$\sum A' = (1-\delta)+(b-a) \in (1-\delta,1]$$](http://latex.artofproblemsolving.com/2/c/a/2ca9b2a7035dadfb0e27f607c54e7dac72b49ef6.png)
which is a contradiction to the minimality condition
.
.![$$\sum A' = (1-\delta)+b \in (1-\delta,1]$$](http://latex.artofproblemsolving.com/f/a/b/fab61cb8039541264c943ea39b7b36dd797c55fd.png)
which is a contradiction to the minimality condition
and call an index 
tasty if and only if 
and 
.
.
for each tasty index 
.
(notice that 
and 
)
Then this sequence is clearly valid, contradiction
where 
denote which term is in which set.
as otherwise 
will give better partition than 
which implies
thus 
.
,
terms) will be clearly less than the RHS (which have 
terms), a contradiction
where there are 
'
'
being minimal is equivalent to 
be minimal. Then, assume WLOG that 
(if the equality ocurred, we would be done). Also, for any strictly increasing sequence of 
,
We want to prove that there exists a strictly increasing sequence of 
such that 
is minimal, for all 
and 
(they exist, since 
,
otherwise we could place 
in 
in 
and 
,
with 
such that 
is minimal. From 
,
.
for all 
and 
,
is the same of 
,
is the same of 
.
,
in the new choice of sequence (the sequence keeps strictly increasing). Hence, this new sequence satisfies 
,
and 
by construction.
for the complement and 
(
"
,
.
.
.
such that 
such that 
.
)
.
and 
with the elements in decreasing order. So 
etc. So 
.
and 
the set 
will have a sum strictly between the two sums, hence 
or 
both of which are easily seen to be only possibly minimizing if 
(so this is where our proof uses 
)
.
for 
and 
for 
.
.
to make it strictly increasing and still have 
into 
and 
where 
.
and the sum of all 
as 
.
is ever 
.
for all 
(where 
at least). If otherwise, then we may send 
to 
since![\[1 - \epsilon < \sum Y' = (1 - \epsilon) + (x_i - y_j) \leq 1.\]](http://latex.artofproblemsolving.com/7/4/c/74c25592d6199cf55a0099b99810d869126849d7.png)
In fact, we may further assume 
since if equality occurs, then after the swap, 
.
that satisfies the requirements. Let 
for which 
term and 
be the set of indices 
for which 
is a 
term. Clearly 
and 
.
works. Indeed, check that 
.
.
are either both in 
since 
.
and 
,
.
and 
,![\[b_{m+1} - b_m = (x_i - y_j) - (\tfrac{\epsilon}{k} + \tfrac{\epsilon}{\ell}) \geq (x_i - y_j) - \epsilon > 0\]](http://latex.artofproblemsolving.com/0/e/0/0e0cd8a7420a9b24343d53a27ce29d5bfd1ad91d.png)
by our first note, along with using the fact that 
for 
unless 
is 
,
which is bad since then the next largest term is a 
,
,
remaning terms is 
terms is 
,
.
the only 
.
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).![$[n]$](http://latex.artofproblemsolving.com/0/d/e/0deff9086fd7840ef23860f5bc924f1d4d2d2310.png)
be the set 
.
,
be 
.
so that![\[ \sum_{i\in X} b_i = \sum_{j \in [n]-X} b_j \]](http://latex.artofproblemsolving.com/0/c/8/0c847a1726c244a59bcf9ee66098bc3c98790f43.png)
and also that the problem statement is equivalent to ![\[ \left| \sum_{i\in X} a_i - \sum_{j \in [n]-X} a_j \right| \]](http://latex.artofproblemsolving.com/3/c/3/3c3c5fe89a5db6e6a22a0bb2c8efe787720a2ebb.png)
being the lowest possible among all set ![$X \subseteq [n]$](http://latex.artofproblemsolving.com/e/2/c/e2c9ff6de45749e499261e14fcdd83987401a87b.png)
,
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 \]](http://latex.artofproblemsolving.com/6/c/9/6c921cbcfcce8cbc6b222a0436df166437bf9140.png)
in terms of 
(here, we let ![$Y = [n] - X$](http://latex.artofproblemsolving.com/a/5/b/a5b46c9d4de3806511cb058ccd5b64694fa73baf.png)
for simplicity). Without Loss of Generality we can assume ![\[
\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}
\]](http://latex.artofproblemsolving.com/f/c/3/fc3c245a234b98492bed862215861a3c30d72ec3.png)
For example, when 
and 
,
(the letters 
.
set the ![\[ \sum_{i; c_i > 0} |c_i|d_i = \sum_{j; c_j<0} |c_j|d_j \]](http://latex.artofproblemsolving.com/d/6/8/d683db3c20838c2221379bea310cf0278bf40520.png)
(one way to do it is to set all 
to be 
except one on the 
to be 
and adjust the one not yet filled accordingly.) In these cases, setting 
fulfills the objective.
Let 
.
,
.
Obvious [Just note that ![$S_d' = S_d - (a_{i+1} - a_{i}) + (a_{i} - a_{i+1})].$](http://latex.artofproblemsolving.com/1/2/2/122855316cb8a34a053ba78e55209fa537097a57.png)
Divide the indices into 
of 
and 
,
b
and 
.
transitional index to be the last index in any 
b
Each 
Consider the coefficient 
of 
.
.
There are at most one 
If ![\[ S_d(X) \geq c_id_i + c_jd_j \geq 1 \cdot d_i + 1 \cdot d_j \]](http://latex.artofproblemsolving.com/4/6/e/46e02d711167d6fa02cd3909fa76126e0abe6b1f.png)
Consider 
and 
after switching 
,
respectively. Then, one of 
and 
is at least 
![$[i,j] \in [n]$](http://latex.artofproblemsolving.com/4/8/e/48e41d11c3118bfca5b2df3ba8fb8bac1c343f91.png)
or a collection of two intervals ![$[a,b], [c,d]$](http://latex.artofproblemsolving.com/0/f/f/0ffc6302f9f30e2052c8a3897e10780ed87ac5e9.png)
where 
.
.
;
is negative. Otherwise we can be sure that the 
obtaining from switching 
contradicts the 
problem statement. (While the value of 
does it)
We refer to 
transitional indices to be the last index in a (particular) 
The length of any 
Let a 
.
above we get 
.
and 
and using the initial 
,
and 
.
)
.
something big accordingly. So, I obtained 
.
is in 
is also in 
and 
further towards 
.
or 
,
for all 
,
,
.
and simple telescoping further eases the process from two-indiced differences to the expression 
.
above -- when some coefficient is negative, we can select big indices to be flung towards 
.
always equal to 
.
.
satisfying ![\[\sum_{i\in X}b_i=\sum_{i\notin X}b_i.\]](http://latex.artofproblemsolving.com/a/8/6/a86cfc631694cc44d9e83648df9fb4e6c79a8d50.png)
This clearly suffices by scaling.
,
with 
.
,
for 
and varying 
.
.![\[\sum_{i\in X}a_{i+1}>2-\sum_{i\in X}a_i.\]](http://latex.artofproblemsolving.com/b/6/3/b6390ad610d6827d46d502fa37c5395d3a28fa1d.png)
is greater than 
but farther from 1 than 
.
with 
;
with 
in 
defined by 
for 
otherwise.![\[\sum_{i\in X}c_i>\sum_{i\notin X}c_i.\]](http://latex.artofproblemsolving.com/7/8/8/7886ce5ee62f61e883c2d01736091b043f087e2f.png)
![\[\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,\]](http://latex.artofproblemsolving.com/0/6/c/06c8d4e0f9c4f525295d03e194279d6ce106dd2e.png)
proving the claim. ![\[\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.\]](http://latex.artofproblemsolving.com/f/e/5/fe57ae5d8ff190283b4f817e86651b4e85ef4816.png)
We are free to vary 
for ![\[\sum_{i\in X}b_i=\sum_{i\notin X}b_i,\]](http://latex.artofproblemsolving.com/5/1/c/51c0062e36fd3d6671e84b7622505dd42117c0bf.png)
and we are done.
'
also satisfies the problem's minimization condition. Therefore, WLOG we can assume that 
,
,
and 
.
.
to 
closer to 
,
,
for every other 
.
for every 
and 
.
.
,
,
.
.
be the elements of 
where 
.
works. We finish the problem by proving three things.
is positive.
.
,
.
,
(Again, to preserve the order).
Claim 2. 
Claim 3. Point 3, above..
,
.
.
![$[n]\coloneqq\{1,2,\dots,n\}$](http://latex.artofproblemsolving.com/3/e/6/3e6367e16b3b73c31664405f8ad63e431dd29542.png)
and define ![$\overline{X}\coloneqq [n]\setminus X$](http://latex.artofproblemsolving.com/f/4/6/f46fc19bbc8e9ce9bab215138fac4efb5a096ecb.png)
.
such that 
for all 
.
also minimises 
we can WLOG assume that 
.![$X=[n]$](http://latex.artofproblemsolving.com/6/8/c/68c59b7a2f69ead9090b471302510c279354f730.png)
,
and because 
,
and hence 
which means that for 
instead of ![$m\in[n]$](http://latex.artofproblemsolving.com/7/6/9/769d5b8c1362e8e41902c4bb88f88060cfbbdecf.png)
,
and 
.
for some 
and 
with 
and 
.
.
for 
is well-defined and it is also injective because the 
are distinct. But if 
for some 
then we have 
,
which would mean that 
such that 
.
and notice that this is indeed a strictly increasing sequence of positive real numbers as 
.
and 
,
and 
Comparing, we obtain
as desired.
for 
,
.
,
.
,
.
since the sequence is increasing. Suppose instead that 
.
.
.
.
,
,
.
.
by 
,
less than 
for some 
.
and 
,
by Lemma 2, and it obviously preserves the strictly increasing property.
to get a sequence that sums exactly to 1, or (2) classify all sets 
between two indices; I thought we would have to more clever with doing this over multiple adjacent pairs of indices to add up to an addition of 
but since the sum is two let us WLOG consider 
Suppose for the sake of contradiction that no such sequence of 
and 
is maximal. Then there must be some 
with 
and 
Note that 
otherwise we could replace 
contradicting maximality of 
then replacing 
As a result, 
so setting 
and 
and 
for 
gives a valid sequence of 
contradiction. 
Whereby for 
giving a valid sequence for 
does not exist then the first absolute sum is not minimised.
,
for even and odd 
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|
\]](http://latex.artofproblemsolving.com/4/c/4/4c4fdbca92e6a192155dd81fed44d5bca6468a99.png)
If ![\[
\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|
\]](http://latex.artofproblemsolving.com/a/9/1/a91e52e540bbfe89c21123da235499cfc95d628f.png)
which will imply that the first sum is not minimised anyways. Contradiction.
![$$|\sum_{i\in [n]\backslash X} a_i - \sum_{i\in X} a_i|$$](http://latex.artofproblemsolving.com/c/a/c/cac5771cf7de1be59789a12a1b2163ccf94a4a1d.png)
and there exists ![$z_j\in [n]\backslash X$](http://latex.artofproblemsolving.com/b/3/d/b3d79eaf80e662047868ec5ba30294525a3d606f.png)
such that 
,
to reduce that absolute value. There is a similar condition for ![$[n]\backslash X$](http://latex.artofproblemsolving.com/4/1/0/410c5bc9381969d1fb479b2e1eaa1209e63aff23.png)
(*)
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 $$](http://latex.artofproblemsolving.com/8/4/6/846a7017b901b1254dba4c230ccadba974d819a4.png)
![$-A=\sum\limits_{i\in [n]\backslash X} c_i - \sum\limits_{i\in X} c_i$](http://latex.artofproblemsolving.com/7/0/6/7068c2eb4d6ec37050f254a08c97745596da15e9.png)
,![$B=\sum\limits_{i\in [n]\backslash X} d_i - \sum\limits_{i\in X} d_i$](http://latex.artofproblemsolving.com/0/1/e/01e091023d958f245ccac705611ec3d8b92f1cb2.png)
,
works![$n\in [n]\backslash X$](http://latex.artofproblemsolving.com/4/7/e/47efba203d43bff47154d134fa4d12f05da04672.png)
,
for all 
and 
![$X=\{x_1,\cdots,x_t\}, [n]\backslash X=\{y_1,\cdots,y_{n-t}\}$](http://latex.artofproblemsolving.com/a/2/4/a248aa18c6b49eb4c62497e9599f654d45bc9772.png)
,
.
and for all 
,
elements (note that we can assume WLOG that 
as note that 
,
elements), then if there doesn't exist a 
such that the 
will not be minimised.
such that 
.
to be any number larger than 
and smaller than 
to get the some equal to 
,
,
is sufficiently small but greater than 
is sufficiently small but greater than 
,
,
,
.
is 
.
but not in 
be the set of all such numbers, ordered from smallest to largest, then let 
,
,
is sufficiently small. This is better than the worse possible case, as the numbers which are meant to be smaller than 
are larger than it. Then the total sum of everything greater than or equal to 
.
sum to 
,
.
.
,
,
,![\[a_{c_1}+a_{c_2}+a_{c_3}+\dots+a_{c_i}=1+d > 1\]](http://latex.artofproblemsolving.com/6/3/7/637f0eafcf53cfc61691d990dc7d66e9b59bebf1.png)
If 
we are already done by making the sequence 
by 
.
by 
,
.![\[a_{c_1}+\dots+a_{c_{j-1}}+a_{c_j-1}+a_{c_{j+1}}+\dots+c_i\ge 1-d\]](http://latex.artofproblemsolving.com/9/7/2/972d7cff5a031de33761d68aca190fe595268912.png)
due to minimality. Now, we have 
which means we can subtract 
and 
where the second condition has the first sum less and the second sum greater, some sort of smoothing argument that changes 
and 
and 
this fails because of, say, 
.
.
.
be the elements of 
.
,
,
,
,
and 
works.
.
.
.
,
.
,
and 
works. Thus we may assume 
.
,
and 
and take 
such that 
.
and 
.
and 
and 
and take 
is close to 
,
be the minimum possible value of 
over all 
.
,
and we're done. So assume 
.
be the set of all subsets 
for which 
is minimized; then we can write 
,
is the set of all subsets 
and 
is the set of all subsets 
First, we will show the result for all 
.
for which 
and 
(not mutually exclusive).
,
,
.
,
,
,
,
for which 
,
.
,
,
by the condition, so 
,
,
,
yields 
since 
.
,
,
,
so 
contradicting the definition of 
Since 
due to 
,
.
since 
is 
,
)
in this case (note that this only applies for 
)
,
,
,
implying that 
which contradicts the definition of 
.
Note that 
,
,
since 
and 
.
,
for all 
.
,
.
,
for which 
(so clearly 
as well), so then consider the sequence 
for some sufficiently small 
.
.
since both 
,
not in 
as well), so then consider the sequence 
for some sufficiently small 
since neither 
or 
,
so 
.
with sum equal to 
then 
so we have constructed such a sequence for 
is minimsed, as desired. 
.
and let 
and 
where 
.![\[s-x+y\ge 2-s\implies y-x\ge 2-2s.\]](http://latex.artofproblemsolving.com/4/5/8/4587b7121fde16f9616586a39f10f982173d62f8.png)
Now if there exist 
and 
.
then 
.
and 
.
.
instead and increase some other element in 
so that the sum of values in ![\[1-\frac{s}{2-s}=\frac{2-2s}{2-s}\]](http://latex.artofproblemsolving.com/5/a/2/5a25c8242251c9391051b383c2167cc7760f521e.png)
and we are done. 
for each 
such that 
for all 
,
dominate each other.
for 
,
.
,
,
is at least 
in ![\[\sum_{j \in X^c} a_j - \sum_{i \in X} a_i \geq 2\varepsilon |X| > 2\varepsilon\]](http://latex.artofproblemsolving.com/7/c/3/7c3820dd05a7216d6ceab33cbdfc23976033f7e6.png)
yields a contradiction. 
.
,
with 
for each ![\[\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\]](http://latex.artofproblemsolving.com/e/3/4/e34398de7cc5612e4792e6831ac3038c1fc834c1.png)
where 
is the increasing sequence of all indices in 
is the increasing sequence of all indices in 
for each 
times in the RHS sum, as it is counted 
times total. So it suffices to demonstrate such a sequence 
with ![\[\sum_{i=1}^n c_i(2f(i) - n+i-1) = 0.\]](http://latex.artofproblemsolving.com/5/b/5/5b519a338154a7771612623a0a3ffc8fe72b6223.png)
There obviously exists such a 
and 
for some 
for all 
with a 
with 
.
,
,
,
.
with 
.
the inequality reads 
.
elements 
.
elements 
unpaired 
,
,
for all 
is minimised. We wish to modify 
.
is, we can assume without loss of generality that 
so we only have to maintain the numerical order.
before they are the same with 
to increase the value of 
.
is held, then intuitively at some point we must have that 
.
,
we have that 
,
which is clear for adding and subtracting it increases the sum 
,
and 
.
.
but 
,
,
.
,
.
.
,
and 
otherwise. This keeps the monoticity except when equality is a held, but in this case we can decrease 
by some 
is excluded). If this is the case, we have two cases:
.
,
for some 
.
,
which is closer to 
,
,
.
,
.
while keeping 
.
for some 
is not possible). By using the minimality on the set 
we have that 
,
from 
.![\[
\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|
\]](http://latex.artofproblemsolving.com/1/6/1/161a7caea273525328b0901d6b44cb83832cfb84.png)
Both 
and 
,
.
.
.
and scale 
for the construction of 
.
to hold, we must have ![\[ s_1(1 - \epsilon - a_n) + s_2a_n = 1 \tag{1.1} \]](http://latex.artofproblemsolving.com/1/f/5/1f5889ae4be0ca2bc03813f3f5fded3ff98219b4.png)
For the sum of terms to be 2, we must have ![\[ s_1(2 - a_n) + s_2a_n = 2 \tag{1.2} \]](http://latex.artofproblemsolving.com/b/c/c/bcc8317492d0fc7c09d4fbf31fd3550c5a0c2f9d.png)
Take (1.2) - (1.1) to get 
Thus, 
Solving for 
Thus 
We construct 
,
.
,
for all 
![\[ \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}\]](http://latex.artofproblemsolving.com/c/2/e/c2ea575bbe9a0bd88d437421b4d365e3843206a8.png)
Also, it is given that the minimum value of 
is achieved when 
.![\[ \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| \]](http://latex.artofproblemsolving.com/8/7/6/8760762138044e457b84cb3cc6931dbe89177739.png)
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} \]](http://latex.artofproblemsolving.com/3/8/2/38258ecaadb97ab0de4a3346069a08053f9b2a9b.png)
Observe that 
because 
is strictly increasing. This means 
.
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\]](http://latex.artofproblemsolving.com/6/b/7/6b794a3de105537e9fa1dd9ce0aa190f9736ccc5.png)
![\[ - a_m + a_{m-1} \le 2\sum\limits_{i \in X} a_i - 2\]](http://latex.artofproblemsolving.com/2/f/5/2f592c5bab43530e309cd7200521c322f959f4e6.png)
![\[ - a_m + a_{m-1} \le -2\epsilon\]](http://latex.artofproblemsolving.com/d/7/9/d79d94c22a2553fbfd167c85ab40ac892b03e5a5.png)
![\[ a_m \ge a_{m-1} +2\epsilon \tag{2.3}\]](http://latex.artofproblemsolving.com/7/0/e/70ee37ffdd0719c501084cc978b392aaa98bbd80.png)
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| \]](http://latex.artofproblemsolving.com/5/9/b/59ba2cdaaa6185ee5eec0beb592b5f407c06fc58.png)
This means that the minimum value of 
is achieved by 
.
finishes for the equality case.
.
with 
,
,
.
.
,
for 
.![$[n]\backslash S$](http://latex.artofproblemsolving.com/0/9/5/095f581428c0bd319fb11a80a1e2c85560b47f20.png)
is dominating.
if and only if 
can be arbitrarily small by letting 
elements close to 
,
with 
for all 
.
since a dominating subset must contain at least half of the elements. Thus, flipping a single 
,
