В клетчатом квадрате 8×8 закрашено 25 клеток, образующих квадрат
5×5. Разрешается выбрать любую клетку квадрата 8×8 и спросить,
закрашена ли она. За какое наименьшее число таких вопросов можно
наверняка определить, какие клетки закрашены?
Нужно доказать что кол-во вопросов, которое вы найдёте наименьшее и привести пример и умляю
Изначально у нас есть клетчатый квадрат размером 8×8. Закрашено 25 клеток, образующих квадрат 5×5. Мы хотим найти наименьшее число вопросов, которое нам необходимо задать, чтобы определить, какие клетки закрашены.
Первым шагом разделим наш исходный квадрат на 4 равных квадрата. Таким образом, каждый квадрат будет иметь размер 4×4. Теперь нам нужно определить, в каком из этих квадратов находятся закрашенные клетки.
Зададим первый вопрос: "Закрашены ли клетки в квадрате в верхнем левом углу?" Если ответ "да", то мы уже знаем, что закрашены 16 клеток, образующих квадрат 4×4, и можем перейти к следующему шагу. Если ответ "нет", то мы точно знаем, что эти клетки не закрашены, и пропускаем следующий шаг.
Далее разделим найденный закрашенный квадрат 4×4 на 4 равных квадрата 2×2. Опять же, мы задаем вопросы о закрашенности клеток в каждом из этих квадратов. Если ответ "да", то мы знаем, что закрашены 4 клетки, образующие квадрат 2×2, и переходим к следующему шагу. Если ответ "нет", то мы точно знаем, что эти клетки не закрашены, и пропускаем следующий шаг.
На последнем шаге мы разделяем найденный закрашенный квадрат 2×2 на 4 одиночные клетки 1×1. Снова задаем вопросы о закрашенности каждой клетки. Если ответ "да", то мы знаем, что закрашена 1 клетка, и задавать дополнительные вопросы уже не нужно. Если ответ "нет", то мы точно знаем, что эта клетка не закрашена.
Таким образом, мы задали вопросы о закрашенности клеток в четырех квадратах размером 4×4, в каждом из которых нашли закрашенные клетки, затем в каждом из этих квадратов задали вопросы о закрашенности клеток в четырех квадратах размером 2×2, где также нашли закрашенные клетки, и, наконец, в каждой из этих четырех клеток задали вопросы о закрашенности каждой из клеток размером 1×1.
В результате, наименьшее число вопросов, которое нам необходимо задать, чтобы наверняка определить, какие клетки закрашены, равно количеству квадратов, в которые мы разделили исходный квадрат. В нашем случае это 4 + 4 + 1 = 9 вопросов.
Примером такой схемы решения задачи может быть следующий:
Пусть A, B, C, D, E, F, G, H обозначают некоторые клетки квадрата 8×8. Закрашенные клетки обозначим буквой Z, пустые клетки - буквой O. Как и ранее, разделим квадрат на 4 равных квадрата, затем на 4 квадрата и, наконец, настроим вопросы в каждой клетке второго разбиения.
Исходный квадрат:
O O O O O O O O
O O O O O O O O
O O O O O O O O
O O O Z Z Z O O
O O O Z Z Z O O
O O O Z Z Z O O
O O O O O O O O
O O O O O O O O
Разделение на 4 квадрата каждый размером 4×4:
O O O O | O O O O | O O O O | O O O O
O O O O | O O O O | O O O O | O O O O
O O O O | O O O O | O O O O | O O O O
O O O O | O O O O | Z Z Z O | O O O O
------------------------------------
O O O O | O O O O | Z Z Z O | O O O O
O O O O | O O