2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

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

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 00:11 


09/07/15
8
Здравствуйте!

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

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

Также пыталась применить производные
$$f^{(k)}(x)=k!a_0$$,

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

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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 00:21 
Заслуженный участник
Аватара пользователя


09/09/14
6089
julinka в сообщении #1035333 писал(а):
Например, задал Б 3 вопроса, и пусть эти 3 точки лежат на одной прямой. Но ведь не факт, что загаданный многочлен 1 степени. Он может быть и 3-ей и 4-ой.

Вы думаете, что может? А попробуйте какой-нибудь пример руками подобрать. Только не забывайте про:
julinka в сообщении #1035333 писал(а):
многочлен с натуральными коэффициентами.

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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 01:34 
Заслуженный участник


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

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

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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 11:50 


09/07/15
8
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 точек составляем систему для параболы, находим ее коэффициенты и задаем еще один вопрос - проверяем принадлежит ли точка параболе и так далее...

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 12:06 
Заслуженный участник
Аватара пользователя


09/09/14
6089
julinka в сообщении #1035445 писал(а):
Не могли бы вы подсказать какие либо строгие мат. свойства по этому поводу?

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

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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 12:18 


09/07/15
8
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$, следовательно, функция выпукла вниз в этой области и перегибов нет?

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 12:22 
Заслуженный участник
Аватара пользователя


09/09/14
6089
julinka в сообщении #1035453 писал(а):
Правильно ли я поняла:...

Конечно.

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 12:50 


29/06/15
270
[0,\infty )
julinka в сообщении #1035445 писал(а):
беру и первого 1 монету из 2ого 2, из 3его 3 монеты,
Мало берете, потому и неоднозначность

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 14:15 
Заслуженный участник


12/08/10
1006
С целыми коэффициентами никогда нельзя будет утверждать что мы получили правильный ответ.
А вот если коэффициенты натуральные то количество шагов не зависит от степени многочлена. :-)

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 14:47 
Заслуженный участник
Аватара пользователя


23/08/07
4696
Нов-ск
julinka в сообщении #1035333 писал(а):
А загадывает некоторый многочлен с натуральными коэффициентами. Б может называть значения аргумента (натуральное число) и получать в ответ значения многочлена на названных им числах.
Игрок Б получает ответ после каждого вопроса? Или после всех сразу?

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 14:57 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 15:03 


09/07/15
8
Null в сообщении #1035469 писал(а):
С целыми коэффициентами никогда нельзя будет утверждать что мы получили правильный ответ.
А вот если коэффициенты натуральные то количество шагов не зависит от степени многочлена. :-)


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

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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 15:10 
Заслуженный участник
Аватара пользователя


23/08/07
4696
Нов-ск
julinka в сообщении #1035478 писал(а):
Появилась такая мысль - что если мы задаем некоторые 2 точки, проводим через них параболу (с натур. коэфф.) и прямую. Но через любые две точки на параболе проходит прямая либо с целыми либо с действительными коэфф. То есть единственная прямая с натур. коэфф. которая проходит через указанную точку это касательная? И у нас никак не может быть что заданные 2 точки принадлежат прямой?
Какое отношение эта мысль имеет к решению задачи?

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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 15:17 


09/07/15
8
TOTAL в сообщении #1035482 писал(а):
julinka в сообщении #1035478 писал(а):
Появилась такая мысль - что если мы задаем некоторые 2 точки, проводим через них параболу (с натур. коэфф.) и прямую. Но через любые две точки на параболе проходит прямая либо с целыми либо с действительными коэфф. То есть единственная прямая с натур. коэфф. которая проходит через указанную точку это касательная? И у нас никак не может быть что заданные 2 точки принадлежат прямой?
Какое отношение эта мысль имеет к решению задачи?

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


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

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

 Профиль  
                  
 
 Re: Определить степень и коэффициенты неизвестного многочлена
Сообщение10.07.2015, 15:21 
Заслуженный участник
Аватара пользователя


23/08/07
4696
Нов-ск
julinka в сообщении #1035487 писал(а):
Да, конечно, сумму узнать можно (назвать в качестве аргумента 1 и получить $f(1)=a_k+a_{k-1}+...$, только их количество пока не представляю как определить по сумме.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group