Задача к ЕГЭ по информатике на тему «Смешанное» №3

Просмотров 9 Комментарии 0

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Обозначим через $m&n$ поразрядную конъюнкцию неотрицательных целых чисел $m$ и $n$ .

Так, например, $14&5 = 1110 &0101 = 0100 = 4 2 2 2$ .

На числовой прямой дан отрезок $Q = [12;48]$ и множество $S = {45,23,67}$ .

Определите наименьшее натуральное число $A$ , такое что выражение

(¬Д ЕЛ(x,3)∧ (x∈∕S)) → ((|x− 50| ≤ 7) → (x ∈ Q ))∨ (x&A = 0)

тождественно истинно, то есть принимает значение 1 при любом целом значении переменной х.

Решение 1 (ручками):

Система для врагов:

( ||| x ||... 3 |||| |||{ x ∕∈ S |x− 50| ≤ 7 ||| |||| x ∕∈ Q |||( x&A ⁄= 0

Разберём мечты врагов:

$1)$ $|x − 50| ≤ 7$ , то есть $x ∈ [43;57]$ .

$2)$ $x∈∕Q$ , то есть $x ∈ [49,57]$ (объединяя с первым условием)

$3)$ $x∈∕S$ , то есть $x ∈ [49,57]$ (предыдущие два условия уже учли третье)

$4)$ $x| ...| 3$ , то есть $x ∈ {49,50,52,53,55,56}$ (учитывая три предыдущих условия)

Теперь рассмотрим последнюю мечту: $x&A ⁄= 0$ . Поскольку мы знаем все иксы, которые будут выбирать враги, переведём их в двоичную систему счисления:

$4910 = 1100012$

$5010 = 1100102$

$5210 = 1101002$

$5310 = 1101012$

$5510 = 1101112$

$5610 = 1110002$

Таким образом, мечты врагов такие: «Вот бы на любом из последних шести разрядов в двоичной записи у числа $A$ была единичка».

Друзья говорят: «Нет, любая из последних шести цифр числа $A$ в двоичной записи равна нолику». Таким образом, $Amin = 10000002 = 26 = 64$ .

Решение 2 (прогой):

def inn(x, A):
    return A[0] <= x <= A[1]

def f(x, A):
    S = {45, 23, 67}
    Q = [12, 48]
    return (((x % 3 != 0) and (not (x in S))) <=
    ((abs(x - 50) <= 7) <= (inn(x, Q))) or (x & A == 0))

for A in range(1, 1000):
    flag = True
    for x in range(-100, 1000):
        if not f(x, A):
            flag = False
            break
    if flag:
        print(A)
        break

Ответ: 64