На Марсе 2000 стран

[Ktina]

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

[Red_Herring]

Ktina в сообщении #1246988 писал(а):

дружит со всеми 3 странами из этой четвёрки

???

[Ktina]

Red_Herring
Сама с собой же не будет дружить
Дружба не рефлексивна.

[Dmitriy40]

1997? Если их меньше, то найдётся четвёрка стран, в которой все 4 дружат не со всеми остальными из четвёрки.

[Red_Herring]

Ktina в сообщении #1247003 писал(а):

Сама с собой же не будет дружить

А откуда следует что эта страна принадлежит этой четверке? В условии этого нет.

[Booker48]

Ktina в сообщении #1247003 писал(а):

Дружба не рефлексивна.

И не симметрична, похоже? Тогда надо "дружбу" заменить на "любовь".

[Slav-27]

Red_Herring в сообщении #1247018 писал(а):

А откуда следует что эта страна принадлежит этой четверке?

Так там же вроде найдётся ИЗ любых четырёх, а не ДЛЯ.

[Red_Herring]

В любом случае "со всеми 3 странами из четырех" вызывает недоумение. "С каждой из остальных 3х стран"

[Ktina]

Red_Herring в сообщении #1247050 писал(а):

В любом случае "со всеми 3 странами из четырех" вызывает недоумение. "С каждой из остальных 3х стран"

Вы, на мой взгляд, правы.
Только вот текст условия задачи - не мой:
http://vadim-soft.narod.ru/math/city/city8.htm
(Городская Олимпиада, 8 класс, 1997г., задача №4)

[zhekas]

1) Доказывается, что для любого множества стран n>=4 существует хотябы одна, которая дружит со всеми.

2) Если предположить, что минимум таких стран k. И при этом 2000-k>=4, то среди 2000-k стран найдется одна, которая дружит со всеми 2000-k-1 странами. При этом эта страна дружит и с первыми k странами (так как они дружат с ней). Следовательно эта страна также дружит со всеми оставшимися 1999 странами. Получили противоречие. Значит минимум стран, которые дружат со всеми 1997.