Теперь Кью работает в режиме чтения

Мы сохранили весь контент, но добавить что-то новое уже нельзя

Открытая математическая проблема: "Существует ли треугольник с целочисленными сторонами, медианами и площадью?".

Можно ли перебором решить задачу, сколько времени уйдет?
ПрограммированиеМатематика+3
  · 6,8 K
Веб-разработчик, геймер, специалист по этике  · 7 дек 2021
Эта проблема сводится к проблеме нахождения целочисленного решения систем квадратных уравнений. Довольно сложная проблема, про которую можно осторожно сказать, что ответа, возможно, нет.
Квадратных уравнений, потому что для вычисления длины медианы используется вот такая формула, включающая в себя извлечение квадратного корня:
Для вычисления площади треугольника, зная только длины его сторон, используется формула Герона
(скриншот взят с https://www.wikidata.org/wiki/Q182714)
Тоже включает в себя извлечение квадратного корня.
Можно ли перебором решить задачу, сколько времени уйдет?
Вот числодробилка на C++, которая решает задачу полным перебором:
#include <iostream>
#include <cmath>

bool is_integer(double k)
{
    return std::floor(k) == k;
}

void log_progress(long long candidate)
{
    if (candidate % 10'000'000 == 0)
    {
        std::cout << '.';
    }
    if (candidate % 1'000'000'000 == 0)
    {
        std::cout << candidate << std::endl;
    }
}

int main()
{
    long long candidate = 0;
    for (double a = 1; a < 10001; ++a)
    {
        for (double b = 1; b < 10001; ++b)
        {
            for (double c = 1; c < 10001; ++c)
            {
                ++candidate;
                double median_a_internals{2 * (b * b + c * c) - a * a};
                double median_b_internals{2 * (a * a + c * c) - b * b};
                double median_c_internals{2 * (a * a + b * b) - c * c};
                double area_internals{(a + b + c) * (-a + b + c) * (a - b + c) * (a + b - c)};
                if (median_a_internals < 1 || median_b_internals < 1 || median_c_internals < 1 || area_internals < 1)
                {
                    log_progress(candidate);
                    continue;
                }
                double median_a{sqrt(median_a_internals) / 2};
                double median_b{sqrt(median_b_internals) / 2};
                double median_c{sqrt(median_c_internals) / 2};
                double area{sqrt(area_internals) / 4};
                if (is_integer(median_a) && is_integer(median_b) && is_integer(median_c) && is_integer(area))
                {
                    std::cout << "Found answer! A=" << a << " B=" << b << " C=" << c;
                    std::cout << " mA=" << median_a << " mB=" << median_b << " mC=" << median_c;
                    std::cout << " S=" << area << std::endl;
                    break;
                }
                else
                {
                    log_progress(candidate);
                }
            }
        }
    }
}
Я добавил там некоторый вывод, чтобы не было скучно смотреть на то, как оно работает.
Как видно, там три вложенных цикла, так что это O(n^3). Скомпилированный в MSVC 19.29.30137 x64 под /O2, запущенный на Core i7-9700 этот код работал около двух часов. Решений в диапазоне длин сторон от 1 до 10000 (десяти тысяч) нет. Перебран, как несложно догадаться, 10^4^3=10^12, то есть, триллион вариантов треугольника.
1 эксперт согласен
пербор это интересно, но как вы собираетесь организовывать действительно ПОЛНЫЙ перебор?
Астрономия, криптография  · 27 дек 2021
Формулировка выглядит неточной.
Формальный ответ: треугольники с целочисленными сторонами, медианами и площадью равной 0 (тоже целое число, однако) существуют. Например: a = 2, b = 2, c = 4, ma = 3, mb = 3, mc = 0, S = 0. 😉
Я бы сказал что так нельзя тк в треугольнике сумма двух сторон должна быть меньше третей, и в вашем решение уже... Читать дальше