Попытка задач

[arseniiv]

Хорхе в сообщении #361824 писал(а):

А тут есть какой-то способ, кроме полного разумного перебора?

Не знаю.

[arseniiv]

4. (Эта задача очень лёгкая, но мне интересно, как её поскорее решить без СКА.) Решите миловидную систему уравнений (решение ей соответствует):

$$\left\{\begin{array}{=} a_1 + a_2 + \ldots + a_n = 1 \\ a^2_1 + a^2_2 + \ldots + a^2_n = 1 \\ \vdots \\ a^n_1 + a^n_2 + \ldots + a^n_n = 1 \end{array}\right.$$

[paha]

в полиа-сеге есть эта задача

[arseniiv]

paha в сообщении #362441 писал(а):

в полиа-сеге

А где это?

[Хорхе]

arseniiv в сообщении #362453 писал(а):

paha в сообщении #362441 писал(а):

в полиа-сеге

А где это?

Где-где... В яндЕ(ксе)! "Задачи и теоремы из анализа".

[Руст]

Для этого все уравнения даже не нужны. Докажем вначале простую лемму
Если все $a_i\ge 0$ и выполняются $\sum_i a_i=1$ и $\sum_i a_i^2=1$, то все равны 0 за исключением одного, который равен 1.
Из первого следует, что $0\le a_i\le 1$. Тогда $a_i^2\le a_i$ равенство только в случае 0 или 1. Отсюда получаем доказательство леммы.
Взяв второе и четвертое уравнение получаем, что все $a_i^2=0$ за исключением одного. Привлекая уравнение с нечетным номером получаем, что единственный не равный нулю равен 1, а не -1.
Случаи $n<=3$ можно разбирать отдельно.

[Профессор Снэйп]

arseniiv в сообщении #362440 писал(а):

4. (Эта задача очень лёгкая, но мне интересно, как её поскорее решить без СКА.) Решите миловидную систему уравнений (решение ей соответствует):

$$\left\{\begin{array}{=} a_1 + a_2 + \ldots + a_n = 1 \\ a^2_1 + a^2_2 + \ldots + a^2_n = 1 \\ \vdots \\ a^n_1 + a^n_2 + \ldots + a^n_n = 1 \end{array}\right.$$

Здесь можно заметить, что $a_1v_1 + a_2v_2 + \ldots + a_nv_n = (1,1,\ldots,1)$, где $v_i = (1,a_i,a_i^2,\ldots,a_i^{n-1})$ --- $i$-ая строка матрицы Вандермонда. Только непонятно, что это даёт. Пойду теорию читать

Руст в сообщении #362508 писал(а):

Для этого все уравнения даже не нужны. Докажем вначале простую лемму
Если все и выполняются и , то все равны 0 за исключением одного, который равен 1.
Из первого следует, что . Тогда равенство только в случае 0 или 1. Отсюда получаем доказательство леммы.
Взяв второе и четвертое уравнение получаем, что все за исключением одного. Привлекая уравнение с нечетным номером получаем, что единственный не равный нулю равен 1, а не -1.
Случаи можно разбирать отдельно.
Для этого все уравнения даже не нужны. Докажем вначале простую лемму
Если все $a_i\ge 0$ и выполняются $\sum_i a_i=1$ и $\sum_i a_i^2=1$, то все равны 0 за исключением одного, который равен 1.
Из первого следует, что $0\le a_i\le 1$. Тогда $a_i^2\le a_i$ равенство только в случае 0 или 1. Отсюда получаем доказательство леммы.
Взяв второе и четвертое уравнение получаем, что все $a_i^2=0$ за исключением одного. Привлекая уравнение с нечетным номером получаем, что единственный не равный нулю равен 1, а не -1.
Случаи $n<=3$ можно разбирать отдельно.

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

-- Сб окт 16, 2010 13:31:06 --

Не, ну так то, решение, конечно, понятно. Образуем многочлен $(x-a_1)(x-a_2)\ldots(x-a_n)$, а затем из данной системы через теорему Виета выведем, что он равен $x^n - x^{n-1}$. Отсюда мораль...

Но поскольку это решение сразу очевидно, хочется чего-нибудь другого

[arseniiv]

5. Задача-конкурс. Придумайте алгоритм вычисления числа Фибоначчи (по его номеру, разумеется ), использующий только целые числа (могут быть специфические целочисленные операции) и как можно более быстрый. Желательно, чтобы промежуточные результаты всегда укладывались в ту же разрядную сетку, что и результат (а то я такое настряпал: $\sum_{j=-1}^{n-1}{C_n^{j+1} \left( \left( j+1 \right) \bmod 2 \right) 5^{j/2}} / 2^{n-1}$).

[Хорхе]

Хм, сдаётся мне, что самый быстрый способ -- по определению. Порядка $n^2$ битовых операций, что может быть лучше?

[arseniiv]

Кокой ужас. Всё время я плошаю.

-- Пн окт 18, 2010 23:23:03 --

Что, даже если учесть, что умножение по времени меньше $O(n)$ (где $n$ — любой множитель)?

[Хорхе]

Что у Вас $n$? У меня $n$ -- номер числа Фибоначчи (пропорционален количеству битов).

Умножение двух $n$-битовых чисел занимает порядка $n^2$ операций.


(Было подумалось, что через эту матрицу с тремя единичками и одним ноликом быстрее: ее можно свести к ЖНФ и считать "быстро". Но это не так, у нас получится эта ужасная формула Бине.)

-- Пн окт 18, 2010 21:41:15 --

Вообще, мне тут подсказывают, что мы числа умеем умножать довольно быстро. Тогда самый быстрый способ, по идее -- через вот эту самую матрицу $\left(\begin{smallmatrix}1 & 1 \\1 & 0\end{smallmatrix}\right)$. Где-то $n\ln^{a} n $, где $a$ около двух (лень точно оценивать).

[venco]

Хорхе в сообщении #363343 писал(а):

Умножение двух $n$-битовых чисел занимает порядка $n^2$ операций.

Позвольте поправить Вас.
Сложность умножения через преобразование Фурье - $O(n \log n \log \log n)$.
Соответственно, число Фибоначчи можно вычислить за $O(n \log^2 n \log\log n)$.

[Хорхе]

(Оффтоп)

Я кагбэ себя и сам уже поправил.

[venco]

(Оффтоп)

Хорхе в сообщении #363399 писал(а):

Я кагбэ себя и сам уже поправил.

Ага, но я уже написал. Не стирать же?

[arseniiv]

5. Заинтересовало. У нас есть автоматически смешивающая то, что внутри, коробка и в мешке различные попарно карточки в счётном количестве. В коробке лежит такая же на ощупь пустая карточка. Мы начинаем итерационный процесс ( ), на каждой итерации которого берём из коробки вслепую карточку, внимательно на неё смотрим и, если она пустая, кладём в коробку очередную карточку из мешка. Потом вынутую карточку кладём обратно. Вопрос: какова вероятность, что на $i$-ом ходу в коробке $k$ карточек? Каково математическое ожидание количества карточек в зависимости от итерации?