Loading [MathJax]/jax/output/SVG/jax.js

Азиатско-Тихоокеанская математическая олимпиада, 2017 год


Пусть n — натуральное число. Пару n-ок целых чисел (a1,,an) и (b1,,bn) назовем исключительной, если |a1b1++anbn|1. Найдите наибольшее возможное количество попарно различных n-ок целых чисел, любые две из которых образуют исключительную пару. ( Pakawut Jiradilok, Warut Suksompong )
посмотреть в олимпиаде

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

  10
1 года 2 месяца назад #

Считайте n-кортежи n векторами v1,v2,,vn в n-пространстве (с целочисленными компонентами). Наш ответ: n2+n+1. Конструкция проста.

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

Доказательство: эти векторы не обязательно должны иметь целые или рациональные компоненты. Базовый случай n=1 тривиален. Теперь, что касается индуктивного шага, предположим, что это верно для некоторого n=k1. Тогда предположим, что у нас есть 2k+1 векторов v1,,v2k+1 в k-пространстве. Поверните так, чтобы v1 стал перпендикулярным плоскости x1=0 и был направлен положительно. Тогда, поскольку все остальные векторы образуют неположительные скалярные произведения с v1, они находятся «под» или на плоскости x1=0; то есть в области x10. Спроецируйте оставшиеся не менее 2k векторов vi на плоскость vi - если один из них v1, то удалите его. Все остальные оставшиеся (не менее 2k1) векторы подлежат рассмотрению. По индуктивной гипотезе два из них имеют отрицательное скалярное произведение. Поскольку координаты x1 этих двух координат неположительны, их произведение неотрицательно, поэтому эти две координаты в исходном k-пространстве действительно имеют положительное скалярное произведение.

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