Рабочий лист урока

← К уроку

Олимпиадная математика • 4 класс

Урок 3 из 3

Графы: рукопожатия и дороги

(Комбинаторика и графы)

Фамилия, имя: ______________________________Класс: ______Дата: ________

1. Цель урока

Цель урока

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

2. Разминка

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

1) В группе $21$ ученик. Сколькими способами можно выбрать дежурного и его помощника?
2) Сколько двузначных чисел с разными цифрами можно составить из цифр $2$ , $3$ , $6$ , $7$ , $8$ ?
3) У Маши $4$ юбки и $2$ кофты. Сколько разных нарядов «юбка + кофта» она может составить?

3. Изучаем новый материал

Графы

Города — точки, дороги — линии между ними.
Сумма числа дорог по всем городам равна удвоенному числу дорог — значит, она чётная.
Если $n$ человек и у каждого по $k$ друзей, пар друзей $n \cdot k : 2$ .

Разберём пример

В стране из каждого города выходит ровно

4

дороги, а всего дорог

36

(каждая соединяет два города). Сколько в стране городов?

Посчитаем дороги «по городам»: каждая дорога посчитается дважды — у двух своих концов. Получится $36 \cdot 2 = 72$ .
У каждого города $4$ дороги, значит, городов $72 : 4 = 18$ .

Ответ: 18.

4. Тренировка

Каждое задание тренирует свой образовательный результат — по возрастанию сложности.

Результат: решать задачи перебором и подсчётом вариантов.

Время на выполнение: ≈16 мин

1) Базовый уровень. Каждый из

8

друзей пожал руку каждому другому по одному разу. Сколько было рукопожатий?

2) Средний уровень. В классе

30

учеников, каждый дружит ровно с

3

одноклассниками. Сколько всего пар друзей?

3) Повышенный уровень. На празднике

8

мальчиков и

7

девочек. Каждый мальчик пожал руку каждой девочке. Сколько было рукопожатий?

4) Повышенный уровень. В шахматном турнире

7

участников, каждый сыграл с каждым по одной партии. За победу дают

1

очко, за ничью — по пол-очка, за поражение —

0

. Сколько очков набрали все участники вместе?

5) Повышенный уровень. В стране из каждого города выходит ровно

5

дорог, а всего дорог

35

(каждая соединяет два города). Сколько в стране городов?

6) Повышенный уровень. В турнире

10

команд, каждая должна сыграть с каждой по одному разу. Пока каждая команда сыграла

2

матча. Сколько матчей ещё осталось сыграть?

Запиши решение в клетчатом поле:

Результат: решать логические задачи, рассуждая по шагам.

Время на выполнение: ≈13 мин

7) Повышенный уровень. Можно ли соединить

11

городов дорогами так, чтобы из каждого города выходило ровно

3

дороги? В ответ запишите «да» или «нет».

8) Повышенный уровень. В стране

17

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

9) Повышенный уровень. В компании

19

человек, некоторые из них пожали друг другу руки. Может ли оказаться, что ровно

14

человек сделали нечётное число рукопожатий? В ответ запишите «да» или «нет».

10) Повышенный уровень. В городе площади А, Б, В, Г, Д. Улицы соединяют площади А и Г, А и Д, Б и В, Б и Г, Б и Д, В и Г, В и Д, Г и Д. Можно ли пройти по всем улицам, побывав на каждой ровно один раз (начать и закончить можно на любых площадях)? В ответ запишите «да» или «нет».

Запиши решение в клетчатом поле: