Есть белая клетчатая полоска 1×58. Какое наименьшее число клеток можно закрасить, чтобы у любой клетки (в том числе закрашенной) была хотя бы одна соседняя клетка закрашена?

Для решения задачи о том, сколько клеток нужно закрасить в белой клетчатой полоске 1×58, чтобы у каждой клетки (включая закрашенные) была хотя бы одна соседняя закрашенная клетка, можно воспользоваться стратегией «закрашивания через одну клетку».

Если мы закрасим каждую вторую клетку, то у нас получится следующая схема:

• Закрашиваем клетки с номерами 1, 3, 5, 7, ..., 57.

Таким образом, у нас будут закрашены 29 клеток (так как 58 делится на 2, и закрашенные клетки будут на позициях всех нечётных чисел).

Такой подход гарантирует, что каждая закрашенная клетка имеет по соседству другую закрашенную клетку (например, клетка 1 будет соседней с клеткой 3), а для белых клеток также найдется хотя бы одна соседняя закрашенная клетка (например, клетка 2 будет соседней с клеткой 1).

Таким образом, наименьшее число клеток, которое нужно закрасить, составляет 29.