15.07 Прочие прототипы

Максимальный размер множества : . Будем выкидывать из него элементы, чтобы найти минимальную сумму.

Очевидно, что при любом чётном первая скобка всегда будет истинной, и неважно, входит в множество или нет. Значит, из множества можно убрать все чётные элементы, то есть

При или в качестве можно взять число , тогда будет верна третья скобка, и неважно, входит в множество или нет. Значит, из множества можно убрать элементы и , то есть

Тогда минимальная сумма элементов равна: .

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

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)

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