Подготовка к ДМ-2009

ПОДГОТОВКА К ЭКЗАМЕНУ ПО ДМ

Оцените следующие высказывания, используя обозначения:

    +     для "утверждение всегда верно"

         для "утверждение всегда неверно"

    ?     для "утверждение может быть верно, а может быть неверно"

    !      для "вопрос поставлен некорректно, в условии есть внутренние противоречия"

    0     для "не знаю"

Первые два ответа означают, что утверждения или противоположные к ним, являются теоремами и поэтому требуют доказательства.

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

Для четвёртого варианта надо объяснить, в чём заключается внутренняя противоречивость условия.

Последний ответ позволяет отвечающему честно оценить уровень своих знаний на момент сдачи экзамена.

Вариант 1.

1. Бинарное рефлексивное отношение R на множестве из M из 15 элементов является отношением частичного порядка. Граф отношения содержит 100 рёбер.

1.1.  Отношение R является асимметричным.

1.2.  Отношение R является отношением линейного порядка.

1.3.  Во множестве M по отношению R существует ровно один минимальный элемент.

1.4.  У графа отношения есть две вершины, между которыми можно построить путь, проходящий через все вершины.

 

2.        Диофантово уравнение 36x+by=c имеет решение {x=1, y=1}.

2.1.  Уравнение имеет бесконечное множество решений (в целых числах).

2.2.  Пара {x=1+b, y= -35} также является решением данного уравнения.

2.3.  Не существует решения {x, y} уравнения (в целых числах), обладающего свойством  -35<y<1.

 

3.        Многочлен  P(x)  с рациональными коэффициентами удовлетворяет сравнениям:

P(x)  ≡ x+1 mod (x2 + 1)

P(x)  ≡ x mod (x2 – 1)

3.1.  Число  x=1  является корнем многочлена  P(x).

3.2.  Наименьшая возможная степень такого многочлена равна 3.

3.3.  Существует многочлен с целыми коэффициентами, удовлетворяющий условию.

 

ОТВЕТЫ И КОММЕНТАРИИ

 

1.1.  – (Рефлексивное отношение не может быть асимметричным).

1.2.  – (В графе отношения линейного порядка между любыми двумя вершинами есть ребро, следовательно, общее число рёбер равно 105).

1.3.  ? (можно привести два примера, один, где минимальный элемент единственный, другой – нет).

1.4.  – (Если бы такой путь был, то по транзитивности любые два элемента будут в данном отношении, и оно будет отношением линейного порядка).

 

2.1. + (Диофантово уравнение имеет либо бесконечно много решений, либо ни одного).

2.2. + (Проверяется подстановкой и учётом условий задачи).

2.3. ? (Можно подобрать различные комбинации параметров, например, b=-35, с=1 – условие будет выполнено, а если b=-36, c=0, то не будет выполняться).

 

3.1. – (Из второго условия следует, что P(x)  = x + Q(x) (x2 – 1). При подстановке x=1 получаем P(1)=1, по теореме Безу это не корень).

3.2. – (Решая уравнение, получаем  P(x)  = -0.5x2+x+0.5).

3.3. – (Общее решение имеет вид:  P(x)  = -0.5x2+x+0.5+ Q(x) (x4 – 1). Пусть Q(x) имеет хотя бы один дробный коэффициент (попытка скомпенсировать дробные коэффициенты частного решения), тогда возьмем самый старший член с дробным коэффициентом, скомпенсировать его будет нечем).

 

Comments