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
k i Adding contests to the Contest Collections
dcouchman   1
N Apr 5, 2023 by v_Enhance
Want to help AoPS remain a valuable Olympiad resource? Help us add contests to AoPS's Contest Collections.

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


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


More specifically:

For new threads:


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

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


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

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


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


For answers to already existing threads:


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

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



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


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

The above rules will be applied from next monday (5. march of 2007).
Feel free to discuss on this here.
49 replies
ZetaX
Feb 27, 2007
NoDealsHere
May 4, 2019
Geometry Problem #42
vankhea   2
N 18 minutes ago by kaede_Arcadia
Source: Van Khea
Let $P$ be any point. Let $D, E, F$ be projection point from $P$ to $BC, CA, AB$. Circumcircle $(ABC)$ cuts circumcircle $(AEF), (BFD), (CDE)$ at $A_1, B_1, C_1$. Let $A_2, B_2, C_2$ be antipode of $A_1, B_1, C_1$ wrt $(AEF), (BFD), (CDE)$. Prove that $A_2, B_2, C_2, P$ are cyclic.
2 replies
1 viewing
vankhea
Sep 6, 2023
kaede_Arcadia
18 minutes ago
divisibility
srnjbr   3
N 20 minutes ago by srnjbr
Find all natural numbers n such that there exists a natural number l such that for every m members of the natural numbers the number m+m^2+...m^l is divisible by n.
3 replies
srnjbr
3 hours ago
srnjbr
20 minutes ago
Very easy inequality
pggp   5
N 30 minutes ago by ionbursuc
Source: Polish Junior MO Second Round 2019
Let $x$, $y$ be real numbers, such that $x^2 + x \leq y$. Prove that $y^2 + y \geq x$.
5 replies
pggp
Oct 26, 2020
ionbursuc
30 minutes ago
Solve in gaussian integers
CHESSR1DER   0
39 minutes ago
Solve in gaussian integers.
$
\sin\left(\ln\left(x^{x^{x^2}}\right)\right) = x^4
$
0 replies
CHESSR1DER
39 minutes ago
0 replies
Inequality and function
srnjbr   4
N an hour ago by srnjbr
Find all f:R--R such that for all x,y, yf(x)+f(y)>=f(xy)
4 replies
srnjbr
3 hours ago
srnjbr
an hour ago
Problem 4
blug   3
N an hour ago by sunken rock
Source: Polish Junior Math Olympiad Finals 2025
In a rhombus $ABCD$, angle $\angle ABC=100^{\circ}$. Point $P$ lies on $CD$ such that $\angle PBC=20^{\circ}$. Line parallel to $AD$ passing trough $P$ intersects $AC$ at $Q$. Prove that $BP=AQ$.
3 replies
blug
Mar 15, 2025
sunken rock
an hour ago
Simple vector geometry existence
AndreiVila   2
N 2 hours ago by sunken rock
Source: Romanian District Olympiad 2025 9.1
Let $ABCD$ be a parallelogram of center $O$. Prove that for any point $M\in (AB)$, there exist unique points $N\in (OC)$ and $P\in (OD)$ such that $O$ is the center of mass of $\triangle MNP$.
2 replies
AndreiVila
Mar 8, 2025
sunken rock
2 hours ago
CMI Entrance 19#6
bubu_2001   5
N 2 hours ago by quasar_lord
$(a)$ Compute -
\begin{align*}
\frac{\mathrm{d}}{\mathrm{d}x} \bigg[ \int_{0}^{e^x} \log ( t ) \cos^4 ( t ) \mathrm{d}t \bigg]
\end{align*}$(b)$ For $x > 0 $ define $F ( x ) = \int_{1}^{x} t \log ( t ) \mathrm{d}t . $

$1.$ Determine the open interval(s) (if any) where $F ( x )$ is decreasing and all the open interval(s) (if any) where $F ( x )$ is increasing.

$2.$ Determine all the local minima of $F ( x )$ (if any) and all the local maxima of $F ( x )$ (if any) $.$
5 replies
bubu_2001
Nov 1, 2019
quasar_lord
2 hours ago
a! + b! = 2^{c!}
parmenides51   6
N 2 hours ago by ali123456
Source: 2023 Austrian Mathematical Olympiad, Junior Regional Competition , Problem 4
Determine all triples $(a, b, c)$ of positive integers such that
$$a! + b! = 2^{c!}.$$
(Walther Janous)
6 replies
parmenides51
Mar 26, 2024
ali123456
2 hours ago
Inequality
srnjbr   0
3 hours ago
a^2+b^2+c^2+x^2+y^2=1. Find the maximum value of the expression (ax+by)^2+(bx+cy)^2
0 replies
srnjbr
3 hours ago
0 replies
Graph Theory
JetFire008   1
N 3 hours ago by JetFire008
Prove that for any Hamiltonian cycle, if it contain edge $e$, then it must not contain edge $e'$.
1 reply
1 viewing
JetFire008
3 hours ago
JetFire008
3 hours ago
Inspired by hunghd8
sqing   1
N 3 hours ago by sqing
Source: Own
Let $ a,b,c\geq 0 $ and $ a+b+c\geq 2+abc . $ Prove that
$$a^2+b^2+c^2- abc\geq \frac{7}{4}$$$$a^2+b^2+c^2-2abc \geq 1$$$$a^2+b^2+c^2- \frac{1}{2}abc\geq \frac{31}{16}$$$$a^2+b^2+c^2- \frac{8}{5}abc\geq \frac{34}{25}$$
1 reply
sqing
3 hours ago
sqing
3 hours ago
Assisted perpendicular chasing
sarjinius   2
N 3 hours ago by chisa36
Source: Philippine Mathematical Olympiad 2025 P7
In acute triangle $ABC$ with circumcenter $O$ and orthocenter $H$, let $D$ be an arbitrary point on the circumcircle of triangle $ABC$ such that $D$ does not lie on line $OB$ and that line $OD$ is not parallel to line $BC$. Let $E$ be the point on the circumcircle of triangle $ABC$ such that $DE$ is perpendicular to $BC$, and let $F$ be the point on line $AC$ such that $FA = FE$. Let $P$ and $R$ be the points on the circumcircle of triangle $ABC$ such that $PE$ is a diameter, and $BH$ and $DR$ are parallel. Let $M$ be the midpoint of $DH$.
(a) Show that $AP$ and $BR$ are perpendicular.
(b) Show that $FM$ and $BM$ are perpendicular.
2 replies
sarjinius
Mar 9, 2025
chisa36
3 hours ago
Find min
hunghd8   4
N 3 hours ago by imnotgoodatmathsorry
Let $a,b,c$ be nonnegative real numbers such that $ a+b+c\geq 2+abc $. Find min
$$P=a^2+b^2+c^2.$$
4 replies
hunghd8
Today at 12:10 PM
imnotgoodatmathsorry
3 hours ago
two sequences of positive integers and inequalities
rmtf1111   49
N Mar 15, 2025 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
Mar 15, 2025
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
6865 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
6865 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
6865 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