15.01 Деление без остатка

Решение 1 (руками)

1. Для того чтобы формула была тождественно истинна, необходимо, чтобы при (то есть не делится на ), выполнялось условие (то есть не делится на 21 и 35).

2. Таким образом, любое число , которое не делится на , не должно делиться на 21 и 35 одновременно. Это означает, что все числа , которые делятся на 21 или на 35, должны делиться на . То есть, должно быть делителем чисел, кратных 21 или 35.

3. Найдем наименьшее общее кратное (НОК) чисел 21 и 35:

Это означает, что все числа, которые делятся на 21 или на 35, также делятся на 105.

4. Следовательно, максимальное значение , которое делит все числа, кратные 21 или 35, является наибольшим делителем 105. Наибольший такой делитель — это , так как является наибольшим общим делителем чисел 21 и 35.

Ответ: .

Решение 2 (прогой)

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все возможные значения в разумном диапазоне через цикл for. Для каждого перебираем все натуральные и от до . Для каждой тройки вычисляем логическое выражение. Если хотя бы для одного (и ) выражение оказывается ложным, текущее отбрасываем. Если выражение истинно для всех , считаем подходящим. В конце цикла выводим найденное наибольшее .

# перебор возможных значений A в широком диапазоне
for a in range(-1000, 1000):
    c = 0  # флаг: 0 - условие выполняется для всех x и y, 1 - хотя бы один случай нарушает
    for x in range(1, 1000):  # перебираем натуральные x
        for y in range(1, 1000):  # вложенный цикл, проверка по y для совместимости с оригиналом
            # проверяем, ложное ли выражение для текущих x, y и A
            if (x % A != 0) <= ((x % 6 == 0) <= (x % 9 != 0)) == False:
                c = 1  # если выражение ложно, ставим флаг
                break  # прерываем внутренний цикл по y
        if c == 1:  # если флаг поднят, прерываем внешний цикл по x
            break
    # если флаг остался 0, выражение истинно для всех x
    if c == 0:
        print(a)  # выводим найденное наибольшее A
        break  # прекращаем поиск после нахождения первого подходящего A

Решение 1 (ручками)

Составим систему для тех случаев, когда выражение тождественно ложно:

 

Отсюда следует, что обязательно должен делиться на НОК.

Нам требуется, чтобы любой , кратный , делится на , то есть — делитель числа . Максимальное равно максимальному делителю числа , то есть .

 

Решение 2 (прогой)

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все возможные значения в убывающем порядке с помощью цикла for. Для каждого перебираем все значения от до . Для каждого вычисляем логическое выражение. Если хотя бы для одного выражение оказалось ложным, текущее отбрасываем. Если выражение истинно для всех , считаем подходящим. В конце цикла первый найденный будет наибольшим, удовлетворяющим условию, и выводим его.

# функция проверяет выполнение выражения для конкретного x и A
def f(x, A):
    return (x % A != 0) <= ((x % 6 == 0) <= (x % 9 != 0))

# перебор возможных значений A в убывающем порядке
for A in range(10000, 0, -1):
    met_false = False  # флаг: False - выражение выполняется для всех x, True - хотя бы один x нарушает
    for x in range(1000):  # перебор натуральных x
        # если выражение ложно для текущего x
        if not(f(x, A)):
            met_false = True  # отмечаем нарушение
    # если выражение истинно для всех x
    if not(met_false):
        print(A)  # выводим наибольшее подходящее A
        break  # прекращаем поиск после нахождения первого подходящего A

Решение 1 (ручками)

Составим систему для тех случаев, когда выражение тождественно ложно:

Отсюда следует, что обязательно должен делиться на .

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

 

Решение 2 (прогой)

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все возможные значения в убывающем порядке с помощью цикла for. Для каждого перебираем все значения от до . Для каждого вычисляем логическое выражение. Если хотя бы для одного выражение оказалось ложным, текущее отбрасываем. Если выражение истинно для всех , считаем подходящим. В конце цикла первый найденный будет наибольшим, удовлетворяющим условию, и выводим его.

# функция проверяет выполнение выражения для конкретного x и A
def f(x, A):
    return (x % A != 0) <= ((x % 21 != 0) and (x % 35 != 0))

# перебор возможных значений A в убывающем порядке
for A in range(10000, 0, -1):
    met_false = False  # флаг: False - выражение выполняется для всех x, True - хотя бы один x нарушает
    for x in range(1000):  # перебор натуральных x
        # если выражение ложно для текущего x
        if not(f(x, A)):
            met_false = True  # отмечаем нарушение
    # если выражение истинно для всех x
    if not(met_false):
        print(A)  # выводим наибольшее подходящее A
        break  # прекращаем поиск после нахождения первого подходящего A

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения в возрастающем порядке с помощью цикла for. Для каждого перебираем все от до и проверяем логическое выражение. Если хотя бы для одного выражение оказалось ложным, текущее отбрасываем. Если выражение истинно для всех , считаем подходящим. В конце цикла первый найденный будет наименьшим, удовлетворяющим условию, и выводим его.

# функция проверяет выполнение выражения для конкретного x и A
def f(x, A):
    return ((x % 34 == 0) and (x % 51 != 0)) <= ((x % A != 0) or (x % 51 == 0))

# перебор возможных значений A в возрастающем порядке
for A in range(1, 100):
    flag = True  # флаг: True - выражение выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1, 1000):  # перебор натуральных x
        # если выражение ложно для текущего x
        if not (f(x, A)):
            flag = False  # отмечаем нарушение
    # если выражение истинно для всех x
    if flag:
        print(A)  # выводим наименьшее подходящее A
        break  # прекращаем поиск после нахождения первого подходящего A

Решение руками

Обозначим элементы выражения как:

Тогда запишем выражение:

Упростим выражение:

Данное выражение должно равняться 1. Найдём случаи, когда известная часть равна 1:

Получается, что максимальное значение А равно НОК(6,24) = 24.

Решение программой

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до с помощью цикла for. Для каждого перебираем все от до и проверяем логическое выражение. Если хотя бы для одного выражение оказалось ложным, текущее отбрасываем. Если выражение истинно для всех , считаем подходящим. В конце цикла выводим все подходящие значения , среди которых наибольшее будет искомым.

# функция проверяет выполнение выражения для конкретного x и A
def f(a):
    for x in range(1, 1000):
        # если формула ложна для текущего x, возвращаем False
        if ((x % a != 0) <= ((x % 6 == 0) <= (x % 24 != 0))) == 0:
            return False
    return True  # если формула истинна для всех x

# перебор возможных значений A от 1 до 9999
for a in range(1, 10000):
    if f(a):
        print(a)  # выводим найденное подходящее A

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до с помощью цикла for. Для каждого перебираем все от до и проверяем логическое выражение. Если хотя бы для одного выражение оказалось ложным, текущее отбрасываем. Если выражение истинно для всех , считаем подходящим. В конце цикла выбираем наибольшее найденное значение и выводим его.

# перебор возможных значений A от 1 до 9999
for A in range(1, 10000):
    flag = True  # флаг: True - выражение выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1, 100000):  # перебор натуральных x
        # вычисляем логическое выражение для текущего x и A
        f = (70 % A == 0) and ((x % 28 == 0) <= ((x % A != 0) <= (x % 21 != 0)))
        if f == False:  # если формула ложна
            flag = False  # отмечаем нарушение
            break  # прекращаем проверку текущего A
    if flag:
        maxim = A  # сохраняем текущее подходящее A
# выводим наибольшее подходящее A
print(maxim)

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до с помощью цикла for. Для каждого перебираем все значения от до и вычисляем логическое выражение. Если хотя бы для одного формула ложна, текущее отбрасываем. Если выражение истинно для всех , фиксируем текущее значение как подходящее. В конце цикла находим наименьшее , для которого формула тождественно истинна.

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    flag = True  # флаг: True - выражение выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1, 1000):  # перебор натуральных x
        # проверяем истинность формулы для текущего x и A
        if ((x % a == 0) <= ((x % 21 != 0) or (x % 35 == 0))) == False:
            flag = False  # если формула ложна для x, отмечаем нарушение
            break  # прекращаем проверку текущего A
    if flag:
        print(a)  # выводим найденный наименьший подходящий A
        break  # завершаем поиск, так как нашли минимальный A

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до с помощью цикла for. Для каждого перебираем все значения от до и вычисляем логическое выражение. Если хотя бы для одного формула ложна, текущее отбрасываем. Если выражение истинно для всех , фиксируем текущее значение как подходящее. В конце цикла находим наименьшее , которое удовлетворяет условию.

# перебор возможных значений A от 1 до 999
for A in range(1,1000):
    flag = True  # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1, 10000):  # перебор натуральных x
        # проверяем истинность формулы для текущего x и A
        if ((((x % A == 0) and (x % 36 == 0)) <= (x % 324 == 0)) and (A > 100)) == 0:
            flag = False  # если формула ложна для x, отмечаем нарушение
            break  # прекращаем проверку текущего A
    if flag == True:
        print(A)  # выводим найденный наименьший подходящий A
        break  # завершаем поиск, так как нашли минимальный A

Решение руками

Обозначим элементы выражения как:

Тогда запишем выражение:

Упростим выражение:

Данное выражение должно равняться 1. Найдем случаи, когда известная часть равна 0, а часть с А - 1, для этого отрицаем известную часть и ищем когда она равна 1:

Получается, что максимальное значение А равно НОД(6,3) = 3.

 

Решение программой

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до с помощью цикла for. Для каждого перебираем все значения от до и вычисляем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. Если формула истинна для всех , фиксируем это значение . В конце цикла получаем наибольшее , которое делает формулу тождественно истинной.

# перебор возможных значений A от 1 до 99
for A in range(1, 100):
    flag = True  # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1,1000):  # перебор натуральных x
        # проверяем истинность формулы для текущего x и A
        if (((x % A != 0) and (x % 6 != 0)) <= (x % 3 != 0)) == 0:
            flag = False  # если формула ложна для x, отмечаем нарушение
            break  # прекращаем проверку текущего A
    if flag == True:
        print(A)  # выводим найденный наибольший подходящий A

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить значения от до в обратном порядке с помощью цикла for. Для каждого перебираем все от до и вычисляем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. Как только находим первый , для которого формула истинна для всех , это и будет наибольшее подходящее .

# перебор возможных значений A от 1000 до 1
for A in range(1000, 0, -1):
    flag = True  # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1000):  # перебор натуральных x
        # проверяем истинность формулы для текущего x и A
        if ((70 % A == 0) and ((x % A != 0) <= ((x % 18 == 0) <= (x % 42 != 0)))) == 0:
            flag = False  # если формула ложна для x, отмечаем нарушение
            break  # прекращаем проверку текущего A
    if flag:
        print(A)  # выводим найденный наибольший подходящий A
        break  # завершение поиска после нахождения максимального A

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить значения от до с помощью цикла for. Для каждого перебираем все от до и вычисляем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. Как только находим первый , для которого формула истинна для всех , это и будет наименьшее подходящее .

# перебор возможных значений A от 1 до 999
for A in range(1, 1000):
    flag = True  # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1, 1000):  # перебор натуральных x
        # проверяем истинность формулы для текущего x и A
        f = (x % A == 0) <= ((x % 21 != 0) or (x % 35 == 0))
        if f == 0:
            flag = False  # если формула ложна для x, отмечаем нарушение
            break  # прекращаем проверку текущего A
    if flag:
        print(A)  # выводим найденный наименьший подходящий A
        break  # завершение поиска после нахождения минимального A

Решение 1 (ручками)

Рассмотрим формулу:

Нам нужно найти наибольшее , при котором формула всегда истинна для любого .

Формула утверждает, что если не делится на , то если делится на 6, то не должно делиться на 9. Чтобы формула была истинной, необходимо, чтобы было таким, что при делении на 6 не делится на 9. Это возможно, если — наименьшее общее кратное чисел 6 и 9:

Таким образом, наибольшее .

Ответ: .

Решение 2 (прогой)

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить значения начиная с большого числа (например, ) и уменьшать до . Для каждого перебираем все от до и вычисляем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. Как только находим первый , для которого формула истинна для всех , это и будет наибольшее подходящее .

# функция проверяет выполнение выражения для конкретного x и A
def f(x, A):
    return (x % A != 0) <= ((x % 6 == 0) <= (x % 9 != 0))

# перебор возможных значений A от 10000 до 1
for A in range(10000, 0, -1):
    flag = True  # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    for x in range(1000):  # перебор натуральных x
        # если формула ложна для текущего x, отмечаем нарушение
        if not f(x, A):
            flag = False
    # если формула выполняется для всех x, выводим A и завершаем поиск
    if flag:
        print(A)
        break

Решение 1 (ручками)

Рассмотрим формулу:

Для того чтобы формула была всегда истинной, необходимо, чтобы если не делится на , то одновременно выполнялись условия, что не делится на 21 и на 35.

Из условий и следует, что не может делиться на 7, так как 21 и 35 имеют общий делитель 7.

Следовательно, должно быть таким числом, что не может делиться на 7, то есть наибольшее возможное значение — это 7.

Таким образом, наибольшее , при котором формула всегда истинна, равно 7.

Ответ: .

Решение 2 (прогой)

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и вычисляем истинность формулы. Если хотя бы для одного формула ложна, текущее отбрасываем. Как только находим , для которого формула выполняется для всех , это и будет наибольшее подходящее .

# функция проверяет выполнение выражения для конкретного x и A
def f(a):
    for x in range(1, 1000):
        # проверяем истинность формулы для текущего x
        if not((x % a != 0) <= ((x % 21 != 0) and (x % 35 != 0))):
            return False
    return True

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    # если формула истинна для всех x, выводим A
    if f(a):
        print(a)

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

Отсюда следует, что x должен делиться на и () и не должен делиться на ().

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

Получаем ответ:

 

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

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного формула ложна, текущее отбрасываем. Как только находим , для которого формула выполняется для всех , это и будет наименьшее подходящее .

# функция проверяет выполнение формулы для конкретного x и A
def f(x, A):
    # проверяем, выполняется ли импликация для данного x и A
    return (x % A == 0) <= ((x % 21 != 0) or (x % 35 == 0))

# перебор возможных значений A от 1 до 9999
for A in range(1, 10000):
    flag = True
    # проверка формулы для всех x от 0 до 999
    for x in range(1000):
        # если формула ложна для текущего x, отбрасываем A
        if not f(x, A):
            flag = False
    # если формула выполняется для всех x, выводим наименьшее подходящее A
    if flag:
        print(A)
        break

Решение 1 (ручками)

Обозначим элементы выражения как:

Тогда запишем выражение:

Упростим выражение:

Данное выражение должно равняться 1. Найдем случаи, когда известная часть равна 0, а часть с А - 1, для этого отрицаем известную часть и ищем когда она равна 1:

Получается, что максимальное значение А равно НОК(6,3) = 6.

Решение 2 (прогой)

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить значения в убывающем порядке от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного формула ложна, текущее отбрасываем. Как только находим , для которого формула выполняется для всех , это и будет наибольшее подходящее .

# функция проверяет выполнение формулы для конкретного x и A
def f(x, A):
    # проверяем импликацию для данного x и A
    return (x % A != 0) <= ((x % 6 == 0) <= (x % 3 != 0))

# перебор возможных значений A от 10000 до 1
for A in range(10000, 0, -1):
    flag = True
    # проверка формулы для всех x от 0 до 999
    for x in range(1000):
        # если формула ложна для текущего x, отбрасываем A
        if not f(x, A):
            flag = False
    # если формула выполняется для всех x, выводим наибольшее подходящее A
    if flag:
        print(A)
        break

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного формула ложна, текущее отбрасываем. Как только находим , для которого формула выполняется для всех , это и будет наименьшее подходящее .

# функция проверяет выполнение формулы для конкретного A
def f(a):
    # перебор всех x от 1 до 999
    for x in range(1, 1000):
        # проверка истинности импликации для текущего x и a
        if (((x % 19 != 0) or (x % 15 != 0)) <= (x % a != 0)) == 0:
            # если формула ложна хотя бы для одного x, возвращаем False
            return 0
    # если формула истинна для всех x, возвращаем True
    return 1

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    # если формула выполняется для всех x, выводим найденное минимальное A
    if f(a):
        print(a)
        break

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

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного формула ложна, текущее отбрасываем. Как только находим , для которого формула выполняется для всех , это и будет наименьшее подходящее .

# перебор возможных значений A от 1 до 999
for A in range(1, 1000):
    # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    p = True
    # перебор всех x от 1 до 999
    for x in range(1, 1000):
        # проверка истинности импликации для текущего x и A
        f = ((x % 34 == 0) and (x % 51 != 0)) <= ((x % A != 0) or (x % 51 == 0))
        # если формула ложна хотя бы для одного x, сбрасываем флаг
        if f == False:
            p = False
            break
    # если формула истинна для всех x, выводим найденное минимальное A и прекращаем перебор
    if p == True:
        print(A)
        break

Получается ответ:

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

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность импликации вместе с дополнительным условием . Если хотя бы для одного формула ложна, текущее отбрасываем. Как только находим , для которого формула выполняется для всех , это и будет наименьшее подходящее .

# функция проверки делимости
def d(x, y):
    return x % y == 0

# перебор возможных значений A от 1 до 999
for a in range(1, 1000):
    # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    flag = True
    # перебор всех x от 1 до 9999
    for x in range(1, 10000):
        # проверка истинности импликации с дополнительным условием для текущего x и A
        if (((d(x, a) and d(x, 36)) <= d(x, 324)) and (a > 100)) == 0:
            flag = False
            break
    # если формула истинна для всех x, выводим найденное минимальное A и прекращаем перебор
    if flag:
        print(a)
        break

Получаем ответ:

Для нахождения наибольшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. В конце выводим наибольшее , для которого формула истинна для всех .

# перебор возможных значений A от 1 до 999
for A in range(1, 1000):
    # флаг: True - формула выполняется для всех x, False - хотя бы один x нарушает
    p = True
    # перебор всех x от 1 до 999
    for x in range(1, 1000):
        # проверка формулы для текущего x и A
        f = (45 % A == 0) and (((x % 30 == 0) and (x % 12 == 0)) <= (x % A == 0))
        # если формула ложна, отмечаем и прекращаем проверку для этого A
        if f == False:
            p = False
            break
    # если формула истинна для всех x, выводим найденное максимальное A
    if p == True:
        print(A)

Решение руками

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

Таким образом истиным для всех должно быть выражение .Упростим это выражение, раскрыв импликацию: .

Из этой формулы видно, что множество должно перекрыть множество, которое не перекрыто множеством . Множество – это множество всех чисел, которые не делятся либо на 15 либо на 18. Поэтому чтобы найти наименьшее достаточно выбрать наименьшее из чисел 15 и 18 – это 15.

 

Решение программой

Для нахождения наименьшего натурального числа , при котором формула

тождественно истинна для всех натуральных , используем программный перебор. Идея заключается в том, чтобы проверить все значения от до . Для каждого перебираем от до и проверяем истинность формулы. Если хотя бы для одного выражение оказывается ложным, текущее отбрасываем. В конце выводим наименьшее , для которого формула истинна для всех .

for a in range(1, 1500):
    # Переменная-флаг,
    # которой присваивается 1, если хотя бы одно выражение выдаёт ложь
    f = 0
    for x in range(1, 5000):
        # Если выражение ложно(нам нужны только истинные),
        # то приостанавливаем цикл
        if (((x % a == 0) and (x % 15 != 0)) <= ((x % 18 == 0) or (x % 15 == 0))) == False:
        #if (((x % a != 0) or (x % 15 == 0) or (x % 18 == 0))) == False:
            f = 1
            break
    if f == 0:
        print(a)
        break

Получаем ответ: