Задача 8.14
Умова:В одній з аудиторій сидять 20 учасників олімпіади. Відомо, що серед будь-яких десяти з них є три однокласники.
Чи вірно, що в аудиторії обов'язково є 5 осіб з одного класу?
Чи вірно, що в аудиторії обов'язково є 5 осіб з одного класу?
Я ЗНАЮ ОТВЕТ
Подсказка будет доступна через
Подсказка
Подсказка: Потрібно виділити максимальне можливе число трійок однокласників, що не перетинаються між собою 
Посмотреть ответ можно через:
Посмотреть ответ
Ответ: Вірно
Я ОШИБСЯ
Я РЕШИЛ ВЕРНО
Посмотреть решение
Решение:
Пронумеруємо учасників олімпіади, що сидять у нашій аудиторії, числами від 1 до 20. Розглянемо десятеро людей 1, 2, ..., 10. Серед цих десяти людей знайдуться троє, які навчаються в одному класі. Без обмеження спільності можемо вважати, що це люди 1, 2, 3. Нехай це буде трійка I.
Розглянемо тепер людей 4, 5, ..., 13. Серед них теж знайдуться троє однокласників. Будемо вважати, що це люди 4, 5, 6. Назвемо цю трійку II. Аналогічно можемо знайти трійку однокласників III, що складається з людей 7, 8, 9, і трійку IV, що складається з людей 10, 11, 12.
Припустимо, знайдеться ще одна трійка однокласників V, що не перетинається з попередніми. Будемо вважати, що до неї входять люди 13, 14, 15. Виберемо по дві людини з кожної трійки, наприклад 1, 2, 4, 5, 7, 8, 10, 11, 13, 14. Якісь троє з них виявляться однокласниками.
При цьому знайдуться двоє людей з різних трійок, які є однокласниками. Нехай це будуть учні 1 і 4. Тоді всі шість учнів 1, 2, 3, 4, 5, 6 навчаються в одному класі. Таким чином, знайшлися навіть не п'ять, а шість однокласників.
Припустимо тепер, що трійку V, що не перетинається з першими чотирма, вибрати не можна. Тоді розглянемо десять чоловік: 1, 4, 7, 10, 13, 14, 15, 16, 17, 18 (ми вибрали по одній людині з кожної трійки і ще шість учнів, що не увійшли до жодної трійки). Якісь троє з цих осіб - однокласники.
Якщо в цій трійці немає жодної людини з 1, 4, 7, 10, то ми знайшли трійку однокласників, що перетинається з раніше вибраними чотирма.
Це суперечить нашим припущенням. Якщо однокласниками виявилися якісь двоє учнів з трійок I, II, III, IV, наприклад, 1 і 4, то знову однокласниками виявиться шість чоловік: 1, 2, 3, 4, 5, 6.
Таким чином, залишився єдиний варіант: до нової трійки увійшли двоє учнів , які не входили до трійок I, II, III, IV, і один, який входив до однієї з них. Нехай це будуть люди 13, 14, 1. Тоді п'ять учнів 1, 2, 3, 13, 14 - однокласники.
Таким чином, ми показали, що завжди знайдуться п'ять учнів з одного класу.
Пронумеруємо учасників олімпіади, що сидять у нашій аудиторії, числами від 1 до 20. Розглянемо десятеро людей 1, 2, ..., 10. Серед цих десяти людей знайдуться троє, які навчаються в одному класі. Без обмеження спільності можемо вважати, що це люди 1, 2, 3. Нехай це буде трійка I.
Розглянемо тепер людей 4, 5, ..., 13. Серед них теж знайдуться троє однокласників. Будемо вважати, що це люди 4, 5, 6. Назвемо цю трійку II. Аналогічно можемо знайти трійку однокласників III, що складається з людей 7, 8, 9, і трійку IV, що складається з людей 10, 11, 12.
Припустимо, знайдеться ще одна трійка однокласників V, що не перетинається з попередніми. Будемо вважати, що до неї входять люди 13, 14, 15. Виберемо по дві людини з кожної трійки, наприклад 1, 2, 4, 5, 7, 8, 10, 11, 13, 14. Якісь троє з них виявляться однокласниками.
При цьому знайдуться двоє людей з різних трійок, які є однокласниками. Нехай це будуть учні 1 і 4. Тоді всі шість учнів 1, 2, 3, 4, 5, 6 навчаються в одному класі. Таким чином, знайшлися навіть не п'ять, а шість однокласників.
Припустимо тепер, що трійку V, що не перетинається з першими чотирма, вибрати не можна. Тоді розглянемо десять чоловік: 1, 4, 7, 10, 13, 14, 15, 16, 17, 18 (ми вибрали по одній людині з кожної трійки і ще шість учнів, що не увійшли до жодної трійки). Якісь троє з цих осіб - однокласники.
Якщо в цій трійці немає жодної людини з 1, 4, 7, 10, то ми знайшли трійку однокласників, що перетинається з раніше вибраними чотирма.
Це суперечить нашим припущенням. Якщо однокласниками виявилися якісь двоє учнів з трійок I, II, III, IV, наприклад, 1 і 4, то знову однокласниками виявиться шість чоловік: 1, 2, 3, 4, 5, 6.
Таким чином, залишився єдиний варіант: до нової трійки увійшли двоє учнів , які не входили до трійок I, II, III, IV, і один, який входив до однієї з них. Нехай це будуть люди 13, 14, 1. Тоді п'ять учнів 1, 2, 3, 13, 14 - однокласники.
Таким чином, ми показали, що завжди знайдуться п'ять учнів з одного класу.
