Question

Задача по комбинаторике.

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

Answer 1

Ответ:

Давайте думать.

Вы 18-тый и пожмете 17 раз руку.

Последний (назовем его его 17-тым), с кем вы пожимали руку пожимал ее 16 раз и 17-тый с вами, но снова считать это не будем.

А до вас он пожимал 16-того который сделал 15 рукопожатий кроме вас и 17-того.

И т.д.

Итого

17+16+15....+1=153

Но я могу и ошибиться.  У меня не было комбинаторики.

Объяснение:

Answer 2

Нарисуйте граф $G(V, E)$ с $|V|=n$, тогда для каждой вершины есть $n-1$ вариантов, теперь нам нужно удалить симметрию, поэтому нам нужно разделить на $2$ в произведение $n(n-1)$, таким образом, для $n$ ответ равен $\frac{n(n-1)}{2}$

Ответ: $\frac{18\cdot 17}{2} = 153$