Question

3. Петрик відмітив на колі 20 жовтих та 20 синіх точок. Після цього Василь з’єднує відрізками точки одного кольору так, щоб ці відрізки не мали спільних точок. Яку найбільшу кількість відрізків зможе гарантовано провести Василь, як би ці точки не розставив по колу Петрик? Відповідь обґрунтуйте.

Answer 1

При розставленні 20 жовтих та 20 синіх точок на колі, Василь може гарантовано провести 10 відрізків, які не мають спільних точок. Це можна обґрунтувати за допомогою принципу Дирихле.

Принцип Дирихле

Принцип Дирихле, також відомий як принцип ящиків або принцип піжонів, стверджує, що якщо n+1 об'єктів розміщені в n контейнерах, то принаймні один контейнер міститиме два або більше об'єкти.

В даному випадку, ми маємо 40 точок (20 жовтих і 20 синіх) і 20 відрізків, які можна провести між ними. Оскільки кожен відрізок може з'єднувати лише дві точки, ми можемо розглядати ці відрізки як контейнери, а точки - як об'єкти.

Застосовуючи принцип Дирихле, ми можемо сказати, що якщо ми розташуємо 40 точок у 20 відрізках, то принаймні один відрізок міститиме дві або більше точок. Отже, Василь може гарантовано провести принаймні 10 відрізків, які не мають спільних точок.

Це є найбільша кількість відрізків, яку Василь може гарантовано провести, незалежно від того, як він розставить точки по колу.