MathLabs

第5問

nn を正整数とする。整数を成分とする nn 個組 (a1,…,an)(a_1,\ldots,a_n) と (b1,…,bn)(b_1,\ldots,b_n) の組が「exquisite」であるとは、∣a1b1+⋯+anbn∣≤1|a_1b_1+\cdots+a_nb_n|\le1 が成り立つことをいう。整数を成分とする相異なる nn 個組であって、そのうちどの二つも exquisite な組をなすようなものの最大個数を求めよ。
ステップ 2/5: exquisite の条件を確かめる
at most two coordinates of aibi are nonzero; same pair, opposite signs  ⟹  sum∈{−1,0,1}\text{at most two coordinates of } a_ib_i \text{ are nonzero}; \text{ same pair, opposite signs} \implies \text{sum} \in\{-1,0,1\}
詳しい解説

この一覧の任意の二つの組について、それぞれ非零成分は高々二つなので、積 aibia_ib_i のうち非零になり得るのは高々二つである。二つの積が同時に非零になる唯一の場合は、両方の組が同じ位置の対 i,ji,j に台を持つ場合であり、(1,1)(1,1) と (1,−1)(1,-1) を比較すると内積は 1⋅1+1⋅(−1)=01\cdot1+1\cdot(-1)=0 となる。また単一成分の組や零ベクトルを他の組と組み合わせても、大きさ 11 の非零積が高々一つ寄与するだけである。したがってどの対ごとの内積も {−1,0,1}\{-1,0,1\} に属し、すべての対は exquisite である。