Back-to-back USAMO and IMO problems in one day!
by shiningsunnyday, Jun 23, 2016, 2:47 PM
1997 IMO P4 wrote:
An
matrix whose entries come from the set
is called a silver matrix if, for each
, the
-th row and the
-th column together contain all elements of
. Show that silver matrices exist for infinitely many values of
.







I claim all powers of two work. For
it's trivial, and for
does the trick. After some experimenting,
works with
(made by Interm CP)
Note how
Similarly, the bottom-left
matrix is the same except with the
being replaced by a 
With a same idea, let's induct on
with the assumption that we can find a
silver matrix. We construct a
by first inserting the
on the upper-left and bottom-right quarters. The upper-right
matrix consists of
being added to each entry of the original
matrix. Finally, the bottom-left is identical to the upper-right matrix, except with every
term replaced by a
term.
Because row
and column
already consists of
(by the inductive hypothesis), the upper right and bottom left matrices will consist of
This however, excludes
which can be easily fixed by replacing each
in the bottom left matrix with
For example, this algorithm renders us the following
silver matrix:
Applying this algorithm, the inductive step is complete.





Note how




With a same idea, let's induct on









Because row









Remark
As with most prove-the-existence-type of problems, experimentation with small cases and construction does the trick.
Tidbit
I solved this right after solving 2002 USAMO P1, which makes me happy (I found them at the end of the induction chapter in Interm CP, the starred problems of which I'm currently going through, in preparation for Combo 3). 
Fun fact: 2002 was the first year the USAMO changed from 3 to 4.5 hours, and qualifiers were invited to MIT to take the exam.

Fun fact: 2002 was the first year the USAMO changed from 3 to 4.5 hours, and qualifiers were invited to MIT to take the exam.

P33 of 101 wrote:
Let
be distinct positive integers. Find the maximum value of
where
is a real number within 




WLOG
which we can clean up a bit by substituting 
We wish to apply
, something of the following nature:
which, unfortunately, doesn't get rid of the
term due to the lack of symmetry. Instead, consider what will happen if we apply
to
Now we're home, since the previous term is the original expression multiplied by
Therefore, the answer is 


![$$\Rightarrow x^n(1-x^{m-n})=[y^n(1-y)^{m-n}]^{\frac{1}{m-n}}.$$](http://latex.artofproblemsolving.com/a/5/9/a59276b1156e186e81a054ecb99dfdbd704562c3.png)




![$$[(m-n)y]^n [n(1-y)]^{m-n} \le \left(\frac{n(m-n)y+n(m-n)(1-y)}{m} \right)^m=\left(\frac{n(m-n))}{m} \right)^m.$$](http://latex.artofproblemsolving.com/b/d/9/bd9ed060dad044996256af8dadb3aa0f1f13c047.png)


Remark
The above beautiful solution is based off of Titu's. I, on the other hand, was lazy and immediately ruined this problem with calculus. 

This post has been edited 1 time. Last edited by shiningsunnyday, Jun 23, 2016, 2:48 PM