Условие
В клетках таблицы 3×3 записаны числа. За один ход разрешается прибавить 1 ко всем трём числам какой-либо одной строки или какого-либо одного столбца. а) Можно ли из таблицы, заполненной нулями, получить таблицу со строками 2, 3, 1; 4, 5, 3; 3, 4, 2? б) Можно ли из таблицы, заполненной нулями, получить таблицу со строками 1, 0, 2; 2, 1, 3; 0, 2, 1? в) В таблице записаны строки 3, 1, 4; 5, 3, 6; 2, 0, 3. За какое наименьшее число ходов можно добиться того, чтобы все девять чисел таблицы стали равными?
Подсказка
Зависит ли итоговая таблица от порядка ходов? Что прибавилось к числу на пересечении i-й строки и j-го столбца?
Найдите комбинацию четырёх клеток (две строки, два столбца), которая не меняется ни при одном ходе.
Показать ответ
а) да, например к строкам 0, 2 и 1 раз, к столбцам 2, 3 и 1 раз; б) нет; в) 9
Пошаговое решение
- Описываем результат ходов
Порядок ходов не важен: если к i-й строке прибавили 1 ровно rᵢ раз, а к j-му столбцу — cⱼ раз, то к числу в клетке (i; j) прибавилось rᵢ + cⱼ.
- Пункт а: пример
Возьмём r = (0; 2; 1) и c = (2; 3; 1): первая строка 0 + 2, 0 + 3, 0 + 1 = 2, 3, 1; вторая 4, 5, 3; третья 3, 4, 2. То есть дважды прибавляем ко второй строке, один раз к третьей, дважды к первому столбцу, трижды ко второму и один раз к третьему — 9 ходов. Ответ — да.
- Пункт б: инвариант
Рассмотрим величину x = a₁₁ + a₃₂ − a₁₂ − a₃₁ (клетки на пересечении строк 1, 3 и столбцов 1, 2). Ход по строке 1 увеличивает a₁₁ и a₁₂ — x не меняется; по строке 3 — a₃₂ и a₃₁; по столбцу 1 — a₁₁ и a₃₁; по столбцу 2 — a₁₂ и a₃₂; остальные ходы этих клеток не касаются. Вначале x = 0, а в нужной таблице x = 1 + 2 − 0 − 0 = 3. Получить её нельзя, ответ — нет (сумма 12 делится на 3, так что проверка одной суммы здесь ничего не даёт).
- Пункт в: оценка
Каждый ход увеличивает сумму чисел на 3, а числа никогда не уменьшаются. Вначале сумма 3 + 1 + 4 + 5 + 3 + 6 + 2 + 0 + 3 = 27 и есть число 6, поэтому общее значение M в конце не меньше 6, а сумма 9M ≥ 54. Ходов не меньше (54 − 27) : 3 = 9.
- Пункт в: пример и типичная ошибка
Прибавим 2 раза к первой строке и 3 раза к третьей: все строки станут 5, 3, 6. Затем 1 раз к первому столбцу и 3 раза ко второму: все числа равны 6. Всего 2 + 3 + 1 + 3 = 9 ходов. Типичная ошибка — пытаться уравнять числа на уровне меньше 6, хотя числа только растут.
Ответ: а) да, например к строкам 0, 2 и 1 раз, к столбцам 2, 3 и 1 раз; б) нет; в) 9
Критерии оценивания (4 балла)
- 4
- Верно получены все четыре результата: указаны ходы, дающие таблицу п. а; доказательство через инвариант a₁₁ + a₃₂ − a₁₂ − a₃₁ (или равенство разностей строк), что таблицу п. б получить нельзя; оценка «не меньше 9 ходов» через рост суммы на 3 и M ≥ 6 (п. в); пример из 9 ходов (п. в).
- 3
- Верно получены три результата из четырёх: например, пункты а и б и пример из 9 ходов, но не доказано, что меньшим числом ходов обойтись нельзя.
- 2
- Верно получены два результата из четырёх: например, верно решены пункты а и б, а в п. в нет ни обоснованной оценки, ни верного примера.
- 1
- Верно получен один результат из четырёх: например, только пример ходов для п. а или только доказательство невозможности в п. б.
- 0
- Не выполнены условия начисления баллов по этой учебной рубрике.