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

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

Листок 6. Графы

1.

Гарри Поттер умеет превращать жабу в принцессу, гриб в жабу и грушу, грушу в яблоко, огрызок от яблока в котёнка и ёжика, котёнка в грушу или яблоко, ёжика в грушу, а яблоко — только в огрызок. Сейчас у него есть яблоко. Сможет ли он превратить его в принцессу?

2.

Расставьте в кружочках числа 1, 2, 3, ..., 8 так, чтобы ни в каких двух соединённых отрезком кружочках не оказались бы соседние (то есть отличающиеся на 1) натуральные числа.

Указание Ответ

Указание. Каждая из указанных на картинке ячеек соединена со всеми остальными ячейками, кроме одной. В то же время для почти любого числа n запрещённых чисел к соседству два: (n − 1) и (n + 1).

Ответ. Существует три варианта расстановки чисел: Разумеется, можно повернуть эти расстановки на 180°, отразить относительно вертикали или горизонтали и получить ещё несколько вариантов.

3.

Замените буквы в слове ТРАНСПОРТИРОВКА цифрами (разные буквы — разными цифрами, одинаковые — одинаковыми) так, чтобы выполнялись неравенства Т > Р > А > Н < С < П < О < Р < Т > И > Р > О < В < К < А.

4.

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

Ответ

Ответ. Можно. Минимальное количество убираемых спичек — 63.

5.

Имеется сетка размера 4×6. На рисунке разрезаны 24 её верёвочки. Они разрезаны таким образом, что сетка не распалась на отдельные куски. Можно ли разрезать больше верёвочек (другим способом), чтобы сетка не распалась?

Ответ

Ответ. Нельзя.

6.

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

7.

По сторонам квадрата можно пройти так, что на каждой стороне мы побываем ровно один раз. Можно ли обойти таким образом куб (вместо сторон — ребра)? Можно ли обойти все вершины куба, побывав ровно один раз в каждой?

Ответ

Ответ. Обойти все рёбра куба нельзя, а все вершины — можно.