Физтех 2026/27 · Математика · 10 кл., №6 — решение · Отборочный этап

Условие

Сколькими способами можно заполнить клетки таблицы $4\times4$ нулями и единицами так, чтобы в каждой строке и в каждом столбце сумма чисел была чётной?

О задаче · 10 класс

Олимпиада: Физтех (МФТИ)
Этап: Отборочный этап, второй тур (2 попытка, 01.11.2026)
Предмет / класс: Математика · 10 класс
Сезон: 2026/27

Начни с маленьких таблиц: сколько правильных заполнений у таблицы $2 \times 2$ У таблицы $3 \times 3$ Какие клетки можно выбрать как угодно, а какие потом уже определены? В модели клади монеты (единицы) на доску и следи за суммами справа и снизу. Ниже можно сверить ответ.

Записать идею

Личный черновик для заметок и расчётов. Он никуда не отправляется и не проверяется.

Исследуй задачу

Самостоятельное исследованиеДоска с монетами

Пробуй свои варианты. Разбор останется закрытым.

Исследуй задачу

Доска с монетами

Сколько клеток можно выбрать свободно, чтобы все суммы строк и столбцов были чётными?

Если модель не открылась (выключен JavaScript или страница загрузилась не полностью), условие, подсказки и разбор доступны и без неё.

Подсказка для решения без модели

Если модель не открылась, попробуй так. Нарисуй таблицу 4×4, впиши нули и единицы в верхний левый угол 3×3 как угодно и допиши последнюю строку и последний столбец так, чтобы все суммы стали чётными. Получилось ли это без противоречия в углу?

Подсказка 1

Попробуй заполнить таблицы $2 \times 2$ и $3 \times 3$ Если в строке уже стоят все числа, кроме последнего, — можно ли выбрать последнее? Сколько клеток на самом деле выбираются свободно, а сколько «достраиваются»?

Подсказка 2

Свободно заполняется только угол $3 \times 3$ Последняя клетка каждой из первых трёх строк и каждого из первых трёх столбцов определяется чётностью. Остаётся угловая клетка: её требуют и последняя строка, и последний столбец — почему они требуют одно и то же?

Разобрать решение по шагам

Последний столбец определяется строками

Заполним как угодно верхний левый угол $3 \times 3$ (первые три строки и первые три столбца). Посмотрим на первую строку: три её числа уже стоят. Если их сумма чётная, четвёртым числом обязан быть $0$ если нечётная — $1$ другого выбора нет, иначе сумма строки станет нечётной. Так же однозначно определяется последнее число второй и третьей строк. Значит, три верхние клетки последнего столбца достраиваются, а не выбираются.

Последняя строка определяется столбцами

Точно так же с первыми тремя столбцами: в каждом из них уже стоят три числа из угла $3 \times 3$ и четвёртое (в последней строке) обязано сделать сумму столбца чётной. Итак, все клетки последней строки и последнего столбца, кроме угловой, определены однозначно.

Угловая клетка подходит и строке, и столбцу

Осталась клетка в правом нижнем углу. Последняя строка требует, чтобы сумма $r$ трёх уже стоящих в ней чисел вместе с угловой была чётной; последний столбец требует того же для суммы $c$ трёх его чисел. Опасность в том, что эти требования могут противоречить друг другу. Покажем, что $r$ и $c$ одной чётности.

Обозначим через $A$ сумму чисел угла $3 \times 3$ Первые три строки целиком чётные, поэтому их общая сумма $A + c$ чётна. Первые три столбца целиком чётные, поэтому $A + r$ чётна. Значит, $r$ и $c$ имеют ту же чётность, что и $A$ — то есть одинаковую. Угловая клетка одна и та же для строки и столбца: $0$ если $A$ чётно, и $1$ если нечётно.

Угол

3 \times 3

выбирается как угодно —

2^9 = 512

способов. Жёлтые клетки достраиваются по чётности своей строки или столбца; угловой (оранжевой) клетке и строка, и столбец назначают одно и то же — здесь

1

Подсчёт

Каждое заполнение угла $3 \times 3$ достраивается ровно до одной подходящей таблицы, и разные заполнения угла дают разные таблицы (угол в них разный). Обратно, у любой подходящей таблицы угол $3 \times 3$ — какое-то заполнение. Поэтому способов столько же, сколько заполнений угла: у каждой из $9$ клеток $2$ варианта,

2^{9} = 512.

Для таблицы $n \times n$ так же получается $2^{(n-1)^2}$

Проверка

Маленькие случаи: таблица $2 \times 2$ — свободна одна клетка, способов $2^1 = 2$ (все нули или все единицы) ✓; $3 \times 3$ — $2^4 = 16$ Тест правила перебирает все $2^{16} = 65\,536$ таблиц $4 \times 4$ и находит ровно $512$ подходящих; для каждого заполнения угла проверено, что угловая клетка по строке и по столбцу совпадает. Другие официальные версии: ID 6378 — таблица $5 \times 5$ $2^{16} = 65\,536$ ID 6379 — $6 \times 6$ $2^{25} = 33\,554\,432$ ID 6380 — $7 \times 7$ $2^{36} = 68\,719\,476\,736$ .

Ответ

$512$

Ответ

$512$

Главная идея

Угол (n − 1)×(n − 1) заполняется свободно, остальное достраивается по чётности, и угловая клетка согласована: сумма всех чисел, посчитанная по строкам и по столбцам, одна и та же. Ответ 2^((n−1)²).

Условия чётности на все строки и столбцы — ищи, сколько клеток «свободны», а сколько определяются остальными; проверь, не противоречат ли друг другу последние условия.

Где легко ошибиться

Считать, что свободна часть 3×4 или 4×3 (получится 2¹² — слишком много), или вычесть из 2¹⁶ «плохие» таблицы и запутаться; забыть проверить, что угловая клетка подходит одновременно строке и столбцу.

Источник и авторство

Олимпиада «Физтех» · математика · 10 класс · 2026/27 · отборочный этап, второй тур (2 попытка, 01.11.2026). Задача 6, версия с ID 6377 — первая в официальном файле; другие версии этого номера (ID 6378, 6379, 6380) можно выбрать в модели.

Официальные условия (PDF организатора, стр. 5) ↗ · Указания к решению от организатора ↗ · Архив заданий олимпиады ↗

Условие — из официального файла организатора. Подсказки, решение и модель — Popov Academy. Авторское решение записано до сверки с указаниями организатора; затем ответ совпадает с ответом организатора («Указания к решению: математика, 10 класс, 2 попытка 2026/27», стр. 4 ↗: ID 6377: 512; ID 6378: 65536; ID 6379: 33554432; ID 6380: 68719476736.). Сверены все четыре официальные версии этого номера. Таблица официальных ответов была прочитана при разборе входных данных до собственного решения; указания к решению не открывались.

Продолжить тему: Подсчёт вариантов →

Тема, знания и приёмы

Подсчёт вариантов · Нужна школьная база

Правило произведения в комбинаторике
Чётность суммы

Приёмы решения: Последовательный подсчёт без повторов · Инвариант или монотонная величина

Задать вопрос по задаче →