Азиатско-Тихоокеанская математическая олимпиада, 2017 год
Комментарий/решение:
Считайте n-кортежи n векторами v1,v2,…,vn в n-пространстве (с целочисленными компонентами). Наш ответ: n2+n+1. Конструкция проста.
Лемма: Учитывая 2n+1 ненулевых векторов в n-пространстве, некоторые два из них имеют положительное скалярное произведение.
Доказательство: эти векторы не обязательно должны иметь целые или рациональные компоненты. Базовый случай n=1 тривиален. Теперь, что касается индуктивного шага, предположим, что это верно для некоторого n=k−1. Тогда предположим, что у нас есть 2k+1 векторов v1,…,v2k+1 в k-пространстве. Поверните так, чтобы v1 стал перпендикулярным плоскости x1=0 и был направлен положительно. Тогда, поскольку все остальные векторы образуют неположительные скалярные произведения с v1, они находятся «под» или на плоскости x1=0; то есть в области x1≤0. Спроецируйте оставшиеся не менее 2k векторов vi на плоскость v′i - если один из них −v1, то удалите его. Все остальные оставшиеся (не менее 2k−1) векторы подлежат рассмотрению. По индуктивной гипотезе два из них имеют отрицательное скалярное произведение. Поскольку координаты x1 этих двух координат неположительны, их произведение неотрицательно, поэтому эти две координаты в исходном k-пространстве действительно имеют положительное скалярное произведение.
ХОРОШО. Далее, если у нас есть >n2+n+1 векторов, у нас есть >n2−n ненулевые или неосевые векторы. Должна существовать координата с более чем 2(n2−n)/n=2n−2 ненулевыми экземплярами, скажем ≥2n−1. Отмените необходимое количество этих 2n−1 векторов, чтобы все координаты xj стали положительными. Проецируя на плоскость xj, мы имеем 2n−1 векторов в n−1 пространстве, и, следовательно, двое из них имеют положительное скалярное произведение ≥1. Поскольку обе компоненты xj у них положительны, для некоторых двух векторов со скалярным произведением ≥2 оно снова должно быть ≥1, что плохо.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.