11) +
12а) +
12б) +
13) +
14) нет
15) -.
Вот как объяснило жюри оценку, поставленную за задачу № 15
"Рассмотрим пример с 10 нестертыми клетками по диагонали. Где бы мы ни размещали в таблице квадрат 2×2, в него может попасть не более двух клеток – это значит, что стертые клетки восстановить в квадрате
невозможно (есть более одного варианта восстановления)".
На самом деле, не значит.
Никакой квадрат 2×2 в отрыве от остальных восстановить нельзя, но это не значит, что нельзя восстановить их все в совокупности.
Контрпример.
Пусть нестертыми клетками будут все клетки первой строки, кроме первой; все клетки первого столбца, кроме первого; а также клетка в правом нижнем углу (см. рисунок).
- КП_15.jpg (17.42 КБ) 21127 просмотров
Тогда в каждом квадрате 2х2 не более двух нестертых клеток. Но, тем не менее, восстановить все знаки можно.
В четырех угловых клетках всегда четное количество клеток (это инвариант), доказывается это аналогично тому, что в любом квадрате 2×2 четное количество клеток (это доказано в присланной работе). Так что
зная 3 угловые клетки, находим четвертую (то есть клетку в левом верхнем углу). Как восстановить остальные клетки, понятно (это тоже есть в работе).
"Если 10 стертых клеток расположены не по диагонали, то такая клетка либо связана по диагонали с одной, либо с двумя, но по одной диагонали (на одном ряду может быть только одна нестертая клетка), либо не
связана ни с кем. В последнем случае для восстановления надо добавить 2 нестертых клетки, а в остальных случаях по одной".
Опять же, непонятно, почему надо добавить.
"Таким образом, при 19 нестертых клетках, расположенных на главной и смежной с ней диагоналях, таблица восстанавливается однозначно."
Хорошо, это доказано и ответ верный (за это точка в оценке).
"Пусть для таблицы К×К выполняется условие, что при 2К–1 нестертых
клетках есть вариант, что таблица восстановится. Добавим к восстановленной таблице одну стертую строку и столбец, т.е. получим (К+1)×(К+1). Очевидно, что если мы добавим только одну нестертую клетку, то возможно восстановление только либо новой строки, либо нового столбца, в зависимости от того, где эту клетку добавили."
Чтобы восстанавливалась таблица, не обязательно, чтобы восстанавливалась ее подтаблица в отрыве от остальных клеток. Контрпример к этому уже приведен. Поэтому нельзя делать шаг индукции таким образом.
