Математический форум Math Help Planet
http://mathhelpplanet.com/

На Марсе 2000 стран (Городская Олимпиада, 8 класс, 1997 год)
http://mathhelpplanet.com/viewtopic.php?f=50&t=55636
Страница 1 из 1

Автор:  Xenia1996 [ 11 сен 2017, 15:58 ]
Заголовок сообщения:  На Марсе 2000 стран (Городская Олимпиада, 8 класс, 1997 год)

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

Автор:  Race [ 03 ноя 2017, 14:39 ]
Заголовок сообщения:  Re: На Марсе 2000 стран (Городская Олимпиада, 8 класс, 1997 год)

Ответ заложен в названии темы: минимальное число таких стран: 1997.

Автор:  Gagarin [ 03 ноя 2017, 15:04 ]
Заголовок сообщения:  Re: На Марсе 2000 стран (Городская Олимпиада, 8 класс, 1997 год)

Race писал(а):
минимальное число таких стран: 1997.
Race
Это так, если отношение "дружить" симметрично и нетранзитивно на множестве дружащих.
Однако в условии это не оговорено. Единственное, что поддаётся здравому смыслу, это то, что дружба антирефлексивна. Но она вполне может быть несимметричной и транзитивной.
Надо бы у топикстартера уточнить формулировочку.

Автор:  Race [ 03 ноя 2017, 15:29 ]
Заголовок сообщения:  Re: На Марсе 2000 стран (Городская Олимпиада, 8 класс, 1997 год)

Gagarin,
я пытался решить задачу чисто логически, учитывая что она для 8го класса.
1. Предположим что в случайно взятой 4рке А, Б, С, Д, 3 страны, А, Б, С, не дружат между собой. Тогда, по условию задачи Д, дружит с ними тремя.
2. Из (1) следует, что все оставшиеся страны дружат с А, Б, С.
3. Берем вместо А, любую другую страну - Е, так как Б и С не дружат между собой, то либо Д дружит с Е, либо Е дружит с Д, а значит, что все оставшиеся страны дружат с Д.
4. Вместо А берем Е, вместо Д Ф, видим, что Ф дружит с Е. Из чего следует, что Е дружит со всеми странами.
5. Вместо Е ставим Ф, вместо Ф - Ж. Продолжаем до момента когда страны кончатся.
6. Все страны дружат между собой, кроме А, Б, С.

Вроде, кроме предположения в п. 1, все логично.

Страница 1 из 1 Часовой пояс: UTC + 4 часа [ Летнее время ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/