Множества —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#47183

Элементами множества $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

Ошибка.
Попробуйте повторить позже

Задача 2#29728

Элементами множеств $P$ , $Q$ и $A$ являются натуральные неотрицательные числа, причём
$P = {2,4,6,8,10,12}$ и $Q = {3,6,9,12,15}$ . Известно, что выражение

------- ------- (x ∈ P ) → (((x ∈ Q) ∧(x ∈ A )) → (x ∈ P ))

тождественно истинно (т.е. принимает значение 1 при любых неотрицательных целых значениях переменной $x$ ). Укажите наименьшее возможное значение суммы элементов множества $A$ .

Показать ответ и решение

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

( |||{x ∈ P x ∈ Q ||| (x ∕∈ A

Враги мечтают чтобы $x$ были в $P$ и в $Q$ , то есть $x ∈ {6,12}$ , и они не были в A.

Друзья хотят чтобы эти иксы были в A и хотят сделать A с минимальной суммой элементов, тогда они возьмут все элементы из пересечения $P$ и $Q$ , тогда ответ $6+ 12 = 18$ .

Ответ: 18

Ошибка.
Попробуйте повторить позже

Задача 3#29727

Элементами множеств $P$ и $Q$ являются натуральные числа, причём
$P = {2,4,8,12,15}$ и $Q = {3,6,8,15}$ . Известно, что выражение

------- (x ∈ P ) → ((x ∈ Q)∨ (x ∈ A ))

тождественно истинно (т.е. принимает значение 1 при любых неотрицательных целых значениях переменной $x$ ). Укажите наименьшее возможное значение произведения элементов множества $A$ .

Показать ответ и решение

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

( |||{x ∈ P x ∈ Q ||| (x ∕∈ A

Враги мечтают чтобы $x$ были в $P$ и в $Q$ и они не были в A.

Друзья хотят чтобы эти иксы были в A и хотят сделать A с минимальным произведением элементов, тогда они возьмут все элементы из пересечения $P$ и $Q$ , тогда ответ $8⋅15 = 120$ .

Ответ: 120

Ошибка.
Попробуйте повторить позже

Задача 4#29726

Элементами множества А являются натуральные числа. Известно, что выражение

------------------- ------- (x ∈ {2,4,6,8,10,12}) → ((x ∈ {3,6,9,12,15})∧(x ∈ A) → (x ∈ {2,4,6,8,10,12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное количество элементов множества A.

Показать ответ и решение

def f(x, A):
    first = [2, 4, 6, 8, 10, 12]
    second = [3, 6, 9, 12, 15]
    return (x not in first) <= (((x in second) and (x not in A)) <= (x in first))

def podh(A):
    for x in range(1, 100):
        if not f(x, A):
            return False
    return True

arr = [2, 3, 4, 6, 8, 9, 10, 12, 15]
ans = 100
for i in range(2 ** len(arr)):
    A = []
    t = i
    for j in range(len(arr)):
        if t % 2 == 1:
            A.append(arr[j])
        t //= 2
    if podh(A):
        if ans > len(A):
            print(A)
        ans = min(ans, len(A))

print(ans)

Ответ: 3

Ошибка.
Попробуйте повторить позже

Задача 5#29725

Элементами множества А являются натуральные числа. Известно, что выражение

------------------- ------- ------------------- (x ∈ {2,4,6,8,10,12}) ∨((x ∈ {3,6,9,12,15})∧ (x ∈ A ) → (x ∈ {2,4,6,8,10,12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное количество элементов множества A.

Показать ответ и решение

def f(x, A):
    first = [2, 4, 6, 8, 10, 12]
    second = [3, 6, 9, 12, 15]
    return (x not in first) or (((x in second) and (x not in A)) <= (x not in first))

def podh(A):
    for x in range(1, 100):
        if not f(x, A):
            return False
    return True

arr = [2, 4, 6, 8, 10, 12, 15, 9, 3]
minim = 100
for i in range(2 ** len(arr)):
    A = []
    t = i
    for j in range(len(arr)):
        if t % 2 == 1:
            A.append(arr[j])
        t //= 2
    if podh(A):
        minim = min(minim, len(A))
print(minim)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 6#23190

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

$P = {2,4,6,8,10},Q = {3,6,9,12,15}.$

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

(¬(x ∈ A ) → (x ∈ P))∨ ((x ∈ Q) → (x ∈ A ))

истинно (т.е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

def f(x, a):
    P = set([i * 2 for i in range(1, 6)])
    Q = set([i * 3 for i in range(1, 6)])
    return ((not(x in a)) <= (x in P)) or ((x in Q) <= (x in a))
a = set()
for x in range(20):
    if not(f(x, a)):
        a.add(x)
print(len(a))

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 7#22656

Элементами множества А являются натуральные числа. Известно, что выражение

------------------- ------- ------------------- (x ∈ {2,4,6,8,10,12})∨ (((x ∈ {3,6,9,12,15})∧ (x ∈ A )) → (x ∈ {2,4,6,8,10,12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное количество элементов множества A.

Показать ответ и решение

def f(x, A):
    first = [2, 4, 6, 8, 10, 12]
    second = [3, 6, 9, 12, 15]
    return (x not in first) or (((x in second) and (x not in A)) <= (x not in first))
def podh(A):
    for x in range(1, 100):
        if not f(x, A):
            return False
    return True
arr = [2, 4, 6, 8, 10, 12, 15, 9, 3]
minim = 100
for i in range(2 ** len(arr)):
    A = []
    t = i
    for j in range(len(arr)):
        if t % 2 == 1:
            A.append(arr[j])
        t //= 2
    if podh(A):
        minim = min(minim, len(A))
print(minim)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 8#20057

На числовой прямой даны два отрезка:

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

$P = {2,4,6,8,10,12,14,16,18,20},Q = {3,6,9,12,15,21,24,27,30}.$

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

$((x ∈ A ) → (x ∈ P ))∨ ((¬(x ∈ Q )) → ¬ (x ∈ A))$

истинно (т.е. принимает значение 1) при любом значении переменной х.

Определите наибольшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

Раскрываем импликацию:

(x ∕∈ A)∨ (x ∈ P )∨(x ∈ Q)

Найдем иксы, при которых известная часть не выполняется, для этого выполним инверсию известной части:

(x ∕∈ P) ∧(x ∕∈ Q )

Нужно найти случаи, когда это выражение будет истинно, потому что для этих случаев в исходном выражении известная часть будет давать ложь. Данное выражение будет давать истину в тех случаях, когда $x$ не принадлежит отрезку $P$ и не принадлежит отрезку $Q$ . Такие $x$ находятся вне множеств $P$ и $Q$ . Следовательно, все эти точки должны НЕ входить в множество $A$ , тогда множество $A$ это объединение множеств $P$ и $Q$ , а именно $A = {2,4,6,8,10,12,14,16,18,20,3,9,15,21,24,27,30}$ . Количество элементов в нем равно 17.

def f(x, P, Q, A):
    return ((x in A) <= (x in P)) or ((not (x in Q)) <= (not (x in A)))

P = set([x for x in range(2, 21, 2)])
Q = set([x for x in range(3, 31, 3)])
A = set(x for x in range(40))
for x in range(40):
    if not f(x, P, Q, A):
        A.remove(x)
print(len(A))

Ответ: 17

Ошибка.
Попробуйте повторить позже

Задача 9#20056

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

$P = {1,3,5,7,9,11,13,15,17,19,21},Q = {3,6,9,12,15,21,24,27,30}.$

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

$((x ∈ A ) → (x ∈ P ))∨ ((¬(x ∈ Q )) → ¬ (x ∈ A))$

истинно (т.е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

def f(x, P, Q, A):
    return ((x in A) <= (x in P)) or ((not (x in Q)) <= (not (x in A)))

P = set([x for x in range(1, 22, 2)])
Q = set([x for x in range(3, 31, 3)])
A = set()
for x in range(40):
    if not f(x, P, Q, A):
        A.add(x)
print(len(A))

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 10#20055

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

$P = {2,4,6,8,10,12,14,16,18,20},Q = {3,6,9,12,15,21,24,27,30}.$

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

$(¬(x ∈ A ) → (x ∈ P))∨ ((x ∈ Q) → (x ∈ A))$

истинно (т.е. принимает значение 1) при любом значении переменной х.

Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

def f(x, P, Q, A):
    return ((not(x in A)) <= (x in P)) or ((x in Q) <= (x in A))

P = set([x for x in range(2, 21, 2)])
Q = set([x for x in range(3, 31, 3)])
A = set()
for x in range(40):
    if not f(x, P, Q, A):
        A.add(x)
print(len(A))

Ответ: 7

Ошибка.
Попробуйте повторить позже

Задача 11#18146

Элементами множеств $A,P,Q$ являются натуральные числа, причём $P = {1,3,4,9,11,13,15,17,19,21}$ , $Q = {3,6,9,12,15,18,21,24,27,30}$ . Известно, что выражение

((x ∈ P) → (x ∈ A )) ∨((x∈∕A ) → (x ∕∈ Q ))

истинно (т.е. принимает значение $1$ при любом значении переменной $x$ . Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

Враги хотят чтобы $x$ одновременно был в $P$ , в $Q$ , не в $A$ . Тогда $x = 3,9,15,21$ .

Друзья хотят чтобы эти $x$ были в $A$ и $|A |$ было как можно меньше. Тогда $A = {3,9,15,21}$ и $|A| = 4$ .

Ответ: 4

Ошибка.
Попробуйте повторить позже

Задача 12#18145

Элементами множеств $A,P,Q$ являются натуральные числа, причём $P = {1,3,7}$ , $Q = {1,2,4,5,6}$ . Известно, что выражение

((x∈∕A ) → (x ∕∈ P))∨ ((x ∕∈ Q )∧ (x ∈ P ))

истинно (т.е. принимает значение 1 при любом значении переменной $x$ . Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

Враги хотят чтобы $x$ одновременно был в $P$ , в $Q$ , не в $A$ . Такой подходящий $x = 1$ .

Друзья хотят чтобы этот $x$ был в $A$ и $|A|$ было как можно меньше. Тогда $A = {1}$ и $|A | = 1$ .

Ответ: 1

Ошибка.
Попробуйте повторить позже

Задача 13#18144

Элементами множеств $A,P,Q$ являются натуральные числа, причём $P = {1,2,3,4,5,6}$ , $Q = {3,5,15}$ . Известно, что выражение

(x∈∕A ) → ((x∈∕P )∧ (x ∈ Q))∨ (x ∕∈ Q )

истинно (т.е. принимает значение 1 при любом значении переменной $x$ . Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

Враги хотят чтобы $x$ был в $P$ , в $Q$ и при этом не в $A$ . Тогда $x ∈ {3,5}$ .

Друзья хотят чтобы эти $x$ были в $A$ , тогда $A = {3,5}$ и $|A| = 2$ .

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 14#16318

Элементами множеств $A$ , $P$ и $Q$ являются натуральные числа, причём $P = {1,2,$

$3,4,5,6}$ и $Q = {3,5,15}$ . Известно, что выражение

(x ∕∈ A ) → (((x∈∕P )∧ (x ∈ Q))∨ (x ∕∈ Q ))

истинно (т.е. принимает значение $1$ при любом значении переменной $x$ . Определите наименьшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

Враги хотят подобрать такие $x$ чтобы они были не в $A$ и в $P$ и в $Q$ , т.е. все иксы что лежат в $P$ и $Q$ . Это: $3,5$ .

Тогда друзья хотят подобрать такое $A$ , что будет содержать $3,5$ . Друзья возьмут множество $A = {3,5}$ с количеством элементов равным $2$ .

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 15#16317

Элементами множеств $A$ , $P$ и $Q$ являются натуральные числа, причём $P = {2,4,6,$

$8,10,12,14,16,18,20}$ и $Q = {5,10,15,20,25,30,35,40,45,50}$ . Известно, что выражение

((x ∈ A) → (x ∈ P))∨ (¬(x ∈ Q ) → ¬ (x ∈ A))

истинно (т.е. принимает значение $1$ при любом значении переменной $x$ . Определите наибольшее возможное количество элементов в множестве $A$ .

Показать ответ и решение

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

$( ||| x ∈ A { || x ∕∈ P |( x ∕∈ Q$

Мечты врагов такие: «Вот бы любой элемент множества $A$ не являлся элементом множеств $P$ и $Q$ ». Тогда друзья, наоборот, хотят, чтобы любой элемент множества $A$ являлся элементом множеств $P$ и $Q$ . Наибольшее возможное число элементов множества $A$ — объединение множеств $P$ и $Q$ (т. е. все их элементы). Таких различных элементов $18$ .

Ответ: 18