Разделы 
Дополнительно
Задача по математике - 3668
2019-06-15 
а) Двое играют в такую игру. Первый записывает один под другим два ряда по 10 чисел так, чтобы выполнялось следующее правило: если число $b$ записано под числом $a$, а число $d$ - под числом $c$, то $a + d = b + c$. Второй игрок, зная это правило, хочет определить все написанные числа. Ему разрешается задавать первому игроку вопросы типа «Какое число стоит в первой строке на третьем месте?» или «Какое число стоит во второй строке на девятом месте?» и т. п. За какое наименьшее число таких вопросов второй игрок сможет узнать все числа?
б) В таблице $m \times n$ записаны числа так, что для любых двух строк и любых двух столбцов сумма чисел в двух противоположных вершинах образуемого ими прямоугольника равна сумме чисел в двух других его вершинах. Часть чисел стерли, но по оставшимся можно восстановить стертые. Докажите, что осталось не меньше чем $m + n - 1$ чисел.
Решение:
а) Узнав все 10 чисел в одной строке и одно - в другой, легко восстановить и все остальные числа. Если же задать лишь 10 вопросов, то однозначно восстановить числа нельзя; с одной стороны, в каждом столбце нужно знать хотя бы одно число - иначе можно прибавлять к обоим числам в этом столбце произвольное число $х$, сохраняя нужное свойство таблицы; с другой стороны, хотя бы в одном столбце надо узнать оба числа - иначе можно взять произвольное число $у$ как разность между числами в каждом столбца и по имеющимся данным построить таблицу.
Ответ: 11 вопросов.
б) Доказательство можно провести индукцией. Будем считать, что $n \geq m$, и вести индукцию по $m + n$. Если в одном из $n$ столбцов неизвестно ни одно из чисел, то, очевидно, числа восстанавливаются неоднозначно. Если же в каждом из $n$ столбцов есть известные числа, то (поскольку общее число $m + n - 2$ известных чисел не больше $2n - 2$) найдется столбец, где известно лишь одно число, а оставшаяся после вычеркивания этого столбца таблица $(n - 1 )m$ содержит лишь $m + (n - 1) - 2$ известных числа и по предположению индукции восстанавливается неоднозначно.
Оценка в этой задаче точна: таблицу вида
(*)
можно восстановить по $m + n - 1$ числам первой строки и первого столбца.
Ответ на более тонкий вопрос - какие именно наборы $Г$ чисел таблицы $m \times n$ для этого подходят - можно сформулировать на языке теории графов.
Рассмотрим «двудольный граф» $Г$ с $m + n$ вершинами $A_1, \cdots, A_m$ и $B_1, \cdots, B_n$, в котором некоторые вершины $A_i$ соединены с некоторыми $B_j$ тем самым указано некоторое множество $Г$ пар $(i, j)$ - элементов таблицы $m \times n$ ($i = 1, 2, \cdots m; j = 1, 2, \cdots n)$. Для того чтобы по такому набору $Г$ пар чисел однозначно восстанавливалась вся таблица, необходимо и достаточно, чтобы граф $Г$ был связен. В дереве с $m + n$ вершинами согласно задаче 8 будет как раз $m + n - 1$ ребер; если $Г$ - дерево, то любой набор $m + n - 1$ чисел, занимающих клетки $(i, j) \in Г$, можно дополнить так, что полученная таблица будет иметь нужный вид (*).
а) Двое играют в такую игру. Первый записывает один под другим два ряда по 10 чисел так, чтобы выполнялось следующее правило: если число $b$ записано под числом $a$, а число $d$ - под числом $c$, то $a + d = b + c$. Второй игрок, зная это правило, хочет определить все написанные числа. Ему разрешается задавать первому игроку вопросы типа «Какое число стоит в первой строке на третьем месте?» или «Какое число стоит во второй строке на девятом месте?» и т. п. За какое наименьшее число таких вопросов второй игрок сможет узнать все числа?
б) В таблице $m \times n$ записаны числа так, что для любых двух строк и любых двух столбцов сумма чисел в двух противоположных вершинах образуемого ими прямоугольника равна сумме чисел в двух других его вершинах. Часть чисел стерли, но по оставшимся можно восстановить стертые. Докажите, что осталось не меньше чем $m + n - 1$ чисел.
Решение:
а) Узнав все 10 чисел в одной строке и одно - в другой, легко восстановить и все остальные числа. Если же задать лишь 10 вопросов, то однозначно восстановить числа нельзя; с одной стороны, в каждом столбце нужно знать хотя бы одно число - иначе можно прибавлять к обоим числам в этом столбце произвольное число $х$, сохраняя нужное свойство таблицы; с другой стороны, хотя бы в одном столбце надо узнать оба числа - иначе можно взять произвольное число $у$ как разность между числами в каждом столбца и по имеющимся данным построить таблицу.
Ответ: 11 вопросов.
б) Доказательство можно провести индукцией. Будем считать, что $n \geq m$, и вести индукцию по $m + n$. Если в одном из $n$ столбцов неизвестно ни одно из чисел, то, очевидно, числа восстанавливаются неоднозначно. Если же в каждом из $n$ столбцов есть известные числа, то (поскольку общее число $m + n - 2$ известных чисел не больше $2n - 2$) найдется столбец, где известно лишь одно число, а оставшаяся после вычеркивания этого столбца таблица $(n - 1 )m$ содержит лишь $m + (n - 1) - 2$ известных числа и по предположению индукции восстанавливается неоднозначно.
Оценка в этой задаче точна: таблицу вида
(*)
можно восстановить по $m + n - 1$ числам первой строки и первого столбца.
Ответ на более тонкий вопрос - какие именно наборы $Г$ чисел таблицы $m \times n$ для этого подходят - можно сформулировать на языке теории графов.
Рассмотрим «двудольный граф» $Г$ с $m + n$ вершинами $A_1, \cdots, A_m$ и $B_1, \cdots, B_n$, в котором некоторые вершины $A_i$ соединены с некоторыми $B_j$ тем самым указано некоторое множество $Г$ пар $(i, j)$ - элементов таблицы $m \times n$ ($i = 1, 2, \cdots m; j = 1, 2, \cdots n)$. Для того чтобы по такому набору $Г$ пар чисел однозначно восстанавливалась вся таблица, необходимо и достаточно, чтобы граф $Г$ был связен. В дереве с $m + n$ вершинами согласно задаче 8 будет как раз $m + n - 1$ ребер; если $Г$ - дерево, то любой набор $m + n - 1$ чисел, занимающих клетки $(i, j) \in Г$, можно дополнить так, что полученная таблица будет иметь нужный вид (*).
