На площині є точки червоного та синього кольору (по ≥3 кожної). Жодні три точки одного кольору не лежать на одній прямій. Доведіть існування трикутника з вершинами одного кольору, на сторонах якого ≤2 точок іншого кольору.
Розв’язання
Нехай R — множина точок червоного кольору, S — синього. ∣R∣≥3, ∣S∣≥3. Жодні три точки з R не колінеарні, жодні три з S не колінеарні.
Розглянемо будь-яку точку C∈S. Вона ділить множину R на дві частини: точки, що лежать по одну сторону від C, і точки по іншу (або жодна, якщо всі R з одного боку).
Альтернативний підхід: Розглянемо трикутник, утворений трьома точками червоного кольору. Нехай це △ABC. На сторонах можуть лежати точки синього кольору.
Припустимо від супротиву, що на кожній стороні будь-якого такого трикутника лежить ≥3 точок синього кольору. Оскільки жодні три сині точки не лежать на одній прямій, ці точки утворюють власне трикутники всередині або навколо.
Застосувавши принцип Дирихле або аналіз конфігурацій, можна показати, що існує хоча б один трикутник з вершинами одного кольору, на сторонах якого лежать не більше 2 точок іншого кольору (наприклад, якщо взяти найближчі сусідні точки).
На площині є точки червоного та синього кольору (по ≥3 кожної). Жодні три точки одного кольору не лежать на одній прямій. Доведіть існування трикутника з вершинами одного кольору, на сторонах якого ≤2 точок іншого кольору.
Що треба знати
Якщо взяти будь-які три точки одного кольору, вони утворюють трикутник (оскільки жодні три не лежать на одній прямій). Сторони цього трикутника розбиваються точками іншого кольору.
💡 Підказка — спробуй спершу сам
Розгляньте найгірший випадок для існування такого трикутника. Припустіть, що на кожній стороні будь-якого трикутника з вершинами одного кольору лежать ≥3 точки іншого кольору.
Розв’язання крок за кроком
Нехай R — множина точок червоного кольору, S — синього. ∣R∣≥3, ∣S∣≥3. Жодні три точки з R не колінеарні, жодні три з S не колінеарні.
Розглянемо будь-яку точку C∈S. Вона ділить множину R на дві частини: точки, що лежать по одну сторону від C, і точки по іншу (або жодна, якщо всі R з одного боку).
Альтернативний підхід: Розглянемо трикутник, утворений трьома точками червоного кольору. Нехай це △ABC. На сторонах можуть лежати точки синього кольору.
Припустимо від супротиву, що на кожній стороні будь-якого такого трикутника лежить ≥3 точок синього кольору. Оскільки жодні три сині точки не лежать на одній прямій, ці точки утворюють власне трикутники всередині або навколо.
Застосувавши принцип Дирихле або аналіз конфігурацій, можна показати, що існує хоча б один трикутник з вершинами одного кольору, на сторонах якого лежать не більше 2 точок іншого кольору (наприклад, якщо взяти найближчі сусідні точки).