МАЛЫЙ МЕХМАТ МГУ

Кружок 5 класса

Графы и обходы графов (18.11.06 и 21.11.06)

1.

В шахматном турнире по круговой системе участвуют семь школьников. Известно, что Ваня сыграл шесть партий, Толя – пять, Леша и Дима – по три, Семен и Илья – по две, Женя – одну. С кем сыграл Леша?

2.

а)

12 команд сыграли турнир по олимпийской системе (встречаются две команды, победитель играет дальше, проигравший выбывает). Сколько всего было сыграно матчей?

б)

а если турнир проходил по круговой системе в один круг? (каждая команда играет с каждой один раз)

3.

а)

Художник-авангардист нарисовал картину “Треугольники”. Мог ли он нарисовать свою картину, не отрывая карандаша от бумаги и не проводя никакую линию дважды?

б)

А если его картина называлась “Треугольник и отрезки”?

4.

В углах шахматной доски 3*3 стоят 4 коня: 2 белых и 2 черных (см. рис). Можно ли за несколько ходов поставить коней так, чтобы во всех соседних углах стояли кони разного цвета.

Б		Б
Ч		Ч

5.

Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто собрался у кинотеатра?

6.

Однажды утром кто-то принес букет цветов и поставил его вазу на учительском столе. Когда ребята собрались, учительница спросила: «А знаете ли вы, кто принес цветы?». Ребята стали гадать. Были высказаны предположения: цветы принесли Андрей и Борис, Андрей и Даша, Андрей и Сергей, Борис и Даша, Борис и Володя, Володя и Галя, Галя и Даша. Учительница сказала, что в одном из этих предположений одно имя названо правильно, а второе - неправильно. Во всех же остальных предположениях оба имени названы неправильно. Кто принес цветы?

7.

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

8.

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

9.

а)

Расположите на плоскости 6 точек и соедините их непересекающимися линиями так, чтобы из каждой точки выходили 4 линии.

б)

проведите 6 прямых и отметьте на них 7 точек так, чтобы на каждой прямой было ровно три из отмеченных точек.

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

10.

Посёлок построен в виде квадрата 3 квартала на 3 квартала (кварталы - квадраты со стороной b, всего 9 кварталов). Какой наименьший путь должен пройти асфальтоукладчик, чтобы заасфальтировать все улицы, если он начинает и кончает свой путь в угловой точке A? (Стороны квадрата - тоже улицы).

11.

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

Домашнее задание

1.

Соедините 13 звёздочек на рисунке, пятью отрезками, не отрывая карандаша от бумаги и не проводя никакую линию дважды.

		*
	*	*	*
*	*	*	*	*
	*	*	*
		*

2.

а)

Художник-авангардист нарисовал картину “Контур квадрата и его диагональ”. Мог ли он нарисовать свою картину, не отрывая карандаша от бумаги и не проводя никакую линию дважды?

б)

А если его картина называлась “Контур квадрата и его диагонали”?

3.

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