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
Bounds on degree of polynomials
Phorphyrion   3
N 8 minutes ago by Kingsbane2139
Source: 2020 Israel Olympic Revenge P3
For each positive integer $n$, define $f(n)$ to be the least positive integer for which the following holds:

For any partition of $\{1,2,\dots, n\}$ into $k>1$ disjoint subsets $A_1, \dots, A_k$, all of the same size, let $P_i(x)=\prod_{a\in A_i}(x-a)$. Then there exist $i\neq j$ for which
\[\deg(P_i(x)-P_j(x))\geq \frac{n}{k}-f(n)\]
a) Prove that there is a constant $c$ so that $f(n)\le c\cdot \sqrt{n}$ for all $n$.

b) Prove that for infinitely many $n$, one has $f(n)\ge \ln(n)$.
3 replies
Phorphyrion
Jun 11, 2022
Kingsbane2139
8 minutes ago
A point on BC
jayme   7
N 9 minutes ago by jayme
Source: Own ?
Dear Mathlinkers,

1. ABC a triangle
2. 0 the circumcircle
3. D the pole of BC wrt 0
4. B', C' the symmetrics of B, C wrt AC, AB
5. 1b, 1c the circumcircles of the triangles BB'D, CC'D
6. T the second point of intersection of the tangent to 1c at D with 1b.

Prove : B, C and T are collinear.

Sincerely
Jean-Louis
7 replies
jayme
Today at 6:08 AM
jayme
9 minutes ago
Zack likes Moving Points
pinetree1   73
N 23 minutes ago by NumberzAndStuff
Source: USA TSTST 2019 Problem 5
Let $ABC$ be an acute triangle with orthocenter $H$ and circumcircle $\Gamma$. A line through $H$ intersects segments $AB$ and $AC$ at $E$ and $F$, respectively. Let $K$ be the circumcenter of $\triangle AEF$, and suppose line $AK$ intersects $\Gamma$ again at a point $D$. Prove that line $HK$ and the line through $D$ perpendicular to $\overline{BC}$ meet on $\Gamma$.

Gunmay Handa
73 replies
1 viewing
pinetree1
Jun 25, 2019
NumberzAndStuff
23 minutes ago
Domain and Inequality
Kunihiko_Chikaya   1
N 28 minutes ago by Mathzeus1024
Source: 2018 The University of Tokyo entrance exam / Humanities, Problem 1
Define on a coordinate plane, the parabola $C:y=x^2-3x+4$ and the domain $D:y\geq x^2-3x+4.$
Suppose that two lines $l,\ m$ passing through the origin touch $C$.

(1) Let $A$ be a mobile point on the parabola $C$. Let denote $L,\ M$ the distances between the point $A$ and the lines $l,\ m$ respectively. Find the coordinate of the point $A$ giving the minimum value of $\sqrt{L}+\sqrt{M}.$

(2) Draw the domain of the set of the points $P(p,\ q)$ on a coordinate plane such that for all points $(x,\ y)$ over the domain $D$, the inequality $px+qy\leq 0$ holds.
1 reply
Kunihiko_Chikaya
Feb 25, 2018
Mathzeus1024
28 minutes ago
Number of roots of boundary preserving unit disk maps
Assassino9931   3
N Yesterday at 2:12 AM by bsf714
Source: Vojtech Jarnik IMC 2025, Category II, P4
Let $D = \{z\in \mathbb{C}: |z| < 1\}$ be the open unit disk in the complex plane and let $f : D \to D$ be a holomorphic function such that $\lim_{|z|\to 1}|f(z)| = 1$. Let the Taylor series of $f$ be $f(z) = \sum_{n=0}^{\infty} a_nz^n$. Prove that the number of zeroes of $f$ (counted with multiplicities) equals $\sum_{n=0}^{\infty} n|a_n|^2$.
3 replies
Assassino9931
May 2, 2025
bsf714
Yesterday at 2:12 AM
|A/pA|<=p, finite index=> isomorphism - OIMU 2008 Problem 7
Jorge Miranda   2
N Thursday at 8:00 PM by pi_quadrat_sechstel
Let $A$ be an abelian additive group such that all nonzero elements have infinite order and for each prime number $p$ we have the inequality $|A/pA|\leq p$, where $pA = \{pa |a \in A\}$, $pa = a+a+\cdots+a$ (where the sum has $p$ summands) and $|A/pA|$ is the order of the quotient group $A/pA$ (the index of the subgroup $pA$).

Prove that each subgroup of $A$ of finite index is isomorphic to $A$.
2 replies
Jorge Miranda
Aug 28, 2010
pi_quadrat_sechstel
Thursday at 8:00 PM
Prove the statement
Butterfly   8
N Thursday at 7:32 PM by oty
Given an infinite sequence $\{x_n\} \subseteq  [0,1]$, there exists some constant $C$, for any $r>0$, among the sequence $x_n$ and $x_m$ could be chosen to satisfy $|n-m|\ge r $ and $|x_n-x_m|<\frac{C}{|n-m|}$.
8 replies
Butterfly
May 7, 2025
oty
Thursday at 7:32 PM
Functional equation from limit
IsicleFlow   1
N Thursday at 4:22 PM by jasperE3
Is there a solution to the functional equation $f(x)=\frac{1}{1-x}f(\frac{2 \sqrt{x} }{1-x}), f(0)=1$ Such That $ f(x) $ is even?
Click to reveal hidden text
1 reply
IsicleFlow
Jun 9, 2024
jasperE3
Thursday at 4:22 PM
f(m+n)≤f(m)f(n) implies existence of limit
Etkan   2
N Thursday at 3:19 PM by Etkan
Let $f:\mathbb{Z}_{\geq 0}\to \mathbb{Z}_{\geq 0}$ satisfy $f(m+n)\leq f(m)f(n)$ for all $m,n\in \mathbb{Z}_{\geq 0}$. Prove that$$\lim \limits _{n\to \infty}f(n)^{1/n}=\inf \limits _{n\in \mathbb{Z}_{>0}}f(n)^{1/n}.$$
2 replies
Etkan
May 15, 2025
Etkan
Thursday at 3:19 PM
Collinearity in a Harmonic Configuration from a Cyclic Quadrilateral
kieusuong   0
Thursday at 2:26 PM
Let \((O)\) be a fixed circle, and let \(P\) be a point outside \((O)\) such that \(PO > 2r\). A variable line through \(P\) intersects the circle \((O)\) at two points \(M\) and \(N\), such that the quadrilateral \(ANMB\) is cyclic, where \(A, B\) are fixed points on the circle.

Define the following:
- \(G = AM \cap BN\),
- \(T = AN \cap BM\),
- \(PJ\) is the tangent from \(P\) to the circle \((O)\), and \(J\) is the point of tangency.

**Problem:**
Prove that for all such configurations:
1. The points \(T\), \(G\), and \(J\) are collinear.
2. The line \(TG\) is perpendicular to chord \(AB\).
3. As the line through \(P\) varies, the point \(G\) traces a fixed straight line, which is parallel to the isogonal conjugate axis (the so-called *isotropic line*) of the centers \(O\) and \(P\).

---

### Outline of a Synthetic Proof:

**1. Harmonic Configuration:**
- Since \(A, N, M, B\) lie on a circle, their cross-ratio is harmonic:
\[
  (ANMB) = -1.
  \]- The intersection points \(G = AM \cap BN\), and \(T = AN \cap BM\) form a well-known harmonic setup along the diagonals of the quadrilateral.

**2. Collinearity of \(T\), \(G\), \(J\):**
- The line \(PJ\) is tangent to \((O)\), and due to harmonicity and projective duality, the polar of \(G\) passes through \(J\).
- Thus, \(T\), \(G\), and \(J\) must lie on a common line.

**3. Perpendicularity:**
- Since \(PJ\) is tangent at \(J\) and \(AB\) is a chord, the angle between \(PJ\) and chord \(AB\) is right.
- Therefore, line \(TG\) is perpendicular to \(AB\).

**4. Quasi-directrix of \(G\):**
- As the line through \(P\) varies, the point \(G = AM \cap BN\) moves.
- However, all such points \(G\) lie on a fixed line, which is perpendicular to \(PO\), and is parallel to the isogonal (or isotropic) line determined by the centers \(O\) and \(P\).

---

**Further Questions for Discussion:**
- Can this configuration be extended to other conics, such as ellipses?
- Is there a pure projective geometry interpretation (perhaps using polar reciprocity)?
- What is the locus of point \(T\), or of line \(TG\), as \(P\) varies?

*This configuration arose from a geometric investigation involving cyclic quadrilaterals and harmonic bundles. Any insights, counterexamples, or improvements are warmly welcomed.*
0 replies
kieusuong
Thursday at 2:26 PM
0 replies
Find solution of IVP
neerajbhauryal   2
N Thursday at 1:50 PM by Mathzeus1024
Show that the initial value problem \[y''+by'+cy=g(t)\] with $y(t_o)=0=y'(t_o)$, where $b,c$ are constants has the form \[y(t)=\int^{t}_{t_0}K(t-s)g(s)ds\,\]

What I did
2 replies
neerajbhauryal
Sep 23, 2014
Mathzeus1024
Thursday at 1:50 PM
fourier series?
keroro902   2
N Thursday at 12:54 PM by Mathzeus1024
f(x)=$\sum _{n=0}^{\infty } \text{cos}(nx)/2^{n}$
f(x) = ?
thanks
2 replies
keroro902
May 14, 2010
Mathzeus1024
Thursday at 12:54 PM
Sets on which a continuous function exists
Creativename27   1
N May 15, 2025 by alexheinis
Source: My head
Find all $X\subseteq R$ that exist function $f:R\to R$ such $f$ continuous on $X$ and discontinuous on $R/X$
1 reply
Creativename27
May 15, 2025
alexheinis
May 15, 2025
Japanese Olympiad
parkjungmin   6
N May 15, 2025 by mathNcheese_aops
It's about the Japanese Olympiad

I can't solve it no matter how much I think about it.

If there are people who are good at math

Please help me.
6 replies
parkjungmin
May 10, 2025
mathNcheese_aops
May 15, 2025
A Sequence of +1's and -1's
ike.chen   34
N Apr 28, 2025 by fearsum_fyz
Source: ISL 2022/C1
A $\pm 1$-sequence is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and $$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.$$
34 replies
ike.chen
Jul 9, 2023
fearsum_fyz
Apr 28, 2025
A Sequence of +1's and -1's
G H J
G H BBookmark kLocked kLocked NReply
Source: ISL 2022/C1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ike.chen
1162 posts
#1 • 1 Y
Y by NO_SQUARES
A $\pm 1$-sequence is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and $$\left| \sum_{i = 1}^{k} a_{t_i} \right| \ge C.$$
This post has been edited 7 times. Last edited by ike.chen, Aug 6, 2023, 10:00 PM
Reason: Typo
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Tintarn
9044 posts
#2 • 1 Y
Y by Funcshun840
Answer
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CrazyInMath
457 posts
#3
Y by
The solution might be flawed but I would post it here
Solution?
edit: I wrote the solution with the statement @below
This post has been edited 1 time. Last edited by CrazyInMath, Jul 9, 2023, 6:09 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ike.chen
1162 posts
#4 • 2 Y
Y by GoodMorning, ehuseyinyigit
For context, this problem appeared during the US IMO Training Camp with the following flavor text:
MOP Test 4 wrote:
There are $2022$ buckets of water arranged in a row, each colored red or blue. Sally the salmon plays the following game:
    1. First, she chooses any bucket to start in and begins to jump.
    2. At each step, she may jump to the next bucket, or the one after that.
    3. She may stop jumping at any point, ending the game.
After the game ends, her score is the absolute value of the difference between the number of red buckets and the number of blue buckets she visited. Find the largest possible score Sally can achieve, regardless of the colors of the buckets.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
VicKmath7
1390 posts
#5
Y by
Solution of C1
This post has been edited 3 times. Last edited by VicKmath7, Jul 9, 2023, 7:43 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cj13609517288
1922 posts
#7
Y by
The answer is $\boxed{506}$, achieved by $+--++--+...+--++-$. If you really want a proof for why this gives $506$ use dp or something.

To prove that $506$ is the lowest you can get, consider the following algorithm:
Start at the first $+$, then go through every $+$ and go through every other $-$ in a gap(so say if we have $++---+++$ we go through indices $1,2,4,6,7,8$).
The algorithm where you swap $+$ and $-$ is the other algorithm we will consider. In both cases, we go through at most half of each gap, so we can just consider what happens if we go through half of the other sign.
Let $x$ be the number of $+$s, so there are $2022-x$ $-$s. Then we must have
\[C\le \text{max}\left(x-\frac{2022-x}{2},2022-x-\frac{x}{2}\right) = \text{max}\left(\frac{3x-2022}{2},\frac{4044-3x}{2}\right).\]This is the maximum of two numbers that sum up to $1011$, so it must be at least $505.5$, so it must be at least $506$. $\blacksquare$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
megarnie
5610 posts
#8 • 3 Y
Y by OronSH, Spectator, jerryzhang16
Solved with OronSH.

The answer is $\boxed{506}$. The construction is $1, -1, -1, 1, 1, -1, -1, 1, \ldots, 1, -1, -1, 1, 1, -1$, where $1, -1, -1, 1$ is repeated $505$ times and $1, -1$ is added to it. Notice the maximal sum we can get in each block of $1,-1,-1,1$ is $1$, and the maximal sum we can get in $1,-1$ is $1$, so we have a maximal value of $505\cdot 1 + 1 = 506$. Similarly, the minimal sum we can get in $-1,1,1,-1$ is $-1$, and the minimal sum we can get in $1,-1$ is $-1$, so we have a minimal value of $(-1) + -1 \cdot 505  = -506$, as desired.

Now we show that we can always create a subsequence as in the problem with absolute value at least $506$. WLOG that there are at least $1011$ ones.

Let $A$ be the number of ones and $B$ be the number of negative ones in total. The idea is to select every single $1$, and the every second element in each string of $-1$'s. This selection satisfies $t_{i+1} - t_i \le 2$. This gives us a total of at least $A - B/2 \ge 1011 - 1011/2 = 505.5$. Since it must be an integer, it is at least $506$.
This post has been edited 1 time. Last edited by megarnie, Jul 14, 2023, 5:27 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
OgnjenTesic
39 posts
#9
Y by
WLOG, we can assume that we have an equal or greater number of $1$ than $-1$ (since we are considering the sum in terms of absolute value).

Let's consider the "blocks" of $-1$. Let's say that in the first "block" we have $n_1$ numbers $-1$, in the second "block" we have $n_2$, ..., and in the $k$-th block, we have $n_k$ numbers $-1$:
$$\dots \underbrace{-1,-1,-1,\dots,-1}_{n_1}, 1,1,1, \dots, 1, \underbrace{-1,-1,-1,\dots,-1}_{n_2},1,1,1, \dots,1, \underbrace{-1,-1,-1,\dots,-1}_{n_k}, \dots$$In a block of $x$ number $-1$, we have to take at least $\left \lfloor{\frac{x}{2}}\right \rfloor$ numbers. Therefore, sum of $-1$ is at most
$$\left \lfloor{\frac{n_1}{2}}\right \rfloor+\left \lfloor{\frac{n_2}{2}}\right \rfloor+\dots+\left \lfloor{\frac{n_k}{2}}\right \rfloor\leqslant \left \lfloor{\frac{n_1+n_2+\dots+n_k}{2}}\right \rfloor=\left \lfloor{\frac{1011}{2}}\right \rfloor=505\text{.}$$So for every $\pm 1$-sequence, we can achieve sum $1011-505=506$. ($1011$ because we have at least 1011 number $1$)

Construction for $506$: $\underbrace{1, -1, -1, 1}{}, \underbrace{1, -1, -1, 1}{}, \dots, \underbrace{1, -1, -1, 1}, 1, -1$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bobthegod78
2982 posts
#10 • 1 Y
Y by centslordm
The answer is $506$, with equality achieved using 505 copies of $1,-1,-1,1$ and then a $1,-1$ at the end. To show this achieves it, consider each block of 4 (plus one block of 2), we can get at most one from each of these and it follows easily.

Let there be at most as many $-1$s as $1$s, then take as little $-1$'s as you can to take all the $+1$s. Let $c(1),c(-1)$ denote the number of 1s and -1s respectively. For each block of $x$ negatives, we need to take at least $\left\lfloor \frac x2 \right\rfloor$ of them. Then the problem follows since
\[
c(1) - \sum_{\text{block of } x} \left\lfloor \frac x2 \right\rfloor \geq 1011 - \left\lfloor \frac{1011}{2} \right\rfloor = 506,
\]as desired.
This post has been edited 2 times. Last edited by bobthegod78, Jul 14, 2023, 2:43 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
#11 • 1 Y
Y by centslordm
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
peace09
5419 posts
#12 • 2 Y
Y by megarnie, pi271828
Solved with pi271828.

The answer is $506$. Let $S$ denote the sum in question; we seek the minimum of $\max(|S|)$ over all sequences $a_1,\dots,a_{2022}$.

Optimality. Consider the sequence $1,-1,-1,1,1,\dots,1,1,-1$, and specifically the middle $2020$ terms; by symmetry, we can maximize the raw value of $S$ (rather than minimizing it and so maximizing its absolute value). If only one of the two terms $a_{4n-1},a_{4n}=1$ are among the chosen $a_{t_1},\dots,a_{t_k}$, we can include the other of the two whilst preserving all conditions and incrementing $S$. Additionally, for any "block" $-1,-1,1,1$ adjacent to but not among the chosen terms, we can include the terms $-1,1,1$ whilst preserving conditions and incrementing $|S|$. Including $a_1=1$, we therefore have the "steady state"
\[S\le1-1+1+1-1+1+1-\dots-1+1+1=506,\]as claimed.

Sufficiency. For any sequence, let $r_1,\dots,r_m$ denote the lengths of contiguous blocks of consecutive $-1$'s, and define $b_1,\dots,b_n$ similarly. To maximize the magnitude of $S$ in the negative direction, we include all the $-1$'s from $r_1,\dots,r_m$, and "bridge" these disjoint blocks with every other $1$, of which there are $\textstyle\sum\lfloor\tfrac{b_i}{2}\rfloor$. Analogously, to maximize the magnitude of $S$ in the positive direction, we include all the $1$'s from $b_1,\dots,b_n$ and bridge with every other $-1$, of which there are $\textstyle\sum\lfloor\tfrac{r_i}{2}\rfloor$. Hence,
\[|S|_1=\sum_{i=1}^mr_i-\sum_{i=1}^n\left\lfloor\frac{b_i}{2}\right\rfloor\quad\text{and}\quad|S|_2=\sum_{i=1}^nb_i-\sum_{i=1}^m\left\lfloor\frac{r_i}{2}\right\rfloor\]are both attainable. Summing, we have
\[|S|_1+|S|_2=\left(\sum_{i=1}^mr_i+\sum_{i=1}^nb_i\right)-\left(\sum_{i=1}^n\left\lfloor\frac{b_i}{2}\right\rfloor+\sum_{i=1}^m\left\lfloor\frac{r_i}{2}\right\rfloor\right)\ge2022-1011=1011,\]whence one of $|S|_1,|S|_2$ are $\ge506$, as desired. $\square$
This post has been edited 1 time. Last edited by peace09, Jul 14, 2023, 6:51 PM
Reason: formatting
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
JAnatolGT_00
559 posts
#13
Y by
We claim the answer $C=506.$ By a straightforward check the exact bound is obtained for the sequence $$+1,-1,-1,+1,+1,-1,-1,\ldots ,+1,+1,-1.$$
Now let's prove that such a sum is attainable for an arbitrary sequence. Divide the sequence in ascending order of index by consecutive blocks of equal numbers, and let these blocks contain $x_1,y_1,x_2,y_2,\ldots ,x_n,y_n$ numbers respectively ($x_i$ belongs to the block of $+1;$ probably $x_1$ or $y_n$ equal to $0$). Multiplying each number by $-1$ doesn't change the condition, so WLOG $\sum_{i=1}^n y_i\leq 1011.$ As a strategy lets pick all $+1,$ and in each block of $-1$ pick all numbers with even positions in this block - the sum of picked elements is $\sum_{i=1}^n \left( x_i-\left\lfloor \frac{y_i}{2}\right\rfloor \right) \geq 2022-\sum_{i=1}^n y_i -\left\lfloor \sum_{i=1}^n \frac{y_i}{2}  \right\rfloor \geq 2022-1011-505=506.$
This post has been edited 2 times. Last edited by JAnatolGT_00, Jul 19, 2023, 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.
GreenTea2593
236 posts
#14 • 2 Y
Y by peace09, CANBANKAN
ike.chen wrote:
A $\pm 1$-sequence is a sequence of $2022$ numbers $a_1, \ldots, a_{2022},$ each equal to either $+1$ or $-1$. Determine the largest $C$ so that, for any $\pm 1$-sequence, there exists an integer $k$ and indices $1 \le t_1 < \ldots < t_k \le 2022$ so that $t_{i+1} - t_i \le 2$ for all $i$, and $$\left| \sum_{i+1}^{k} a_{t_i} \right| \ge C.$$

isn't it supposed to be $i=1$ instead of $i+1$ in the sigma notation?
\[\left| \sum_{i=1}^{k} a_{t_i} \right| \geqslant C.\]
Attachments:
This post has been edited 3 times. Last edited by GreenTea2593, Aug 3, 2023, 8:35 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
awesomeming327.
1721 posts
#15
Y by
The answer is $506$ with construction is $+,-,-,+$ $505$ times and $+,-$ in addition. In each $+,-,-,+$ and $-,+,+,-$ we can get at most $1$ in absolute value so the construction works.

$~$
Now to show the bound, suppose WLOG there are at least $1011$ $+$. Select all the $+$, and every other $-$ then it's easy to show that we have at least $506$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Inconsistent
1455 posts
#16
Y by
Answer $506$ from taking $-1, 1, 1, -1, -1, 1, 1, \ldots$. To prove notice that we can process each block of consecutive $+1$ or $-1$ so that if $x, y$ are the number of $+1, -1$ total then we have on a fixed sequence:

$\max \text{LHS} \geq \max(x - y/2, y - x/2) \geq \frac{x+y}{4} = 505 \frac{1}{2}$, so $\max \text{LHS} \geq 506$.

This constant is achieved by the construction via the same blocking logic 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.
asdf334
7585 posts
#18
Y by
Assume there are $a$ of the $+1$ and $b$ of the $-1$. Then $a+b=2022$.

Let's now try to find the worst possible configuration for a fixed $a$ and $b$.
  • To maximize $C$, realize that we are limited by the number of $-1$ we can remove. Turns out when all the $-1$ are consecutive this is the worst possible (there are equivalent configurations, but calculations will be the same.)
  • Analogously all the $1$s are consecutive.
From this logic we've proven both (1) guaranteed maximums and minimums and (2) provided the construction, say, $1,1,1,\dots,-1,-1,-1$.

Now realize that the maximum is $M=a-b+\left \lceil \frac{b}{2}\right \rceil$ and the minimum is $m=a-b-\left \lceil \frac{a}{2}\right \rceil$.
\[M+(-m)=\left \lceil \frac{a}{2}\right \rceil + \left \lceil \frac{b}{2}\right \rceil\]which is equal to $1011$ when $a$ is even. When $a$ is odd it's equal to $1012$. So we can always get at least $506$ difference.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jelena_ivanchic
151 posts
#19
Y by
Proof
This post has been edited 1 time. Last edited by jelena_ivanchic, Jan 13, 2024, 10:33 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Leo.Euler
577 posts
#20
Y by
The answer is $\boxed{506}$. Construction is to take $1, -1, -1, 1$ repeatedly $505$ times and append $1, -1$.

WLOG, suppose that there are at least $1011$ positive terms and at most $1011$ negative terms among the $a_i$. Break the sequence of $a_i$ into blocks of $1$s and $-1$s, so that the signs of the blocks alternate. If we let $x_1$, $x_2$, ... denote the sequence of negative block sizes, then the number of negative terms in the subsequence $a_{t_i}$ is at most \[ \sum \left\lfloor x_i/2 \right\rfloor \le \left\lfloor (x_1+x_2+\dots)/2 \right\rfloor \le 505, \]so adding in all of the positive terms yields that $C \le 506$ always.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SnowPanda
186 posts
#21
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.
Shreyasharma
682 posts
#22
Y by
We will work the wording provided during the US IMO Training Camp.

We claim that the answer is $\boxed{506}$.

Upper Bound
Proof. Consider the arrangement,
\begin{align*}
\text{RBBRRBB \dots RRB}
\end{align*}Clearly it is optimal for Sally to begin on a ``block" of red buckets as if she begins on blue, she may just shift one ``block" back. Thus say she attempts to maximize $\text{Red} - \text{Blue}$. It is clear that in any block of four buckets, Sally can achieve a score of at most $+1$. As there are at most $506$ such sets, Sally can guarantee a score of at most $506$. $\square$

Lower Bound
Proof. To show that Sally can always guarantee a score of $506$ take a random sequence. Assume that there are at most $1011$ blue buckets and at least $1011$ red buckets. Then say that there are ``blocks" of red buckets $r_1$, $r_2$, \dots, $r_x$ and blocks of blue buckets $b_1$, $b_2$, \dots $b_{x-1}$. Then the problem becomes the following.
  • Pick an initial block $r_i$ to begin at, and a block $r_j$ to end at.
  • Define the function $S(i, j) = \sum_{m=i}^j r_m - \sum_{m=i}^{j-1} \left\lfloor \frac{b_m}{2} \right\rfloor$
  • Maximize $S(a, b)$.
Note that we may bound,
\begin{align*}
\sum_{m = i}^{j-1} \left\lfloor \frac{b_m}{2} \right\rfloor \leq \left\lfloor \frac{\sum_{m=1}^{x-1} b_m}{2} \right\rfloor \leq \left\lfloor \frac{1011}{2} \right\rfloor = 505
\end{align*}Then we guarantee at least,
\begin{align*}
S(1, x) \geq \sum_{m=1}^{x} r_m - 505 \geq 1011 - 505 = 506
\end{align*}and hence we are done. $\square$
This post has been edited 1 time. Last edited by Shreyasharma, Feb 7, 2024, 7:03 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mathboy100
675 posts
#23
Y by
The answer is $506$.

Define $f(S, C)$ for subsequence $S$ and $C \in {1, -1}$ to be the sum of the lengths of consecutive subsequences of $C$ in subsequence $S$ minus the sum of the floors of half of the length of each consecutive subsequence of $-C$ in subsequence $S$. It is obvious that the problem is asking for the minimum value of the maximum value of $C$ over every subsequence of every possible $\pm 1$ sequence.

Observe that if $x$ is the number of $1$s in a subsequence, and $y$ is the number of $-1$s in a subsequence, then $f(S, 1) \geq x - \frac{y}{2}$, and $f(S, -1) \geq y - \frac{x}{2}$. Adding the two, we obtain $f(S, 1) + f(S, -1) \geq \frac{x+y}{2}$, so one of the function values must be greater than or equal to $\frac{x+y}{4}$. In particular, if our subsequence is the entire sequence, we must have a function value greater than or equal to $506$.

Now, we claim that the sequence $1, -1, -1, 1, 1, -1, -1, \ldots -1$ satisfies the conditions. Observe that both $f(S, 1)$ and $f(S, -1)$ are equal to $506$ when $S$ is the full sequence. The rest of the proof that this sequence works is just casework, and I will omit it because I am lazy.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mogmog8
1080 posts
#24 • 1 Y
Y by centslordm
We claim the answer is $506$, which can be achieved by $505$ repetitions of $1,1,-1,-1$ followed by $1,-1$. For the bound, WLOG there are $a\le 1011$ negative ones. Then, in each consecutive group of negative ones we can eliminate at least half of them so there are at most $\lfloor a/2\rfloor$ negative ones left. Hence, the sum is at least $2022-a-\lfloor a/2\rfloor\ge 506$, as desired. $\square$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
sami1618
910 posts
#25
Y by
The answer is $\boxed{506}$.

Construction:
WLOG assume that there are at least $1011$ $a_i$ equal to $1$. Then over each gap of $a$ consecutive $a_i$ equal to $-1$ we can choose all but $\lfloor\frac{a}{2}\rfloor$ of them. So there exists a sequence with at least $1011$ positive $a_i$ and at most $505$ negative $a_i$.

Bound:
Consider the sequence $1,-1,-1,1,1,\dots,-1,-1,1,1,-1$. Each middle gap is 'unavoidable' leading to the desired bound.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Nuterrow
254 posts
#26
Y by
Proof: We claim that the answer is $506$. Note that if we have more $-1$'s than $+1$'s, we can flip the signs of all the numbers without affecting the problem. For the upper bound, we just consider the sequence,
$$+1 - 1 - 1 + 1 +1 -1 -1 \dots$$Now for the lower bound, suppose the number of $+1$'s in each block is $a_i$ from $a_1$ through $a_n$ and similarly the number of $-1$'s in each block is $b_i$ from $b_1$ through $b_m$. Our strategy will be to pick all the $+1$'s and pick as few $-1$'s as possible. For each block of $-1$ we will end up picking $\left \lfloor{\frac{b_i}{2}} \right \rfloor$ and thus,
$$C \geq \sum_{i=1}^n a_i - \left(\sum_{i=1}  \left \lfloor{\frac{b_i}{2}} \right \rfloor \right)$$$$C \geq \sum_{i=1}^n a_i - \left \lfloor {\frac{\sum_{i=1}^m b_i}{2}} \right \rfloor$$$$C \geq 1011 - 505 = 506$$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
SomeonesPenguin
129 posts
#27
Y by
The answer is $506$.

For the construction take $$1,-1,-1,1,1,-1,-1,\dots,-1,-1,1,1,-1$$
Where the sequence $1,-1,-1,1$ is repeated $505$ times and at the end we add $1$ and $-1$.

Now we show that we can always achieve $506$. Suppose that $1$ appears $a$ times and $-1$ appears $b$ times.

Case 1. $a=b=1011$.

Suppose the last number is negative and suppose the first one is positive (if it is not positive than just deleting the first negative numbers from the sequence gives a weaker problem). So consider the sequence $a_{1},a_{2},\dots,a_{2021}$. Now choose $t_i$ by this algorithm: Pick $t_{1}=1$. After this, if we have chosen $t_1,t_2,\dots,t_k$ and $a_{t_k+1} = 1$ pick $t_{k+1}=t_k+1$ and if $a_{t_k+1}=-1$ pick $t_{k+1}=t_k+2$. Notice that by doing this, we pick all the $1$s and skip at least $505$ of the $-1$s so the overall sum is at least $506$.

Case 2. $a\neq b$.

Suppose that $a > b$. We have that $a \ge 1012 > 1010 \ge b$ so by repeating the same algorithm from the start (without forgetting about the last number) we can choose every positive number and skip at least $\left\lfloor\frac{b}{2}\right\rfloor$ negative numbers so the sum will be at least $a-\left\lceil\frac{b}{2}\right\rceil\ge 1012-505=507$.
This post has been edited 1 time. Last edited by SomeonesPenguin, Aug 14, 2024, 2:00 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
laura0105_somali
16 posts
#28
Y by
2022 C1 Ex. Ex.
the extreme version found here
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
onyqz
195 posts
#29
Y by
posting for storage
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ezpotd
1275 posts
#30
Y by
I claim the answer is $506$.

Construction with $506$ as maximal: $xxyyxxyyxxyy \cdots xxyyxy$, where $x$ represents $1$ and $y$ represents $-1$. The largest possible positive sum is accomplished when all positive elements are in the sequence, and we are forced to take $505$ negative elements since there are $505$ blocks of $2$ negative elements, this gives a sum of $1011 - 505 = 506$.

Proof that we can always get $506$: Without loss of generality let there be at least as many positive elements as negative ones. Separate the sequence into blocks of positive and negative elements, we can take all the elements in positive blocks and we can ensure we take at most half of the elements in the negative blocks, so letting there be $x$ positive elements we can guarantee as a sum of at least $x - (\frac{2022 - x}{2}) = \frac 32 x - 1011$, since $x \ge 1011$ we have we can guarantee a sum at least $505.5$, since the sum is an integer we can guarantee $506$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Bonime
36 posts
#31 • 1 Y
Y by H_Taken
Ps: For some reason, AOPS won't let me post the solution to this problem in English, so it will be in Portuguese.

Primeiro, observe que a resposta é $\boxed{506}$ e pode ser facilmente obtida pelo seguinte padrão: $$+--++--++--++...--++-$$
Agora, para provar o limite, vamos supor, SPG, que a quantidade de $a_i=+1$ é $\ge a_j=-1$

Seja $X_i$ o $i$-ésimo bloco composto de $x_i$ $a_j=+1$ e $Y_i$ o $i$-ésimo bloco composto de $y_i$ $a_j=-1$
Observe que para cada $\pm1$-sequência, podemos executar o seguinte algoritmo para obter $\sum_{i = 1}^{k} a_{t_i} \ge 506.$

Tome $(t_1, t_2, ..., t_{x_1})=X_1$ e $(t_{x_1+1}, t_{x_1+2}, ..., t_{x_1+\left \lfloor{\frac{y_1}{2}}\right \rfloor})$ alternadamente entre os termos de $Y_1$ começando com $t_{x_1+1}=a_{x_1+2}$. Mais especificamente, para cada $X_i$, tome todos os seus termos como elementos do conjunto ${a_{t_1}, a_{t_2}, ..., a_{t_k}}$ e, para cada $Y_i$, tome alternadamente seus valores como termos desse conjunto. Portanto, veja que isso pode ser feito já que a maior distância entre dois $t_i$s é $2$. Além disso, com este algoritmo, garantimos que: $$\sum_{i = 1}^{k} a_{t_i} \ge \sum_i x_i + \sum_i {\left \lfloor{\frac{y_i}{2}}\right \rfloor} \ge 1011-505=506$$Como queríamos mostrar.
This post has been edited 3 times. Last edited by Bonime, Oct 29, 2024, 1:46 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
sansgankrsngupta
143 posts
#32
Y by
is $t_{k+1}= t_1$?
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
eibc
600 posts
#35
Y by
The answer is $C = 506$. For a construction, take the sequence $+1, +1, \ldots, +1, -1, \ldots, -1$, consisting of $1011$ terms of $+1$ followed by $1011$ terms of $-1$.

To prove bound holds, suppose WLOG there are more terms which are $+1$ than $-1$. Let $x$ be the number of terms which are $+1$. Now, suppose that whenever we come across a run of consecutive $-1$s, we only take the second term in the run to be one of the $a_{t_i}$, and then the fourth term, and so on. Then at most $\lfloor \tfrac{2022 - x}{2}\rfloor$ of the $a_{t_i}$ will be $-1$, so the sum of $a_{t_i}$ across all $1 \le i \le k$ is at least $x - \lfloor \tfrac{2022 - x}{2}\rfloor$. Since $x \ge 1011$ we have $\lfloor \tfrac{2022 - x}{2}\rfloor \le \tfrac{2022 - 1011}{2} = 505$, so $x - \lfloor \tfrac{2022 - x}{2}\rfloor \ge 1011 - 505 = 506.$
This post has been edited 1 time. Last edited by eibc, Dec 27, 2024, 10:33 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
AshAuktober
1008 posts
#36
Y by
Warning: Super long writeup.
Answer
Solution:
This post has been edited 2 times. Last edited by AshAuktober, Jan 1, 2025, 8:33 AM
Reason: Hid stuff for cleanliness.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
lelouchvigeo
183 posts
#37
Y by
sketch
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
EpicBird08
1754 posts
#38
Y by
The answer is $\boxed{C = 506}.$

Necessity: Consider the $\pm 1$-sequence $$1, 1, -1, -1, 1, 1, -1, -1, \dots, 1, 1, -1, -1, 1, 1, -1, -1, 1, -1.$$Here there are $505$ chunks of $1$s and $505$ chunks of $-1$s, for a total of $1011$ ones and $1011$ negative ones. Clearly we want to maximize the absolute difference between the number of $1$s we choose and the number of $-1$s we choose. If we want the number of $1$s we use to be greater than the number of $-1$s we use, we want to choose all the $1$s we can and choose as little $-1$s as we can. In each chunk of $-1$s, we must take at least one of the $-1$s as we cannot skip over any of them at once. Thus the absolute value of our absolute sum is bounded by $1011 - \frac{1010}{2} = 506.$ Similar work holds if we let the number of $-1$s we use to be greater than the number of $1$s we use. This gives $C \le 506.$

Sufficiency: Suppose without loss of generality that there are $a \ge 1011$ ones in our sequence, so that there are $2022-a$ negative ones. As before, we choose our sequence $t_i$ greedily. We choose all of the ones, and choose as little $-1$s as possible. while still navigating the entire sequence (so we don't stop in the middle somewhere). Suppose that the $-1$s come in contiguous runs of length $x_1, x_2, \dots, x_k,$ where $x_1 + \dots + x_k = 2022 - a.$ In a run of $m$ contiguous $-1$s, we can clearly only ignore at most $\left\lceil \frac{m}{2} \right\rceil$ of them, requiring us to choose $\left\lfloor \frac{m}{2} \right\rfloor$ of them. Therefore, when we choose the sequence which satisfies this, we get our sum is $$a - \sum_{i=1}^k \left\lfloor \frac{x_i}{2} \right\rfloor \ge a - \sum_{i=1}^k \frac{x_i}{2} = a - \frac{2022-a}{2} = \frac{3a-2022}{2} \ge \frac{3 \cdot 1011 - 2022}{2} \ge 505.5.$$Since the sum is an integer, it is at least $506,$ showing sufficiency.

Therefore, the best we can do is $C = 506,$ as claimed.

Remark: Once you get the idea of "jumping over" the $-1$s, both the equality case and the bound come naturally.
This post has been edited 2 times. Last edited by EpicBird08, Mar 3, 2025, 1:27 AM
Reason: messed up construction slightly
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
fearsum_fyz
53 posts
#39
Y by
We claim that the answer is $\boxed{506}$.

Proof of attainability: Assume, without loss of generality, that there are at least as many $+1$s in the sequence as there are $-1$s. There must be at least $1011$ $+1$s and at most $1011$ $-1$s.
Divide the sequence into maximal contiguous blocks of $+1$s and $-1$s:
$$\underbrace{+1, +1, \dots, +1,}_{a_1 \text{ times}} \underbrace{-1, -1, \dots, -1,}_{a_2 \text{ times}} \underbrace{+1, +1, \dots, +1,}_{a_3 \text{ times}} \underbrace{-1, -1, \dots, - 1}_{a_4 \text{ times}} \dots$$Consider all the $+1$s, and the $-1$s that are at even numbered positions within their block (of which there may be at most $\lfloor \frac{1011}{2} \rfloor = 505$). Clearly, no two elements of this subsequence are further than two places apart, and the sum is at least $1011 - 505 = 506$ as desired.

Proof of bound: Consider the following sequence:
$$+, -, -, +, +, -, -, +, + \dots, -, -, +, +, -$$It is easy to check that the maximum possible sum in this case is 506.

We are done.
Z K Y
N Quick Reply
G
H
=
a