На плоскости отметили 11 точек и соединили их все между собой отрезками. Прямая не прошла ни через одну из данный точек. Какое наибольшее число таких отрезков она могла пересечь?

Задача сводится к подсчету числа отрезков, которые пересекает данная прямая.

1. Обозначим:

• a — число точек слева от прямой (или в одной из полуплоскостей),
• b — число точек справа от прямой, где a + b = 11 и ни одна точка не лежит на прямой.

2. Когда прямая пересекает отрезок между двумя точками? Отрезок пересечёт прямую тогда, когда концы отрезка находятся по разные стороны прямой. Так что число пересечённых отрезков равно числу всех пар точек, одна в одной полуплоскости, другая в другой — то есть a·b.

3. Максимум a·b при a + b = 11 Функция a·b = a(11 − a) достигает максимума, когда a примерно равен 11/2 = 5.5. При целых значениях:

• a = 5, b = 6 → a·b = 30
• a = 6, b = 5 → a·b = 30

Максимум равен 30. Значит, максимум пересечённых прямой отрезков — 30.

4. Достижимо ли это? Да. Разместим 5 точек одной стороны прямой и 6 точек — другой стороны (прямая не должна проходить через точки). Тогда масса пересечённых отрезков равна 5·6 = 30, и такой максимум достигается.

Ответ: 30. Как дополнительная ремарка: для n точек максимум пересечений с линией без прохода через точки равен floor(n^2/4).