Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/mccme/2007/8klass/08.doc Дата изменения: Sat Dec 2 17:11:14 2006 Дата индексирования: Sat Dec 22 18:51:59 2007 Кодировка: koi8-r Поисковые слова: созвездие лебедя

Математический кружок МЦНМО

8 класс

8 занятие. «Ориентированные графы»
02.12.06


1. Мюнхгаузен, вернувшись из путешествия, рассказывал, что он побывал в
стране Мюнхгандии, и видел там несколько красивейших озер, соединенных
между собой реками. Из каждого озера вытекают 3 реки, и в каждое озеро
впадают 4 реки. Может ли барон говорить правду?

2. В некоторой стране есть столица и еще 100 городов. Некоторые города (в
том числе и столица) соединены дорогами с односторонним движением. Из
каждого нестоличного города выходит 20 дорог, и в каждый такой город
входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного
города.

3. В некотором государстве каждый город соединен с каждым дорогой.
Сумасшедший король хочет ввести на дорогах одностороннее движение так,
чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так
сделать, если в государстве а) 4 города; б) 5 городов; в) n городов?

4. В некотором государстве 65 городов. Некоторые города соединены дорогами
с односторонним движением, причем в каждый город входит 32 дороги, и из
каждого города выходит 32 дороги. Докажите, что из любого города можно
добраться до любого другого, проехав не более чем по двум дорогам.

5. 25 команд сыграли в волейбольный турнир (каждая команда сыграла с
каждой, ничьих не было). Оказалось, что 1-я команда выиграла у 2-й, 2-я -
у 3-й, .., 23 - у 24-й. А 24-я проиграла 25-й. Докажите, что команды
можно перенумеровать так, чтобы ликвидировать это «недоразумение» (т.е.
чтобы при новой нумерации 1-я команда выиграла у 2-й, 2-я - у 3-й, .., 23
- у 24-й, 24 - у 25-й).

6. Несколько команд сыграли между собой круговой турнир по волейболу
(ничьих не бывает). Будем говорить, что команда А «сильнее» команды В,
если либо А выиграла у В, либо существует команда X такая, что А выиграла
у X, а X выиграла у В.

а) Верно ли, что если А «сильнее» В, а В «сильнее» С, то А «сильнее» С?

б) Докажите, что есть команда, которая «сильнее» всех.

в) Верно ли, что команда выигравшая наибольшее число матчей сильнее всех?