На Марсе 2000 стран, причём из любых четырёх стран найдётся по крайней мере одна страна, которая дружит со всеми 3 странами из этой четвёрки. Найдите наименьшее возможное количество стран на Марсе, которые дружат со всеми странами.

задан 11 Сен 15:55

3

1997 А что, это не очевидно?

Если есть две непересекающиеся пары недружащих стран (A с B, С c D), то в этой четверке нарушено условие. Следовательно, если есть одна пара недружащих (A и B), то любая из остальных стран либо дружит со всеми, либо может не дружить только с A или B. Таких стран, которые могут не дружить с какой-то из этих двух, не более одной (иначе опять нарушено условие для четверки из A,B и двух таких стран). Таким образом, не менее чем 2000-2-1=1997 стран дружат со всеми прочими.

(11 Сен 16:16) knop
1

@knop, Вы пишете: "А что, это не очевидно?" Очевидность - понятие субъективное. Но даже если это и было для меня очевидным, мне задача всё равно очень понравилась. Ну и потом, надо же и о тех школьниках подумать, которые делают первые шаги в олимпиадной математике. Полагаю, их немало среди читателей форума. Не начинать же им с самых трудных задач.

(11 Сен 23:45) Аллочка Шакед
1

@Аллочка Шакед: я сейчас вряд ли найду ссылку, но задача с таким сюжетом на форуме где-то уже была. Я не знаю насчёт "очевидности", но эффект в этой задаче достаточно простой. Он состоит в том, что "не дружб" очень мало. Это становится совсем наглядно, если рассмотреть граф, соответствующий этим "не дружбам". Тогда условие выглядит так: для любых четырёх точек найдётся одна, которая не соединена ни с одной из трёх.

(12 Сен 0:05) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×939
×349
×104
×101
×100

задан
11 Сен 15:55

показан
87 раз

обновлен
12 Сен 0:05

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru