aabzel May 21 at 22:43

Задача про рукопожатия

Easy

2 min

5.3K

Entertaining tasks

Tutorial

Пролог

Существует классическая задача:

Каждый гость на встрече обменивается рукопожатием с другим. Всего было 78 рукопожатий. Сколько гостей пришло на встречу?

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

Определения

Для начала микро ликбез.

Граф - множество вершин и рёбер (палочки и кружочки).

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

Две вершины неориентированного графа смежны, если они являются разными концами одного ребра

полный граф - простой неориентированный граф, в котором каждая пара различных вершин смежна.

Сочетание - неупорядоченная выборка из n элементов по k без повторений. Вычисляется по кнопке калькулятора nCr.

Это всё, что надо для решения этой задачи.

Решение

Это задача из раздела дискретной математики, комбинаторики и алгебры.

Если людей принять за вершины графа, а рукопожатия за ребра графа, то сформируется так называемый полный граф. Как математически связаны количество ребер и количеcтво вершин?

Занумеруем всех гостей натуральными числами (1; 2; 3; 4; 5 и т д). Для одного рукопожатия надо выбрать два гостя. Рукопожатие это неупорядоченная (если Уолли жмет руку Ашоку, то и Ашок жмет руку Уолли) выборка без повторений (Тэд же не может пожать руку сам себе).

Согласно формуле nСm надо посчитать

$\mathrm{C}_{n}^{2}= \frac{n!}{2!(n-2)!} = \frac{n(n-1)(n-2)!}{2!(n-2)!} = \frac{n(n-1)}{2} \qquad (2)$

Вот и получается, что у полного графа есть свойство. Если n- это количество вершин, то

(3) это количество рёбер. Задача сводится к тому, что надо решить уравнение (4)

$78=\frac{n(n-1)}{2} \qquad (4)$

Это уравнение вырождается в квадратное уравнение

$n^{2}-n-156= 0 \qquad (5) \\ x_1 = 13 ; \qquad x_2 = -12 \qquad (6)$

Так как ответ мы ищем в множестве натуральных чисел, то выбираем решение 13. Ответ: на встрече пришло 13 человек.

Второй способ

1--Надо составить квадратную матрицу n*n. Это количество рукопожатий каждый с каждым, матрица.

2--вычитаем диагональ n*n-n, сам с собой здороваться не имеет смысла: например A1 с A1, A2 с A2 и.т.д.

3--(n*n-n)/2 Если A1 поздоровался с A2, то A2 здороваться с A1 не нужно, делим на 2

4--Вот и получается формула для количества способов составить неупорядоченную выборку без повторений.(n*n-n)/2=K. K-количество рукопожатий.

5--Далее решаем квадратное уравнение n^2-n-K*2=0

6--выбираем положительный корень.

Итог

Вот теперь и Вы умеете решать задачу про рукопожатия и можете объяснить другим.

Ссылки

#	Название	URL
1	Полный Граф	https://en.wikipedia.org/wiki/Complete_graph
3	Рукопожатия	https://tproger.ru/articles/7-zakovyristyh-logiko-matematicheskih-zadach
2	LaTex Editor	https://latexeditor.lagrida.com/
4	Калькулятор квадратных уравнений	https://calc.by/math-calculators/quadratic-equations.html
5	Задача про мышей и отраву (спрашивали на собеседовании)	https://habr.com/ru/users/aabzel/articles/
6	Задача про игральные кубики и треугольники (спрашивали на собеседовании)	https://habr.com/ru/articles/763372/
7	Задача про две ёмкости для жидкости (спрашивали на собеседовании)	https://habr.com/ru/articles/662561/

Only registered users can participate in poll. Log in, please.

При устройстве на работу Вас спрашивали задачу про рукопожатия?

4.08% да2

95.92% нет47

49 users voted. 18 users abstained.

Hubs:

Entertaining tasks