15.05 Отрезки

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

Первым шагом раскроем импликацию:

Инвертируем известную часть, чтобы понять при каких выражение ложно:

Это выражение истино (а исходное соответственно ложно), когда принадлежит или отрезку , или отрезку , или им одновременно. Поскольку в исходном выражении между условием с P и условием с Q стоит И, то нам нужно в отрезок А включить все случаи, когда выражение, написанное в предыдущем предложении истинно. – это отрезок P, его мы включаем в отрезок А, – это отрезок Q, его мы тоже включаем в отрезок А. Таких случаев когда и равны 1 нет, поскольку между отрезками P и Q нет пересечения. Сейчас наш отрезок А это два отрезка: и . Такого быть не может и нам нужно получить один отрезок. Единственная возможность, когда эти два отрезка будут включены в один отрезок и при этом данный отрезок будет минимальным по длине, это отрезок , при таком отрезке А выражение будет тождественно истинным. Его длина .

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

Идея заключается в переборе возможных концов отрезка (от 1 до 100) и проверке, что при всех значениях переменной (от 1 до 1000) исходное выражение даёт истину. Если во время проверки найдётся хотя бы одно значение , нарушающее условие, программа должна перейти к рассмотрению нового отрезка. После завершения перебора минимальная полученная длина отрезка и будет ответом.

Для реализации этой идеи необходимо задать отрезки и при помощи функции range(), а также ввести переменную , равную 10 ** 100: в неё будет записан наш ответ. Далее, создадим цикл for, необходимый для перебора значений начала отрезка . Внутри него, с помощью того же цикла, организуем перебор значений конца искомого отрезка. При каждой итерации будем создавать переменную-флаг, которая изначально равна 0, а затем задавать отрезок при помощи функции range(). Внутри нижнего цикла необходимо начать перебор значений переменной . Если выражение ложно хотя бы для одного , то флагу присваивается значение 1, а последний цикл останавливается. Если после перебора всех значений флаг остаётся равным 0, значит выражение тождественно истинно для текущего отрезка : присваиваем его длину , если она меньше текущего значения данной переменной. В конце ответ выводится на экран.

p = range(0, 10 + 1)  # Задаём отрезок P
q = range(25, 50 + 1)  # Задаём отрезок Q
r = 10 ** 100  # Длина отрезка A
for a1 in range(1, 100):  # Перебираем начало отрезка A
    for a2 in range(a1 + 1, 101):  # Перебираем конец отрезка A
        f = 0  # Флаг, указывающий на истинность выражения при любых значениях переменной x
        a = range(a1, a2)  # Задаём отрезок A
        for x in range(1, 1000):  # Перебираем значения переменной x
            # Если при текущем значении переменной x выражение даёт ложь (0), то
            if ((x not in a) <= ((x not in p) and (x not in q))) == 0:
                f = 1  # меняем значение флага на 1,
                break  # останавливаем цикл и переходим к следующему отрезку A
        if f == 0:  # Если значение флага не менялось, значит текущий отрезок A подходит
            r = min(len(a), r)  # Сравниваем длину отрезка A с переменной r
print(r)  # Выводим ответ на экран