Problem 1

Let

n

be a positive integer. Let

T

be the set of points

(x,y)

in the plane where

x

and

y

are non-negative integers with

x+y<n

. Each point of

T

is coloured red or blue, subject to the following condition: if a point

(x,y)

is red, then all points of

T

with first coordinate at most

x

and second coordinate at most

y

are also red. 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

Step 2 of 3: Remove red points one at a time

Previous step Next step

In plain words

Remove red points one at a time

a_x=b_y=n-x-y-1

Detailed analysis

Start with every point blue. Build any lower-left red ideal by changing admissible blue points to red. When $(x,y)$ is changed, exactly $n-x-y-1$ blue points remain in its column and row, so the same count is removed from both multisets. Initially both multisets are $\{1,2,\ldots,n\}$ , hence they remain equal.