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

Напишем, чего хотят враги:

Отсюда следует, что x должен делиться на и () и не должен делиться на ().

Друзья же хотят помешать врагам, и для этого они берут, согласно условию, наименьшее , чтобы их система была всегда ложна, то есть при любом множество решений системы пусто. Для этого достаточно взять : все иксы, которые подходят врагам делятся на и , а раз они делятся на , то .

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

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

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

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

# функция проверяет выполнение формулы для конкретного x и A
def f(x, A):
    # проверяем, выполняется ли импликация для данного x и A
    return (x % A == 0) <= ((x % 21 != 0) or (x % 35 == 0))

# перебор возможных значений A от 1 до 9999
for A in range(1, 10000):
    flag = True
    # проверка формулы для всех x от 0 до 999
    for x in range(1000):
        # если формула ложна для текущего x, отбрасываем A
        if not f(x, A):
            flag = False
    # если формула выполняется для всех x, выводим наименьшее подходящее A
    if flag:
        print(A)
        break