15.01 Деление без остатка

Решение руками:

Введем обозначения:

Таким образом истиным для всех должно быть выражение . Упростим это выражение, раскрыв импликацию: .

Из этой формулы видно, что множество должно перекрыть множество, которое не перекрыто множеством . Множество – это множество всех чисел, которые делятся одновременно на 19 и 15. Поэтому чтобы найти наименьшее необходимо найти наименьшее общее кратное чисел 15 и 19 – это 285.

Решение программой:

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. Так как нам нужно минимальное , поиск прекращаем сразу после нахождения первого подходящего значения.

# перебор возможных значений A от 1 до 299
for a in range(1, 300):
    # переменная-флаг: 0 - формула истинна для всех x, 1 - хотя бы один x нарушает
    f = 0
    # перебор всех x от 1 до 499
    for x in range(1, 500):
        # проверка формулы для текущего x и A
        if (((x % 19 != 0) or (x % 15 != 0)) <= (x % a != 0)) == False:
            # если формула ложна, отмечаем и прекращаем проверку для этого A
            f = 1
            break
    # если формула истинна для всех x, выводим найденное минимальное A
    if f == 0:
        print(a)

Получаем ответ: