Главная страница
Навигация по странице:

  • Решение: первое выражение не зависит от выбора A : ( y + 2 x 

  • Основные понятия математической логики


    Скачать 2.32 Mb.
    НазваниеОсновные понятия математической логики
    Дата02.02.2022
    Размер2.32 Mb.
    Формат файлаdoc
    Имя файлаege15.doc
    ТипЗакон
    #349239
    страница3 из 50
    1   2   3   4   5   6   7   8   9   ...   50

    Ещё пример задания:

    Р-32. Укажите наибольшее целое значение А, при котором выражение

    (y + 2x 99) (y > A) (x > A)

    истинно для любых целых положительных значений x и y.


    Решение:

    1. первое выражение не зависит от выбора A: (y +2x 99)

    2. таким образом, нам нужно выбрать значение A так, чтобы условие (y > A) or (x > A)

    выполнялось при всех x и y, для которых ложно (y +2x 99), то есть истинно (y +2x = 99) или = –2x + 99

    1. нарисуем линию = –2x + 99, а также заштрихуем область (y > A) or (x > A) для некоторого значения A, например, для A = 50 (конечно, нужно учесть, что x и y положительны и добавить ещё два ограничения: (x > 0)and (y > 0)):



    1. по условию задачи нужно, чтобы все точки отрезка прямой = –2x + 99 в первой четверти плоскости оказались в заштрихованной зоне

    2. поэтому все точки образовавшегося белого квадрата, в том числе и его вершина (A, A), должны находиться строго под этим отрезком; такой квадрат, соответствующий максимальному значению A, выделен на рисунке зелёной штриховкой

    3. находим координаты вершины зелёного квадрата: находим точку пересечения прямых = –2x + 99 и = x; эта задача сводится к линейному уравнению = –2x + 99 решение которого – = 33

    4. значение A должно быть меньше этого x, поэтому максимальное значение A= 32

    5. Ответ: 32.

    Ещё пример задания:

    Р-31. Укажите наименьшее целое значение А, при котором выражение

    (y + 3x < A) (2y +x > 50) (4y x < 40)

    истинно для любых целых положительных значений x и y.


    Решение:

    1. второе и третье выражения не зависят от выбора A: (2y +x > 50) or (4yx < 40)

    2. таким образом, нам нужно выбрать значение A так, чтобы условие (y + 3x < A)

    выполнялось при всех x и y, для которых ложно (2y +x > 50) or (4yx < 40), то есть истинно

    (2y +x  50) and (4yx  40)

    1. последние два условия можно переписать в виде

    (y  – x/2 + 25) and (yx/4 + 10)

    1. поскольку по условию x и y должны быть положительны, добавляем ещё два условия:

    (y  – x/2 + 25) and (yx/4 + 10) and (x > 0) and (y > 0)

    1. изобразим схематично на плоскости x y эту область (она заштрихована):



    1. для всех точек этой области должно выполняться условие y + 3x < A, равносильное условию

    y < – 3x +A

    1. это значит, что вся область должна лежать ниже линии y = – 3x +A; одна такая подходящая линия показана на рисунке сверху

    2. из рисунка видно, что при параллельном переносе вниз, соответствующем изменению A, она коснётся заштрихованной области в правой вершине заштрихованного треугольника

    3. найдём эту точку пересечения:

    y =x/2 + 25 = x/4 + 10  x = 20, y = 15

    1. поэтому допустимые значение A определяются условием:

    15 < – 320 +AA > 75

    откуда следует, что Amin = 76.

    1. Ответ: 76.

    Примечание: фактически эта задача представляет собой задачу целочисленного линейного программирования, на что впервые обратил внимание Б.А. Державец3.

    Решение (программа на Python, Г.М. Федченко):

    1. программа на Python, полный перебор:

    def f( x, y, A ):

    return (y + 3*x < A) or (2*y + x > 50) or (4*y - x < 40)
    for A in range(1, 200):

    OK = True

    for x in range(1,1000):

    for y in range(1,1000):

    if not f(x, y, A):

    OK = False

    break

    if OK:

    print( A )

    break

    1. вариант без функции:

    for A in range(1, 200):

    OK = 1

    for x in range(1,1000):

    for y in range(1,1000):

    OK *= (y + 3*x < A) or (2*y + x > 50) or (4*y - x < 40)

    if not OK: break

    if OK:

    print( A )

    break

    1. Ответ: 76.
    1   2   3   4   5   6   7   8   9   ...   50


    написать администратору сайта