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
Inequality => square
Rushil   12
N 7 minutes ago by ohiorizzler1434
Source: INMO 1998 Problem 4
Suppose $ABCD$ is a cyclic quadrilateral inscribed in a circle of radius one unit. If $AB \cdot BC \cdot CD \cdot DA \geq 4$, prove that $ABCD$ is a square.
12 replies
+1 w
Rushil
Oct 7, 2005
ohiorizzler1434
7 minutes ago
p + q + r + s = 9 and p^2 + q^2 + r^2 + s^2 = 21
who   28
N 24 minutes ago by asdf334
Source: IMO Shortlist 2005 problem A3
Four real numbers $ p$, $ q$, $ r$, $ s$ satisfy $ p+q+r+s = 9$ and $ p^{2}+q^{2}+r^{2}+s^{2}= 21$. Prove that there exists a permutation $ \left(a,b,c,d\right)$ of $ \left(p,q,r,s\right)$ such that $ ab-cd \geq 2$.
28 replies
who
Jul 8, 2006
asdf334
24 minutes ago
H not needed
dchenmathcounts   44
N an hour ago by Ilikeminecraft
Source: USEMO 2019/1
Let $ABCD$ be a cyclic quadrilateral. A circle centered at $O$ passes through $B$ and $D$ and meets lines $BA$ and $BC$ again at points $E$ and $F$ (distinct from $A,B,C$). Let $H$ denote the orthocenter of triangle $DEF.$ Prove that if lines $AC,$ $DO,$ $EF$ are concurrent, then triangle $ABC$ and $EHF$ are similar.

Robin Son
44 replies
dchenmathcounts
May 23, 2020
Ilikeminecraft
an hour ago
IZHO 2017 Functional equations
user01   51
N an hour ago by lksb
Source: IZHO 2017 Day 1 Problem 2
Find all functions $f:R \rightarrow R$ such that $$(x+y^2)f(yf(x))=xyf(y^2+f(x))$$, where $x,y \in \mathbb{R}$
51 replies
user01
Jan 14, 2017
lksb
an hour ago
No more topics!
IMO ShortList 2002, combinatorics problem 1
orl   58
N Mar 13, 2025 by HamstPan38825
Source: IMO ShortList 2002, combinatorics problem 1
Let $n$ be a positive integer. Each point $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers with $x+y<n$, is coloured red or blue, subject to the following condition: if a point $(x,y)$ is red, then so are all points $(x',y')$ with $x'\leq x$ and $y'\leq y$. Let $A$ be the number of ways to choose $n$ blue points with distinct $x$-coordinates, and let $B$ be the number of ways to choose $n$ blue points with distinct $y$-coordinates. Prove that $A=B$.
58 replies
orl
Sep 28, 2004
HamstPan38825
Mar 13, 2025
IMO ShortList 2002, combinatorics problem 1
G H J
G H BBookmark kLocked kLocked NReply
Source: IMO ShortList 2002, combinatorics problem 1
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
orl
3647 posts
#1 • 7 Y
Y by Amir Hossein, mssmath, Davi-8191, AopsUser101, Adventure10, megarnie, Mango247
Let $n$ be a positive integer. Each point $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers with $x+y<n$, is coloured red or blue, subject to the following condition: if a point $(x,y)$ is red, then so are all points $(x',y')$ with $x'\leq x$ and $y'\leq y$. Let $A$ be the number of ways to choose $n$ blue points with distinct $x$-coordinates, and let $B$ be the number of ways to choose $n$ blue points with distinct $y$-coordinates. Prove that $A=B$.
Attachments:
This post has been edited 4 times. Last edited by orl, Sep 27, 2005, 4:57 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
orl
3647 posts
#2 • 4 Y
Y by Takeya.O, Adventure10, megarnie, Mango247
Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
grobber
7849 posts
#3 • 16 Y
Y by Amir Hossein, Tawan, arandomperson123, Abdollahpour, HolyMath, Adventure10, megarnie, rayfish, metricpaper, two_steps, Mango247, and 5 other users
This was actually in the contest, wasn't it?

It's kind of hard to put into words. The red points consists of a series of $n$ columns of decreasing height (I mean decreasing starting from left to right, and I don't mean strictly decreasing). The blue points consist of the completion of the red columns up to the border of the triangle having vertices $(0,0),(0,n-1),(n-1,0)$. At the same time, the blue and red sets can also be regarded as rows instead of columns.

$A$ is simply the product of the lengths of all blue columns, while $B$ is the product of the lengths of all blue rows. If we show that the same numbers, with the same multiplicities, appear in the collections of a) blue column lengths and b) blue row lengths, then we are clearly done. Call this assertion $(*)$.

The blue set can be regarded as the union of some maximal right triangles with the legs parallel to the axes of the plane (maximal in the sense that they aren't part of any other similar right triangles). The triangles are obtained as follows: from a point on the diagonal $x+y=n-1$ go down as far as you can without taking any red points. Now go to the right until you meet the diagonal again. The maximal triangles of this set are the ones we're looking for.

We can now prove the assertion $(*)$ by induction on $n$.

If there are points on the diagonal $x+y=n-1$ which are red, then it's easy to see that the number of blue columns of length $0$ is equal to the number of blue rows of length $0$, and we can look at the picture as the union of some smaller pictures (for smaller $n$'s), by breaking the diagonal where it has red points. We use the induction hypothesis on these smaller pictures.

On the other hand, if no points on $x+y=n-1$ are red, then we can look at the points strictly below the diagonal $x+y=n-1$, and use the induction hypothesis on these. After we append the diagonal $x+y=n-1$ all lengths (of blue columns and rows) increase by $1$, so we have shown what we wanted: the number of blue columns of length $t$ is the same as the number of blue rows of length $t$ for all $0\le t\le n$.

Watch out: I might have reversed "red" and "blue" in some places. :)
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
cyshine
236 posts
#4 • 3 Y
Y by Tawan, Adventure10, Mango247
Yes, this problem was on the IMO.

I did a bijection: assign to all lattice blue points on the line $x + y = n - k$ the number $k$. Let $n_k$ the number of blue points labeled with number $k$. Let $M$ be the maximum $k$ such that $n_k > 0$. Then $A$, as well as $B$, is equal to the product of $n$ numbers: $n_k$, $n_{k-1}-n_k$, $\ldots$, $n_1-n_2$ (draw a diagram and do the number assignment to see why).
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
aznlord1337
130 posts
#5 • 4 Y
Y by Amir Hossein, Tawan, paragdey01, Adventure10
If $ n=4$, construct the set of points like this (or for any other $ n$).
$ (3,0) (2,1) (1,2) (0,3)$
$ (2,0) (1,1) (0,2)$
$ (1,0)  (0,1)$
$ (0,0)$

Let $ C(n)$ be the number of blue points in column $ n$, and $ D(n)$ be the number of blue points in diagonal $ n$ (starting from the diagonal that cuts through only the top left point). It is clear that the number of ways to choose an x coordinate is $ C(1)C(2)...C(n)$.



Call a coloring good if $ C(1),C(2),...C(n)$ is a permutation of $ D(1), D(2)...D(n)$. It is clear that a good coloring would satisfy the problem conditions. Obviously for $ n=1$ any coloring is good. Suppose for some $ n$ any coloring is good.

To construct the set $ x+y<n+1$, attach the row of points $ (n,0)...(0,n)$ above the set $ x+y<n$. For example,
$ (3,0) (2,1) (1,2) (0,3)$
$ (2,0) (1,1) (0,2)$
$ (1,0)  (0,1)$
$ (0,0)$

is constructed by adding points $ (3,0)...(0,3)$ above the set $ x+y<4$. Since any coloring of $ x+y<n$ is good, constructing $ x+y<n+1$ adds $ 1$ to each column and diagonal so it is also good. Now suppose we color a point red in the row $ (n,0)...(0,n)$. But coloring $ (a,n-a)$ is equivalent to coloring $ (a, n-a-1), (a-1,n-a-1)$ and $ (a,n-a)$ red. Note that the first two points lie within $ x+y<n$, which remains good. However, by coloring $ (a,n-a)$, $ C(a)$ and $ D(n-a)$ are $ 0$. Therefore, removing that point does not affect the goodness of $ x+y<n+1$. This completes the induction, and since all colorings are good, $ A=B$.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
huang
83 posts
#6 • 2 Y
Y by Adventure10, Mango247
Wait... I think my solution is correct, but thinking I got it in 5 minutes makes me think otherwise.

You create a bijection. Suppose you have a configuration where the points $ B_{1}$, ..., $ B_{k}$ are blue and the points $ R_{1},...,R_{l}$ are red. Then you just switch the $ y$ coordinate by the $ x$ coordinate in each point. It's easy to see that all the points that were in the original line $ x+y=n$ are in the transformed line ($ x+y=y+x$) and the red points still meet the conditions $ x'\leq x$ and $ y'\leq y$, but now the blue points have distinct $ y$ coordinates instead of distinct $ x$ coordinates.

Its trivial proving that this transformation is equivalent to rotating the plane $ 90$ degrees counter-clockwise and then reflecting it over the $ y$-axis. Finally, since each of the planes with blue points having distinct $ x$ coordinates each correspond to exactly one plane with distinct blue $ y$ coordinates, and also each plane having blue points with distinct $ y$ coordinates corresponds to a plane having blue points with distinct $ x$ coordinates (for this case just perform the reverse transformation), then we can easily conclude that $ A=B$.

I agree with grobber... it IS hard to put into words, but I hope it's clear enough.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
hrithikguy
1791 posts
#7 • 1 Y
Y by Adventure10
Call P a critical point if it is red and there are no red points above or to the right of it. Call Q, the set of points P, "x-good" if it leads to a configuration where all the blue points have distinct x coordinates. Let Q' be the set of points P with their x and y coordinate points switched. Therefore, Q' is "y-good", where "y-good" is analogously defined. Since this is a bijection, QED.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yugrey
2326 posts
#8 • 2 Y
Y by Adventure10, Mango247
I thought of the bijection solution, but we can also use recursion by seeing what happens if add a row, right?

If we take the n+1 by n+1, take out the bottom row, and assume the result for n, we get that for n+1, if the bottom row has k blue squares, the number of ways to choose distinct vertical blue points gets multiplied by k and the number of ways to choose distinct horizontal blue points gets multiplied by (2/1)...(k/(k-1))=k.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
confusedhexagon
71 posts
#9 • 2 Y
Y by Adventure10, Mango247
Don't mean to spam or anything, but isn't this too easy even for IMO P1?
Just drawing a neat figure makes the bijection pretty obvious!
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
yugrey
2326 posts
#10 • 2 Y
Y by Adventure10, Mango247
Confusedhexagon, it's pretty easy for an IMO P1, but then again people weren't as smart ten years ago. :P Also remember that in the early days of the IMO, there was not much combinatorics at all.

Just find a down-left-ward pointing corner of the blue and then the bijection does follow.

I found that solution, but also I found this other solution that I posted...

Will anyone tell me if it is correct?

I really want to know this lol.
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
tchebytchev
584 posts
#11 • 1 Y
Y by Adventure10
Let $A(p,.)$ be red point with $p$ maximal, $B(.q)$ be the point with $q$ maximal among red point. ($A$ and $B$ can be equal).
Point $C(h,k)$ is blue iff $h>p$ or $k>q$. To choose $n$ blue points with distinct $x-$ coordinates $\{(0,k_0),...,(n-1,k_{n-1})\}$ it necessarily that : \[n>k_0>q, n-1>k_1>q,...,n-p>k_p>q\] and \[k_{p+1}<n-(p+1),...,k_{n-1}<n-(n-1)\] which gives a number (if it is not equal to zero i.e $p+q$ not large enough) of possible configurations \[\prod_{i=1}^{p+1}(n-i-q)\prod_{i=p+1}^{n-1}(n-i)=\frac{(n-(q+1))!(n-(p+1))!}{(n-p-q-2)!}\]
This is symmetric with respect to $p$ and $q$ so it is also equal to the number of configurations with distinct $y-$ coordinates.
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
#12 • 4 Y
Y by Abdollahpour, Adventure10, Mango247, and 1 other user
Ok....
Hard to put in words.........

Still I'll give it my best shot.


Let $a_i$ denote the number of blue points with coordinate $x_i$
and $b_i$ denote the number of blue points with coordinate $y_i$

Now we have to prove $\prod_{i=0}^{n-1}a_i=\prod_{i=0}^{n-1}b_i$

Let $(x_i,y_i)$ denote the rightmost red point of the form $(k,y_i)$
Observe that $x_i \ge x_{i+1}$
Then quite easily, the number of blue points of the form $(x_i,a)$ is $(n+1-x_i-y_i)$ (since $x+y \le n$, the above lines)

Thus $\prod_{i=0}^{n-1}a_i= \prod_{i=0}^{n-1}(n+1-x_i-y_i)$

The same result is true when we replace $x_i$ by $y_i$
That is,
$\prod_{i=0}^{n-1}b_i= \prod_{i=0}^{n-1}(n+1-x_i-y_i)$

$\implies \prod_{i=0}^{n-1}a_i=\prod_{i=0}^{n-1}b_i$
$\implies A=B$
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
math_pi_rate
1218 posts
#13 • 2 Y
Y by Adventure10, Mango247
Solution (possibly flawed)

EDIT (26 Jan 2020): This solution seems incorrect to me now that I read it. It might be possible that I am missing something which I had in mind while writing this solution, but in any case this is a really badly written solution. I'll try to correct this later if I get time :)
This post has been edited 1 time. Last edited by math_pi_rate, Jan 26, 2020, 7:01 AM
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
#14 • 4 Y
Y by v4913, Mattthebat2569, Adventure10, Jack_w
Let $a_x$ denote the number of blue points with a given $x$-coordinate, and define $b_y$ similarly.

We actually claim that

Claim: The multisets $\mathcal A \overset{\text{def}}{=} \{ a_x \mid x \}$ and $\mathcal B \overset{\text{def}}{=} \{ b_y \mid y \}$ are equal.

Proof. By induction on the number of red points. If there are no red points, then $\mathcal A = \mathcal B = \{1, \dots, n\}$. Now suppose we color one point $P = (x,y)$ red. Before the coloring, we have $a_x = b_y = n-(x+y)$; afterwards $a_x = b_y = n-(x+y)-1$ and no other numbers change, as desired. Since every permissible set of red points can be built inductively this way (indeed it's a Young tableaux!) this implies the result. $\blacksquare$

Finally, \[ A = \prod_{x=0}^{n-1} a_x = \prod_{y=0}^{n-1} b_y = B. \]
This post has been edited 2 times. Last edited by v_Enhance, Apr 8, 2019, 8:04 PM
Z K Y
The post below has been deleted. Click to close.
This post has been deleted. Click here to see post.
anantmudgal09
1979 posts
#15 • 2 Y
Y by Adventure10, Mango247
orl wrote:
Let $n$ be a positive integer. Each point $(x,y)$ in the plane, where $x$ and $y$ are non-negative integers with $x+y<n$, is coloured red or blue, subject to the following condition: if a point $(x,y)$ is red, then so are all points $(x',y')$ with $x'\leq x$ and $y'\leq y$. Let $A$ be the number of ways to choose $n$ blue points with distinct $x$-coordinates, and let $B$ be the number of ways to choose $n$ blue points with distinct $y$-coordinates. Prove that $A=B$.

Notice that the red points form a "staircase". For each $0 \le i, j <n$, let $x_i$ denote the number of blue points with $x$ coordinate $i$ and $y_j$ denote the number of blue points with $y$ coordinate $j$. We need to show that $\prod^{n-1}_{i=0} x_i = \prod^{n-1}_{j=0} y_j$, to conclude.

We induct on the number of red points. If there is none; we're done. Otherwise, any time a red point is added, it must be added to the North-East of an "L" vertex of the staircase, to increase the number of red points by $1$. Then, suppose $(a, b)$ was now marked red; except $x_a$ and $y_b$, none of the $x_i$'s or the $y_j$'s change. Also, $x_a \mapsto x_a-1$ and $y_b \mapsto y_b-1$ but $x_a=y_b$, if $(a, b)$ was added to the NE neighbor of an "L" vertex, anyway, so we're done.
Z K Y
G
H
=
a