Question

На аркуші паперу вибрали довільно 100 клітинок. Доведітт, що серед них можна знайти не менше ніж 25 клітинок, які не мають спільних точок. Будь ласка допоможіть

Answer 1

Ответ:

Ми можемо використовувати принцип Дирихле для доведення цього твердження. Принцип Дирихле стверджує, що якщо n об'єктів розміщені в m "контейнерах" (або клітинках), і n > m, то хоча б один контейнер міститиме більше одного об'єкта.

В нашому випадку у нас є 100 клітинок (контейнерів), і ми розміщуємо в них об'єкти (наприклад, точки). Ми хочемо знайти кількість точок (об'єктів), які не мають спільних точок.

Застосуємо принцип Дирихле: якщо ми вибрали 100 точок (об'єктів) і розміщуємо їх в 24 клітинки (контейнери), то хоча б одна клітинка міститиме більше однієї точки (оскільки 100 > 24).

Тепер, якщо хоча б одна клітинка міститиме більше однієї точки, то ці точки не мають спільних точок (вони не можуть бути в одній і тій же клітинці одночасно).

Отже, серед 100 клітинок ми можемо знайти не менше ніж 25 клітинок, які мають неспільні точки.

Объяснение:

Answer 2

Для доведення цього твердження ми можемо скористатися принципом "принаймні одне з двох".

Розглянемо ситуацію, коли всі 100 клітинок мають хоча б одну спільну точку. Це означає, що всі ці клітинки не можуть бути розташовані на аркуші паперу одночасно без перетину.

Тепер давайте розглянемо аркуш паперу, розміром 10x10 клітинок. Якщо всі 100 клітинок мають спільну точку, то кожна клітинка з цих 100 має перетинатися з іншими клітинками. Якщо ми подивимося на будь-яку клітинку, вона має 9 сусідніх клітинок (за винятком клітинок на краях та в кутах). Це означає, що ця клітинка має спільну точку з щонайменше 9 іншими клітинками.

Отже, всі 100 клітинок разом мають спільну точку з щонайменше 100 * 9 = 900 іншими клітинками (оскільки кожна з них має по 9 спільних точок). Однак у нас є лише 100 клітинок на аркуші паперу. Це суперечить тому, що кожна клітинка може мати спільну точку з не більш ніж 100 - 1 = 99 іншими клітинками, оскільки вона не може мати спільну точку сама з собою.

Отже, ми прийшли до протиріччя, що всі 100 клітинок не можуть мати хоча б одну спільну точку одночасно. Це означає, що серед цих 100 клітинок повинні бути принаймні 25 клітинок, які не мають спільних точок.