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

Занятие 15. И снова графы(4.03.2006)

1.

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

2.

На дискотеке каждый мальчик танцевал ровно с десятью девочками, а каждая девочка — ровно с девятью мальчиками. Кого было больше: мальчиков или девочек?

3.

В гости к маломехматянам прилетели двадцать пять пятируких марсиан. Могут ли все маломехматяне и их гости-марсиане одновременно взяться за руки так, чтобы свободных рук не осталось?

4.

Существует ли граф, степени вершин которого равны:
а) 9, 8, 7, 6, 5, 4, 3, 2, 1;
б) 5, 5, 4, 4, 4, 3, 2, 2, 1;
в) 9, 8, 8, 7, 6, 5, 4, 2, 1;
г) 9, 8, 5, 4, 3, 3, 2, 2, 1;
д) 2, 1, 1, 1, 1, 1, 1, 0, 0?

5.

Среди 40 внешне одинаковых монет 2 фальшивые — они легче, чем остальные и весят одинаково. Как за два взвешивания на чашечных весах без стрелок и гирек определить 20 настоящих монет?

6.

Превратите зубчатый квадрат в обыкновенный, разрезав его на пять частей.

7.

На столе лежит 5 коробочек. В некоторых коробочках лежит по пять коробочек, в некоторых из них тоже лежит по пять коробочек, и так далее, а пустых коробочек получилось всего 25. Сколько всего коробочек?

8.

В марсианском метро 101 станция и 5000 перегонов между станциями. Докажите, что можно добраться с любой станции до любой другой.

9.

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