Индукция в комбинаторике
Ошибка.
Попробуйте повторить позже
У Вани есть клетчатая бумага двух видов: белая и чёрная. Он вырезает кусок из любой бумаги и наклеивает на серую клетчатую доску
делая так много раз. Какое минимальное число кусков нужно наклеить, чтобы «раскрасить» клетки доски в
шахматном порядке? (Каждый кусок — набор клеток, в котором от любой клетки до любой другой можно пройти, переходя из
клетки в соседнюю через их общую сторону. Можно наклеивать куски один поверх другого. Все клетки имеют размер
Источники:
Подсказка 1
Когда сложно понять, как устроена наша конструкция, можно попробовать рассмотреть “маленькие” поля, со стороной 1,2 или 3, в них будет легче понять закономерность и прийти к мысли об оценке и примере.
Подсказка 2
Если мы увидели предположительную закономерность на маленьких числах, для оценки можно попытаться применить индукцию. Для того чтобы осуществить шаг индукции, можно воспользоваться тем, что шахматная доска состоит из большого числа отдельных белых и черных “кусочков”. Как это формализовать?
Подсказка 3
Шахматная раскраска означает, что при переходе в соседнюю по стороне клетку мы всегда меняем цвет. И для оценки можно как раз считать количество таких “смен цвета”, в данной задаче эта конструкция очень и очень поможет!
Оценка.
Можно считать, что первый наклеенный кусок — весь квадрат, от этого ничего не испортится. Считаем его нулевым. Докажем индукцией
по 
утверждение:
_________________________________________________________________________________________________________________________________________________________________________________
После еще 
кусков между любыми двумя клетками есть путь с не более чем 
сменами цвета.
_________________________________________________________________________________________________________________________________________________________________________________
База при 
верна.
_________________________________________________________________________________________________________________________________________________________________________________
Рассмотрим наклеивание 
-го куска 
. Пусть до этого между двумя клетками был путь с не более 
сменами цвета. Если он не
заходил в 
, то он таким и остался. Иначе заменим его кусок от первой его клетки в 
до последней такой клетки на путь по 
между
этими клетками. Тогда количество смен цвета в новом пути увеличилось не более чем на 2 по сравнению со старым. Переход
доказан.
_________________________________________________________________________________________________________________________________________________________________________________
В конце между противоположными углами любой путь имеет хотя бы 88 смен цвета. Значит, поверх нулевого куска наклеено еще хотя бы 44.
_________________________________________________________________________________________________________________________________________________________________________________
Пример.
Пусть верхний слой состоит из центральной клетки. Далее пусть каждый нижележащий слой состоит из клеток предыдущего слоя и из клеток, примыкающих к ним по стороне, и имеет противоположный цвет.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
