Олимпиадные задачи

[rid3r]

Добрый день, вот друг вчера увлек интересными задачками, сначало было интересно порешать.
Потом вместе с ним сломали голову. До одной додумались, остальные выкладываю тут.
Оч. интересно узнать как они решаются, у кого есть свободное время и желание порешать, подключайтесь.
Вот задания:Задача №1
Имеется 5 городов из них никакие три не лежат на одной прямой. Эти города нужно соединить железнодорожной сетью состоящей из четырех прямых дорог. При этом можно провести одну ж/д линию над другой по виадукам. Сколько существует таких ж/д сетей?

Задача №2
Найти целые решения уравн 21р^2 + рq - 2q^2 = 19




Заранее всем спасибо.

[ИСН]

В первом надо сидеть и перебирать графы. Говоря химическим языком, 60 вариантов типа н-пентана, 120 - а, нет, чёрт ещё 60 типа изопентана и 5 типа неопентана - всего 125.
Во втором выражение слева равно (3p+q)(7p-2q). Hope this helps.

[Edward_Tur]

Если многочлен ${x^m} + {x^n} + 1$ делится на многочлен ${x^k} + {x^l} + 1$, где $m > n,k > l,m > k$, то $k = 2l$.

[Edward_Tur]

Собирался написать решение, но обнаружил в нём ошибку. Возможно, утверждение неверно.

[neo66]

Утверждение верно. Видел доказательство в книге Прасолова "Многочлены". Элементарно, но муторно.

[RIP]

У Прасолова это доказано только при $m\ge2n$ вроде бы.

[maxal]

Edward_Tur в сообщении #308596 писал(а):

Если многочлен ${x^m} + {x^n} + 1$ делится на многочлен ${x^k} + {x^l} + 1$, где $m > n,k > l,m > k$, то $k = 2l$.

Контрпример:

$$x^5 + x + 1 = (x^2 + x + 1) (x^3 - x^2 + 1)$$

[TOTAL]

maxal в сообщении #308942 писал(а):

Edward_Tur в сообщении #308596 писал(а):

Если многочлен ${x^m} + {x^n} + 1$ делится на многочлен ${x^k} + {x^l} + 1$, где $m > n,k > l,m > k$, то $k = 2l$.

Контрпример:

$$x^5 + x + 1 = (x^2 + x + 1) (x^3 - x^2 + 1)$$

Здесь, как и утверждается, $k = 2l$

[maxal]

TOTAL в сообщении #308954 писал(а):

Здесь, как и утверждается, $k = 2l$

И то верно. Мартышка к старости слепа глазами стала...
Убрал "контр" из утверждения. Будем искать.

[RIP]

Пусть $p>5$ --- простое число, $n\in\mathbb Z$, $1\le n<2p$. Докажите, что многочлен $x^{2p}+px^n-1$ неприводим над $\mathbb Q$.

[neo66]

А какая тут идея доказательства? Мне, вроде бы, удалось только доказать, что, если этот многочлен факторизуем, то степени сомножетелей должны быть $p+1$ и $p-1$.

[RIP]

Я, если честно, не знаю док-ва. Просто это один из запомнившихся примеров с доклада на спецсеминаре про признаки неприводимости. Он относится к многочленам вида $f(x)^p+pg(x)$, где на $f$ и $g$ накладывались некие условия в терминах результантов (типа "для любого $d(x)|f(x)$ что-то там про $\operatorname{Res}(d(x),g(x))$", причём тут многочлены рассматриваются над $\mathbb F_p$). Фамилию докладчика не помню.

[ASHKA93]

А мне кажется, что у второго задания нет решений, т.к. 19 - простое число, и как произведение двух целых чисел может быть представлено как 19*1 или (-1)*(-19) а там, если я не обсчиталась, решений целочисленных нет.

[ИСН]

Некропост detected.
Обсчитались. Есть.

[ASHKA93]

Ну значит, обсчиталась