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

Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
Contests & Programs AMC and other contests, summer programs, etc.
AMC and other contests, summer programs, etc.
3 M G
BBookmark  VNew Topic kLocked
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
AIME score for college apps
Happyllamaalways   56
N 5 hours ago by Countmath1
What good colleges do I have a chance of getting into with an 11 on AIME? (Any chances for Princeton)

Also idk if this has weight but I had the highest AIME score in my school.
56 replies
Happyllamaalways
Mar 13, 2025
Countmath1
5 hours ago
MIT Beaverworks Summer Institute
PowerOfPi_09   0
5 hours ago
Hi! I was wondering if anyone here has completed this program, and if so, which track did you choose? Do rising juniors have a chance, or is it mainly rising seniors that they accept? Also, how long did it take you to complete the prerequisites?
Thanks!
0 replies
PowerOfPi_09
5 hours ago
0 replies
Convolution of order f(n)
trumpeter   70
N 5 hours ago by HamstPan38825
Source: 2019 USAMO Problem 1
Let $\mathbb{N}$ be the set of positive integers. A function $f:\mathbb{N}\to\mathbb{N}$ satisfies the equation \[\underbrace{f(f(\ldots f}_{f(n)\text{ times}}(n)\ldots))=\frac{n^2}{f(f(n))}\]for all positive integers $n$. Given this information, determine all possible values of $f(1000)$.

Proposed by Evan Chen
70 replies
trumpeter
Apr 17, 2019
HamstPan38825
5 hours ago
Linear algebra
Dynic   2
N Today at 3:32 PM by loup blanc
Let A and B be two square matrices with the same size. Prove that if AB is an invertible matrix, then A and B are also invertible matrices
2 replies
Dynic
Today at 2:48 PM
loup blanc
Today at 3:32 PM
3-dimensional matrix system
loup blanc   0
Today at 1:04 PM
Let $A=\begin{pmatrix}1&1&0\\0&1&1\\0&0&1\end{pmatrix}$.
i) Find the matrices $B\in M_3(\mathbb{R})$ s.t. $A^TA=B^TB,AA^T=BB^T$.
ii) Show that each solution of i) is in $M_3(K)$, where $K=\mathbb{Q}[\sin^2(\dfrac{2}{3}\arctan(3\sqrt{3}))]$.
iii) Solve i) when $B\in M_3(\mathbb{C})$.
EDIT. In iii) we again consider the transpose of $B$ and not its conjugate transpose.
0 replies
loup blanc
Today at 1:04 PM
0 replies
k HOT TAKE: MIT SHOULD NOT RELEASE THEIR DECISIONS ON PI DAY
alcumusftwgrind   8
N Today at 10:13 AM by maxamc
rant lol

Imagine a poor senior waiting for their MIT decisions just to have their hopes CRUSHED on 3/14 and they can't even celebrate pi day...

and even worse, this year's pi day is special because this year is a very special number...

8 replies
alcumusftwgrind
Today at 2:11 AM
maxamc
Today at 10:13 AM
Very hard group theory problem
mathscrazy   3
N Today at 9:50 AM by quasar_lord
Source: STEMS 2025 Category C6
Let $G$ be a finite abelian group. There is a magic box $T$. At any point, an element of $G$ may be added to the box and all elements belonging to the subgroup (of $G$) generated by the elements currently inside $T$ are moved from outside $T$ to inside (unless they are already inside). Initially $
T$ contains only the group identity, $1_G$. Alice and Bob take turns moving an element from outside $T$ to inside it. Alice moves first. Whoever cannot make a move loses. Find all $G$ for which Bob has a winning strategy.
3 replies
mathscrazy
Dec 29, 2024
quasar_lord
Today at 9:50 AM
limit of u(pi/45)
EthanWYX2009   0
Today at 7:08 AM
Source: 2025 Pi Day Challenge T5
Let \(\omega\) be a positive real number. Divide the positive real axis into intervals \([0, \omega)\), \([\omega, 2\omega)\), \([2\omega, 3\omega)\), \([3\omega, 4\omega)\), \(\ldots\), and color them alternately black and white. Consider the function \(u(x)\) satisfying the following differential equations:
\[
u''(x) + 9^2u(x) = 0, \quad \text{for } x \text{ in black intervals},
\]\[
u''(x) + 63^2u(x) = 0, \quad \text{for } x \text{ in white intervals},
\]with the initial conditions:
\[
u(0) = 1, \quad u'(0) = 1,
\]and the continuity conditions:
\[
u(x) \text{ and } u'(x) \text{ are continuous functions}.
\]Show that
\[
\lim_{\omega \to 0} u\left(\frac{\pi}{45}\right) = 0.
\]
0 replies
EthanWYX2009
Today at 7:08 AM
0 replies
Integration Bee Kaizo
Calcul8er   42
N Today at 12:57 AM by awzhang10
Hey integration fans. I decided to collate some of my favourite and most evil integrals I've written into one big integration bee problem set. I've been entering integration bees since 2017 and I've been really getting hands on with the writing side of things over the last couple of years. I hope you'll enjoy!
42 replies
Calcul8er
Mar 2, 2025
awzhang10
Today at 12:57 AM
maximum value
Tip_pay   3
N Yesterday at 9:37 PM by alexheinis
Find the value $x\in [0,4]$ at which the function $f(x)=\int_{0}^{\sqrt{x}}\ln \frac{e}{1+t^2}dt$ takes its maximum value
3 replies
Tip_pay
Yesterday at 8:48 PM
alexheinis
Yesterday at 9:37 PM
Spheres and a point source of light
mofidy   3
N Yesterday at 9:22 PM by kiyoras_2001
How many spheres are needed to shield a point source of light?
Unfortunately, I didn't find a suitable solution for it on the page below:
https://artofproblemsolving.com/community/c4h1469498p8521602
Here too, two different solutions are given:
https://math.stackexchange.com/questions/2791186
3 replies
mofidy
Mar 11, 2025
kiyoras_2001
Yesterday at 9:22 PM
Real Analysis
rljmano   4
N Yesterday at 4:38 PM by alexheinis
In [0 1], {f(t)}*{f’(t)-1} =0 and f is continuously differentiable. How do we conclude that either f is identically zero or f’(t) is identically 1 in [0 1]?
4 replies
rljmano
Yesterday at 6:32 AM
alexheinis
Yesterday at 4:38 PM
find the isomorphism
nguyenalex   14
N Yesterday at 1:49 PM by Royrik123456
I have the following exercise:

Let $E$ be an algebraic extension of $K$, and let $F$ be an algebraic closure of $K$ containing $E$. Prove that if $\sigma : E \to F$ is an embedding such that $\sigma(c) = c$ for all $c \in K$, then $\sigma$ extends to an automorphism of $F$.

My attempt:

Theorem (*): Suppose that $E$ is an algebraic extension of the field $K$, $F$ is an algebraically closed field, and $\sigma: K \to F$ is an embedding. Then, there exists an embedding $\tau: E \to F$ that extends $\sigma$. Moreover, if $E$ is an algebraic closure of $K$ and $F$ is an algebraic extension of $\sigma(K)$, then $\tau$ is an isomorphism.

Back to our main problem:

Since $K \subset E$ and $F$ is an algebraic extension of $K$, it follows that $F$ is an algebraic extension of $E$. Assume that there exists an embedding $\sigma : E \to F$ such that $\sigma(c) = c$ for all $c \in K$. By Theorem (*), there exists an embedding $\tau : F \to F$ that extends $\sigma$. Since $F$ is algebraically closed, $\tau(F)$ is also an algebraically closed field.

Furthermore, because $\sigma(c) = c$ for all $c \in K$ and $\tau$ is an extension of $\sigma$, we have
$$K = \sigma(K) \subset K \subset \sigma(E) \subset \tau(F) \subset F.$$
This implies that $F$ is an algebraic extension of $\tau(F)$. We conclude that $F = \tau(F)$, meaning that $\tau$ is an automorphism. (Finished!!)

Let choose $F = A$ be the field of algebraic numbers, $K=\mathbb{Q}$. Consider the embedding $\sigma: \mathbb{Q}(\sqrt{2}) \to \mathbb{Q}(\sqrt{2}) \subset A$ defined by
$$
a + b\sqrt{2} \mapsto a - b\sqrt{2}.
$$Then, according to the exercise above, $\sigma$ extends to an isomorphism
$$
\bar{\sigma}: A \to A.
$$How should we interpret $\bar{\sigma}$?
14 replies
nguyenalex
Mar 12, 2025
Royrik123456
Yesterday at 1:49 PM
find the convex sets satisfied
nguyenalex   2
N Yesterday at 9:54 AM by ILOVEMYFAMILY
In $\mathbb{R}^2$, let $B = \{(x, y) \mid x \geq 0\}$. Find all convex sets $C$ such that

\[\mathcal{E}(B \cup C) = B \cup C.\]
2 replies
nguyenalex
Yesterday at 8:57 AM
ILOVEMYFAMILY
Yesterday at 9:54 AM
happy configs
KevinYang2.71   60
N Yesterday at 6:38 AM by Ilikeminecraft
Source: USAJMO 2024/2
Let $m$ and $n$ be positive integers. Let $S$ be the set of integer points $(x,y)$ with $1\leq x\leq 2m$ and $1\leq y\leq 2n$. A configuration of $mn$ rectangles is called happy if each point in $S$ is a vertex of exactly one rectangle, and all rectangles have sides parallel to the coordinate axes. Prove that the number of happy configurations is odd.

Proposed by Serena An and Claire Zhang
60 replies
KevinYang2.71
Mar 20, 2024
Ilikeminecraft
Yesterday at 6:38 AM
happy configs
G H J
G H BBookmark kLocked kLocked NReply
Source: USAJMO 2024/2
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Shreyasharma
666 posts
#48
Y by
Forget about rotation and consider inducting.

Claim: There are an odd number of happy tilings for $2 \times 2n$ grid.
Proof. Note that the number of such tilings is clearly,
\begin{align*}
T = \frac{1}{n!} \binom{2n}{2} \binom{2n-2}{2} \dots \binom{2}{2} = \frac{(2n)!}{2^k \cdot n!}
\end{align*}It suffices to show that $\nu_2(T) = 0$, which is obvious from Legendre's. $\square$

Now assume for $m \leq k - 1$ we have shown that there is an odd number of happy tilings of a $2m \times 2n$ grid. It suffices to show that the number of tilings for a $2k \times 2n$ grid is odd. To do this, label the $(2k - 1)^{\text{th}}$ and $(2k)^{\text{th}}$ row by the set $A$, and all other rows by $B$. There are then two cases:
  • Each rectangle is contained strictly in $A$ or $B$.
  • There is at least one rectangle that has vertices in both $A$ and $B$.
Clearly the number of happy configurations of the first type is odd from our induction. Thus it suffices to show that the number of happy configurations of the second type are even. Call all happy configurations of the second kind special.

To do this consider the involution permuting the $(2k - 1)^{\text{th}}$ and $(2k)^{\text{th}}$ rows. This is an involution (hopefully I got it right this time) from special happy configurations to special happy configurations, which finishes.

Remark: Oops @below, lemme fix that real quick. This problem isn't really difficult you just have to be careful really. Unfortunately it's a bit tough to sort our the rotation invariant thing, and it's a lot easier to just swap rows, both of which I had motivated by looking at the $m = n = 2$ case.
This post has been edited 3 times. Last edited by Shreyasharma, Mar 24, 2024, 5:30 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
a_smart_alecks
51 posts
#49 • 2 Y
Y by vsamc, Shreyasharma
Shreyasharma wrote:
However we must also account for happy configurations that map to themselves under this operation. It is clear only $1$ such configuration exists, and thus the number of happy configurations is odd.

Note for all future solutions I guess: if your proof uses a reflection/rotation involution, there are many more configs that map to themselves than the $1$ configuration where each rectangle maps to itself. It is possible for $2$ different rectangles in a config to map to each other, which still allows the original config and its map to be identical. If your solution doesn't tackle these cases, your solution is incomplete.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mulberrykid
110 posts
#50
Y by
What percentage of students fakesolved this? Is it really that easy to fakesolve it?
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
#51 • 1 Y
Y by a_smart_alecks
Here is the (rather overcomplicated) solution that I first found.
Define $f(2m, 2n)$ in the obvious way. Given a happy configuration, consider all the rectangles whose left edge is in the first column. Highlight every column containing the right edge of such a rectangle. For example, in the figure below, there are two highlighted columns. (The rectangles are drawn crooked so one can tell them apart.)
[asy]
real eps = 0.6; for (int x=1; x<=10; ++x) { for (int y=1; y<=6; ++y) { pair P = (x,y); dot(P); } } dotfactor *= 1; real eps = 0.3; void rect(real a, real b, real u, real v, pen p) { draw( (a,b)--((a+u)/2, b-eps)--(u,b)--(u+eps,(b+v)/2)--(u,v) --((a+u)/2, v+eps)--(a,v)--(a-eps, (b+v)/2)--cycle, p); fill(circle((a,b), 0.2), p); fill(circle((u,b), 0.2), p); fill(circle((a,v), 0.2), p); fill(circle((u,v), 0.2), p); }
rect(1,1,8,3, blue + 1.5); rect(1,2,5,6, deepgreen + 1.5); rect(1,4,8,5, red + 1.5);
filldraw(box((4.5, 0.6), (5.5, 6.4)), invisible, black+dashed); filldraw(box((7.5, 0.6), (8.5, 6.4)), invisible, black+dashed);
[/asy]
We organize happy configurations based on the set of highlighted columns are highlighted. Specifically, define the relation $\sim$ on configurations by saying that $\mathcal C \sim \mathcal C'$ if they differ by any permutation of the highlighted columns. This is an equivalence relation. And in general, if there are $k$ highlighted columns, its equivalence class under $\sim$ has $k!$ elements.
Then
Claim: $f(2m, 2n)$ has the same parity as the number of happy configurations with exactly one highlighted column.
Proof. Since $k!$ is even for all $k \ge 2$, but odd when $k=1$. $\blacksquare$
There are $2m-1$ ways to pick a single highlighted column, and then $f(2, 2n) = (2n-1){!}{!}$ ways to use the left column and highlighted column. So the count in the claim is exactly given by \[ (2m-1) \cdot (2n-1){!}{!} f(2m-2, 2n). \]This implies $f(2m, 2n) \equiv f(2m-2,2n) \pmod 2$ and proceeding by induction solves the problem.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
mulberrykid
110 posts
#52
Y by
Hi, Evan, what do you think of the difficulty level of this problem?
v_Enhance wrote:
Here is the (rather overcomplicated) solution that I first found.
Define $f(2m, 2n)$ in the obvious way. Given a happy configuration, consider all the rectangles whose left edge is in the first column. Highlight every column containing the right edge of such a rectangle. For example, in the figure below, there are two highlighted columns. (The rectangles are drawn crooked so one can tell them apart.)
[asy]
real eps = 0.6; for (int x=1; x<=10; ++x) { for (int y=1; y<=6; ++y) { pair P = (x,y); dot(P); } } dotfactor *= 1; real eps = 0.3; void rect(real a, real b, real u, real v, pen p) { draw( (a,b)--((a+u)/2, b-eps)--(u,b)--(u+eps,(b+v)/2)--(u,v) --((a+u)/2, v+eps)--(a,v)--(a-eps, (b+v)/2)--cycle, p); fill(circle((a,b), 0.2), p); fill(circle((u,b), 0.2), p); fill(circle((a,v), 0.2), p); fill(circle((u,v), 0.2), p); }
rect(1,1,8,3, blue + 1.5); rect(1,2,5,6, deepgreen + 1.5); rect(1,4,8,5, red + 1.5);
filldraw(box((4.5, 0.6), (5.5, 6.4)), invisible, black+dashed); filldraw(box((7.5, 0.6), (8.5, 6.4)), invisible, black+dashed);
[/asy]
We organize happy configurations based on the set of highlighted columns are highlighted. Specifically, define the relation $\sim$ on configurations by saying that $\mathcal C \sim \mathcal C'$ if they differ by any permutation of the highlighted columns. This is an equivalence relation. And in general, if there are $k$ highlighted columns, its equivalence class under $\sim$ has $k!$ elements.
Then
Claim: $f(2m, 2n)$ has the same parity as the number of happy configurations with exactly one highlighted column.
Proof. Since $k!$ is even for all $k \ge 2$, but odd when $k=1$. $\blacksquare$
There are $2m-1$ ways to pick a single highlighted column, and then $f(2, 2n) = (2n-1){!}{!}$ ways to use the left column and highlighted column. So the count in the claim is exactly given by \[ (2m-1) \cdot (2n-1){!}{!} f(2m-2, 2n). \]This implies $f(2m, 2n) \equiv f(2m-2,2n) \pmod 2$ and proceeding by induction solves the problem.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Shreyasharma
666 posts
#53
Y by
I would say that this problem is $5$ to $10$ mohs, it's not extremely difficult but from a different perspective it's easy to fakesolve; I don't really know if that contributes to the actual difficulty of solving the problem though. All my opinion though.

Edit: Edited it to make the bounds $5$ mohs lower because I found an easy fix to the common fakesolve. Will add in a bit.
This post has been edited 2 times. Last edited by Shreyasharma, Mar 24, 2024, 7:09 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
#54
Y by
Hi, Evan, what do you think of the difficulty level of this problem?
Harder than JMO1, that's for sure :D

When I did this on stream the video ended up being about 20 minutes, though about half of that was me trying to explain the mess of my white board to the understandly confused audience. The video will go up sometime today, if you want to see my stumble around a bit before I manage to find this approach --- that might be more informative than hearing me making up a MOHS number. I think it was pretty clear to me that it needed to be some sort of grouping argument, but it wasn't obvious to me which grouping was going to eventually work. It didn't occur to me to only swap two rows.

Edit: VOD up at https://www.youtube.com/watch?v=eZe8tDDSx70
This post has been edited 1 time. Last edited by v_Enhance, Mar 27, 2024, 6:33 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Mathdreams
1411 posts
#55 • 1 Y
Y by AtharvNaphade
Shreyasharma wrote:
I would say that this problem is $10$ to $15$ mohs, it's not extremely difficult but from a different perspective it's easy to fakesolve; I don't really know if that contributes to the actual difficulty of solving the problem though. All my opinion though.

I would say its like 5 mohs or less, but as above said, the mohs scale is a bit broken.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
eibc
595 posts
#56
Y by
I did the following in contest (I hope this works), and I don't think this exact sol has been mentioned in this thread though the ideas seem to be similar to those in post #24. This solution would have been a lot shorter if I done vertical symmetry, rather than only considering horizontal symmetry, but oh well.

Let $f(m, n)$ denote the corresponding number of happy configurations. We first resolve when $m = 1$. In this case, we note that for $1 \le k \le 2n$, the points $(1, k)$ and $(2, k)$ must be vertices of the same rectangle, so it's equivalent to find the number of ways to form unordered pairs from $\{1, 2, \ldots, 2n\}$. By choosing which number to pair with $1$, we see for $n \ge 2$ that $f(1, n) = (2n - 1)f(1, n - 1)$. Since $f(1, 1) = 1$ is odd, by an inductive argument $f(1, n)$ is odd for any positive integer $n$.

Now, we move on to the general case for $m \ge 2$. Note that for any point in $S$, its reflection across the line $x = m + \tfrac{1}{2}$ (denote this by $\ell$) is also in $S$. This lets us pair up happy configs which are asymmetric wrt $\ell$, so it now suffices to show the number of symmetric happy configs about $\ell$ is odd.

For this, we let $P_1$ be some point in $S$, and $P_2$ be the unique other point in $S$ with the same $x$-coordinate and on the same rectangle as $P_1$. If we let $P_1'$, $P_2'$ be the other vertices of the rectangle s.t. $P_1, P_1'$ have the same $y$-coordinate, as do $P_2$ and $P_2'$, then we must have one of the following three cases:
  • Case 1: $P_1P_2P_2'P_1$ is symmetric across $\ell$. We will then say $P_1$ and $P_2$ are in a couple, as are $P_1'$ and $P_2'$
  • Case 2: $P_1P_2P_2'P_1'$ is asymmetric across $\ell$, and all four points lie on the same side of $\ell$. We then say the four points $P_1P_2P_2'P_1'$ form a quadruple, and we also note that their corresponding reflections over $\ell$ are also all vertices of one rectangle. We also call these two rectangles a Type A pair
  • Case 2: $P_1P_2P_2'P_1'$ is asymmetric across $\ell$, yet not all four points lie on the same side of $\ell$. Then if we let $Q_1, Q_2, Q_1', Q_2'$ be their corresponding reflections over $\ell$, we note that $Q_1Q_2Q_2'Q_1'$ is also a rectangle, and that $\{P_1, P_2, Q_1', Q_2'\}$ are on the same side of $\ell$, as are $\{P_1' P_2', Q_1, Q_2\}$. These two sets of four points will also each be a quadruple, and the two rectangles in this case will be a Type B pair
Then, the following process will generate all happy configs symmetric across $\ell$:
  • 1. Partition the $2mn$ points in $S$ to the left of $\ell$ (i.e. with $x$-coordinates less than $m + \tfrac{1}{2}$) into couples and quadruples such that every point is in either one couple or one quadruple, but not both.
  • 2. For any points $\{P_1, P_2\}$ in a couple, reflect them over $\ell$ to $P_1', P_2'$ and draw rectangle $P_1P_2P_2'P_1$
  • 3. For any points $\{P_1, P_2, P_3, P_4\}$ in a quadruple, reflect them over $\ell$ so there are $8$ points in total. Then, using these $8$ points, draw either a pair of Type A or a pair of Type B rectangles, but not both.
It's also evident enough that this process generates a unique happy config every time, depending on how the points are partitioned and what we choose to do in the third step. Thus, we can see that after we fix the quadruples and couples, we are able to generate $2^{\# \text{ of  quadruples}}$ happy configs, so it now suffices to show that the number of happy configs with only couples is odd. But by considering the points in $S$ on $x = k$ for $1 \le k \le m$, we find there are $f(1, n)^m$ ways to do this, which is odd. 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.
blueprimes
300 posts
#57
Y by
Easy :P

Let $C(2m, 2n)$ be the number of happy configurations on a $2m \times 2n$ lattice grid. Let column $i$ be the set of points $x = i, 1 \le y \le 2n$. Define the swiping operation as swapping column $1$ and column $2m$. In particular, any point $(1, k)$ goes to $(2m, k)$ and vice versa. Note that swiping is an involution, so we want to show the number of configurations that remain the same after being swiped (say, unswipeable configurations) is odd.

Now note that in any unswipeable configuration, for any rectangle with two vertices on column $1$ or $2m$, its reflection over the line $y = \frac{2m + 1}{2}$ is also present in the configuration. It is natural to consider the operation
$$\{(1, j) (1, k), (t, j), (t, k) \} \to \{(1, j) (1, k), (2m - t, j), (2m - t, k) \}$$$$\{(2m, j) (2m, k), (2m - t, j), (2m - t, k) \} \to \{ (2m, j), (2m, k), (t, j), (t, k) \}$$on any rectangles with vertices $(1, j), (1, k), (t, j), (t, k)$ and its reflection. We will call it crossing. Since it is also an involution, define all configurations that remain the same under the operation uncrossable. It suffices to show the number of such configurations is odd.

But in any uncrossable configuration, all rectangles sharing two vertices on column $1$ cannot have a reflection over $y = \frac{2m + 1}{2}$ otherwise the crossing operation can be performed, hence all such rectangles must also share two vertices with column $2m$. Note that these rectangles are completely independent from the middle $(2m - 2) \times 2n$ subgrid. There are $(2n - 1)!!$ ways to choose the rectangles, and $C(2m - 2, 2n)$ ways to arrange rectangles in the subgrid.

Collectively, we obtain $C(2m, 2m) \equiv (2n - 1)!! C(2m - 2, 2n) \equiv C(2m - 2, 2n) \pmod{2}$. Since we can also decrease in both $2m$ and $2n$, we can keep going down until we have $C(2m, 2n) \equiv C(2, 2) \equiv 1 \pmod {2}$ and we are done.
This post has been edited 3 times. Last edited by blueprimes, Aug 7, 2024, 2:34 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
joshualiu315
2513 posts
#58 • 1 Y
Y by blueprimes
Begin by considering the points $(1,y)$. In order for them to be placed into a happy configuration, they must be divided up into $n$ pairs of points, which can be done in

\[\frac{\binom{2n}{2} \cdot \binom{2n-2}{2} \cdot \dots \cdot \binom{2}{2}}{n!}.\]
Observe that this simplifies to

\[\prod_{i=1}^n \frac{\frac{2i(2i-1)}{2}}{i} = \prod_{i=1}^n (2i-1),\]
which is odd. We WLOG suppose that the points on $x=1$ are paired up such that $(1,2y-1)$ and $(1,2y)$ are together for $y = 1,2,\dots,n$. After ignoring $x=1$, we are left with a $(2m-1) \times 2n$ grid with $n$ segments connecting $(x_i,2i-1)$ and $(x_i,2i)$:


[asy]
size(10cm);
import geometry;

for(int i = 0; i<12; ++i){
for(int j = 0; j<6; ++j){
dot((i,j));
}
}

draw((0.5,-0.5)--(0.5,5.5),dotted);
draw((3,1)--(0,1)--(0,0)--(3,0),red+dotted); 
draw((3,1)--(3,0),red); 
draw((10,3)--(0,3)--(0,2)--(10,2),blue+dotted); 
draw((10,3)--(10,2),blue); 
draw((2,5)--(0,5)--(0,4)--(2,4),green+dotted); 
draw((2,5)--(2,4),green); 
[/asy]

If any tuple $(x_1, x_2, \dots x_n)$ produces any happy configurations, then $(2(m+1)-x_1, 2(m+1)-x_2, \dots, 2(m+1)-x_n)$ produces an equal amount of happy configurations due to symmetry. The only time where the symmetry fails is when $x_1=x_2=\dots=x_n = m+1$. At this point, we can also ignore the line $x=m+1$, reducing $m$ to $m-1$ in the original problem. Hence, we can use induction on $m$ to reduce the $2m \times 2n$ grid to a $1 \times 2n$ grid; on a $1 \times 2n$ grid, the number of happy configurations is equivalent to the number of ways to split up $2n$ numbers into $n$ pairs, which we already know is odd. $\blacksquare$

Remark: The above solution is a cleaned up writeup of what I submitted in the contest.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Danielzh
476 posts
#60
Y by
Motivation
Our task is to prove that the number of happy configurations is always odd. Thus, let's proceed by pairing happy configurations with each other! Consider what we can pair: Two configurations that differ only by a few rectangles? Too complicated. Two configurations that are obtained by reflecting one over the line $x=\frac{2m+1}{2}$? Yes!!

Solution
Reflect each happy configuration over the line $x=\frac{2m+1}{2}$. Pair the original happy configuration with the resulting (happy) configuration. There are edge cases though: when a happy configuration is symmetric about the line $x=\frac{2m+1}{2}$. In that case, again, consider pairing: each rectangle thus must reflect onto another (possibly identical) rectangle in the happy configuration. There are three types of such rectangles:

Type 1: The rectangle is symmetric about the line $x=\frac{2m+1}{2}$

Type 2: A pair of rectangles is symmetric about the line $x=\frac{2m+1}{2}$ with neither rectangle crossing the line.

Type 3: A pair of rectangles is symmetric about the line $x=\frac{2m+1}{2}$ with both rectangles crossing the line.

Notice by pairing two unique configurations differing only by a Type 2 and Type 3 pair (all other $4mn-4$ points have the same configuration) from the top-left most to the bottom-right most set of the 4 points, we have only the configurations where all rectangles are Type 1 left.

The number of configurations with only Type 1 rectangles is $(\frac{\binom{2n}{2} \binom{2n-2}{2} \cdots \binom{2}{2}}{n!})^m$, which is odd.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
CBMaster
85 posts
#61
Y by
My solution is basically same as in Solution #2, so I'll just give a motivation to this problem.
I get the idea of 'xooking'(I'll use the phrase used in #2) from USAMO 2018_6, especially the part that thinking each configuration as vertex of graph, and connect two by edge iff each two configuration can be made from the another one by some 'operation'.

Think each configuration as vertex of graph, and connect two vertice $x, y$ iff corresponding configuration $X, Y$ is in following relationship;
$X$ can be made from $Y$ by xooking some non-$V$-symmetric rectangle of $Y$.

You can find out easily that this operation is transitive, so resulting graph is non-directed graph. And each vertex having $k$ non-$V$-symmetric rectangle has degree $2^k-1$, which is odd if $k$ is positive, $0$ if $k$ is $0$.

This means resulting graph has two kinds of components;
(1) isolated vertices(which means corresponding configurations have $k=0$), (2) components that each vertex has odd degree(which means corresponding configurations have $k>0$).
By using Handshaking Lemma, it is easy that total number of vertices of kind 2) is even.

So we just need to consider vertices of kind 1), which corresponding to configurations with no non-$V$-symmetric rectangles.
Using same idea as above, we can prove that we only need to consider whether the number of configuration that every rectangle is $H, V$ symmetric is odd. And this is trivial, since there is only one.
This post has been edited 2 times. Last edited by CBMaster, Feb 9, 2025, 10:07 AM
Reason: .
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
#62 • 1 Y
Y by KenWuMath
Sub 2 minute fakesolve => like 10-15 minute actual solve
Note that in a happy configuration if we swap two rows but preserve all of the rectangles (basically shift the bases of the rectangles by swapping) we get a happy configuration. So in a 2mx2n grid it suffices to check the number of ways swapping the top and bottom rows doesn't change anything, because the amount of times it does is counted an even number of times because of this observation. We can prove there is an odd number of ways to choose this because the only way this swap wont change anything is if the rectangles involving the top and bottom row of squares only contain the top and bottom rows of squares. There are $\prod_{1 \le 1+ 4k \le 2n} (2n-1-4k) \equiv 1 \pmod{2}$ ways to do that, and we multiply by the number of ways to do it in a 2(m-1)x2n grid. Note that a 2x2 grid is trivially odd so by induction we are done.
This post has been edited 1 time. Last edited by bjump, Feb 23, 2025, 12:22 AM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
Ilikeminecraft
272 posts
#63
Y by
so how come I didn't solve this last year and then almost instasolve this year

Let $f(m, n)$ be the number of happy configs for values $m, n$ given in the problem statement.
Claim: $f(1, n)$ is odd.
Proof: It is very easy to compute the exact value, that is, $f(1, n) = (2n - 1)!!$. The top row must correspond to another one. There are $2n-1$ ways to pick this. Then, simply shift the lattices down. This gives the recursion $f(1,n) = (2n-1)f(1,n-1)$ which finishes.
Claim: $f(m, n) \equiv f(m+1,n)\pmod2$
Proof: Take the last two columns. Simply swap the last two, and it gives us another happy configuration. Of course, this fails when all happy rectangles are in the last two columns. Considering this, we get \[f(m + 1,n) = f(m, n)\cdot f(1, n) + 2\cdot(\text{happy configurations with some rectangles having vertices in both the last two columns and first }2m\text{ columns}) \equiv f(m,n)\pmod2.\]
This finishes.
Z K Y
N Quick Reply
G
H
=
a