,
on the circle, where 
are not collinear. Let 
be the circumcircle of triangle 
.
intersect 
,
.
be a circle through 
be points on 
be points such that 
for 
. Prove that as 
moves the circumcircle 
passes through fixed point.
be a triangle with circumcircle 
.
and 
intersect at 
.
intersects the line 
at 
and 
is the midpoint of 
.
and 
intersect on 
,
,
,
be distinct circles such that 
,
,
,![\[
\frac{AB\cdot BC}{AD\cdot DC}=\frac{PB^2}{PD^2}.
\]](http://latex.artofproblemsolving.com/0/4/e/04ead9928d0c767a2209f610885e30f6b6e0a4e9.png)
Y by Rounak_iitr, cubres
Let 
be a fixed integer. The cells of an 
table are filled with the integers from 
to 
with each number appearing exactly once. Let 
be the number of unordered quadruples of cells on this board which form an axis-aligned rectangle, with the two smaller integers being on opposite vertices of this rectangle. Find the largest possible value of .
Anonymous
be a fixed integer. The cells of an 
table are filled with the integers from 
to 
with each number appearing exactly once. Let 
be the number of unordered quadruples of cells on this board which form an axis-aligned rectangle, with the two smaller integers being on opposite vertices of this rectangle. Find the largest possible value of .Anonymous
This post has been edited 1 time. Last edited by tapir1729, Jun 24, 2024, 9:36 PM
![[asy]
for (int i = 0; i < 6; ++i) {
draw((0,i)--(5,i));
draw((i,0)--(i,5));
}
label("1",(0.5,0.5));
label("2",(1.5,1.5));
label("3",(2.5,2.5));
label("4",(3.5,3.5));
label("5",(4.5,4.5));
label("6",(0.5,1.5));
label("7",(1.5,2.5));
label("8",(2.5,3.5));
label("9",(3.5,4.5));
label("10",(4.5,0.5));
label("11",(0.5,2.5));
label("12",(1.5,3.5));
label("13",(2.5,4.5));
label("14",(3.5,0.5));
label("15",(4.5,1.5));
label("16",(0.5,3.5));
label("17",(1.5,4.5));
label("18",(2.5,0.5));
label("19",(3.5,1.5));
label("20",(4.5,2.5));
label("21",(0.5,4.5));
label("22",(1.5,0.5));
label("23",(2.5,1.5));
label("24",(3.5,2.5));
label("25",(4.5,3.5));
[/asy]](http://latex.artofproblemsolving.com/3/0/b/30b236f23db8add606b9d14b08a093575ed61518.png)
![[asy]
for (int i = 0; i < 6; ++i) {
draw((0,i)--(5,i));
draw((i,0)--(i,5));
}
label("1",(0.5,0.5));
label("1",(1.5,1.5));
label("1",(2.5,2.5));
label("1",(3.5,3.5));
label("1",(4.5,4.5));
label("2",(0.5,1.5));
label("2",(1.5,2.5));
label("2",(2.5,3.5));
label("2",(3.5,4.5));
label("2",(4.5,0.5));
label("3",(0.5,2.5));
label("3",(1.5,3.5));
label("3",(2.5,4.5));
label("3",(3.5,0.5));
label("3",(4.5,1.5));
label("4",(0.5,3.5));
label("4",(1.5,4.5));
label("4",(2.5,0.5));
label("4",(3.5,1.5));
label("4",(4.5,2.5));
label("5",(0.5,4.5));
label("5",(1.5,0.5));
label("5",(2.5,1.5));
label("5",(3.5,2.5));
label("5",(4.5,3.5));
[/asy]](http://latex.artofproblemsolving.com/9/0/a/90a01a338dd1ebcc3b279b1eea20a6e56e878244.png)
in the grid, let 
denote the number of cells in its column smaller than it, and 
be the number of cells in its row smaller than it.
for 
is exactly 
times. (Consider the relative ordering of numbers within each column.) The same is true for 
for all 
(This is why equality holds in our maximum construction.)
Then there are 
nondesired rectangles.
as desired. 
if its two smallest integers are on opposite vertices.
be the number of ordered triples of distinct squares 
such that 
are in the same row, 
are in the same column, the the number in 
of its 
sets of three consecutive vertices correspond to valid triples. For each non-good rectangle, exactly 
for any 
,
So by the rearrangement inequality, 
This is constructed by just labeling the diagonals in order.
.
is twice the number of bad rectangles.
,
minus "row-indegree". Let 
and 
denote the row and column indegrees of cell 
for 
,
and the quantity we're counting is 
.
(actually these expressions are equal lmao), which by rearrangement is 
(achieved when 
)
and the number of good rectangles is at most 
minus this or 
achieved by diagonal type construction; that is, 
in center diagonal 
in the following diagonal and continue in similar fashion.
denote the number of cells in row 
less than 
and similarly we define 
for columns. Define 
to be three cells 
such that 
is neither in increasing or decreasing order, we count the number of 
,
which is clearly maximized when all 
which gives the same answer as desired.
to 
respectively.
Summing over all possible 
for all rows is obviously 
As we want to maximize the sum of all 
by the rearrangement inequality we have that the maximum is when all 
which is 
Therefore by subtracting 
from 
our answer is 
Construction is just having the smallest 
,
denote the coloumn indegree and 
denote the row indegree, and let ![\[\sum_{i\in C}(n-f(i)-1)g(i)+(n-g(i)-1)f(i)\]](http://latex.artofproblemsolving.com/e/d/6/ed605c3255c384c0aab712126e662809fd03f580.png)
Which by rearrangement inequality is minimsed when 
,
rectangles.
such that 
and 
share a row, 
and 
.
pivots.
,
the number of cells in the same row as 
to be the same number for the column. The number of pivots is given by the sum of 
across all cells ![\[\{a_{i1}, a_{i2}, \dots, a_{in}\} = \{0, 1, 2, \dots, n-1\} = \{b_{i1}, b_{i2}, \dots, b_{in}\}\]](http://latex.artofproblemsolving.com/a/3/5/a35279da5fe3413491c1c95cb13180cad8d4201f.png)
so by the Rearrangement inequality,![\[\sum_{j=1}^n a_{in}b_{in} \leq \sum_{j=1}^n j^2 = \frac 16n(n-1)(2n-1).\]](http://latex.artofproblemsolving.com/7/7/5/7759668136754920088d4e2eb5b6bfbdfa237dbd.png)
Summing across all columns yields the result. 
rectangles that satisfy the condition. Then among the vertices of each of these 
remaining rectangles, we can find precisely one pivot. If there are 
as required.
;
case as an illustration:![\[\begin{tabular}{ccccc}
1 & 6 & 11 & 16 & 21 \\
22 & 2 & 7 & 12 & 17 \\
18 & 23 & 3 & 8 & 13 \\
14 & 19& 24 & 4 & 9 \\
10 & 15 & 20 & 25 & 5
\end{tabular}\]](http://latex.artofproblemsolving.com/6/b/3/6b31077b5352c3a4e32b2d768c9c5fde07592fed.png)
