Art of Problem Solving
AoPS Online AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy AoPS Academy
Small live classes for advanced math
and language arts learners in grades 1-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Stay ahead of learning milestones! Enroll in a class over the summer!
No tags match your search
M
G
Topic
First Poster
Last Poster
H
k a April Highlights and 2025 AoPS Online Class Information
jlacosta   0
Apr 2, 2025
Spring is in full swing and summer is right around the corner, what are your plans? At AoPS Online our schedule has new classes starting now through July, so be sure to keep your skills sharp and be prepared for the Fall school year! Check out the schedule of upcoming classes below.

WOOT early bird pricing is in effect, don’t miss out! If you took MathWOOT Level 2 last year, no worries, it is all new problems this year! Our Worldwide Online Olympiad Training program is for high school level competitors. AoPS designed these courses to help our top students get the deep focus they need to succeed in their specific competition goals. Check out the details at this link for all our WOOT programs in math, computer science, chemistry, and physics.

Looking for summer camps in math and language arts? Be sure to check out the video-based summer camps offered at the Virtual Campus that are 2- to 4-weeks in duration. 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 events:
[list][*]April 3rd (Webinar), 4pm PT/7:00pm ET, Learning with AoPS: Perspectives from a Parent, Math Camp Instructor, and University Professor
[*]April 8th (Math Jam), 4:30pm PT/7:30pm ET, 2025 MATHCOUNTS State Discussion
April 9th (Webinar), 4:00pm PT/7:00pm ET, Learn about Video-based Summer Camps at the Virtual Campus
[*]April 10th (Math Jam), 4:30pm PT/7:30pm ET, 2025 MathILy and MathILy-Er Math Jam: Multibackwards Numbers
[*]April 22nd (Webinar), 4:00pm PT/7:00pm ET, Competitive Programming at AoPS (USACO).[/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, 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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Apr 2, 2025
0 replies
J
H
Weighted Activity Selection Algorithm
Maximilian113   1
N 2 minutes ago by Maximilian113
An interesting problem:

There are $n$ events $E_1, E_2, \cdots, E_n$ that are each continuous and last on a certain time interval. Each event has a weight $w_i.$ However, one can only choose to attend activities that do not overlap with each other. The goal is to maximize the sum of weights of all activities attended. Prove or disprove that the following algorithm allows for an optimal selection:

For each $E_i$ consider $x_i,$ the sum of $w_j$ over all $j$ such that $E_j$ and $E_i$ are not compatible.
1. At each step, delete the event that has the maximal $x_i.$ If there are multiple such events, delete the event with the minimal weight.
2. Update all $x_i$
3. Repeat until all $x_i$ are $0.$
1 reply
Maximilian113
Today at 12:30 AM
Maximilian113
2 minutes ago
J
H
Mock 22nd Thailand TMO P3
korncrazy   1
N 12 minutes ago by YaoAOPS
Source: own
Find all triples of positive integers $(a,b,c)$ such that $$a|b+c,\,b|c+a, c|a+b$$and $\gcd(a,b,c)=1$.
1 reply
korncrazy
an hour ago
YaoAOPS
12 minutes ago
J
H
Mock 22nd Thailand TMO P2
korncrazy   1
N 14 minutes ago by YaoAOPS
Source: Own
Let $ABC$ be a triangle with $\angle BAC=60^\circ$. Let $B'$ be the reflection of $B$ across the line $AC$ and $B'$ be the reflection of $C$ across the line $AB$. Let $B'C$ and $BC'$ intersect at $A'$. Prove that the orthocenter of triangle $ABC$ coincides with the circumcenter of triangle $A'B'C'$.
1 reply
korncrazy
an hour ago
YaoAOPS
14 minutes ago
J
H
Mock 22nd Thailand TMO P1
korncrazy   1
N 19 minutes ago by YaoAOPS
Source: Own, Folklore
Let $a,b,c$ be real numbers such that $a+b+c=0$ and $a^2+b^2+c^2=2$. Find the largest possible value of $abc$.
1 reply
korncrazy
an hour ago
YaoAOPS
19 minutes ago
J
H
Index of Coincidence of a ciphertext with respect to itself.
fortenforge   0
Oct 18, 2009
If we are comparing a text to itself, we basically are mathematically finding the probability that if we choose $ 2$ characters from the text, the characters will be the same.
Here is the formula:
$ \displaystyle\sum_{i=1}^{c}\frac{n_i(n_i - 1)}{N(N-1)}$.
where $ c$ is the number of characters in the alphabet, $ n_i$ is the number of times the $ i$th of the alphabet appears in the plaintext, and $ N$ is the number of letters in the plaintext.
Let us try to derive this formula. Probability is defined as the number of ways you get what you want divided by the total number of possibilities. How many ways are there to choose any $ 2$ letters from a group of $ N$ letters? It is of course, $ \dbinom{N}{2}$ which is equal to $ \frac{N!}{2!(N-2)!} = \frac{N(N-1)}{2}$. This is the denominator. To calculate the numerator, we first calculate the number of ways to pick $ 2$ a's from our plaintext and add that to the number of ways to pick $ 2$ b's from our plaintext, and so on. If the number of a's in our plaintext was $ n_i$, then the number of ways to pick $ 2$ a's is $ \dbinom{n_i}{2}$, this is equal to $ \frac{n_i(n_i-1)}{2}$ as we have shown before. This numerator and denominator gives us $ \displaystyle\sum_{i=1}^{c}\frac{n_i(n_i - 1)/2}{N(N-1)/2}$, the $ /2$'s cancel giving us our desired formula:

$ \boxed{\displaystyle\sum_{i=1}^{c}\frac{n_i(n_i - 1)}{N(N-1)}}$.
0 replies
fortenforge
Oct 18, 2009
0 replies
J
H
Why frequency analysis does not work
fortenforge   0
Aug 30, 2009
Frequency Analysis works because there is a one to one correspondence between the plaintext alphabet and the ciphertext alphabet. If frequency analysis is going to work, the letter $ p$ should ALWAYS be encrypted as the letter $ c$. In a Vigenere cipher this does not occur. Depending of $ p$'s position in the plaintext, $ p$ could be encrypted as one of several letters. If the keyword has length $ 5$, then $ p$ could be encrypted as $ c_1,c_2,c_3,c_4,c_5$. This is not a one to one correspondence so frequency analysis does not work.

Let us say that the frequency of $ p$ in normal English was $ i$. If the key word was of length $ 1$, the frequency of $ c$ in the cipher text would be $ i$ as well. But if the key word was of length $ 2$, then the frequency of $ c_1 = i/2$ and the frequency of $ c_2 = i/2$. Basically frequency analysis works if there is one alphabet that corresponds to another alphabet in a 1 to 1 correspondence.
To find a method for cryptanalysis we need to be more creative.
0 replies
fortenforge
Aug 30, 2009
0 replies
J
H
Mathematics of the Vigenere Cipher
fortenforge   0
Aug 21, 2009
Ok, so I lied. I said that the next post was going to be about why frequency analysis fails on the Vigenere cipher but I decided to talk about how to mathematically define the cipher.

Let us say that we have already translated our plaintext into numbers (A = 0, B = 1, C = 2, ...). Let us say that the numbers are $ p_0, p_1, p_2, \cdots p_n$.

Let us say that we have chosen a key of length $ x$ and the letters of our key transformed into numbers are $ k_0, k_1, \cdots k_x$.

To encrypt plaintext number $ p_i$ we use $ k_j$ where $ j \equiv i \pmod{x}$. This accounts for the fact that the key is repeated over each letter of the plaintext. We use mod $ x$ because $ x$ is the length of the keyword.

Call $ c_i$ the corresponding ciphertext number to $ p_i$.

$ c_i \equiv p_i + k_j \pmod{26}$ where $ k_j \equiv i \pmod{x}$.

The first part is just the Caesar Cipher mathematically. The only difference is that as $ p_i$ changes $ k_j$ changes as well. This is what makes the Vigenere cipher a much better code.

Let's take an example:

plaintext: BLITZKRIEG
Numerical equivalent: 1 11 8 19 25 10 17 8 4 6

keyword: WAR
Numerical equivalent: 22 0 17

For the $ 0$th number of our plaintext, $ 1$, to find the equivalent key letter we take $ 0 \pmod{3} = 0$. So we take the $ 0$th keyword number which is $ 22$.

For the $ 5$th number of our plaintext, $ 10$ to find the equivalent key letter we take $ 5 \pmod{3} = 2$. So we take the $ 2$nd keyword number which is $ 17$.

We would continue this process for all the letters there by finding each letters keyword equivalent.

Notice that the first number in our list is being considered as our 0th number and the 2nd number is being considered as the 1st number to make the math work. In cryptography this is normal.

You can see that this method works by verifying it here:

WARWARWARW
BLITZKRIEG

The math method and the visual method match up, the 0th plaintext letter corresponds to the 0th key letter and the 5th plaintext letter corresponds to the 2nd key letter.

If we wanted to encrypt the 0th letter mathematically we would find:

$ 1 + 22 \pmod{26} \equiv 23$. So our 0th ciphertext number is 23.

If we wanted to encrypt the 5th letter mathematically we would find:

$ 10 + 17 \pmod{26} \equiv 1$. So our 5th ciphertext number is 1.

We would continue the process for all the letters.

Again when doing it mathematically and doing it without math you get the same ciphertext:

XLZPZBNIVC.

Learning what a cipher is mathematically is not much useful if you are decrypting a message by hand, but it is enormously useful if you are trying to program a cipher on a computer.
0 replies
fortenforge
Aug 21, 2009
0 replies
J
H
Number of Possible Keys for Substitution cipher.
fortenforge   0
Jul 6, 2009
We know that the Monoalphabetic Substitution Cipher should have a lot more keys than the Caesar Cipher, but how many more?

Ptext: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Ctext: ??????????????????????????

Let's look at the first "?" under the "A" in the ciphertext.
How many choices do we have for that "?". Well, we have $ 26$ choices because we can choose any letter of the alphabet. Let us say we chose "R".

Ptext: ABCDEFGHIJKLMNOPQRSTUVWXYZ
Ctext: R?????????????????????????

How many choices do we have for the next "?". We can choose any letter of the alphabet except "R", because we have already chosen that for the plaintext letter "A". So we have $ 25$ choices. Let's say we chose "E". Now for the next question mark we can't chose the letter "R" or "E" so we have $ 24$ choices. By now you should see the pattern, we have $ 26 \cdot 25 \cdot 24 \cdot 23 \ldots$ choices. That is equivalent to $ 26$ factorial.

$ 26! \approx 400000000000000000000000000$.

This is a lot of keys. Much much more keys than a Caesar Cipher. Unfortunately, with today's computers this is not that many keys. But this makes it impossible to try to crack a monoalphabetic substitution cipher using brute force by hand. There is however another method to crack this code...
0 replies
fortenforge
Jul 6, 2009
0 replies
J
H
Mathematics of the Caesar Cipher
fortenforge   0
Jun 21, 2009
We can write the algorithm for the Caesar cipher in terms of math.

$ k$ is the key. $ p$ is the letter being encrypted and $ c$ is the encrypted letter. The variables p and c are used to represent the letter being encrypted because in cryptography we refer to the original message as the 'plaintext' and the encrypted message as the 'ciphertext'.

We know $ k$, represents a number because it is the key. But $ p$ and $ c$ are actually letters. We need to convert them into numbers. This is very simple. Represent A by 0, B by 1, C by 2 ... Z by 25.

When encrypting a message we are shifting it by $ k$ letters. In terms of numbers we are just adding $ k$ to $ p$ to get $ c$.

$ c = p + k$.

There is one problem with this. If $ p = 25$ and $ k = 1$ then $ c = 26$ which is a number we cannot convert to a letter. This problem occurs because of the 'wrapping around' from Z to A. To fix this we can use modular arithmetic. If you don't know what this is try googling it. We will almost always be working in mod 26 because there are 26 letters in the alphabet. Our new equation would be:

$ c \equiv p + k \text{ }(\text{mod } 26)$

This is how to encrypt a message. To decrypt a message instead of adding $ k$ we should subtract it.

$ c\equiv p - k \text{ }(\text{mod } 26)$
0 replies
fortenforge
Jun 21, 2009
0 replies
J
No more topics!
H
J
H
Related to common tangent
utkarshgupta   3
N Jul 3, 2014 by jlammy
Source: BrMO 2000 R2 P1
$2$ intersecting circles $C_1$ and $C_2$ have a common tangent intersecting $C_1$ in $P$ and $C_2$ in $Q$.
The $2$ circles intersect in $M$ and $N$ where $N$ is nearer to $PQ$ than $M$.
Prove that the triangles $MNP$ and $MNQ$ have equal areas.
3 replies
utkarshgupta
Jun 8, 2014
jlammy
Jul 3, 2014
J
Related to common tangent
G H J
Reveal topic tags
geometry
trigonometry
geometry proposed
L
G H BBookmark kLocked kLocked NReply
Source: BrMO 2000 R2 P1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
utkarshgupta
2280 posts
utkarshgupta
#1 h  Jun 8, 2014, 11:22 AM • 2 Y
Y by Adventure10, Mango247
$2$ intersecting circles $C_1$ and $C_2$ have a common tangent intersecting $C_1$ in $P$ and $C_2$ in $Q$.
The $2$ circles intersect in $M$ and $N$ where $N$ is nearer to $PQ$ than $M$.
Prove that the triangles $MNP$ and $MNQ$ have equal areas.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Sowmitra
52 posts
Sowmitra
#2 h  Jun 8, 2014, 1:27 PM • 2 Y
Y by Adventure10, Mango247
Suppose, $MN\cap PQ=L$.
Then, $LP^2=LM\cdot LN=LQ^2\Rightarrow LP=LQ$.
So, $LM$ is a median of $\triangle MPQ\Rightarrow [MLP]=[MLQ]$ and $[NLP]=[NLQ]$ $\Rightarrow[MLP]-[NLP]=[MLQ]-[NLQ]\Rightarrow[MNP]=[MNQ]$
Here, $[X]$ denotes the area of region $X$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
utkarshgupta
2280 posts
utkarshgupta
#3 h  Jun 8, 2014, 2:23 PM • 2 Y
Y by Adventure10, Mango247
Exactly the proof I got!
I got another a rather messy proof using sine rule and area of triangle in terms of sines which ultimately led to the above result.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
jlammy
1099 posts
jlammy
#4 h  Jul 3, 2014, 4:42 PM • 2 Y
Y by Adventure10 and 1 other user
As in http://www.artofproblemsolving.com/Forum/viewtopic.php?f=56&t=592770&p=3538195#p3538195, see

http://ohkawa.cc.it-hiroshima.ac.jp/http://www.kalva.demon.co.uk/bmo/bsoln/bsol001.html
Z K Y
N Quick Reply
G
H
=
a