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