ЕГЭ Информатика 2023: Задача 15 (решение)

Задание 15 ЕГЭ по информатике 2023 года относится к заданиям повышенного уровня сложности и проверяет знание основных понятий и законов математической логики. На его выполнение отводится около трёх минут.

Условие задачи

Обозначим через A(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа a формула

(x % 2 == 0) → (¬(x % 3 == 0)) ∨ (x + a ≥ 10)

тождественно истинна (принимает значение 1 при любом натуральном значении переменной x)?

Решение задачи

Наиболее эффективным способом решения является перебор значений с использованием языка программирования. Формула может быть представлена функцией.

Функция проверки

Создадим функцию f(x, a), вычисляющую значение формулы:

def f(x, a):
  return (x % 2 == 0) <=> ((x % 3 != 0) or (x + a >= 10))

Здесь <=> обозначает эквивалентность (логическое равенство). Использование оператора <= для импликации в данном случае некорректно, необходимо использовать эквивалентность, так как задача требует тождественной истинности.

Перебор значений

Переберем натуральные значения a (например, от 1 до 1000). Для каждого a проверим формулу для различных x. Если для некоторого x функция f(x, a) вернет False, дальнейший перебор x для данного a бессмысленен.

for a in range(1, 1001):
  flag = True
  for x in range(1, 1001): # Диапазон x можно ограничить для повышения скорости
    if not f(x, a):
      flag = False
      break
  if flag:
    print(a)
    break

Переменная flag служит флагом, устанавливаемым в False, если найдено значение x, при котором формула ложна. Если после перебора всех x флаг остаётся True, найденное значение a удовлетворяет условию. break прерывает цикл после нахождения наименьшего подходящего a.

Результат

Запустив код, получим ответ: 94. Наименьшее натуральное число a, при котором формула тождественно истинна, равно 94.