Задача на графы В графе 85 вершин, все они попарно соединены и никакие 3 не лежат на одной прямой. Может ли прямая пересекать РОВНО десятую часть рёбер в этом графе? С ДОКАЗАТЕЛЬСТВОМ!

Предыдущий
вопрос Следующий
вопрос

Пусть прямая пересекает ровно k рёбер.

Так как все вершины соединены попарно, количество рёбер в графе равно C(85, 2) = 3570.

Количество рёбер, которые прямая пересекает, можно представить как количество возможных парных комбинаций вершин, через которые проходит прямая.

Таким образом, количество таких комбинаций равно C(85, 2) = 3570.

Разделим это количество на 10, чтобы найти, сколько рёбер составляют 1/10 от всех рёбер:

3570 / 10 = 357.

Это означает, что для того, чтобы прямая пересекала ровно десятую часть рёбер в графе, ей нужно пересечь 357 рёбер.

Но так как 357 не делится нацело на 85 (количество вершин в графе), то прямая не может пересечь ровно десятую часть рёбер в данном графе.

Таким образом, прямая не может пересечь ровно десятую часть рёбер в графе с 85 вершинами.