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.
rmtf1111
698 posts
#1 • 5 Y
Y by Resolut1on07, Adventure10, Mango247, anantmudgal09, cubres
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$.)
This post has been edited 1 time. Last edited by darij grinberg, Nov 28, 2020, 5:26 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.
62861
3564 posts
#2 • 7 Y
Y by BobaFett101, Illuzion, star32, Aniruddha07, IAmTheHazard, aopsuser305, Adventure10
Solution
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
juckter
322 posts
#3 • 4 Y
Y by star32, Illuzion, trololo23, Adventure10
Let $r = (a_1 + a_2 + \dots + a_n) \pmod{n}$, and let $d_i = b_i - a_i$. Then we have

$$b_1 + b_2 + \dots + b_n \leq n\left(\frac{n - 1}{2} + \frac{a_1 + a_2 + \dots + a_n - r}{n}\right)$$$$\iff$$$$d_1 + d_2 + \dots + d_n = (b_1 - a_1) + \dots + (b_n - a_n) \leq \frac{n(n - 1)}{2} - r$$
So now we can see the problem as follows: We have a vector $(a_1, a_2, \dots, a_n)$ in $\mathbb{Z}_n^n$ and we're allowed to make a move that adds $1$ to one of the coordinates. We want to prove that we can make all the coordinates distinct in at most $\frac{n(n - 1)}{2} - r$ moves. Notice that a trivial way to attain this is to fix a vector $v = (v_1, v_2, \dots, v_n)$ with all distinct coordinates and gradually transform $a_i$ into $v_i$. Consider doing this for all $n$ choices of $v$ which are rotations of $(0, 1, 2, \dots, n - 1)$. By looking at the moves that we perform at each coordinate we can see that we perform

$$n\left(\frac{n(n - 1)}{2}\right)$$
Moves in total, so one of these rotations uses at most $\frac{n(n - 1)}{2}$ moves. But by considering the sum modulo $n$ we see that every valid sequence must use a number of moves congruent to $\frac{n(n - 1)}{2} - r \pmod{n}$, since at the end the sum is $0 + 1 + \dots + n - 1 \equiv \frac{n(n - 1)}{2} \pmod{n}$ and at the start it is $r$. So this choice in fact uses at most $\frac{n(n - 1)}{2} - r$ moves, as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sepled
10 posts
#4 • 6 Y
Y by MazeaLarius, BG71, MathbugAOPS, star32, Adventure10, Mango247
The key idea is quite simple.
Solution
This post has been edited 2 times. Last edited by Sepled, Apr 10, 2019, 12:01 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#5 • 12 Y
Y by Assassino9931, Math-Ninja, MihaiT, MathbugAOPS, star32, v4913, MrOreoJuice, PIartist, sabkx, Adventure10, vrondoS, MS_asdfgzxcvb
Cute/fun problem. (But not really number theory.)

Note that if $a_i > n$, we can replace $a_i$ with $a_i-n$ and $b_i$ with $b_i-n$, and nothing changes. So we may as well assume $a_i \in \{1, \dots, n\}$ for each $i$.

Pick a uniformly random permutation $\sigma$ on $\{1, \dots, n\}$ and define \[ b^\sigma_i = 	\begin{cases} 		n + \sigma(i) & a_i > \sigma(i) \\ 		\sigma(i) & \text{otherwise}. 	\end{cases} \]In that case, $\sum_i b^\sigma_i = (1+\dots+n) + n e_\sigma$, where $e_\sigma$ is the number of indices $i$ with $a_i > \sigma(i)$. Note that \[ \mathbb E[e_\sigma] 	= \sum_{i=1}^n \frac{a_i-1}{n} \]by linearity of expectation.

Thus there is some choice of $\sigma$ with $e_\sigma \le \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works.
This post has been edited 2 times. Last edited by v_Enhance, Apr 10, 2019, 2:40 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
ubermensch
820 posts
#6 • 2 Y
Y by Adventure10, Mango247
Wow this was a not too complicated but yet nice problem... who proposed this?
This post has been edited 1 time. Last edited by ubermensch, Apr 10, 2019, 2:21 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
prague123
230 posts
#7 • 1 Y
Y by Adventure10
v_Enhance wrote:
Thus there is some choice of $\sigma$ with $e_\sigma < \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works.

This statement definitely need a proof. In particular, it needs a proof for cases like $a_1=a_2=\cdots=a_n=1$, and for other cases where the righthand side is 0.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
prague123
230 posts
#8 • 2 Y
Y by Adventure10, Mango247
ubermensch wrote:
Wow this was a not too complicated but yet nice problem... who proposed this?
I have heard that is has been proposed by Poland but I do not know the author.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#9 • 3 Y
Y by v4913, Adventure10, Mango247
prague123 wrote:
v_Enhance wrote:
Thus there is some choice of $\sigma$ with $e_\sigma < \left\lfloor \sum_i \frac{a_i-1}{n} \right\rfloor$ and that choice works.

This statement definitely need a proof. In particular, it needs a proof for cases like $a_1=a_2=\cdots=a_n=1$, and for other cases where the righthand side is 0.

Typo, I meant $\le$ there.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hwl0304
1840 posts
#10 • 2 Y
Y by Adventure10, Mango247
First, zero-index the sequences (i.e. so they are \(a_0,\ldots, a_{n-1}\) and \(b_0,\ldots b_{n-1}\)). Moreover, we prove the general case where \(a_i,b_i\) are nonnegative.

Note that if the problem holds for some \(a_i\), we can perform the following invertible operations to prove it for a modified \(a_i\):
- We can sort/reorder the \(a_i\) by symmetry.
- We can add/subtract \(1\) from each \(a_i\) and \(b_i\) - this increases/decreases each side of the inequality in \(C\) by \(n\), and maintains everything else.
- We can add/subtract \(n\) from one of the \(a_i\) and \(b_i\) - similar reason.

Claim: We can modify any \(a_i\) such that \(a_i\le i\) for all \(0\le i\le n-1\). This clearly solves the problem, as we can just set \(b_i=i\) for all \(0\le i\le n-1\), then invert the process (sidenote: this appears wrong because it gives the bound \(\le n(n-1)/2\), but the transformation utilizes the "breathing space").

First, we can force everything to be \(\le n-1\) by subtracting by the appropriate factors of \(n\). Moreover, we can sort the integers and shift down accordingly so that \(0=a_0\le a_1\le \ldots\le a_{n-1}\le n-1\).

Now, consider the following process, assuming that there exists \(a_i>i\). We claim that \(\sum_{k=0}^{n-1}a_k-k\) is strictly decreasing.

Let \(i\) be the minimum number such that \(a_{i}>i\) (note \(i\neq 0\)). Shift the subsequence \(a_0,\ldots, a_{i-1}\) to the right by \(n-i\), then add \(n\), such that the new sequence is \(a_i, a_{i+1},\ldots, a_{n-1}, a_{0}+n, a_{1}+n, \ldots, a_{i-1}+n\).

Redefining the indices, we can see that \(a_k-k\) has now increased by \(i\) for each \(k\), because if originally \(k\ge i\), then \(k\) had been shifted to the left by \(i\), and if originally \(k<i\), then \(k\) had been shifted to the right by \(n-i\) but \(a_k\) had been increased by \(n\). Thus, the sum has increased by \(in\).

Now, we subtract what was originally \(a_i>i\) from every index. This decreases the sum by \(a_in\). Thus, each step of this process decreases the desired sum by \(n(a_i-i)\), while maintaining the fact that the numbers are between \(0\) and \(n-1\).

Assuming that the process can be carried out infinitely, \(\sum_{k=0}^{n-1}a_k-k\) is eventually small enough so that we force one of \(a_i\) to be negative, contradiction. Thus, the process must eventually stop, so that \(a_i\le i\) for all \(i\), as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Morskow
46 posts
#11 • 7 Y
Y by JANMATH111, MazeaLarius, anser, Illuzion, Infinityfun, Adventure10, Mango247
First, construct the $b_i$ one after the other as follows: Let $b_i\in \{a_i, a_i+1, \ldots, a_i+(i-1)\}$ such that the remainder of $b_i$ modulo $n$ is not equal to any remainder of the previously constructed $b_1, b_2, \ldots, b_{i-1}$ (pigeonhole principle forces this to work). If there are multiple choices, pick arbitrarily.

We claim the constructed set satisfies the conditions of the problem. Indeed, for all $i$, define $c_i=b_i-(i-1)$. By our construction, $c_i\leq a_i$ and $n\;|\;c_1+c_2+\ldots+c_n$ , therefore

\begin{align*}
b_1+b_2+\ldots+b_n&=c_1+c_2+\ldots+c_n+\frac{n(n-1)}{2}\\
&=n\left(\frac{n-1}{2}+\left\lfloor\frac{c_1+c_2+\ldots+c_n}{n}\right\rfloor\right)\\
&\leq n\left(\frac{n-1}{2}+\left\lfloor\frac{a_1+a_2+\ldots+a_n}{n}\right\rfloor\right),
\end{align*}
as desired.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
v_Enhance
6857 posts
#12 • 5 Y
Y by Polynom_Efendi, v4913, Adventure10, Mango247, tediousbear
Here is the same solution I posted earlier, but phrased in a way that I think is more natural (albeit longer), and also how I actually thought about the problem when I was solving it. Hopefully more instructive.

Note that if $a_i > n$, we can replace $a_i$ with $a_i-n$ and $b_i$ with $b_i-n$, and nothing changes. So we may as well assume $a_i \in \{1, \dots, n\}$ for each $i$.

We choose our $b_i$'s in the following way. Draw an $n \times n$ grid and in the $i$th column fill in the bottom $a_i-1$ cells red. We can select $b_i$ by marking $n$ cells, one in each row or column. If we chose $j$th lowest row in the $i$th column, then we would set $b_i = j$ on non-red cells and $b_i = j + n$ on red cells.

In this way, define the penalty $p$ as the number of selected cells which are red. Then \[ b_1 + \dots + b_n = (1+2+\dots+n) + n \cdot p 	= n \cdot \frac{n-1}{2} + n \cdot (p-1).  \]and we seek to minimize the penalty $p$.

[asy]defaultpen(fontsize(8pt)); 	size(8cm); 	fill( (1,0)--(1,2)--(2,2)--(2,3)--(4,3)--(4,4)--(5,4)--(5,0)--cycle, palered); 	for (int i=0; i<=5; ++i) { 		draw((i,0)--(i,5), grey); 		draw((0,i)--(5,i), grey); 	} 	draw(scale(5)*unitsquare); 	label("$b_i \equiv 1 \pmod 5$", (0,0.5), dir(180), lightblue); 	label("$b_i \equiv 2 \pmod 5$", (0,1.5), dir(180), lightblue); 	label("$b_i \equiv 3 \pmod 5$", (0,2.5), dir(180), lightblue); 	label("$b_i \equiv 4 \pmod 5$", (0,3.5), dir(180), lightblue); 	label("$b_i \equiv 5 \pmod 5$", (0,4.5), dir(180), lightblue); 	label("$a_1-1$", (0.5,0), dir(-90), lightred); 	label("$a_2-1$", (1.5,0), dir(-90), lightred); 	label("$a_3-1$", (2.5,0), dir(-90), lightred); 	label("$a_4-1$", (3.5,0), dir(-90), lightred); 	label("$a_5-1$", (4.5,0), dir(-90), lightred); 	label("$b_1$", (0.5, 3.5), blue); 	label("$b_2$", (1.5, 2.5), blue); 	label("$b_3$", (2.5, 4.5), blue); 	label("$b_4$", (3.5, 0.5), blue); 	label("$b_5$", (4.5, 1.5), blue); 	[/asy]

But the expected penalty of a random permutation is the red area divided by $n$, which is \[ \mathbb E[p] = \frac{(a_1-1) + \dots + (a_n-1)}{n} \]and so there exists a choice for which the penalty is at most $\lfloor \mathbb E[p] \rfloor$. This gives the required result.
This post has been edited 3 times. Last edited by v_Enhance, Apr 12, 2019, 12:41 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yayups
1614 posts
#13 • 1 Y
Y by Adventure10
Let $x_i=b_i-a_i$. We want $\{x_i+a_i\}$ to be a complete residue system modulo $n$. To this end, pick a uniformly random permutation
\[\sigma:[n]\to\mathbb{Z}/n\mathbb{Z},\]and pick $x_i$ to be the smallest non-negative number such that $x_i+a_i\equiv \sigma(i)\pmod{n}$. We see that $x_i$ has an equal chance to be any of $0,\ldots,n-1$, so
\[\mathbb{E}(x_i)=\frac{n-1}{2}.\]Thus,
\[\mathbb{E}(x_1+\cdots+x_n)=\frac{n(n-1)}{2},\]so there exists a valid choice of the $x_i$s such that
\[x_1+\cdots+x_n\le\frac{n(n-1)}{2}.\]However, we have that
\[\sum a_i+\sum x_i\equiv 0+\cdots+(n-1)=\frac{n(n-1)}{2}\pmod{n},\]so $\sum x_i=\frac{n(n-1)}{2}-\left(\sum a_i\pmod{n}\right)+kn$ for some integer $k$. Thus, we see that in fact, the $x_i$s we chose must further satisfy
\[\sum x_i\le \frac{n(n-1)}{2}-\left(\sum a_i\pmod{n}\right).\]Adding $\sum a_i$ to both sides yields the desired conclusion.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
spartacle
538 posts
#15 • 3 Y
Y by Assassino9931, tapir1729, Adventure10
Relabel $a_n, b_n$ as $a_0, b_0$. WLOG $0 \le a_i \le n-1$ for all $i$, and further WLOG $a_0 \le a_1 \le \ldots \le a_{n-1}$.

We use a simple greedy algorithm. For $0 \le i \le n-1$, select $b_i$ to be the smallest number such that $b_i \ge a_i$ and $b_i \not \equiv b_{i-1}, \ldots, b_0$. Since only $i$ of the $b_j$ have been selected already, clearly we will have $b_i \le a_i + i$. Summing this across all $i$, we have $b_0 + b_1 + \ldots b_{n-1} \le a_1 + a_2 + \ldots + a_{n-1} + 1 + 2 + \ldots + n-1$, which is almost (but not quite) what we want.

However, we can do better. Since $b_0, \ldots, b_{n-1}$ is a permutation of $0, \ldots, n-1 \pmod{n}$, $b_0 + \ldots + b_{n-1} - 0 - 1 - \ldots - {n-1}$ is a multiple of $n$. So in fact this quantity is less than or equal to the largest multiple of $n$ which is $\le a_0 + \ldots + a_{n-1}$, i.e. $n\left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor$. Hence
$$b_0 + \ldots + b_{n-1} - 0 - 1 - \ldots - {n-1} \le n\left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor \implies b_0 + \ldots + b_{n-1} \le n\left( \frac{n-1}{2} + \left \lfloor \frac{a_0 + \ldots + a_{n-1}}{n} \right \rfloor \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.
GeronimoStilton
1521 posts
#16 • 2 Y
Y by Adventure10, Mango247
For each $a_i$, we define $x_i$ and $r_i$ such that $x_i n + r_i$, $0 \le r_i < n$, and $x_i$ is an integer. Consider a random permutation $\pi$ of the set $\{0, 1, \cdots , n-1\}$. We define
\[\pi(a_i) = n\left\lceil \frac{a_i - \pi(i)}{n} \right\rceil + \pi(i),\]that is, the minimal number greater than or equal to $a_i$ congruent to $\pi(i)$ modulo $n$. Now, we consider
\[\sum_{i = 1}^n \pi(a_i) = \sum_{i = 1}^n \left(n\left\lceil \frac{a_i - \pi(i)}{n} \right\rceil + \pi(i)\right) = \sum_{i = 1}^n \pi(i) + n\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil = \]\[\sum_{i = 0}^{n-1} i + n\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil = n\left(\frac{n-1}{2} + \sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil\right).\]It suffices to show that there exists a permutation $\pi$ such that
\[\sum_{i = 1}^n \left\lceil \frac{a_i - \pi(i)}{n} \right\rceil \le \left\lfloor \frac{\sum_{i = 1}^n a_i}{n}\right\rfloor.\]Substituting in $a_i = x_in + r_i$, we see that it suffices to show that
\[\sum_{i = 1}^n \left(x_i + \left\lceil \frac{r_i - \pi(i)}{n} \right\rceil\right) \le \sum_{i = 1}^n x_i + \left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor,\]or equivalently,
\[\sum_{1 \le i \le n, r_i > \pi(i)} 1 = \sum_{i = 1}^n \left\lceil \frac{r_i - \pi(i)}{n} \right\rceil \le \left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor.\]Now, by the probabilistic method, it suffices to show that the expected value of $\sum_{1 \le i \le n, r_i > \pi(i)} 1$ is less than or equal to $\left\lfloor \frac{\sum_{i = 1}^nr_i}{n}\right\rfloor$, since we will then have that such a permutation $\pi$ exists. We compute that
\[\mathbb{E}\left[\sum_{1 \le i \le n, r_i > \pi(i)} 1\right] = \sum_{i=1}^n\mathbb{P}[r_i > \pi(i)] = \sum_{i=1, r_1 \ge 1}^n\frac{r_i - 1}{n} = \frac{\sum_{i=1, r_1 \ge 1}^n r_i}{n} - 1 \le \]\[\left\lfloor\frac{\sum_{i=1, r_1 \ge 1}^n r_i}{n}\right\rfloor = \left\lfloor\frac{\sum_{i=1}^n r_i}{n}\right\rfloor.\]Thus, we are done by the probabilistic method. $\blacksquare$
Z K Y
G
H
=
a