Число треугольников

На плоскости n точек. Каждая пара точек соединена прямыми линиями и из каждой точки выходит k линий красного цвета, остальные линии чёрного цвета. Эти линии образуют треугольники либо одноцветные, либо разноцветные. Каково максимальное число одноцветных треугольников.
Это задача физтеховской олимпиады прошлых лет для 9 класса.

На самом деле в нижеприведенном рассуждении допущена грубая ошибка, которую, однако, не легко заметить (под конец мы укажем на ошибку).

Легко понять, что мы имеем дело с (k,n-k-1)-регулярным двухцветным графом на n вершинах (далее мы будем обозначать любой такой граф как G_{k,n}) и нас спрашивают о максимальном числе одноцветных циклов в нем. Удивительно, но несмотря на то, что таких графов как грязи, число одноцветных циклов есть инвариант (т.е. это число зависит лишь от n и k и не зависит от конкретного (k,n-k-1)-регулярного двухцветного графа).

Легко понять, что всего в G_{k,n} bin(n,3) треугольных циклов (здесь bin(n,3) есть число сочетаний из n элементов по k; я бы использовал стандартное обозначение, но TeX не работает). Мы посчитаем число не одноцветных треугольных циклов.

Заметим, что каждому не одноцветному треугольному циклу в G_{k,n} можно единственным образом сопоставить две пары смежных не одноцветных ребер. Предположим, что мы знаем число пар смежных не одноцветных ребер в нашем графе, теперь надо заметить, что число разноцветных треугольников вдвое меньше этого числа (в каждом треугольнике ровно две такие пары!). Найдем число интересующих нас пар ребер. Из каждой вершины выходит k ребер одного цвета и n-k-1 ребер другого, значит каждая вершина "принимает участие" в k(n-k-1) разноцветных парах. Всего вершин n, значит рассматриваемых нами пар k(n-k-1)n штук. Значит не одноцветных треугольников k(n-k-1)n/2 штук, а одноцветных bin(n,3)-k(n-k-1)n/2 штук (возможно, очевидные случаи n = 0,1,2 следует разобрать отдельно, а может и приведенная формула годится; мне лень проверять).

Ошибка была в том, что мы не доказали, что существует хотя бы один (k,n-k-1)-регулярный двухцветный граф...

Ну какие графы в школе( в 9-ом классе). Для школьников надо проще. Всего треугольников очевидно [m]C_{n}^{k}[/m]. Чтобы вычислить число одноцветных треугольников, вычислим число разноцветных, это сделать проще. Чтобы треугольник был разноцветным, необходимо и достаточно, чтобы к стороне одного цвета прилегали стороны другого цвета, а это равносильно тому, что из одной точки выходят линии разных цветов. Вершину можно выбрать n способами. Красный отрезок выбираем к способами, а чёрный (n-k-1) способами. Но при таком выборе каждый треугольник будет подсчитан дважды, поэтому все способы (их число) надо перемиожить и разделить на два.
Итак ответ: [m]C_{n}^{3}-\frac{n(n-k-1)k}{2}[/m]

Только число треугольников bin(n,3), а не bin(n,k).

Ответ совпадает с ответом Андрея Михайловича
: [m]C_{n}^{3}-\frac{n(n-k-1)k}{2}[/m]

Да, конечно, число сочетаний по три.
Однако ученик нас развел на решение задачи текущей олимпиады Физтех2017, вот задача.

В некотором государстве 40 городов. Каждая пара городов соединена авиарейсом одной из двух авиакомпаний. Оказалось, что из каждого города выходит ровно 6 авиарейсов первой авиакомпании. Назовем тройку городов A comma space B comma space C замкнутой, если все три авиарейса A B comma space B C comma space C A осуществляются одной авиакомпанией. Каково наибольшее возможное количество замкнутых троек городов может быть в этом государстве?

Добрый день! Нужна помощь в решении системы уравнений из сборника Ершовой, Голобородько (9 класс), С-11*
Как видите, на фото есть решение, ответы сходятся с ответами в сборнике, но я не могу понять, откуда в одном случае еще одна пара корней (1;1,5), а в другом две пары корней. Спасибо.

Пожалуйста, помогите решить задачу для 4-го класса.
Я уже всю голову себе сломал.

Лёша написал два числа: 4 и 12. Дима придумал некоторое правило и продолжил по нему последовательность: 4, 12, 8, 10, …
Каким будет следующее число?
Как Вы думаете, по какому правилу Дима продолжал последовательность?

Задача из варианта прошлых лет для поступающих в школу "Интеллектуал" в 5-й класс, опубликована тут:
http://sch-int.ru/sites/default/files/_uploaded/doc/primery1tour.pdf

ЗАДАЧА4.БЕССЕКТРИСЫ УГЛОВ ПРИ ОСНОВАНИЕ ТРАПЕЦИИ ПЕРЕСЕКАЮТСЯ НА ЕЁ ВТОРОМ ОСНОВАНИИ.ДОКАЖИТЕ ЧТО ВТОРОЕ ОСНОВАНИЕ РАВНО СУММЕ БОКОВЫХ СТОРОН ТРАПЕЦИИ.
ЗАДАЧА5.в равнобокой трапеции меньшее основание равно 10 см,боковая сторона 4 см,а угол между боковой стороной и большим основанием равен 60.найдите среднию линию трапеции
ЗАДАЧА6.Сторона треугольника равно 10см,а одна из средних линий-6см.найдите две другие стороны треугольника,если периметр данного треугольника равен 30см

Составить уравнения касательной прямой и нормальной плоскости для данных линий в указанных точках:
x2 + y2 + z2 = 6, x + y + z = 0 в точке ( 1, 1, -2 )

В мешке лежат шарики трёх цветов: чёрного, белого и синего. Какое наименьшее число шариков нужно вынуть из мешка не глядя, чтобы среди них заведомо оказалось три одноцветных?

(lда-да, ессно, для младшеклассников)

Каждая вершина квадрата соединена отрезками со всеми серединами
его сторон. Сколько РАЗЛИЧНЫХ прямоугольных треугольников изображено
на рисунке? Найдите отношения их площадей к площади исходного квадрата,
которые в ответе укажите в порядке возрастания.