15.06 Смешанное

Решение аналитикой
Система для врагов:

Раскроем последнее неравенство системы: и , то есть и , то есть . Враги мечтают, чтобы (в и в ), и при этом они не делились на . Таким образом, чтобы победить, враги будут брать только следующие иксы: . Также враги мечтают, чтобы . Максимальный икс, который могут взять друзья, равен , то есть , а минимальный икс = , то есть . Отсюда заметим, что ни один икс, подходящий врагам, не содержит единичку в пятом с конца разряде в двоичной записи. Тогда мечты врагов такие: «Вот бы у числа была единичка в первом, втором, третьем, четвёртом или шестом с конца разряде в двоичной записи».

Друзья говорят: «Нет, число не содержит единичку ни на одном из этих разрядов». Минимальное , которое могут взять друзья, равно , то есть .

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

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

1. Мы создаём функцию f(x, A), которая проверяет истинность формулы для конкретного и . - Внутри функции задаём отрезки Q = [12, 48] и P = [32, 64]. - Возвращаем результат логического выражения: число делится на 5 (x%5==0) или не принадлежит (not inn(x, Q)) или поразрядная конъюнкция с равна нулю (x&A==0) или импликация для ((inn(x, P) <= (abs(x-31)>=17))).

2. Для проверки принадлежности числа отрезку или определяем вспомогательную функцию inn(x, P), которая возвращает True, если , и False иначе.

3. Мы перебираем все значения от 1 до 999 с помощью цикла for A in range(1, 1000): - Для каждого устанавливаем флаг flag = True, предполагая, что текущий подходит. - Перебираем все значения от -1000 до 999 с помощью вложенного цикла for x in range(-1000, 1000). - Если для текущего функция f(x, A) возвращает False, устанавливаем flag = False и прерываем цикл по , так как это не подходит.

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

Таким образом, программа гарантированно находит наименьшее целое , при котором формула тождественно истинна для любого целого .

# Функция проверяет истинность формулы для конкретного x и A
def f(x, A):
    # Определяем отрезки Q и P
    Q = [12, 48]
    P = [32, 64]
    # Проверяем выражение: делимость на 5 или не принадлежность Q или поразрядная конъюнкция с A равна нулю
    # или импликация для P
    return ((x % 5 == 0) or (not inn(x, Q)) or (x & A == 0) or ((inn(x, P)) <= (abs(x - 31) >= 17)))

# Вспомогательная функция для проверки принадлежности x отрезку P
def inn(x, P):
    return P[0] <= x <= P[1]

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