Условие
В прямоугольнике 3×n стоят фишки трёх цветов, по n штук
каждого цвета.
Доказать, что можно переставить фишки в каждой строке так, чтобы в каждом столбце были фишки всех цветов.
Решение
Докажем это индукцией по n. База (n = 1) очевидна.
Шаг индукции. Пусть в верхней клетке последнего столбца стоит фишка цвета a. Разберём два случая.
1) В третьей строке есть фишки обоих оставшихся цветов. Заметим, что во второй строке есть фишка цвета, отличного от а (фишек цвета a всего n, а одна уже занята в первой строке). Пусть это фишка цвета b; переставим её в последний столбец. В третьей строке есть фишка третьего цвета c; переставим её в последний столбец.
2) В третьей строке есть фишки только одного цвета, отличного от a; обозначим этот цвет c. Переставим её в третий столбец. Во второй строке должна быть фишка цвета b (в третьей строке их нет, а в первой их меньше n); переставим её в последний столбец.
В любом случае в последнем столбце оказались фишки всех трёх цветов. Отбросив его, мы получим таблицу 3×(n–1), удовлетворяющую условию задачи. По предположению индукции фишки в ней можно переставить требуемым образом. Тем самым, мы переставили фишки и в исходной таблице 3×n.
Источники и прецеденты использования
|
|
|
книга |
|
Автор |
Иванов С.В. |
|
Название |
Математический кружок |
|
глава |
|
Номер |
14 |
|
Название |
Разные задачи |
|
Тема |
Неопределено |
|
задача |
|
Номер |
25 |
