ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97787
Тема:    [ Связность и разложение на связные компоненты ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

Автор: Фольклор

Несколько фишек двух цветов расположены в ряд (встречаются оба цвета). Известно, что фишки, между которыми 10 или 15 фишек, одинаковы.
Какое наибольшее число фишек может быть?


Решение

  Занумеруем фишки слева направо. В соответствующем графе соединим рёбрами вершины, одноцветные по условию. При 25 фишках образуются две компоненты связности:  10-21-5-16  и  11-22-6-17-1-12-23-7-18-2-13-24-8-19-3-14-25-9-20-4-15;  их можно раскрасить в разные цвета.
  При добавлении 26-й фишки между этими двумя компонентами образуется перемычка  15-26-10.  Следовательно, граф связен, и раскрасить его нельзя. Тем более нельзя раскрасить граф с большим числом фишек.


Ответ

25 фишек.

Замечания

баллы: 7

Источники и прецеденты использования

олимпиада
Название Турнир городов
Турнир
Дата 1982/1983
Номер 4
вариант
Вариант первый тур, 7-8 класс
Задача
Номер 2

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .