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