|
|
 |
Условие
Карточка матлото представляет собой таблицу 10×10 клеточек. Играющий
отмечает 10 клеточек и отправляет карточку в конверте. После этого в газете
публикуется десятка проигрышных клеточек. Докажите, что
а) можно заполнить 13 карточек так, чтобы среди них обязательно
нашлась "выигрышная" карточка – такая, в которой не отмечена ни одна проигрышная клеточка;
б) двенадцати карточек для этого недостаточно.
Решение
а) 13 карточек K1, K2, ..., K13 можно заполнить так: в Ki при i = 1, 2, ..., 9 отметить все клетки i-й строки, в K10 – левые половины первой и последней (10-й) строк, в K11 – правую половину первой и левую последней, в K12 – левую половину второй и правую последней, в K13 – правые половины второй и последней строк.
Если 10 клеток, объявленных проигрышными, стоят в 10 разных строках, то в одной из половин – левой или правой – последней строки и в одной из половин первой (второй) строки нет проигрышных клеток, так что выиграет одна из карточек K10, ..., K13.
Если в какой-то строке две проигрышных клетки, то должна быть строка, свободная от них. Если "свободна" одна из первых 9 строк, то выиграет одна из карточек K1, ..., K9. Если "свободна" только последняя строка, то хотя бы в одной из первых двух строк ровно одна проигрышная клетка, и снова выиграет одна из карточек K10, ..., K13.
б) Докажем, что для 12 заполненных карточек всегда можно объявить проигрышными такие 10 клеток, что в каждой карточке хотя бы одна из отмеченных клеток окажется проигрышной.
Если есть клетка, отмеченная не менее чем в трёх карточках, то объявим её проигрышной. Поскольку карточек, где она не отмечена, не более 9, то справедливость доказываемого утверждения в этом случае очевидна.
Пусть ни одна из клеток не отмечена более чем в двух карточках. Ясно, что найдётся клетка A, отмеченная в двух карточках. В каждой из 10 других карточек будет отмечено по 10 клеток из 99 (кроме A), поэтому среди этих 99 клеток найдётся клетка B, отмеченная в двух карточках. Проигрышными объявим A, B и по одной отмеченной клетке из каждой карточки (каковых будет не более 8), где ни A, ни B не отмечены.
Замечания
1. Практически без изменений решение переносится на случай таблицы n×n для чётного n (n + 3 карточек достаточно, а n + 2 – нет) –
см. задачу М1585 б) из Задачника "Кванта".
2. Баллы: 5 + 5
