Дан клетчатый прямоугольник 5×5, на котором отмечены некоторые клетки. Известно, что любой трёхклеточный уголок на этой доске покрывает хотя бы 2 отмеченные клетки. Какое наименьшее количество клеток может быть отмечено?
x x o o o
x o o o o
o o ? ? ?
o o ? ? ?
o o ? ? ?
Минимальное число клеток, которое мы сможем отметить, удовлетворяя условию, будет равно 8 (при отметке всех угловых клеток):
x x o o o
x o o o o
o o x ? ?
o o ? ? ?
o o ? ? ?
Очевидно, что при таком раскладе минимальное количество клеток, которое можно отметить, будет больше 7.
Теперь рассмотрим случай, когда отмечено 8 клеток:
x x o o o
x o o o o
o o x x ?
o o ? ? ?
o o ? ? ?
Очевидно, что в углоке, сформированном по углу доски, есть только 1 отмеченная клетка, поэтому подобное расположение не подходит, так как нарушает условие задачи.
Проверим случай, когда отмечено 9 клеток:
x x o o o
x o o o o
o o x x ?
o o x ? ?
o o ? ? ?
Теперь все трехклеточные уголки покрывают как минимум 2 отмеченные клетки, поэтому это распределение удовлетворяет условию задачи.
Таким образом, минимальное количество отмеченных клеток, удовлетворяющих условию задачи, равно 9.Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет
Нажимая «Регистрация» или «Войти через Google», вы соглашаетесь с Публичной офертой, даете Согласие на обработку персональных данных, а также подтверждаете что вам есть 18 лет