На бесконечном листе закрасили 2020 клеток. Докажите, что среди них найдутся 505 закрашенных клеток, не имеющих общих точек.

Предыдущий
вопрос Следующий
вопрос

Предположим противное, то есть все 505 закрашенных клеток имеют хотя бы одну общую точку. Рассмотрим одну из таких клеток и ее общую точку с другой закрашенной клеткой. Таких клеток будет не менее 505, так как каждая из них имеет общую точку с выбранной клеткой.

Теперь рассмотрим еще одну из этих 505 клеток и ее общую точку с другой закрашенной клеткой, не являющейся первой выбранной. Таких клеток с каждой из предыдущих выбранных клеток будет не менее 505 - 1 = 504. Продолжим этот процесс для всех 505 клеток. Общее количество закрашенных клеток с общими точками будет не менее 505 + 504 + ... + 1 = (505 * 506) / 2 = 128015.

Таким образом, суммарное количество закрашенных клеток с общими точками не меньше 128015. Но общее количество закрашенных клеток равно 2020. Поскольку 128015 больше, чем 2020, то возникает противоречие. Значит, среди 505 закрашенных клеток найдутся как минимум две, не имеющие общих точек.