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

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

Занятие 10. Карты и схемы (26.11.2011)

Основные задачи

0.

В сказочной стране живут семь гномов. Между их домами есть дороги: 1-3, 2-4,4-6, 7-3, 7-5,6-2, 5-1, 3-5. Можно ли добраться по дорогам от дома 1 до дома 6?

1.

В далеком будущем в Солнечной системе оказались освоены все планеты (для знатоков: и Плутон снова стал считаться планетой!), и между ними существуют транспортные маршруты: Плутон – Уран, Уран – Нептун, Венера – Марс, Сатурн – Юпитер, Марс – Меркурий, Юпитер – Нептун, Меркурий – Земля, Уран – Сатурн, Сатурн – Нептун, Земля – Венера. Можно ли добраться от Земли до Плутона?

2.

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

3.

a)

Расположите на плоскости 9 городов и соедините их дорогами так, чтобы из каждого города выходило ровно 4 дороги.

б)

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

4.

Костя нарисовал 2011-угольник и соединил каждые две вершины диагональю. Сколько всего отрезков, включая стороны, нарисовал Костя?

5.

а)

Можно ли, не отрывая карандаш от бумаги и не проведя никакой линии более одного раза, нарисовать открытый конверт, закрытый конверт (рис. 1)?

б)

Нарисуйте одним росчерком, не проводя ни одной линии дважды, фигуры, изображенные на рис. 2.

в)

(Задача Эйлера о мостах Кенигсберга) Можно ли, гуляя по городу, пройти по каждому мосту ровно один раз (рис. 3)?

6.

Программисты одного НИИ решили соединить имеющиеся у них 2011 компьютеров проводами так, чтобы каждый из них был соединен ровно с пятью другими. Удастся ли программистам осуществить свой замысел?

7.

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

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

8.

В верхних углах доски 3×3 стоят чёрные кони, а в нижних — белые. Кони могут ходить по шахматным правилам.

а)

Поменяйте коней местами, то есть добейтесь того, чтобы в нижних углах оказались чёрные кони, а в верхних — белые.

б)

За сколько ходов этого можно достичь?

в)

А можно ли за несколько ходов поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?

9.

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

10.

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

11.

Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

12.

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