В квадрате 17 ** 17 клеток лежат "в шахматном порядке" алые и белые розы (по одной **...

Question

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

Comments

а есть ответ? у меня получилось 16, но насколько это близко к наименьшему варианту, без понятия.

Answer 1

Ответ:

16 операций

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

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

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

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

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

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

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

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

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

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

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

---

Comments

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

---

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