We have your learning goals covered with Spring and Summer courses available. Enroll today!

G
Topic
First Poster
Last Poster
k a March Highlights and 2025 AoPS Online Class Information
jlacosta   0
Mar 2, 2025
March is the month for State MATHCOUNTS competitions! Kudos to everyone who participated in their local chapter competitions and best of luck to all going to State! Join us on March 11th for a Math Jam devoted to our favorite Chapter competition problems! Are you interested in training for MATHCOUNTS? Be sure to check out our AMC 8/MATHCOUNTS Basics and Advanced courses.

Are you ready to level up with Olympiad training? Registration is open with early bird pricing available for our WOOT programs: MathWOOT (Levels 1 and 2), CodeWOOT, PhysicsWOOT, and ChemWOOT. What is WOOT? WOOT stands for Worldwide Online Olympiad Training and is a 7-month high school math Olympiad preparation and testing program that brings together many of the best students from around the world to learn Olympiad problem solving skills. Classes begin in September!

Do you have plans this summer? There are so many options to fit your schedule and goals whether attending a summer camp or taking online classes, it can be a great break from the routine of the school year. Check out our summer courses at AoPS Online, or if you want a math or language arts class that doesn’t have homework, but is an enriching summer experience, our AoPS Virtual Campus summer camps may be just the ticket! We are expanding our locations for our AoPS Academies across the country with 15 locations so far and new campuses opening in Saratoga CA, Johns Creek GA, and the Upper West Side NY. Check out this page for summer camp information.

Be sure to mark your calendars for the following events:
[list][*]March 5th (Wednesday), 4:30pm PT/7:30pm ET, HCSSiM Math Jam 2025. Amber Verser, Assistant Director of the Hampshire College Summer Studies in Mathematics, will host an information session about HCSSiM, a summer program for high school students.
[*]March 6th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar on Math Competitions from elementary through high school. Join us for an enlightening session that demystifies the world of math competitions and helps you make informed decisions about your contest journey.
[*]March 11th (Tuesday), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS Chapter Discussion MATH JAM. AoPS instructors will discuss some of their favorite problems from the MATHCOUNTS Chapter Competition. All are welcome!
[*]March 13th (Thursday), 4:00pm PT/7:00pm ET, Free Webinar about Summer Camps at the Virtual Campus. Transform your summer into an unforgettable learning adventure! From elementary through high school, we offer dynamic summer camps featuring topics in mathematics, language arts, and competition preparation - all designed to fit your schedule and ignite your passion for learning.[/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
Sunday, Mar 2 - Jun 22
Friday, Mar 28 - Jul 18
Sunday, Apr 13 - Aug 10
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
Tuesday, Mar 25 - Jul 8
Sunday, Apr 13 - Aug 10
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, Mar 23 - Jul 20
Monday, Apr 7 - Jul 28
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
Sunday, Mar 16 - Jun 8
Wednesday, Apr 16 - Jul 2
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
Monday, Mar 17 - Jun 9
Thursday, Apr 17 - Jul 3
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
Sunday, Mar 2 - Jun 22
Wednesday, Apr 16 - Jul 30
Tuesday, May 6 - Aug 19
Wednesday, Jun 4 - Sep 17
Sunday, Jun 22 - Oct 19
Friday, Jul 18 - Nov 14

Introduction to Geometry
Tuesday, Mar 4 - Aug 12
Sunday, Mar 23 - Sep 21
Wednesday, Apr 23 - Oct 1
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

Intermediate: Grades 8-12

Intermediate Algebra
Sunday, Mar 16 - Sep 14
Tuesday, Mar 25 - Sep 2
Monday, Apr 21 - Oct 13
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
Sunday, Mar 23 - Aug 3
Wednesday, May 21 - Sep 17
Sunday, Jun 22 - Nov 2

Intermediate Number Theory
Friday, Apr 11 - Jun 27
Sunday, Jun 1 - Aug 24
Wednesday, Jun 18 - Sep 3

Precalculus
Sunday, Mar 16 - Aug 24
Wednesday, Apr 9 - Sep 3
Friday, May 16 - Oct 24
Sunday, Jun 1 - Nov 9
Monday, Jun 30 - Dec 8

Advanced: Grades 9-12

Olympiad Geometry
Wednesday, Mar 5 - May 21
Tuesday, Jun 10 - Aug 26

Calculus
Sunday, Mar 30 - Oct 5
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
Sunday, Mar 23 - Jun 15
Wednesday, Apr 16 - Jul 2
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
Friday, Apr 11 - Jun 27
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
Tuesday, Mar 4 - May 20
Monday, Mar 31 - Jun 23
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

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
Monday, Mar 24 - Jun 16
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
Sunday, Mar 30 - Jun 22
Wednesday, May 21 - Aug 6
Sunday, Jun 15 - Sep 14
Monday, Jun 23 - Sep 15

Physics 1: Mechanics
Tuesday, Mar 25 - Sep 2
Thursday, May 22 - Oct 30
Monday, Jun 23 - Dec 15

Relativity
Sat & Sun, Apr 26 - Apr 27 (4:00 - 7:00 pm ET/1:00 - 4:00pm PT)
Mon, Tue, Wed & Thurs, Jun 23 - Jun 26 (meets every day of the week!)
0 replies
jlacosta
Mar 2, 2025
0 replies
Coloring
demmy   6
N 5 minutes ago by Kaimiaku
Source: Thailand TST 2015
What is the maximum number of squares in an $8 \times 8$ board that can be colored so that for each square in the board, at most one square adjacent to it is colored.
6 replies
demmy
Dec 2, 2023
Kaimiaku
5 minutes ago
Nice and easy FE on R+
sttsmet   21
N 9 minutes ago by bo18
Source: EMC 2024 Problem 4, Seniors
Find all functions $ f: \mathbb{R}^{+} \to \mathbb{R}^{+}$ such that $f(x+yf(x)) = xf(1+y)$
for all x, y positive reals.
21 replies
sttsmet
Dec 23, 2024
bo18
9 minutes ago
max power of 2 that divides \lceil(1+\sqrt{3})^{2n}\rceil for pos. integer n
parmenides51   2
N 18 minutes ago by Inspector_Maygray
Source: Gulf Mathematical Olympiad GMO 2017 p4
1 - Prove that $55 < (1+\sqrt{3})^4 < 56$ .

2 - Find the largest power of $2$ that divides $\lceil(1+\sqrt{3})^{2n}\rceil$ for the positive integer $n$
2 replies
parmenides51
Aug 23, 2019
Inspector_Maygray
18 minutes ago
Points in general position
AshAuktober   1
N 20 minutes ago by Rdgm
Source: 2025 Nepal ptst p1 of 4
Shining tells Prajit a positive integer $n \ge 2025$. Prajit then tries to place n points such that no four points are concyclic and no $3$ points are collinear in Euclidean plane, such that Shining cannot find a group of three points such that their circumcircle contains none of the other remaining points. Is he always able to do so?

(Prajit Adhikari, Nepal and Shining Sun, USA)
1 reply
AshAuktober
Yesterday at 2:15 PM
Rdgm
20 minutes ago
No more topics!
two sequences of positive integers and inequalities
rmtf1111   49
N Yesterday at 6:28 PM by dolphinday
Source: EGMO 2019 P5
Let $n\ge 2$ be an integer, and let $a_1, a_2, \cdots , a_n$ be positive integers. Show that there exist positive integers $b_1, b_2, \cdots, b_n$ satisfying the following three conditions:

$\text{(A)} \ a_i\le b_i$ for $i=1, 2, \cdots , n;$

$\text{(B)} \ $ the remainders of $b_1, b_2, \cdots, b_n$ on division by $n$ are pairwise different; and

$\text{(C)} \ $ $b_1+b_2+\cdots b_n \le n\left(\frac{n-1}{2}+\left\lfloor \frac{a_1+a_2+\cdots a_n}{n}\right \rfloor \right)$

(Here, $\lfloor x \rfloor$ denotes the integer part of real number $x$, that is, the largest integer that does not exceed $x$.)
49 replies
rmtf1111
Apr 10, 2019
dolphinday
Yesterday at 6:28 PM
two sequences of positive integers and inequalities
G H J
Source: EGMO 2019 P5
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cj13609517288
1858 posts
#38
Y by
It's not hard to see by global that the statement is true if the floors weren't there(choose any construction and rotate the residues mod $n$ cyclically). The sum of the $b_i$ will then be $\frac{n(n-1)}{2}$ more than a multiple of $n$, so the floor part follows.
This post has been edited 1 time. Last edited by cj13609517288, Dec 21, 2023, 8:07 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Aaryabhatta1
1631 posts
#39
Y by
Consider choosing $b_i \in \{a_i, a_i + 1, \dots, a_i + (n-1)\}.$ Observe that all possible residues $\pmod{n}$ are encompassed uniquely in the intervals. If we select $(b_1, b_2, \dots, b_n)$ to have residues a permutation of $\{0, 1, \dots, n-1\}$ and assign $b_i$ to the corresponding value in the interval we satisfy conditions $(1), (2).$

The expected value of $b_i - a_i$ is $\frac{n-1}{2}$ since $b_i$ has equal probability of being any residue. Therefore the expected value of $\frac{1}{n}(\sum_{i = 1}^{n} b_i - a_i) = \frac{n-1}{2}$ by LoE. By Pigeonhole Principle, there must exist a tuple $(b_1, b_2, \dots, b_n)$ satisfying,
\begin{align*}
	\frac{1}{n} (\sum_{i = 1}^{n} b_i - a_i) &\le  	 \frac{n-1}{2} \\
	\frac{1}{n}(b_1 + b_2 + \cdots+ b_n) &\le (\frac{n-1}{2} + \frac{1}{n}(a_1 + a_2 + \cdots + a_n)).
\end{align*}Observe that $\frac{1}{n}\sum_{i = 1}^{n} b_i - \frac{(n-1)}{2} \equiv \frac{1}{n} \frac{n(n-1)}{2} -  \frac{n-1}{2} \equiv 0 \pmod{n}$ hence we conclude,
$$(b_1 + b_2 + \cdots+ b_n) \le n(\frac{n-1}{2} + \lfloor \frac{a_1 + a_2 + \cdots + a_n}{n} \rfloor).$$
This post has been edited 1 time. Last edited by Aaryabhatta1, Dec 22, 2023, 12:48 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mannshah1211
651 posts
#40
Y by
Let us assume $b_i = q_i \cdot n + r_i,$ with $r$ being a permutation of $\{0, 1, \dots, n - 1 \}$, so that $r_1 + r_2 + \dots + r_n = \frac{n(n - 1)}{2}$. Then, we must have $$q_1 + q_2 + \cdots + q_n \le \left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor,$$and also for the second condition, we must have $a_i \le q_i \cdot n + r_i,$ or $\left \lceil \frac{a_i - r_i}{n} \right \rceil \le q_i,$ or $\left \lfloor \frac{a_i - r_i + n - 1}{n} \right \rfloor \le q_i,$ but if $r_i$ is a permutation of $\{0, 1, \dots, n - 1 \}$, $n - 1 - r_i$ is a permutation also, so call this $p$. So, we write this compactly as $q_i \ge \frac{a_i + p_i}{n}$ and our earlier condition doesn't change, just that $r$ is replaced by $p$ so it suffices to show that there exists some permutation $p$ of $\{0, 1, \dots, n - 1\}$ with $$\left \lfloor \frac{a_1 + p_1}{n} \right \rfloor + \left \lfloor \frac{a_2 + p_2}{n} \right \rfloor + \dots + \left \lfloor \frac{a_n + p_n}{n} \right \rfloor \le \left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor.$$Now, consider the expected value of above expression over all possible $p$. By LoE, it is just $$\frac{\left \lfloor \frac{a_1}{n} \right \rfloor + \left \lfloor \frac{a_1 + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_1 + n - 1}{n} \right \rfloor}{n} + \frac{\left \lfloor \frac{a_2}{n} \right \rfloor + \left \lfloor \frac{a_2 + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_2 + n - 1}{n} \right \rfloor}{n} + \dots + \frac{\left \lfloor \frac{a_n}{n} \right \rfloor + \left \lfloor \frac{a_n + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_n + n - 1}{n} \right \rfloor}{n}.$$But, by Hermite identity, we have $$\left \lfloor \frac{a_i}{n} \right \rfloor + \left \lfloor \frac{a_i + 1}{n} \right \rfloor + \dots + \left \lfloor \frac{a_i + n - 1}{n} \right \rfloor = a_i,$$for any $i$. So, the expected value is $\frac{a_1 + a_2 + \dots + a_n}{n},$ but since the above quantity can only be an integer, it follows that there exists some such permutation with it not exceeding $\left \lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right \rfloor$.
This post has been edited 1 time. Last edited by mannshah1211, Jan 4, 2024, 6:44 PM
Reason: \left \right
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
RedFireTruck
4207 posts
#41
Y by
Since subtracting $n$ from $a_i$ and $b_i$ for some $i$ keeps a, b, and c true, we can assume that $0\le a_i < n$ WLOG. For some $i$, let $b_i\mod n = x$. Then, $a_i > x$ with probability $\frac{a_i}{n}$. If $a_i>x$ then $b_i=x$ works, otherwise $b_i=x+n$ works. Notice that $b_1\mod n, b_2\mod n,\dots, b_n\mod n$ is a permutation of $0,1,\dots,n-1$, so $\mathbb{E}[b_1+\dots+b_n]=\frac{n(n-1)}{2}+n\sum_{i=1}^{n}\frac{a_i}{n}=n(\frac{n-1}{2}+\frac{a_1+\dots+a_n}{n})$.

Since $b_1+\dots+b_n-\frac{n(n-1)}2$ must be a multiple of $n$, we must have that $b_1+\dots+b_n\le n(\frac{n-1}{2}+\lfloor\frac{a_1+\dots+a_n}{n}\rfloor)$ for some $b_1,\dots,b_n$, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
InterLoop
247 posts
#42 • 1 Y
Y by Funcshun840
natural
solution
This post has been edited 1 time. Last edited by InterLoop, Apr 30, 2024, 2:35 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
bjump
962 posts
#43
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.
Mathandski
706 posts
#44
Y by
$        $
Attachments:
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ihategeo_1969
161 posts
#45
Y by
Assume the contrary.

Assign each $b_i$ with $\pi(i)$ where $\pi$ is a permutation of $\{1,\dots,n\}$; such that $b_i \equiv \pi(i) \pmod n$. And now greedily choose $b_i$ to be the smallest number to satisfy this and the first condition of the question; and call such sequence $(b_1,\dots,b_n)$ \emph{good}.

And so for all good sequences we have that the third condition is not satisfied. And so we have \[\sum_i b_i-a_i \geq  \frac{n(n+1)}2-n \left \{\frac{\sum_i a_i}n \right\}\]This is because the LHS and RHS in the third condition is obviously congruent. So now, we will sum up this expression for all such good sequences.

See that for a particular $a_i$, we have that $\sum b_i-a_i$ for different choices of $b_i$ being assigned to $1$, $\dots$ or $n$; it is equal to \[(n+0-a_i+\dots+n+a_i-1-a_i)+(a_i-a_i+\dots+n-1-a_i)=na_i-na_i+\frac{n(n-1)}2=\frac{n(n-1)}2\]And hence the total summation gives us \begin{align*}
&\frac{n(n-1)}2 \cdot (n-1)! \cdot n \geq n! \left(\frac{n(n+1)}2-n \left \{\frac{\sum_i a_i}n \right\} \right) \iff \left \{\frac{\sum_i a_i}n \right\} \geq 1
\end{align*}Which is a contradiction.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Assassino9931
1194 posts
#46
Y by
Why so many solutions with randomness??? Childish greedy suffices, probabilistic stuff is too fancy for this problem.

For each $i$ pick the smallest possible $b_i \geq a_i$ such that the remainder $b_i \pmod n$ does not appear among those of $b_1,\ldots, b_{i-1}$.
Then for $i$ there are at most $i-1$ forbidden remainders mod $n$ from the previous numbers, so $b_i \leq a_i + i - 1$ for all $i$ and the distinct remainders condition is satisfied. Summing yields $\sum_{i=1}^n b_i - \frac{n(n-1)}{2} \leq \sum_{i=1}^n a_i$. The left-hand side is a multiple of $n$ (as the $b_i$ give the remainders $0,1,\ldots,n-1$ each once), so it is at most the largest multiple of $n$ not exceeding the right-hand side, i.e. $n\left\lfloor \frac{\sum_{i=1}^n a_i}{n} \right\rfloor$ 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.
Ywgh1
136 posts
#47
Y by
Let $b_i-a_i=c_i$ , we know that the maximum of the sum $c_1+c_2+ \dots +c_n = \frac{n(n-1)}{2}$. Hence we have that
\begin{align*}
b_1+b_2+\dots +b_n &= (a_1+a_2+ \dots+a_n)+ (c_1+c_2+\dots+c_n)\\
&\leq (a_1+a_2+ \dots+a_n)+ \frac{n(n-1)}{2}
\end{align*}Now as
\[ b_1+b_2+\dots+b_n \equiv \frac{n(n-1)}{2}\pmod{n}\]Then we have that.
\[ n |b_1+b_2+\dots+b_n-\frac{n(n-1)}{2}\]
Hence it can at most be the largest multiple of $n$ less than or equal to $a_1+a_2+\dots+a_n$.

Which means it’s $n\lfloor \frac{a_1+a_2+\dots+ a_n}{n} \rfloor$, hence we are done.
This post has been edited 17 times. Last edited by Ywgh1, Nov 9, 2024, 5:57 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
thdnder
193 posts
#48
Y by
Nice problem!

Obviously, we can pick non-negative integers $x_1, x_2, \dots, x_n$ such that the set $\{a_1 + x_1, a_2 + x_2, \dots, a_n + x_n\}$ is a complete residue system modulo $n$. Let $y_i$ be the number of times $i$ appears on the set $\{x_1, x_2, \dots, x_n\}$. (We can make sure that $0 \le x_1, x_2, \dots, x_n \le n - 1$.) Then after adding $k$ on each term of the set $\{x_1, x_2, \dots, x_n\}$ and taking modulo $n$, we see that the sum of our set will become $S_k = \sum_{i=0}^{n-1-k} (i + k)y_i + \sum_{i=n-k}^{n-1} (i + k - n)y_i$, and note that $\sum_{k=0}^{n-1} S_k = \sum_{i=0}^{n-1} y_i(i + (i+1) + \dots + (n-1) + 0 + 1 + \dots + (i-1)) = \frac{n(n-1)}{2}\sum_{i=0}^{n-1} y_i = \frac{n^2(n-1)}{2}$. Therefore, by pigeonhole principle, we can choose $k$ such that the sum of the set $\{x_1 + k, x_2 + k, \dots, x_n + k\} (n)$ is less or equal to $\frac{n(n-1)}{2}$. Let $z_i$ be the remainder of $x_i + k$ upon division by $n$, and let $r$ be the remainder of $a_1 + a_2 + \dots + a_n$ when divided by $n$. Then, since $\{a_1 + z_1, a_2  + z_2, \dots, a_n + z_n\}$ is a complete residue system module $n$, we have $(a_1 + z_1) + (a_2 + z_2) + \dots + (a_n + z_n) \equiv \frac{n(n-1)}{2} (n)$. $\implies z_1 + z_2 + \dots + z_n \equiv \frac{n(n-1)}{2} - r (n)$. Since $z_1 + z_2 + \dots + z_n \le \frac{n(n-1)}{2}$, we get that $z_1 + z_2 + \dots + z_n \le \frac{n(n-1)}{2} - r$.

Hence, if we set $b_i = a_i + z_i$, we deduce that $b_1 + b_2 + \dots + b_n = (a_1 + a_2 + \dots + a_n) + (z_1 + z_2 + \dots + z_n) \le \frac{n(n-1)}{2} - r + (a_1 + a_2 + \dots + a_n) = n(\frac{n-1}{2} + \left\lfloor \frac{a_1 + a_2 + \dots + a_n}{n} \right\rfloor)$, as desired. $\blacksquare$
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
#49
Y by
wanted greedy, ended up with expected value
solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mariairam
5 posts
#50
Y by
No expected value, just some quick and nice observations with residues.

Lemma: There exist positive integers $c_1,c_2,...,c_n\in\{0,1,2,...,n-1\}$ such that $a_i+c_i \neq a_j+c_j$(mod $ n$) $\forall i\neq j$ and $\displaystyle\sum_{i=1}^{n}c_i\le\frac{n(n-1)}{2}$.

Proof: Obviously, $\{a,a+1,...,a+n-1\}=\{0,1,...,n-1\}$(mod $n$). Now, for each $i=\overline{1,n-1}$ look at $A_i=\{a_i,a_i+1,...,a_i+n-1\}$ and order its elements in ascending order mod $n$. We can create $n!$ sets that contain $n$ elements, one from each $A_i$ such that no 2 elements are on corresponding positions in their respective $A_i$ and $A_j$ sets. For each such set, we can associate the sum of its elements minus $\displaystyle\sum_{i=1}^{n}a_i$: call it $s_i\forall i=\overline{1,n!}$. We get that $\displaystyle\sum_{i=1}^{n!}s_i=n!\cdot\frac{n(n-1)}{2}$ and by PHP, there is $s_i\le\frac{n(n-1)}{2}$. This means that there is a set $C=\{a_j+c_j|c_j\in\{0,...,n-1\}\forall j\overline{1,n-1}\}$ with the desired properties.

We carry on with the problem. Let $b_i=a_i+c_i$. The first $2$ conditions clearly hold, so all that remains is to show that the third one is true as well. Let $\displaystyle\sum_{i=1}^{n}a_i=cn+r$, with $r\le n-1$. Obviously, $\displaystyle\sum_{i=1}^{n}(a_i+c_i)=\frac{n(n-1)}{2}$ (mod $n$), so $\displaystyle\sum_{i=1}^{n}c_i=\frac{n(n-1)}{2}-r$ (mod $n$), meaning that $\displaystyle\sum_{i=1}^{n}c_i\le\frac{n(n-1)}{2}-r$(assuming the contrary quickly leads to a contradiction). We now wish to prove that $\displaystyle\sum_{i=1}^{n}(a_i+c_i)\le \frac{n(n-1)}{2}+\bigg\lfloor\frac{\displaystyle\sum_{i=1}^{n}a_i}{n}\bigg\rfloor$. Since the $LHS\le nc+r+\frac{n(n-1)}{2}-r=RHS$ 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.
Avron
18 posts
#51
Y by
Clearly we can assume that $0 \leq a_i \leq n-1$.

Order of $(a_n)$ does not matter so sort it non-decreasing. Let $S=\left\lfloor\frac{\sum_{i=1}^n a_i}{n}\right\rfloor$. We'll prove that $S+k-1 \geq a_k$ for each $k$. Note that

$$S=\left\lfloor\frac{\sum_{i=1}^{k-1} a_i+\sum_{i=k}^n a_i}{n}\right\rfloor\geq \left\lfloor\frac{\sum_{i=1}^{k-1} 0+\sum_{i=k}^n a_k}{n}\right\rfloor=
=\left\lfloor\frac{(n-(k-1))a_k}{n}\right\rfloor=\left\lfloor a_k-\frac{(k-1)a_k}{n}\right\rfloor=a_k+\left\lfloor-\frac{(k-1)a_k}{n}\right\rfloor$$
so it suffices to prove $k-1\geq-\left\lfloor-\frac{(k-1)a_k}{n}\right\rfloor$ which is true since $a_k<n$.

Now we claim that the sequence $b_i=S+i-1$ satisfies the conditions.

Conditions $A$ and $B$ follow from construction and the earlier property.

To prove $C$ note that:

$$\sum_{i=1}^n b_i=\sum_{i=1}^n(S+i-1)=nS+n\cdot\frac{n-1}{2}=n\left(\frac{n-1}{2}+S\right)$$
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.
dolphinday
1310 posts
#53
Y by
Randomize $b_i \pmod{n}$. Then $b_i$ ranges from $[a_i, a_i + n - 1]$, so $\mathbb{E}(b_i) = a_i + \frac{n-1}{2}$. This implies that there is some choice of $b_i$(by expected value) so that
\[\left(\frac{\sum_{i} b_i}{n} \right) \leq \frac{\sum_i a_i}{n} + \frac{n-1}{2} \]

If $ n$ is odd, then both $\frac{\sum_{i} b_i}{n}$ and $\frac{n-1}{2}$ are integers, so $ \frac{\sum_i a_i}{n}$ is also an integer.

If \( n \) is even, then $\left(\frac{\sum_{i} b_i}{n} \right) - \frac{n-1}{2}$ is an integer which implies that $\frac{\sum_i a_i}{n}$ is also an integer.

Thus there is some choice of $b_i$ so that
\[
\left(\frac{\sum_{i} b_i}{n} \right) \leq \left\lfloor \frac{\sum_i a_i}{n} \right\rfloor + \frac{n-1}{2}.
\]from our initial existence claim and replacing the fraction with the floor value in the problem statement.
Multiplying by $n$ on both sides gives us the desired, so we are done.
Z K Y
N Quick Reply
G
H
=
a