Конкурсная задача ММ191 (4 балла)

Рассматриваются тройки чисел a ≤ b ≤ c, не превосходящих данного натурального числа n. Каких троек больше, тех, которые могут быть длинами сторон некоторого треугольника, или остальных?

Решение

Для каждого фиксированного значения c зададим преобразование множества троек по правилу: (a,b,c) переходит в (c+1-b,c+1-a,c). При этом тройки, не образующие треугольник перейдут в тройки, образующие треугольник, а обратное не всегда верно. Поэтому троек, образующих треугольник, больше.

Приведу решения Олега Полубасова, Сергея Половинкина и Ариадны.

Решение Олега Полубасова
Решение Сергея Половинкина
Решение Ариадны

Обсуждение

Эта задача привлекла меня двумя моментами:
наличием простого изящного решения;
любопытным совпанением чисел T_c и N_c+1, где T_c и N_c количества троек с фиксированным с, соответственно образующих и не образующих треугольник.

Участники порадовали разнообразием решений. Решения Олега Полубасова и Анатолия Казмерчука идентичны авторскому. Решения Константина Хадаева и Виктора Филимоненкова основаны на той же идее, но в несколько иной редакции. Другие участники посчитали количества подходящих и неподходящих троек для каждого фиксированного c (иногда этот подсчет был оформлен в виде шага индукции) или для всех троек, у которых большая сторона не превосходит c. В результате некоторые решения растянулись до шести полновесных страниц Очень наглядное решение визуальное решение предложил Дмитрий Пашуткин (то, что при этом он перепутал цвета, я списал на проблемы с цветовосприятием )

Антон Никонов заметил, что последовательность T_c (а следовательно и N_c) есть в OEIS под номером A002623.

Награды

За правильное решение задачи ММ191 Олег Полубасов и Сергей Половинкин получают по 5 призовых баллов. Антон Никонов, Виктор Филимоненков, Владимир Дорофеев, Ариадна, Анатолий Казмерчук, Константин Хадаев, Николай Дерюгин, Дмитрий Пашуткин, - по 4 призовых балла. За правильное решение с некоторыми вычислительными погрешностями Денис Артюшин получает 3 призовых балла.

Эстетическая оценка задачи - 4.7 балла

---