Определить степень и коэффициенты неизвестного многочлена

[julinka]

Здравствуйте!

Есть такая задача:
А загадывает некоторый многочлен с натуральными коэффициентами. Б может называть значения аргумента (натуральное число) и получать в ответ значения многочлена на названных им числах. Сколько вопросов необходимо задать (минимально), чтобы определить степень и коэффициенты многочлена.

Мои попытки решения:
Первая идея --- если многочлен степени k то надо задать (k+1) вопрос для того, чтобы решить СЛАУ где в качестве неизвестных выступают коэффициенты. У многочлена степени k имеется (k+1) коэффициент. Но как определить это k? Например, задал Б 3 вопроса, и пусть эти 3 точки лежат на одной прямой. Но ведь не факт, что загаданный многочлен 1 степени. Он может быть и 3-ей и 4-ой.

Также пыталась применить производные

$$f^{(k)}(x)=k!a_0$$

,

но по-моему это тут не поможет.

Не могли бы вы подсказать какие-нибудь идеи по решению такой задачи?

[grizzly]

julinka в сообщении #1035333 писал(а):

Например, задал Б 3 вопроса, и пусть эти 3 точки лежат на одной прямой. Но ведь не факт, что загаданный многочлен 1 степени. Он может быть и 3-ей и 4-ой.

Вы думаете, что может? А попробуйте какой-нибудь пример руками подобрать. Только не забывайте про:

julinka в сообщении #1035333 писал(а):

многочлен с натуральными коэффициентами.

Вы ведь именно это хотели сказать? (а не про целые коэффициенты)?

[Cash]

в 2 хода.
По аналогии, например, с такой известной задачей:
Имеется 9 мешков с неограниченным количеством монет по 10 грамм каждая. И еще один мешок, неотличимый от других, с фальшивыми монетами по 9 грамм. Как с помощью только одного взвешивания определить в каком мешке фальшивые?

-- Пт июл 10, 2015 01:55:08 --

Upd.
Наверное, все-таки далекая аналогия. Давайте такую: 9 мешков с монетами. В одном монеты по 1 грамму, в другом 2 грамма, и т.д. в девятом мешке - 9 грамм. Количество монет в каждом мешке неограниченно. Монеты на вид неотличимы. Как одним взвешиванием (на электронных весах) определить вес монет в каждом мешке?

[julinka]

Cash в сообщении #1035343 писал(а):

Наверное, все-таки далекая аналогия. Давайте такую: 9 мешков с монетами. В одном монеты по 1 грамму, в другом 2 грамма, и т.д. в девятом мешке - 9 грамм. Количество монет в каждом мешке неограниченно. Монеты на вид неотличимы. Как одним взвешиванием (на электронных весах) определить вес монет в каждом мешке?

Не совсем поняла вашу аналогию. Для простоты рассмотрела 3 мешка, пусть они расположены так: 1гр,2гр,3гр, беру и первого 1 монету из 2ого 2, из 3его 3 монеты, в сумме 14гр.

Если мешки расставлены 2гр,1гр,3гр, то сумма равна 13 гр (та же сумма возникает если расположить мешки: 1гр,3гр,2гр). Вообще таких комбинаций 3!, а в случае 9 мешков - 9!, плюс возникает неоднозначность.

-- 10.07.2015, 12:57 --

grizzly в сообщении #1035334 писал(а):

julinka в сообщении #1035333 писал(а):

Например, задал Б 3 вопроса, и пусть эти 3 точки лежат на одной прямой. Но ведь не факт, что загаданный многочлен 1 степени. Он может быть и 3-ей и 4-ой.

Вы думаете, что может? А попробуйте какой-нибудь пример руками подобрать. Только не забывайте про:

julinka в сообщении #1035333 писал(а):

многочлен с натуральными коэффициентами.

Вы ведь именно это хотели сказать? (а не про целые коэффициенты)?

Поняла вашу идею, поигралась с коэффициентами многочленов. Но все-таки это я поняла экспериментально. В интернете не нашла каких-либо особых свойств многочленов с натур. коэфф. (как например то, что при натуральном $x$ многочлен не имеет "перегибов" и прямая в этой области его пересекает только в 2 точках). Не могли бы вы подсказать какие либо строгие мат. свойства по этому поводу?

Тогда идея алгоритма такая: задаем 2 вопроса (минимум), составляем систему для прямой, находим коэффициенты. Далее задаем еще один вопрос и проверяем принадлежит ли новая точка кривой. Если да, то искомый многочлен найден. Если нет, то из 3 точек составляем систему для параболы, находим ее коэффициенты и задаем еще один вопрос - проверяем принадлежит ли точка параболе и так далее...

[grizzly]

julinka в сообщении #1035445 писал(а):

Не могли бы вы подсказать какие либо строгие мат. свойства по этому поводу?

Могу Вам посоветовать для начала посмотреть по ключевым словам "Выпуклость" и "Вторая производная". Если не получится вспомнить / разобраться, задавайте вопросы.

А насчёт решения я бы советовал Вам ещё подумать над аналогией Cash. Что-то мне подсказывает, что этот путь будет короче и приятней.

[julinka]

grizzly в сообщении #1035450 писал(а):

Могу Вам посоветовать для начала посмотреть по ключевым словам "Выпуклость" и "Вторая производная". Если не получится вспомнить / разобраться, задавайте вопросы.

Правильно ли я поняла:
вторая производная многочлена

$$f(x)=a_kx^k+a_{k-1}x^{k-1}+...$$

$$f''(x)=k(k-1)a_kx^{k-2}+(k-1)(k-2)a_{k-1}x^{k-3}+...>0$$

при $x>0$, следовательно, функция выпукла вниз в этой области и перегибов нет?

[grizzly]

julinka в сообщении #1035453 писал(а):

Правильно ли я поняла:...

Конечно.

[iancaple]

julinka в сообщении #1035445 писал(а):

беру и первого 1 монету из 2ого 2, из 3его 3 монеты,

Мало берете, потому и неоднозначность

[Null]

С целыми коэффициентами никогда нельзя будет утверждать что мы получили правильный ответ.
А вот если коэффициенты натуральные то количество шагов не зависит от степени многочлена.

[TOTAL]

julinka в сообщении #1035333 писал(а):

А загадывает некоторый многочлен с натуральными коэффициентами. Б может называть значения аргумента (натуральное число) и получать в ответ значения многочлена на названных им числах.

Игрок Б получает ответ после каждого вопроса? Или после всех сразу?

[Cash]

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

[julinka]

Null в сообщении #1035469 писал(а):

С целыми коэффициентами никогда нельзя будет утверждать что мы получили правильный ответ.
А вот если коэффициенты натуральные то количество шагов не зависит от степени многочлена.

Чисто теоретически через, например, параболу может пройти секущая. т.е. у нас есть 2 точки и неопределенность - парабола это или прямая. Сейчас попробовала найти конкретный пример и не получилось.

Появилась такая мысль - что если мы задаем некоторые 2 точки, проводим через них параболу (с натур. коэфф.) и прямую. Но через любые две точки на параболе проходит прямая либо с целыми либо с действительными коэфф. То есть единственная прямая с натур. коэфф. которая проходит через указанную точку это касательная? И у нас никак не может быть что заданные 2 точки принадлежат прямой?

[TOTAL]

julinka в сообщении #1035478 писал(а):

Появилась такая мысль - что если мы задаем некоторые 2 точки, проводим через них параболу (с натур. коэфф.) и прямую. Но через любые две точки на параболе проходит прямая либо с целыми либо с действительными коэфф. То есть единственная прямая с натур. коэфф. которая проходит через указанную точку это касательная? И у нас никак не может быть что заданные 2 точки принадлежат прямой?

Какое отношение эта мысль имеет к решению задачи?

Сможете одним вопросом узнать сумму коэффициентов?

[julinka]

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

julinka в сообщении #1035478 писал(а):

Появилась такая мысль - что если мы задаем некоторые 2 точки, проводим через них параболу (с натур. коэфф.) и прямую. Но через любые две точки на параболе проходит прямая либо с целыми либо с действительными коэфф. То есть единственная прямая с натур. коэфф. которая проходит через указанную точку это касательная? И у нас никак не может быть что заданные 2 точки принадлежат прямой?

Какое отношение эта мысль имеет к решению задачи?

Сможете одним вопросом узнать сумму коэффициентов?

"И у нас никак не может быть что заданные 2 точки принадлежат прямой"
это значит что если мы задали 2 вопроса, то искомый многочлен - парабола (то есть не нужно задавать 3й вопрос для того, чтобы убедиться действительно ли это парабола или нет, как я предлагала ранее). Однако данное мнение ничем теоретически не подкреплено.

Да, конечно, сумму узнать можно (назвать в качестве аргумента 1 и получить $f(1)=a_k+a_{k-1}+...$, только их количество пока не представляю как определить по сумме.

[TOTAL]

julinka в сообщении #1035487 писал(а):

Да, конечно, сумму узнать можно (назвать в качестве аргумента 1 и получить $f(1)=a_k+a_{k-1}+...$, только их количество пока не представляю как определить по сумме.

А сможете затем назвать в качестве аргумента число, которое в сто раз больше суммы коэффициентов?