Математика тоже магия!

ITYM
"Известно, что многочлен n-ой степени P(x) при целых x принимает целые значения. Как выглядит этот многочлен?"
Зачем? Да просто так. У нашей группы из 6-ти человек 4-ре дня чтобы решить эту задачу, на которую великий ГлебоГриш, они же преподы-студенты-садисты, и другую, про которую покачто известно лишь то, что решения её не знает пока никто.
P.S. Echo, с возвращением. Зря уходил, в этом не было необходимости ни тебе, ни остальным.

Pashen, определение этого многочлена рекурсивное и содержит немного магии, но идея там простая.

P(x, n) = p1*x^0 + p2*x^1 + ... pn*x^n =
1. P(x, n) = P(x, n) + p1*x^0 + p2*x^1 + ... pn*x^n, p1,p2,...,pn - целые числа.
2. P(x, n) = (1/a) * mul(P(x,a)+i, i=0..a-1) * P(x, n-a), a - натуральное число > 1, b - целое число.

Первая строка в пояснении не нуждается, линейная комбинация целых чисел - целое число.
Со второй строкой похитрее. Докажем сначала, что коэффициенты искомого многочлена рациональные. Доказательство рациональности можно выполнить при помощи рассмотрения n+1 различных целых значений x, составить систему из n+1 уравнений относительно p0...pn, по построению матрица системы содержит только целые числа, как вектор неизвестных, поэтому по формуле Крамера ее решение рационально.

Пусть коэффициент pk - рациональный, по определению pk=c/d - несократимая дробь, c - целое число, d - натуральное. Тогда многочлен P(x,n) представим в виде P(x,n) = (1/d) * Q(x,n), где Q(x,n) - многочлен с рациональными коэффициентами. Произведение двух рациональных чисел будет целым, если одно из них нацело делится на обратное к другому. Т.е. задача сводится к поиску такого многочлена Q(x,n) c рациональными коэффициентами, который делится на натуральное число d при любых целых x. Заметим, что произведение любых k последовательных целых чисел делится на k, т.к. хотя бы одно из них делится на k. Тогда для делимости многочлена Q(x,n) на d при любых целых x необходимо и достаточно, чтобы Q(x,n) можно было представить в виде Q(x,n) = S(x,d)*(S(x,d)+1)*(S(x,d)+2)*...*(S(x,d)+d-1) * R(x,n-d). Отсюда следует, что если коэффициент pk - рациональный, то многочлен P(x,n) = (1/d) * S(x,d)*(S(x,d)+1)*(S(x,d)+2)*...*(S(x,d)+d-1) * R(x,n-d) - целый, если многочлены S(x,d) и R(x,n-d) - целые.
Таким образом задача свелась к задачам с меньшей размерностью. Поэтому можно определить вид многочлена P(x,n) рекурсивно по новой формуле.

Zeratul: О, спасибо! Но вот рекурсия... Shit... Не самый мой любимый метод. =)
Однако ещё раз спасибо, буду опираться на твоё детище. Мы решили рассматривать степени от нулевой и далее, выводя общие формулы и требования для многочленов, дабы потом постараться объеденить в одну. За сегодня разобрана вторая степень( P(x)=a1*x^2/2+a2*x/2+c, a1,a2,c"принадлежат"Z, a1 и a2 одной чётности) и выдвинуты несколько идей по поводу 3-ей. ГлебоГриш оформил всё в Тех'е, завтра перекину в текстовый формат и запощу сюда, если вдруг кому-нибудь интересно.

Подумал сейчас над вашей формулой и сделаю исправления в своем решении. Я сузил класс подходящих многочленов, неправильно выдумав формулу для последовательных чисел. Исправляю.

Upd, вот теперь формула покрывает действительно всевозможные многочлены с точностью до преобразований и упрощений.

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

ShprotaN писал(а):Один с помощью лопаты извлекал квадратный корень...

Где? О_о

ShprotaN писал(а):...а другой делал из члена многочлен... :о)

Номер "РазпредставитьМедСервис"а, срочно!

ShprotaN писал(а):Математические рассуждения про многочлены почему-то напомнили старый анекдот про Петьку и Василия Ивановича, когда они в институт поступили. Один с помощью лопаты извлекал квадратный корень, а другой делал из члена многочлен... :о)

Пусть профессора устроят мастер-класс ^^

Sonic ZR1
Както так:
Послали Петьку с Чапаем в академию учиться. Немного погодя Фурманов поехал узнать, как они экзамены сдают. Ходит среди абитуриентов , найти не может. Стал спрашивать, говорят, что вроде Петька на заднем дворе копает. Пошёл туда Фурманов, смотрит, Петька весь двор перекопал, сидит еле живой от усталости.
- Ты зачем копаешь?
- Да по математике задали квадратный корень извлечь. Нет тут ни фига!!
- А Чапай где?
- На конюшне закрылся, ему член на многочлен поделить надо. Плакать - плачет, а шашку точит.

Альтернативный вариант:

Чапаев и Петька поступили на физмат. Приходит Чапаев вечером домой, а Петька всю клумбу вскопал. Ты че делаешь? Домашнее задание дали- корень квадратный найти. Вот разные попадаются, а квадратного нету. На следующий день Петька возвращается поздно вечером домой, а Василь Иванович сидит на диване, рыдает. Че с вами, командир?- спрашивает. Во изверги, эти математики. Сказали член на многочлен разделить

Krynnit
Спасибо за иллюстрация с "квадратно-кубическими" корнями! :о)

Zeratul писал(а):Подумал сейчас над вашей формулой и сделаю исправления в своем решении. Я сузил класс подходящих многочленов, неправильно выдумав формулу для последовательных чисел. Исправляю.

Upd, вот теперь формула покрывает действительно всевозможные многочлены с точностью до преобразований и упрощений.

Всё, вывели общую формулу для всех подобных многочленов представляя их как суммы других целочисленных. Итого всё идеально вписалось в:
n k
P(x):(deg P=n)= Σ ak*C , где ak целое.
k=0 x+k-1
Формулу написал свёрнуто, надеюсь всё понятно, если надо - могу расписать. Писал с сотового, так что могло что-нибудь сместиться, надеюсь читаемость ф-лы не исчезнет. Ход рассуждения пока написать не могу, ибо долго, а до текстового файла ещё не дорвался.
Сегодня мы выяснили, что вчера занимались полной фигнёй. То, на что было затрачено три часа и куча бумаги было передоказано в 6 строчек за 5 минут. =(
Зато потом стало легче и к концу второй пары мы управились. Правда местами ГлебоГриш выпадал в осадок("Синус?!! В рот мне ноги, СИНУС?!!), но было весело. Ещё раз спасибо за твои идеи.
UPD: Блин, ф-лу всё же распи... ломает вообщем(как минимум при просмотре форума с сотового). Приклепляю фото.

ShprotaN писал(а):Sonic ZR1
Както так:
Послали Петьку с Чапаем в академию учиться. Немного погодя Фурманов поехал узнать, как они экзамены сдают. Ходит среди абитуриентов , найти не может. Стал спрашивать, говорят, что вроде Петька на заднем дворе копает. Пошёл туда Фурманов, смотрит, Петька весь двор перекопал, сидит еле живой от усталости.
- Ты зачем копаешь?
- Да по математике задали квадратный корень извлечь. Нет тут ни фига!!
- А Чапай где?
- На конюшне закрылся, ему член на многочлен поделить надо. Плакать - плачет, а шашку точит.

Альтернативный вариант:

Чапаев и Петька поступили на физмат. Приходит Чапаев вечером домой, а Петька всю клумбу вскопал. Ты че делаешь? Домашнее задание дали- корень квадратный найти. Вот разные попадаются, а квадратного нету. На следующий день Петька возвращается поздно вечером домой, а Василь Иванович сидит на диване, рыдает. Че с вами, командир?- спрашивает. Во изверги, эти математики. Сказали член на многочлен разделить

Славва богу, что я уже успел записать номер "РазвидетьМедСервис"а... Хотя всё-таки смешно.
[/offtopic]

Друг попросил помочь ему с одним интегралом, а я сам не помню, как такие решаются. Настрочил невесть что, но наверняка там где-то жуткая ошибка и ересь. Кто-нибудь может ткнуть меня носом в оную?

P.S. Некромантия — тоже магия.