задачка, математическое

[avva]

Предположим, я загадал многочлен F(x) с целыми неотрицательными коэффициентами. Вы можете сказать мне любое рациональное число a, а я вам в ответ скажу F(a). Сколько таких попыток нужно вам, чтобы гарантированно отгадать многочлен?

Update: в комментах есть правильные ответы.

Comments

[(Anonymous)]

Пожалуй, от нескольких до бесконечности.

[valery-pavlov.livejournal.com]

А членов сколько?

[avva.livejournal.com]

Этого я не говорю.

[komprendre.livejournal.com]

две. сначала узнаем сумму коеффицентов k=F(1), а потом просим посчитать F(1/k).

[i_eron]

Замечательно!

[avva.livejournal.com]

Предположим, сумма коэффициентов равна 1.

[kukutz.livejournal.com]

7 и 1.469804...

[dmarck.livejournal.com]

Что-то подсказывает, что n+1, при этом две первые очевидны: ноль даёт свободный член, единица даёт сумму коэффициентов.

"На этом мысль останавливается" © ;-P

[altal.livejournal.com]

За два можно.
Первый вопрос про F(1).
Затем подбираем n, чтобы 10^n>F(1) и спрашиваем 1/10^n.

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

[avva.livejournal.com]

Ага, так можно.

[akalenuk.livejournal.com]

n+2?

[dimrub.livejournal.com]

I seem to remember the required number of trials is equal to the degree of the polynom.

[dimrub.livejournal.com]

Oops... Sorry, missed the part about integer coefficients.

[imfromjasenevo.livejournal.com]

подозреваю, что одна если туда например a=пи засунуть.

[toluca.livejournal.com]

Пи каплю НЕ рациональное.

[bukky-boogwin.livejournal.com]

Две. Сначала F(1) - число знаков в ответе будет больше или равно числу знаков в самом большом из коэффициентов. Потом F(0,1^(x+1)) или F(10^(x+1)), где x - то самое число знаков в первом ответе; в результате получим длинное число, состоящее из искомых коэффициентов многочлена, перемежаемых нулями (для этого и +1 - можно и без него, но так, имхо, удобнее).

[avva.livejournal.com]

Еще можно сделать чуть проще и экономнее, отказавшись от десятичной системы счисления.

[timur0.livejournal.com]

Две попытки:
1. F(1)

2. Выбираю n так, чтобы 10ⁿ > F(1) и спрашиваю F(10ⁿ)

В результате получаю длинное натуральное число, n младших разрядов это свободный член, следующие n разрядов это коэффициент при x и т.д.

[gulagly.livejournal.com]

чёт не пойму ведь вопрос про 100% получение F(x) - а при таком решении исключаются что нить типа ax+bx^2+cx^3...

[gulagly.livejournal.com]

N-1 попыток где N кол- во коэф-ов

[(Anonymous)]

Забавный вопрос на тему. Если разрешено называть иррациональные числа, можно ли угадать многочлен за одну попытку, но все же за конечное время? Скажем, загадывающий должен по заданному x называть цифры десятичной записи F(x) по очереди, а угадывающий должен в какой-то момент его остановить и назвать F. Интуитивно кажется, что да, возможно.

[avva.livejournal.com]

Думаю, что да: можно воспользоваться трансцедентным числом типа 0.101001000100001.... Чтобы изолировать коэффициенты, можно добавить еще нулей, если надо.

[zlyuk.livejournal.com]

похожая задача: отгадать вектор из N положительных целых чисел. Каждая попытка такова: отгадывающий называет вектор из N целых чисел, загадавший сообщает скалярное произведение названного вектора с загаданным.

[the-aaa13.livejournal.com]

А если ослабить требование о неотрицаетельности, то индейская народная изба?

[kadzekuma.livejournal.com]

скажем 3
одно из самых проситых это узнать свободный член F(0)
сумма коэффциентов равна единице, значит либо F(x)=1 либо F(x)=x.
но это только при условии что сумма равняется единице
дальше по ходу дела, ведь неизвестно есть ли нулевые коэффициенты.
общее решение пока не могу сообразить.

[(Anonymous)]

Две, я думаю. Одна, чтобы оценить коэффициенты (подойдёт a=1), а вторая, чтобы получить ответ, выписанный в строку (a= 10^N, где N достаточно большое). За одну не справиться -- сказав a=p/q, можно получить в ответ p^2 как результат F(x)=q^2 x^2, а можно как результат константы F(x)=p^2.

[burivykh.livejournal.com]

Опс -- разлогинился и не заметил...

[gaz-v-pol.livejournal.com]

Если известны f(1) и f(f(1)), то многочлен можно указать явно.



(под {x} понимается дробная часть числа x)

Это решение имеет изъян, оно не работает при f(1)=1, т.е. не различает 1, x, x^2, x^3 и т.д. Это можно разными способами исправить: заменить единицу на двойку, или f(f(1)) на f(1+f(1)), но тогда формула получается более длинной.

n+2

[nemirovd.livejournal.com]

* если неизвестна степень многочлена, то n+2.
* если известна, то n+1.

(Сторим матрицу линейного уранения и решаем уравнение степени k. Если уравнение не решается, то увеличиваем размер матрицы на 1.)

n+2

[nemirovd.livejournal.com]

n+1, если известа степень многочлена

кстати, коэффициенты могут быть любыми, хоть иррациональными

Re: n+2

[nemirovd.livejournal.com]

протупил *;-)

Задачи-предшественники

[knop.livejournal.com]

Как-то здесь еще не отмечали, что это разумное обобщение (в каком-то смысле даже переформулировка) широко известного фокуса с угадыванием ДВУХ задуманных двузначных чисел по результату вычисления 100a+b, и развития этого фокуса - когда задуманных чисел больше двух или когда их разрядность неизвестна.

Там тоже первым вопросом спрашивается сумма чисел, а дальше используется система счисления с основанием S+1.