РЕШУ ЕГЭ — информатика

Варианты заданий

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

Для какого наибольшего натурального числа А формула

¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 4))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Решение. Введём обозначения A  =  ДЕЛ(x, А), P  =  ДЕЛ(x, 6) и Q  =  ДЕЛ(x, 4).

Введём множества:

A  — множество натуральных чисел, для которых выполняется условие A;

P  — множество натуральных чисел, для которых выполняется условие P;

Q  — множество натуральных чисел, для которых выполняется условие Q;

истинным для всех X должно быть выражение $\overlineA \to левая круглая скобка P \to \overlineQ правая круглая скобка .$

Упростим это выражение, раскрыв импликацию по правилу $A \to B = \overlineA плюс B:$

$\overlineA \to левая круглая скобка P \to \overlineQ правая круглая скобка = A плюс левая круглая скобка P \to \overlineQ правая круглая скобка = A плюс \overlineP плюс \overlineQ$

из этой формулы видно, что множество A должно перекрыть множество, которое не перекрыто множеством  $\overlineP плюс \overlineQ,$ то есть перекрыть множество $\overline\overlineP плюс \overlineQ = P умножить на Q.$ Множество P · Q  — это множество всех чисел, которые делятся одновременно на 4 и 6 (все числа, кратные 4 и 6), то есть 12, 24, 36 и так далее. (заметим, что 12  — это наименьшее общее кратное чисел 4 и 6). Для того, чтобы перекрыть эти числа, можно выбрать в качестве A любой делитель числа 12, то есть 1, 2, 3, 4, 6 или 12; наибольшее из этих чисел  — 12.

Ответ: 12.

Приведём другое решение на языке Python.

for a in range(100, 0, -1):

k = True

for x in range(1, 1000):

if not ((x % a != 0) <= ((x % 6 == 0) <= (x % 4 != 0))):

k = False

if k:

print(a)

break

Приведём решение Полины Егрушовой на языке Python.

m=[]

def f(x,a):

return (x%a!=0)<=((x%6==0)<=(x%4!=0))

for a in range (1,1000):

if all(f(x,a)==1 for x in range(1,1000)):

m.append(a)

print(max(m))

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

ДЕЛ(x, А) → (ДЕЛ(x, 21) + ДЕЛ(x, 35))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

(М. В. Кузнецова)

Решение. Приведём решение К. Ю. Полякова.

Введём обозначения:

A = ДЕЛ(x, А), D₂₁ = ДЕЛ(x, 21), D₃₅ = ДЕЛ(x, 35) и D_N = ДЕЛ(x, N)

Введём множества:

A  — множество натуральных чисел, для которых выполняется условие A, D₂₁  — множество натуральных чисел, для которых выполняется условие D₂₁, D₃₅  — множество натуральных чисел, для которых выполняется условие D₃₅ и т. д.

Запишем формулу из условия в наших обозначениях A → (D₂₁ + D₃₅) = 1.

Раскроем импликацию по правилу $A \to B = \overlineA плюс B:$

$A \to левая круглая скобка D_21 плюс D_35 правая круглая скобка = \overlineA плюс D_21 плюс D_35.$

Чтобы формула была тождественно истинной необходимо, чтобы $\overlineA = 1$ (т. е. A = 0), когда D₂₁ + D₃₅ = 0. Тогда наибольшее множество A определяется как A_max = D₂₁ + D₃₅. Множество A_max, точно соответствующее выражению с помощью функции ДЕЛ получить невозможно. Выполним анализ исходной формулы с помощью кругов Эйлера. Чтобы в множество $\overlineA$ входили все числа, не попавшие в объединение D₂₁ + D₃₅, достаточно, чтобы множество А находилось внутри этого объединения, например, совпадая с одним из множеств D₃₅ или D₂₁, или располагаясь внутри любого из них, что возможно, если использовать делители, кратные 21 или 35. В задании требуется найти наименьшее значение, этому условию соответствует 21.

Ответ: 21

Приведём другое решение на языке Python.

for a in range(1, 100):

k = 0

for x in range(1, 1000):

if (x % a == 0) <= ((x % 21 == 0) + (x % 35 == 0)):

k += 1

if k == 999:

print(a)

break

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наибольшего натурального числа А формула

¬ДЕЛ(x, А) → (¬ДЕЛ(x, 21) ∧¬ ДЕЛ(x, 35))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

(Задание М. В. Кузнецовой)

Решение. Введём обозначения: A = ДЕЛ(x, А), D₂₁ = ДЕЛ(x, 21), D₃₅ = ДЕЛ(x, 35) и D_N = ДЕЛ(x, N).

Введём множества:

A  — множество натуральных чисел, для которых выполняется условие A,

D₂₁  — множество натуральных чисел, для которых выполняется условие D₂₁,

D₃₅  — множество натуральных чисел, для которых выполняется условие D₃₅,

…

Тогда исходное выражение

¬ДЕЛ(x, А) → (¬ДЕЛ(x, 21) ∧¬ ДЕЛ(x, 35))

принимает вид $\overlineA \to левая круглая скобка \overlineD_21 умножить на \overlineD_35 правая круглая скобка ,$ откуда в силу правила $A \to B = \overlineA плюс B$ получаем:

$\overlineA \to левая круглая скобка \overlineD_21 плюс \overlineD_35 правая круглая скобка = A плюс \overlineD_21 умножить на \overlineD_35.$

Заметим, что второе слагаемое принимает значение 0 для чисел кратных 21 или 35, то есть для чисел вида 21k и 35n, где k и n натуральные. Чтобы логическая сумма была тождественно истинной, для чисел указанного вида первое слагаемое должно обращаться в 1. Следовательно, число А должно быть таким, чтобы любое из чисел 21k и 35n делилось на него нацело. Общие делители чисел 21k и 35n, не зависящие от k и n,  — суть числа 1 и 7. Наибольшее из них равно 7.

Ответ: 7.

Примечание.

Если бы требовалось определить наименьшее натуральное А, обеспечивающее истинность исходного выражения для всех чисел Х, можно было бы начать анализ с наименьшего натурального числа  — с числа 1, и убедиться, что оно и является искомым: посылка импликации для числа 1 ложна, а значит, сама импликация истинна.

Приведём другое решение на языке Python.

for a in range(100, 0, -1):

k = 0

for x in range(1, 1000):

if (x % a != 0) <= ((x % 21 != 0) and (x % 35 != 0)):

k += 1

if k == 999:

print(a)

break

ДЕЛ(x, А) → (¬ДЕЛ(x, 21) + ДЕЛ(x, 35))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

Задание К. Ю. Полякова

Решение. Приведём решение К. Ю. Полякова.

Введём обозначения A = ДЕЛ(x, А), P = ДЕЛ(x, 21) и Q = ДЕЛ(x, 35)

Введём множества:

A  — множество натуральных чисел, для которых выполняется условие A

P  — множество натуральных чисел, для которых выполняется условие P

Q  — множество натуральных чисел, для которых выполняется условие Q

Истинным для всех X должно быть выражение $A \to левая круглая скобка \overlineP плюс Q правая круглая скобка .$ Упростим это выражение, раскрыв импликацию по правилу $A \to B = \overlineA плюс B:$

$A \to левая круглая скобка \overlineP плюс Q правая круглая скобка = \overlineA плюс \overlineP плюс Q.$

Из этой формулы видно, что $\overlineA$ может быть равно 0 (и соответственно, A может быть равно только там, где  $\overlineP плюс Q =1;$ таким образом, наибольшее возможное множество A определяется как $A_max=\overlineP плюс Q$   — множество всех чисел, которые делятся на 35 плюс множество чисел, которые не делятся на 21. Заметим, что в точности такое множество A_max нельзя получить с помощью функции ДЕЛ никаким выбором A. Итак, нам нужно множеством A перекрыть все числа, которые делятся на 35, это можно сделать, например, выбрав в качестве A любой делитель числа 35 = 5 · 7 в то же время нам нельзя перекрывать числа, которые не делятся на 35, но делятся на 21 = 3 · 7 (в этих точках $\overlineP плюс Q = 0,$ и если будет A = 1, то $\overlineA плюс \overlineP плюс Q = 0.$ Предположим, что мы выбрали некоторое значение A; тогда выражение $\overlineA$ ложно в точках A · k, где k  — натуральное число, если число A · k делится на 21, то есть A · k  =  21 · m при некотором натуральном числе m, то такое число должно (для выполнения условия $\overlineA плюс \overlineP плюс Q =1$ ) делиться на 35. Раскладываем 21 на простые сомножители: 21  =  3 · 7; для того, чтобы число A · k  =  3 · 7 · m делилось на 35, в правой части нужно добавить сомножитель 5, это и есть искомое минимальное значение A (вообще говоря, А может быть любым числом, кратным 5)

Ответ: 5.

Приведём второй способ решения:

Введём обозначения A = ДЕЛ(x, А), D₂₁ = ДЕЛ(x, 21), D₃₅ = ДЕЛ(x, 35) и D_N = ДЕЛ(x, N)

Введём множества:

A  — множество натуральных чисел, для которых выполняется условие A

D₂₁  — множество натуральных чисел, для которых выполняется условие D₂₁

D₃₅  — множество натуральных чисел, для которых выполняется условие D₃₅

…

Запишем формулу из условия в наших обозначениях $A \to левая круглая скобка \overlineD_21 плюс D_35 правая круглая скобка = 1.$ Раскроем импликацию по правилу $A \to B = \overlineA плюс B:$

$A \to левая круглая скобка \overlineD_21 плюс D_35 правая круглая скобка = \overlineA плюс \overlineD_21 плюс D_35$

Чтобы формула была тождественно истинной необходимо, чтобы $\overlineA = 1$ (т. е. А = 0), когда $\overlineD_21 плюс D_35 = 0.$ Тогда наибольшее множество А определяется как $A_max=\overlineD_21 плюс D_35$ Множество A_max, точно соответствующее выражению с помощью функции ДЕЛ получить невозможно. Очевидно, что А_min = D₃₅, т. е. 35  — наибольшее из чисел, соответствующих условию задачи. Меньшим может быть делитель 35, не являющийся делителем 21. Чтобы делитель 35 был решением необходимо, чтобы ни для одного из чисел, кратных ему не выполнилось условие:

$\overlineA_max = D_21 умножить на \overlineD_35 = 1.$

Разложим 35 и 21 на простые множители: 35 = 5 · 7, 21 = 3 · 7. 7  — общий делитель, не может быть решением.

Проверим 5. Вычислим «опасное» число, принадлежащее множеству $D_5 умножить на D_21,$ это 5 · 21 = 105, но 105 : 35 = 3 (остаток 0), т. е. 105 ∈ D₃₅ и для него $D_21 умножить на \overlineD_35 = 0,$ значит, 5 соответствует условию задачи.

Ответ: 5.

Приведём другое решение на языке Python.

for a in range(1, 100):

k = 0

for x in range(1, 1000):

if (x % a == 0) <= ((x % 21 != 0) + (x % 35 == 0)):

k += 1

if k == 999:

print(a)

break

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

Для какого наибольшего натурального числа А формула

¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))

тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?

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

Для какого наибольшего натурального числа А логическое выражение

¬ДЕЛ(x, А) → (ДЕЛ(x, 14) → ¬ДЕЛ(x, 4))

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

Решение. Введём обозначения A = ДЕЛ(x, А), P = ДЕЛ(x, 14) и Q = ДЕЛ(x, 4)

Введём множества:

A  — множество натуральных чисел, для которых выполняется условие A

P  — множество натуральных чисел, для которых выполняется условие P

Q  — множество натуральных чисел, для которых выполняется условие Q

истинным для всех X должно быть выражение $\overlineA \to левая круглая скобка P \to \overlineQ правая круглая скобка$

Упростим это выражение, раскрыв импликацию по правилу $A \to B = \overlineA плюс B:$

из этой формулы видно, что множество A должно перекрыть множество, которое не перекрыто множеством  $\overlineP плюс \overlineQ,$ то есть перекрыть множество $\overline\overlineP плюс \overlineQ = P умножить на Q.$ Множество P · Q  — это множество всех чисел, которые делятся одновременно на 4 и 14 (все числа, кратные 4 и 14), то есть, 28, 56, 112 и т. д. (заметим, что 28  — это наименьшее общее кратное чисел 4 и 14). Для того, чтобы перекрыть эти числа, можно выбрать в качестве A любой делитель числа 28, то есть, 1, 2, 4, 7, 14 или 28; наибольшее из этих чисел  — 28.

Ответ: 28.

Приведём другое решение на языке Python.

for a in range(100, 0, -1):

k = 0

for x in range(1, 1000):

if (x % a != 0) <= ((x % 14 == 0) <= (x % 4 != 0)):

k += 1

if k == 999:

print(a)

break

№ п/п	№ задания	Ответ
1	8106	12
2	9320	21
3	9321	7
4	9322	5
5	27412	18
6	68516	28

Ключ