Конкурсная задача ММ191 (4 балла)
Рассматриваются тройки чисел a ≤ b ≤ c, не превосходящих данного натурального числа n. Каких троек больше, тех, которые могут быть длинами сторон некоторого треугольника, или остальных?
Решение
Для каждого фиксированного значения c зададим преобразование множества троек по правилу: (a,b,c) переходит в (c+1-b,c+1-a,c). При этом тройки, не образующие треугольник перейдут в тройки, образующие треугольник, а обратное не всегда верно. Поэтому троек, образующих треугольник, больше.
Приведу решения Олега Полубасова, Сергея Половинкина и Ариадны.
Решение Олега Полубасова
Решение Сергея Половинкина
Решение Ариадны
Обсуждение
Эта задача привлекла меня двумя моментами:
наличием простого изящного решения;
любопытным совпанением чисел Tc и Nc+1, где Tc и Nc количества троек с фиксированным с, соответственно образующих и не образующих треугольник.
Участники порадовали разнообразием решений. Решения Олега Полубасова и Анатолия Казмерчука идентичны авторскому. Решения Константина Хадаева и Виктора Филимоненкова основаны на той же идее, но в несколько иной редакции. Другие участники посчитали количества подходящих и неподходящих троек для каждого фиксированного c (иногда этот подсчет был оформлен в виде шага индукции) или для всех троек, у которых большая сторона не превосходит c. В результате некоторые решения растянулись до шести полновесных страниц Очень наглядное решение визуальное решение предложил Дмитрий Пашуткин (то, что при этом он перепутал цвета, я списал на проблемы с цветовосприятием )
Антон Никонов заметил, что последовательность Tc (а следовательно и Nc) есть в OEIS под номером A002623.
Награды
За правильное решение задачи ММ191 Олег Полубасов и Сергей Половинкин получают по 5 призовых баллов. Антон Никонов, Виктор Филимоненков, Владимир Дорофеев, Ариадна, Анатолий Казмерчук, Константин Хадаев, Николай Дерюгин, Дмитрий Пашуткин, - по 4 призовых балла. За правильное решение с некоторыми вычислительными погрешностями Денис Артюшин получает 3 призовых балла.
Эстетическая оценка задачи - 4.7 балла