第5問

n

を正整数とする。整数を成分とする

n

個組

(a_1,\ldots,a_n)

と

(b_1,\ldots,b_n)

の組が「exquisite」であるとは、

|a_1b_1+\cdots+a_nb_n|\le1

が成り立つことをいう。整数を成分とする相異なる

n

個組であって、そのうちどの二つも exquisite な組をなすようなものの最大個数を求めよ。

ステップ 4/5: 最後の非零成分の位置で exquisite な族を分割する

前のステップ次のステップ

A=A_1\cup\cdots\cup A_n,\quad A_i=\{\text{tuples whose last nonzero entry is at position } i\},\quad |A_i|\le2i

詳しい解説

$A$ を、どの二つも exquisite であるような非零の組の集合とする。 $A=A_1\cup A_2\cup\cdots\cup A_n$ と書く。ここで $A_i$ は、 $A$ の中で最後の非零成分が位置 $i$ にある組の集合である。 $2+4+\cdots+2n=n^2+n$ なので、すべての $i$ について $|A_i|\le2i$ を示せば十分であり、零ベクトルと合わせて $|A|+1\le n^2+n+1$ が評価される。