Азия-тынық мұхит математикалық олимпиадасы, 2017 жыл

$n$ — натурал сан болсын. Егер әрқайсысы $n$ бүтін саннан тұратын $(a_1,\ldots,a_n)$ және $(b_1,\ldots,b_n)$ тізбектері $|a_1b_1+\cdots+a_nb_n|\leq 1$ теңсіздігін қанағаттандырса, онда ондай екі тізбек жұбын ерекше деп атайық. Кез келген екеуі ерекше жұп құрайтын $n$ бүтін саннан құралған ең көп дегенде қанша әртүрлі тізбек бар? ( Pakawut Jiradilok, Warut Suksompong )

Комментарий/решение

Считайте $n$-кортежи $n$ векторами $v_1, v_2, \ldots, v_n$ в $n$-пространстве (с целочисленными компонентами). Наш ответ: $n^2 + n + 1$. Конструкция проста.

Лемма: Учитывая $2n+1$ ненулевых векторов в $n$-пространстве, некоторые два из них имеют положительное скалярное произведение.

Доказательство: эти векторы не обязательно должны иметь целые или рациональные компоненты. Базовый случай $n = 1$ тривиален. Теперь, что касается индуктивного шага, предположим, что это верно для некоторого $n = k-1$. Тогда предположим, что у нас есть $2k+1$ векторов $v_1, \ldots , v_{2k+1}$ в $k$-пространстве. Поверните так, чтобы $v_1$ стал перпендикулярным плоскости $x_1 = 0$ и был направлен положительно. Тогда, поскольку все остальные векторы образуют неположительные скалярные произведения с $v_1$, они находятся «под» или на плоскости $x_1 = 0$; то есть в области $x_1\leq 0$. Спроецируйте оставшиеся не менее $2k$ векторов $v_i$ на плоскость $v_i'$ - если один из них $-v_1$, то удалите его. Все остальные оставшиеся (не менее $2k-1$) векторы подлежат рассмотрению. По индуктивной гипотезе два из них имеют отрицательное скалярное произведение. Поскольку координаты $x_1$ этих двух координат неположительны, их произведение неотрицательно, поэтому эти две координаты в исходном $k$-пространстве действительно имеют положительное скалярное произведение.

ХОРОШО. Далее, если у нас есть $> n^2 + n + 1$ векторов, у нас есть $> n^2 - n$ ненулевые или неосевые векторы. Должна существовать координата с более чем $2(n^2 - n)/n = 2n-2$ ненулевыми экземплярами, скажем $\geq 2n-1$. Отмените необходимое количество этих $2n-1$ векторов, чтобы все координаты $x_j$ стали положительными. Проецируя на плоскость $x_j$, мы имеем $2n-1$ векторов в $n-1$ пространстве, и, следовательно, двое из них имеют положительное скалярное произведение $\geq 1$. Поскольку обе компоненты $x_j$ у них положительны, для некоторых двух векторов со скалярным произведением $\geq 2$ оно снова должно быть $\geq 1$, что плохо.