Олимпиада имени Леонарда Эйлера 2024-2025 учебный год, I тур дистанционного этапа
Комментарий/решение:
Ответ. 300, 2*300, 3*300,... 33*300.
Решение. Пример: Зn строк (или столбцов) красные, остальные белые, n = 1,2,...,33. Условие делимости на 3 выполнено: если столбец и строка пересекаются по белой клетке, то в их объединении 3n красных клеток, если по красной клетке то 100 + 3n - 1 = 3(n + 33) красных клеток.
Покажем, что других вариантов нет. Рассмотрим 4 клетки, образующие прямоугольник со сторонами, па- раллельными сторонам таблицы. Сложим количества красных клеток в строках и столбцах, содержащих две противоположные вершины прямоугольника, и вычтем количества красных клеток в строках и столбцах, содер- жащих две оставшихся вершины. Результат будет равен разности количества красных клеток во второй пареe вершин и количества красных клеток в первой паре вершин. Эта разность не больше 2 и не меньше 2. Кроме того, она делится на 3. Значит, она равна 0, есть количества красных клеток в парах противоположных вершин равны.
Пусть нашлась строка С, где есть белая клетка Б и красная клетка К. Тогда из доказанного следует, что столбец с клеткой Б целиком белый, с клеткой К целиком красный. Аналогичные утверждения верны и для всех остальных клеток строки С. Таким образом, в этом случае каждый столбец таблицы состоит из клеток одного цвета. В противном случае каждая строка таблицы состоит из клеток одного цвета.
Пусть каждая из строк таблицы целиком красная или целиком белая, и красных строк к штук. Целиком красной таблица быть не может, так как в этом случае число красных клеток в объединении строки и столбца не делится на 3. Значит, есть белая строка. В ее объединении с любым столбцом к красных клеток. Значит, к делится на 3 и N = 300 * (k/3), что и требовалось доказать. Случай, когда каждый столбец таблицы состоит из клеток одного цвета, рассматривается аналогично.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.