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

orl

#1 h Sep 28, 2004, 1:31 PM • 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

orl

#2 h Sep 28, 2004, 1:32 PM • 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

grobber

#3 h Sep 29, 2004, 3:14 AM • 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

cyshine

#4 h Sep 29, 2004, 3:46 PM • 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

aznlord1337

#5 h Apr 18, 2009, 7:33 PM • 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

huang

#6 h Jul 1, 2009, 9:48 PM • 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

hrithikguy

#7 h Sep 30, 2011, 5:39 AM • 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

yugrey

#8 h Sep 12, 2012, 5:11 PM • 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

confusedhexagon

#9 h Sep 12, 2012, 8:22 PM • 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

yugrey

#10 h Sep 12, 2012, 11:44 PM • 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.

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

tchebytchev

#11 h Jan 13, 2014, 12:35 PM • 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

utkarshgupta

#12 h Nov 4, 2014, 4:45 PM • 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

math_pi_rate

#13 h Nov 11, 2018, 1:51 PM • 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

v_Enhance

#14 h Apr 8, 2019, 8:04 PM • 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

anantmudgal09

#15 h May 19, 2019, 6:46 PM • 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

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MagicalToaster53

159 posts

MagicalToaster53

#46 h Oct 23, 2023, 2:47 PM

Y by

What do you mean? As in we may have used blue instead of red?

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Tintarn

9022 posts

Tintarn

#47 h Oct 23, 2023, 2:49 PM

Y by

No. I mean that the reds can lie in a more complicated configuration than the ones covered by your cases (they do not need to form a "complete triangle").

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

EpicBird08

1730 posts

EpicBird08

#48 h Oct 23, 2023, 5:15 PM

Y by

omg i actually solved a combo. marabot solve btw

We further claim that the number of blue points of each $x$ coordinate is the same as the number of blue coordinates of each $y$ coordinate up to permutation. We will prove this using strong induction on $n,$ with the base case $n = 1$ being fairly obvious.

Now assume that the result is true for $n = 1, 2, \dots, k.$ There are 2 cases:

Case 1: There are no blue points on the line $x + y = k - 1.$ Then just shift one to the left and apply the inductive hypothesis; this does not affect the ordering of the blue points.

Case 2: There is some blue point on the line $x + y = k - 1.$ Then this blue point separates the red and blue points into two halves, and apply the inductive hypothesis on each half.

Therefore, we have finished the induction. As a result, multiplying all of the number of blue points of each $x$ coordinate will yield the same result with the $y$ coordinates, so $A = B,$ as desired.

This post has been edited 1 time. Last edited by EpicBird08, Oct 23, 2023, 5:17 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Quidditch

815 posts

Quidditch

#49 h Oct 25, 2023, 3:22 AM • 1 Y

Y by NathanBikeSki

huashiliao2020 wrote:

Let $a_k,b_k$ be the number of blue points with x (resp. y) coordinates k; we'll prove that $A=\prod a_k=\prod b_k=B$ by showing the sequence b is a permutation of the sequence a using strong induction, with base case n=1 trivial, so assume now the inductive hypotheses, and for convenience let $\iff$ denote permutation of each other. If all points on the line x+y=n are blue, we're done since $\forall1\le k\le n-1$ , $a_k\iff b_k$ due to inductive hypothesis and just adding 1 for every point (since there's an extra blue point now on every horizontal/vertical line). However, if some point (m,n-m) is red, then $a_m=0=b_m$ , meaning A=0=B. We conclude. :surf:

Remark. Looking at the extremal line x+y=n is well motivated by induction.

Just want to point out that the induction is not complete because your induction’s hypothesis is that the the sequence $a$ is a permutation of $b$ . However, in the end of your solution, you only show that $A=B=0$ . Fortunately, this is not very hard to fix.

This post has been edited 2 times. Last edited by Quidditch, Oct 25, 2023, 3:24 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

MagicalToaster53

159 posts

MagicalToaster53

#51 h Oct 27, 2023, 9:13 PM

Y by

Let $c_x$ and $d_y$ denote the number of blue points of column $x$ and row $y$ , respectively. Let $(x, y)$ be red with $x + y = n - k$ , with $k > 1$ .

We prove by strong induction that $A = \prod c_x = \prod d_y = B$ . The base case with $x + y = 2$ is trivial. Assume now that $A = B$ for all $x + y = 2, 3, \ldots, n - 2$ . Adding in the (new) blue line $x + y = n - 1$ turns the product
$\begin{align*} c_0c_1 \cdots c_{n - 2} &= d_0d_1 \cdots d_{n - 2} \\ \implies (1)(c_0 + 1)(c_1 + 1) \cdots (c_{n - 2} + 1)(1) &= (1)(d_0 + 1)(d_1 + 1) \cdots (d_{n - 2} + 1)(1), \end{align*}$ so that $A' = B'$ . $\blacksquare$
Remark

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

ryanbear

1055 posts

ryanbear

#52 h Nov 30, 2023, 8:58 PM

Y by

first combo ISL (probably fakesolve)

Attachments:

This post has been edited 4 times. Last edited by ryanbear, Dec 19, 2023, 4:26 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

shendrew7

787 posts

shendrew7

#53 h Jan 7, 2024, 5:28 AM

Y by

Define $a_c$ as the number of blue points with $x$ -coordinate $c$ , and $b_c$ as the number of blue points with $y$ -coordinate $c$ . We claim the stronger statement that $\{a_i\}$ and $\{b_i\}$ are permutations of each other through induction on $n$ , with trivial base case $n=2$ .

Assuming that $n=k$ satisfies the condition, we claim that adding the $k+1$ points on the line $x+y=k$ to prove the case $n=k+1$ , as
$(a_0+1) \cdot \ldots \cdot (a_k+1) \cdot 1 = (b_0+1) \cdot \ldots \cdot (b_k+1) \cdot 1.$
Now we just need to consider the cases where the added line contains a red point $(m, k-m)$ , which can be handled by noting a configuration where we can add the desired red point such that no other red points are forced. This just changes the pair $(a_m, b_{k-m}) = (1,1)$ to $(0,0)$ , as desired. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

dolphinday

1310 posts

dolphinday

#54 h Mar 11, 2024, 8:33 PM

Y by

We will do induction on $n$ with our base cases of $n = 1$ and $n = 2$ being true. We can do induction by adding in the set of points on the line $x + y = n$ from which our total set of points becomes $x + y < n + 1$ .
If $x_k$ is the number of blue points on row $k$ and $x_y$ is the number of blue points on column $k$ , the problem is equivalent to showing that the set $\{x_1, x_2, \dots, x_n\} = \{y_1, y_2, \dots, y_n\}$ .
If after adding in the points on $x + y = n$ we don't add any extra red points on the new line, we have $\{x_1 + 1, x_2 + 1, \dots, x_n + 1, 1\} = \{y_1 + 1, y_2 + 1, \dots, y_n + 1, 1\}$ . If we do add an extra red point on the line $x + y = n$ then we don't have to add any other new points since it is equivalent to just adding the one red point in a different configuration(where no new red points would be added). Clearly the sets $x_i$ and $y_i$ are equal since we are just changing one of the variables in each set from $1$ to $0$ , and we are done by the induction hypothesis.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Aaryabhatta1

1631 posts

Aaryabhatta1

#55 h Mar 18, 2024, 4:53 AM

Y by

Let $r_i, c_i$ be the number of blue points in each row and column. It satisfies to prove multisets $\{r_i\} = \{c_i\}$ as $A = \prod r_i = \prod c_i = B.$ We prove this by induction. The base case of $n = 1$ is trivial.

Assume for $n = k$ and consider $n = k+1.$ Observe that for $T' \subset T$ bounded by $x + y < k$ with row/column blue values $r'_i, c'_i$ , by induction $\{r_i'\} = \{c_i'\}.$ Now for each point $x + y = k$ , if $(x-1, y)$ or $(x, y-1)$ were blue, then $(x,y)$ must be blue. So the corresponding $r'_i, c'_i$ are incremented by $1$ to get $r_i, c_i$ . Otherwise, if both (or only 1 for edges) are red, the new point can be red or blue. In the former, the corresponding $r_i = c_i = 0.$ In the latter, $r_i = c_i = 1.$ Either way, the inductive step is complete as the multisets $\{r_i\} = \{c_i\}$ (since non-zero terms increment and zero terms have preserved equality).

This post has been edited 2 times. Last edited by Aaryabhatta1, Mar 18, 2024, 4:54 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

PEKKA

1835 posts

PEKKA

#56 h Jul 6, 2024, 12:48 AM

Y by

The only thing I can do is induct :skull:
First of all, we define $A_k$ and $B_k$ to the the number of $x$ sets and $y$ sets respectively, when the restraint is $x+y<k.$
Next, define $X(i)$ and $Y(i)$ to be the number of points with $x$ and $y$ coordinate $i$ respectively that are blue, plus one.
This means $A_k=\prod_{i=0}^{k-1}X(i)$ and $B_k=\prod_{i=0}^{k-1}Y(i).$
Now we claim that $A_k=B_k$ all the time, over all $k.$
Base Case (k=1)
This is simple as the only point that we care about is (0,0) and it is either red or blue, making $A_k=B_k=0$ and $A_k=B_k=1$ respectively.
Inductive Step
Actually, we will use strong induction so assume the inductive hypothesis holds for $n\le k.$
Now when $n=k+1,$ we have the set of points with $x+y\le k, x,y \in \mathbb{Z}^{+}$
We define the "biggest" red point (called $B_r$ ) as the red point with the largest sum of coordinates. If there are multiple "biggest" red points, picking any will suffice. Let $Q(p)$ be the function that sums a point's coordinates.
We are presented with two cases.
Case 1: $Q(B_r)<k$
Then ignore the points with a coordinate sum higher than $B_r.$ this is just a case from the inductive hypothesis. Now the points with coordinate sum higher than $B_r$ contribute $k-Q(B_r)$ to each $X(i)$ and $Y(i)$ term, so equality is preserved. This case is complete
Case 2 $Q(B_r)=k$ .
Then draw the rectangle with opposite points $(0,0)$ and $B_r$ with sides perpendicular to the axes.
Color the rectangle red because we can by the problem statement.
Now, we are left with two smaller isosceles right triangles. These right triangles are just the inductive hypothesis that underwent translation along the axes. Furthermore, since the functions counting $A$ and $B$ are multiplicative, we can just multiply together the two equations representing equality for the two small isosceles right triangles we just made. Therefore, this case is complete.
Since we addressed all the cases, 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.

ezpotd

1245 posts

ezpotd

#57 h Aug 24, 2024, 8:37 PM

Y by

We instead interpret this is on a $n$ by $n$ grid, where we are to choose blue squares from $n$ columns and $n$ rows, and no red or blue point square can be beyond the main diagonal. Clearly all red squares in a column are consecutive starting at the lower boundary. Now let $a_i$ be the number of red squares in the $i$ th column, clearly $a_i$ is nonincreasing by the condition, otherwise we would have some blue square that lies to the left of a red square, likewise, we see that all nonincreasing sequences indeed correspond to some working coloring. Now induct on $\sum a_i$ . The base case of $\sum a_i = 1$ is obvious by symmetry, its just $a_1 =1$ . Now we show we can always remove a square from a nondecreasing $a$ to get another working $a$ , of course this is just doable by decrementing $a_j$ where $j$ is the last index associated with a positive number of squares. Since we can achieve every working coloring via this method, it suffices to show that the factor by which the number of distinct-row sets of $n$ blue squares changes by applying this operation is equal to the factor of change for distinct-column sets of $n$ blue squares, and we can then rely on the inductive hypothesis to finish. Let $a_y$ originally be $x$ , where $y$ is the column we removed the square from. Then the change in distinct column sets is just $\frac{n - y - x }{n - y - x - 1}$ , since we just went from $n - y - x - 1$ options to $n - y - x$ options for that column, and no other columns changed. An identical argument on row $x$ finishes.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Maximilian113

490 posts

Maximilian113

#58 h Nov 29, 2024, 10:44 PM

Y by

We show this by induction. The base case, $n=1,$ is trivial by casework. Now, assume that our proposition holds for $n=k$ where $k$ is some positive integer. Then consider our grid when $n=k+1.$ Clearly, we are essentially adding another line below the grid for $n=k.$ On this row, let the number of blue points be $m.$ Then clearly the first $k+1-m$ points are red. By our inductive hypothesis, the product of the number of blue points in the first $k$ rows divided by the product of the number of blue points in the first $k$ columns is $1.$ By adding the new row, the product of the number of blue points in the rows is increased by a factor of $m.$ Meanwhile, in each of the last $m$ columns, it is clear that the number of blue points in column $i$ (where $1 \leq i \leq m$ ) is increased by $\frac{i+1}{i}.$ Thus, $\frac{A}{B} = 1 \cdot (m+1) \cdot \frac{1}{2} \cdot \frac23 \cdot \cdots \cdot \frac{m}{m+1} = 1$ by telescoping, so our induction is complete. QED

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

joshualiu315

#59 h Dec 3, 2024, 2:44 AM

Y by

Let $x_i$ and $y_i$ be the number of blue points in the rows and columns. We will prove a stronger claim that the multisets $\{x_i\}$ and $\{y_i\}$ are equal, which obviously proves the desired statement. We prove this with induction on $n$ .

The base case of $n = 1$ is vacuous; suppose the inductive hypothesis holds for $n = k$ . Consider each of the points $(x,y)$ on the line $x+y = k$ . If $(x-1, y)$ or $(x, y-1)$ were blue, then $(x,y)$ must be blue. Hence, the corresponding $x_i, y_i$ are increased by $1$ . If both $(x-1, y)$ or $(x, y-1)$ were red instead, then $(x,y)$ could either be red or blue, and we get $x_i =y_i = 0$ or $x_i = y_i = 1$ for the corresponding $x_i, y_i$ . Either way, we see that the resulting multisets $\{x_i\}$ and $\{y_i\}$ are equal, completing the induction. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

AshAuktober

917 posts

AshAuktober

#60 h Dec 20, 2024, 10:37 AM

Y by

Gonna sketch this one.
We call a red point a boundary point if there exists no other red point with both coordinates at least that of this point. Then changing the color of a boundary point leaves $\frac{A}{B}$ invariant.
Further, any configuration having a red point has a boundary point, due to finiteness. Thus we keep removing boundary points until we reach the configuration with all points blue, for which $A = B$ is obvious by symmetry.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

HamstPan38825

8846 posts

HamstPan38825

#61 h Mar 13, 2025, 10:29 PM

Y by

Let $A_n = A$ and $B_n = B$ for the $x+y < n$ grid. We will prove the result by induction on $n$ ; it is easy to check the base cases, and we will assume $A_{n-1} = B_{n-1}$ . Furthermore, let $x_k$ be the number of blue points in the column $x = k$ , and define $y_k$ similarly, such that $A_n = \prod x_i$ and $B_n = \prod y_i$ .

Call a column very blue if all the points in that column are blue; the set of very blue columns then consists of $x \geq k$ where $k \leq n$ is a positive integer. (If $k = n$ , then $A_n = 0 = B_n$ is vacuous.) Observe that since $x_i$ is unchanged for $i < k$ and $x_i = i$ for $i \geq k$ , we have $A_{n-1} = A_n \cdot \frac 12\cdot \frac 23 \cdots \frac{k-1}k = \frac{A_n}k$ and clearly $B_{n-1} =\tfrac{B_n}k$ as there are $k$ points in the row $y = 0$ , so the equality $A_n = B_n$ follows, which completes the induction.

Z K Y