|
|
 |
Условие
Квадрат $N\times N$ разбит на $N^2$ единичных квадратов. Одна из вершин единичных квадратов радиоактивна. Имеется также прибор, который про любой из этих единичных квадратов определяет, есть ли среди его вершин радиоактивная. Найдите радиоактивную вершину за наименьшее число проверок, если а) $N=7$; б) $N=8$.
Решение
а) Оценка. Вначале имеются 64 подозрительные вершины. Если первые 15 проверок дали отрицательный результат (это возможно), осталось не менее $64 - 15\cdot4 = 4$ подозрительных вершин. Если при 16-й проверке используется квадрат, содержащий не менее двух подозрительных вершин, то при положительном результате этой проверки все они останутся подозрительными. Если же используется квадрат с одной подозрительной вершиной, то при отрицательном результате ещё не менее трёх вершин останутся подозрительными. Значит, 16-ти проверок недостаточно.Алгоритм. Последовательно проверяем 15 синих квадратов (см. рисунок справа). Если одна из проверок даст положительный результат, подозрительными останутся 4 вершины соответствующего квадрата. В следующей проверке используем квадрат, содержащий ровно две из них (при любом исходе останутся две подозрительные вершины), а далее — квадрат, содержащий ровно одну подозрительную вершину.
Если же 15 проверок дадут отрицательный результат, подозрительными остаются только 4 вершины красного квадрата. Аналогично за две оставшиеся проверки находим радиоактивную вершину.
б) Оценка. Разобьём квадрат $8\times8$ на квадраты $2\times2$ и рассмотрим 25 узлов сетки — вершины этих квадратов. Каждый отрицательный результат проверки освобождает от подозрения не более одного из этих узлов. Поэтому после 23 проверок найдутся два подозрительных узла. Значит, 23 проверок недостаточно.
Алгоритм. Последовательно проверяем 16 синих квадратов (см. рисунок справа), затем 6 зелёных. Если хотя бы один результат положителен, то радиоактивная вершина находится за две дополнительные проверки. Если все 22 проверки дают отрицательный результат, проверяем красный квадрат. При положительном результате подозрительными остаются только две его правые вершины (две левые проверены ранее), и одной проверки хватит, чтобы определить радиоактивную.
При отрицательном результате подозрительными остаются только левый верхний и правый нижний углы исходного квадрата. И в этом случае хватит одной дополнительной проверки.
Ответ
а) 17 проверок.
б) 24 проверки.
