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

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

Элементами множества $A$ являются натуральные числа, причем

$A ⊂ {1,2,3,4,5,6,7,8,9}$

Известно, что выражение

$(x%2 == 0)∨(x ∈ A)∨ ($ существует $y ∈ A$ такой, что $(x ⋅y)%15 == 0)$

истинно (т.е. принимает значение $1$ ) для всех $x ∈ {1,2,3,4,5,6,7,8,9}$

Определите минимальную сумму элементов множества $A$ .

Максимальный размер множества $A$ : $A = {1,2,3,4,5,6,7,8,9}$ . Будем выкидывать из него элементы, чтобы найти минимальную сумму.

Очевидно, что при любом чётном $x$ первая скобка всегда будет истинной, и неважно, входит $x$ в множество $A$ или нет. Значит, из множества $A$ можно убрать все чётные элементы, то есть $A = {1,3,5,7,9}$

При $x = 3$ или $x = 9$ в качестве $y$ можно взять число $5$ , тогда будет верна третья скобка, и неважно, входит $x$ в множество $A$ или нет. Значит, из множества $A$ можно убрать элементы $3$ и $9$ , то есть $A = {1,5,7}$

Тогда минимальная сумма элементов $A$ равна: $1 +5 + 7 = 13$ .

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

a = []
for x in range(1, 10):
    if ((x % 2 == 0) or (x in a) or (any(y*x % 15 == 0 for y in a))) == 0:
        a.append(x)
print(a)

В данной задаче стандартное решение программой ошибочно, поскольку оно не учитывает, что, если в множестве $A$ будет элемент $5$ , то элементы $3$ и $9$ можно не добавлять в множество, поскольку они оба в произведении с $5$ кратны $15$ . Тогда итоговая сумма будет меньше той, что получила программа.

Ответ: 13