IPB

Добро пожаловать, гость ( Вход | Регистрация )

> Правила раздела

Публикующим:
     1. Задачу можно опубликовать двумя способами:
          - создав для нее отдельную тему с информативным названием;
          - добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
     2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
     1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
     2. Правильность решения можно проверить, написав личное сообщение автору.

 
Ответить в эту темуОткрыть новую тему
> Сеть
0
4.8.2018, 1:55
Сообщение #1


Охгдеж
****

Группа: Пользователи Braingames
Сообщений: 1 323
Регистрация: 26.3.2009
Пользователь №: 13 618



Есть множество точек некоторые из которых соединены линией одного из шести цветов.
Причем из каждой точки может выходить не более одной линии каждого цвета.
Какое минимальное количество точек надо взять чтобы из них можно было гарантированно выбрать пару не соединенных линией?

Сообщение было отредактировано 0: 4.8.2018, 1:55
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения
UNDEFEAT
4.8.2018, 16:12
Сообщение #2


Avorthoren
****

Группа: Модераторы BrainGames
Сообщений: 3 369
Регистрация: 13.11.2010
Из: Kиев
Пользователь №: 21 696



Спойлер:

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

Если предположить, что мы смогли сделать это для полного 7-графа, то с одной стороны мы получим, что в каждой строке (как и в каждом столбце) ровно по одному числу от 1 до 6, а значит каждое число в этой таблице встречается ровно 7 раз.
Но из-за симметрии относительно главной диагонали, каждое число должно встречаться чётное число раз - противоречие.


Сообщение было отредактировано UNDEFEAT: 4.8.2018, 16:15
Пользователь в офлайнеКарточка пользователяОтправить личное сообщение
Вернуться в начало страницы
+Ответить с цитированием данного сообщения

Ответить в эту темуОткрыть новую тему
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0 -

 



- Упрощённая версия Сейчас: 22.7.2019, 5:11