YaoAOPS wrote:

Unfortunately, the only charitable thing you can give the AI is that it found the construction.

R9182 wrote:

We now explain briefly why no doubly stochastic matrix can yield a larger value of $\frac{R}{C}$ . At the heart of the matter is the trade–off already discussed. If one tries to increase some row’s maximum beyond $\frac{1}{45}$ , then (since the sum of its row is 1) one must concentrate even more mass in a single entry. But then the column that “carries” that mass will have its maximum raised. In our construction the choice of “heavy” columns has been optimized: by “packing” exactly 45 large entries of size $1/45$ in each such column, we guarantee that each heavy column carries the minimal possible maximum to serve 45 rows. (A short optimization shows that if one designates $k$ columns to serve as the targets for high entries and distributes the mass evenly among them so that every heavy row gets exactly $1/r$ in the column it uses, then one may obtain a ratio of
$\frac{n}{\,k+r-1}\,,$ with the constraint $k\cdot r=n$ . This expression is maximized when $k=r=\sqrt{n}$ ; in our case $\sqrt{2025}=45$ , and the maximum value is exactly
$\frac{2025}{45+45-1}=\frac{2025}{89}\,.$ )

A more “dual” formulation of the problem (via linear programming duality) leads to the same optimum. We omit the details for brevity.

This is nonsensical and does not go into actually proving the bound.

R9182 wrote:

A careful (and somewhat lengthy) verification shows that one may indeed “patch” the matrix so that all the doubly stochastic constraints are met. (There are several ways to complete the construction; one may view the process as “gluing” together an extreme point of the Birkhoff–von Neumann polytope on a $45\times45$ block with the “flat” matrix on the remaining cells.)

Throwing the words Birkhoff–von Neumann around in a doubly stochastic matrix problem does not actually prove anything other than looking impressive.

R9182 wrote:

- If we partition the $2025$ rows into $k$ groups (with equal size, say) and have each group’s rows use a distinct column for their row–maximum, then in any column which is so chosen the column sum constraint forces the common maximum to be equal to the reciprocal of the group’s size.
- At the same time, by “filling in” the remaining cells very uniformly the maximum of every other column may be made as low as possible.

This is a highly nontrivial step and most of the problem's difficulty lies in proving this. Showing that these maximums are equal is also nontrivial.

Oh, thanks for the detailed analysis of the AI's attempt at this problem. It seems that AI is still far from actually being able to solve problems of this kind. I see what you're saying — it skipped the highly non-trivial and important steps without providing any proof.