Question

На клетчатой доске 8×8 где-то отмечен прямоугольник из трёх клеток. Где — мы не знаем. Мы можем задать Ефиму вопрос про любую из клеток: «Верно ли, что эта клетка принадлежит отмеченному прямоугольнику?» Какое наименьшее количество вопросов нужно задать Ефиму, чтобы гарантированно определить хотя бы одну клетку прямоугольника?

Answer 1

8*8=64(всего клеток)

64-3=61(пустые клетки)

61+1=62(вопроса)

под "1" подразумевается клетка прямоугольника ,которую нужно найти.

Ответ:нужно задать 62 вопроса

Answer 2

Для решения этой задачи нам нужно воспользоваться методом деления и завоевания. Мы можем поделить доску на четыре равные части, каждую размером 4x4. По крайней мере, в одной из этих частей обязательно находится хотя бы одна клетка прямоугольника. Далее, мы делим эту часть доски на еще более мелкие кусочки и таким образом сужаем область поиска, пока не останется только одна клетка.

1. Задаем вопрос для определения, в какой из четырех частей доски находится хотя бы одна клетка прямоугольника. Это требует 1 вопроса.

2. Затем мы выбираем эту часть и делим ее на четыре равные части 2x2.

3. Снова задаем вопрос, чтобы определить, в какой из четырех маленьких частей находится хотя бы одна клетка прямоугольника. Это требует еще 1 вопроса.

4. Выбираем эту маленькую часть и делаем дополнительное разбиение на отдельные клетки.

5. Наконец, задаем вопрос для определения конкретной клетки прямоугольника внутри последней маленькой части. Это требует еще 1 вопроса.

Итак, всего нам потребуется 1 + 1 + 1 = 3 вопроса, чтобы гарантированно определить хотя бы одну клетку прямоугольника.