>>319

〔補題1〕
r_i ≧ 0 のとき、実対称行列 min｛r_i，r_j｝は半正値。
(略証）
0 = r_0 ≦ r_1 ≦ r_2 ≦ …… ≦ r_n としてよい。
　Σ[i，j］min｛r_i，r_j｝x_i x_j = Σ[i=1，n］r_i（(x_i)^2 + 2Σ[j=i+1,n] x_i x_j）
　= Σ[i=1，n］r_i（(Σ[j=i，n］x_j)^2 -（Σ[j=i+1，n］x_j)^2）
　= Σ[i=1，n]（r_i - r_{i-1}）（Σ[j=i，n］x_j)^2
　≧ 0,

〔補題2〕
min｛a_i b_j，a_j b_i｝- min｛a_i a_j，b_i b_j｝= min｛r_i，r_j｝x_i x_j

ここに、
　r_i = max｛a_i/b_i，b_i/a_i｝
　x_i = sgn(a_i-b_i）min｛a_i，b_i｝
とおいた。（証明略）

これらを使うと解けるらしいよ。

USAMO-2000 Problem_6

http://artofproblemsolving.com/wiki/index.php?title=2000_USAMO