Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/mccme/2010/8klass/28.doc Дата изменения: Sat May 15 20:28:59 2010 Дата индексирования: Sat Jun 26 05:17:15 2010 Кодировка: koi8-r Поисковые слова: http astrokuban.info astrokuban

Математический кружок 8 класс
занятие ?28 Ориентированные графы. 15.05.10



1. Ученики по очереди входят в класс, и каждый входящий пишет на доске
число - количество своих друзей, уже находящихся в классе. После всех
учеников (а их 20) заходит учитель и суммирует все записанные на доске
числа. Какое число получится у учителя, если

а) у каждого в этом классе ровно один друг?

б) у каждого в этом классе ровно 5 друзей?

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

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

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

5. а) Несколько чаеловек сыграли в однокруговой теннисный турнир (каждый с
каждым, ничьих нет). Всех участников (кроме Петрова, который куда-то
отлучился) построили для фотографирования в ряд так, что каждый следующий
выиграл у предыдущего. Тут прибежал Петров. Докажите, что ему найдется
место в этом ряду такое, что по-прежнему каждый следующий теннисист
выиграл у стоящего перед ним.

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

6. Расставьте все цифры от 1 до 9 в ряд так, чтобы любое двузначное число,
составленное из двух соседних цифр, делилось на 7 или на 13.

7. В компании из k человек (k>3) каждый узнал по новому анекдоту. За один
телефонный разговор двое сообщают друг другу все известные им анекдоты.
а) Докажите, что: за 2k-3 звонка все могут узнать все анекдоты;

б) Докажите, что это можно сделать за 2k-4 звонка.










Дополнительные задачи.

8. В некоторой стране города соединены дорогами, причем из каждого города
выходит 10 дорог. Из любого города можно добраться по дорогам в любой
другой. Докажите, что можно закрыть любую дорогу и при этом все равно из
каждого города можно будет добраться в любой другой.

9. В стране, кроме столицы, больше 100 городов. Столица страны соединена
авиалиниями со 100 городами. Каждый из остальных городов соединен
авиалиниями ровно с 10 городами. Известно, что из любого города можно
перелететь в любой другой (может быть, с пересадками). В связи с
экономическим кризисом было принято решение закрыть половину авиарейсов
из столицы. Докажите, что это можно сделать таким образом, чтобы после
этого снова можно было бы из любого города перелететь в любой другой.

10. На белом листе клетчатой бумаги нарисовали квадрат размером 12 ( 12.
Две клетки считаются соседними, если у них есть общая вершина или
сторона. Саша закрашивает по одной клетке, вписывая в каждую закрашенную
клетку число ранее закрашенных ее соседей. Чему будет равна сумма
записанных чисел, когда все клетки будут закрашены (перечислите все
возможности)?