Question

В квадрате 17 на 17 клеток лежат "в шахматном порядке" алые и белые розы (по одной на клетку). Одной операцией Лида может изменить цвета всех роз в произвольном прямоугольнике, начерченном по линиям клеток, на противоположные. Какое наименьшее количество операций понадобится Лиде, чтобы сделать все розы одноцветными?

Answer 1

Ответ:

16 операций

Пошаговое объяснение:

см. рисунок (алые розы - темные клетки, белые розы - белые клетки)

1) нарисуем квадрат 17х17 и закрасим клетки в шахматном порядке

Для удобства, пронумеруем столбцы и строки

2) в столбцах 16,14,12,10,8,6,4,2 так же поменяем цвета клеток на противоположные

Итого: получилось 9 строк алых роз (темные клетки) и 8 строк белых роз

Сделано 8 операций

3) теперь все строки белых роз (8 шт) превращаем в алые розы

Итого: во всех клетках квадрата лежат алые розы

Сделано 8+8=16 операций

Ответ : 16 операций

Answer 2

Почему невозможно обойтись, затратив меньшее количество операций?

Answer 3

Количество операций зависит от суммы клеток определенного цвета, расположенных в первой строке и первом столбце. Например: у нас в первой строчке и в первом столбце расположены 17 алых роз (темные клетки). Значит, что бы их сделать белыми надо 17 операций. ------------------------------------------- в то же время в первой строке и в первым столбце расположены 16 белых роз (белые клетки). Значит, что бы их сделать алыми, надо 16 операций