Question

В каждой клетке доски 4х4 стоит целое число от 1 до 16 (каждое по разу). За ход можно указать любой набор клеток и узнать, какие в них числа (без уточнения, какую клетку какое число занимает). Можно ли гарантированно узнать, какие числа где стоят, а) за 4 хода; б) за 3 хода?

Answer 1

A) за три возможно
1. Сначала спрашиваешь какие числа стоят в прямоугольнике (вертикальном) 4*2
2. После какие числа стоят в прямоугольнике (горизонтальном) 2*4
3. После спрашиваешь какие числа стоят в 1 и 3 строках
4. Спрашиваешь какие числа стоят в 1 и 3 столбцах
Расставляешь, и все получается, решение 100% проверяла. Если будет не понятно, могу написать поподробнее.
Б) невозможно, т.к. 16:2:2:2:2=1, т.е. Узнаем какое число в каждой клетке
16:2:2:2=2 узнаем какие числа стоят в двух клетках.
16 - кол-во клеток в квадрате
2 - за 1 ход мы узнаем какие цифры находятся в двух фигурах внутри квадрата (про 1 фигуру спрашиваем; недостающие цифры будут в другой фигуре)

Answer 2

а) Да, за 4 хода можно гарантированно узнать, какие числа где стоят на доске 4х4.

Рассмотрим возможный алгоритм:

Шаг 1: Выберите произвольные 4 клетки на доске и запишите числа, которые они содержат.

Шаг 2: Выберите новый набор из 4 клеток на доске (можно включать уже выбранные в предыдущем шаге) и запишите числа, которые они содержат.

Шаг 3: Повторите шаг 2 ещё два раза, выбирая новые наборы клеток на каждом шаге.

По итогам 4-х шагов у вас будет информация о 16 числах на доске, так как каждое число было учтено хотя бы один раз. Составляя таблицу, вы сможете сопоставить каждое число с его местом на доске.

б) Нет, за 3 хода нельзя гарантированно узнать, какие числа где стоят на доске 4х4.

При трех ходах у вас будет информация о 12 числах на доске, и останется 4 незаполненных клетки. Это недостаточно для однозначного определения расположения всех чисел на доске.