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

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

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

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

тождественно истинна, то есть принимает значение при любых натуральных значениях и ?

Запишем, чего хотят враги:

( |||| Д ЕЛ (xy, A ) |||| y ≤ 4095 |{ | x ≤ 2⋅y+ 1 |||| |||| Д ЕЛ (y, 2) ( ¬Д Е Л(x, 2)

Исходя из этого уменьшим поиск $x,y$ по нечетным и четным значениям соответственно:

Решение $1$ (прогой, работает пару минут):

for A in range(1, 10000):
    flag = True
    for x in range(5, (4095 + 1)*2 + 1, 2):
        for y in range(2, 4095 + 1, 2):
            if x*y % A == 0:
                flag = False
                break
        if not flag:
            break
    if flag:
        print(A)
        break

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

Повторим, чего хотят враги:

(| |||| Д ЕЛ (xy, A ) |||| y ≤ 4095 { || x ≤ 2⋅y+ 1 |||| Д ЕЛ (y, 2) |||( ¬Д Е Л(y, 2)

Друзья хотят, чтобы выполнялось условие $¬Д Е Л(xy, A)$ при всех хотелках врага. Соответственно, нужно понять, когда же произведение $xy$ не будет делиться на $A$ .

Исходя из хотелок врага мы понимаем, что будут подбираться такие $xy$ , чтобы они делились на $A$ . Это значит, что $A$ будет содержать внутри себя делители хотя бы одного набора $xy$ . Наша задача — предоставить такое $A$ , чтобы при любом произведении $xy$ там не было такого делителя, что и в $A$ .

Заметим, что $y$ — четные числа. Значит, в самых больших $y$ будет содержаться максимум $211$ умноженное на что-то. Тогда, чтобы минимизировать $A$ возьмем $A = 212$ (т.к. $2$ в степени что-то будет явно меньше, чем числа большие в степени что-то).

Ответ: 4096