Помощь - Поиск - Пользователи - Календарь
Полная версия: Сеть
Форум Игры разума [braingames] > Главный форум > Разминка для мозгов
0
Есть множество точек некоторые из которых соединены линией одного из шести цветов.
Причем из каждой точки может выходить не более одной линии каждого цвета.
Какое минимальное количество точек надо взять чтобы из них можно было гарантированно выбрать пару не соединенных линией?
UNDEFEAT
Спойлер:

7 точек.
Для начала покажем, что с указанными ограничениями рёбра полного 6-графа можно раскрасить в 6 цветов:
x12345
1x5436
25x163
341x52
4365x1
56321x

Если предположить, что мы смогли сделать это для полного 7-графа, то с одной стороны мы получим, что в каждой строке (как и в каждом столбце) ровно по одному числу от 1 до 6, а значит каждое число в этой таблице встречается ровно 7 раз.
Но из-за симметрии относительно главной диагонали, каждое число должно встречаться чётное число раз - противоречие.
Это упрощенная версия форума. Для просмотра полной версии нажмите нажмите сюда.
Invision Power Board © 2001-2020 Invision Power Services, Inc.