В деревне 9 домов. Известно, что у Алмаза соседи Илья и Даня, Миша сосед Илье и Саше, Вика – Паше и Никите, а также по соседству живут Кирилл с Никитой, Илья с Сашей, Кирилл с Пашей, Саша с Даней и больше соседей в означенной деревне нет (соседними считаются дворы, у которых есть общий участок забора). (a) Может ли Алмаз огородами пробраться к Никите за яблоками? (b) Постройте ещё 2 графа, изоморфных тому, что вы использовали в первом пункте.
190 прямых
Пошаговое объяснение:
попробуем построить, ну, например для 4-х точек (см.рис).
Прямая проходит через каждые две точки. Т.е. нужно посчитать сколько различных пар точек можно выбрать из 4-х точек. Это - известная в комбинаторике формула для подсчета числа сочетаний (именно сочетаний, а не размещений, потому, что прямая АВ и прямая ВА - одна и таже прямая). Подсчитаем для 4-х точек:
C₄²=4!/(4-2)!4!=4!/(2!*2!)=3*4/2=6;
и действительно видим 6 прямых. Тогда для 20 точек:
C₂₀²=20!/((20-2)!2!)=19*20/2=190.