Каждая клетка доски 2017x2017 раскрашена в один из 2016 цветов. За ход можно взять строку или столбец и, если там есть две клетки одного цвета, перекрасить эту строку или столбец в этот цвет. Всегда ли можно за несколько ходов ...

Каждая клетка доски 2017x2017 раскрашена в один из 2016 цветов. За ход можно взять строку или столбец и, если там есть две клетки одного цвета, перекрасить эту строку или столбец в этот цвет. Всегда ли можно за несколько ходов покрасить таблицу в один цвет? Если можно, то в ответе напишите 1, а если нельзя, то в ответе напишите 0
Гость
Ответ(ы) на вопрос:
Гость
Можно. Клеток в строке или в столбце 2017, а цветов всего 2016. Значит, если покрасить 2016 клеток в 2016 разных цветов, то 2017-ую клетку придется покрасить в один из уже имеющихся цветов. В итоге в каждой строке получится по 2 клетки какого-то одного цвета. Эту строку можно покрасить целиком в этот цвет. Допустим, получилось 2016 строк в 2016 разных цветов, тогда 2017-ая строка опять же покрашена в один из тех же 2016 цветов. Теперь перейдем к столбцам. В каждом столбце будет 2016 разных цветов и 2017-ый повторяется. То есть в каждом столбце 2 клетки покрашены в один цвет. Причем этот цвет - один и тот же во всех столбцах. Теперь можно покрасить всю таблицу в один цвет. Если изначально какая-то строка покрашена не во все 2016 цветов, то всё ещё проще. Ответ: 1. Всегда.
Не нашли ответ?
Ответить на вопрос
Похожие вопросы