2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Попытка задач
Сообщение14.10.2010, 13:06 
Заслуженный участник


27/04/09
28128
Хорхе в сообщении #361824 писал(а):
А тут есть какой-то способ, кроме полного разумного перебора?
Не знаю. :-)

 Профиль  
                  
 
 Re: Попытка задач
Сообщение15.10.2010, 18:35 
Заслуженный участник


27/04/09
28128
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.$$

 Профиль  
                  
 
 Re: Попытка задач
Сообщение15.10.2010, 18:36 
Заслуженный участник
Аватара пользователя


03/02/10
1928
в полиа-сеге есть эта задача

 Профиль  
                  
 
 Re: Попытка задач
Сообщение15.10.2010, 18:48 
Заслуженный участник


27/04/09
28128
paha в сообщении #362441 писал(а):
в полиа-сеге
А где это? :oops:

 Профиль  
                  
 
 Re: Попытка задач
Сообщение15.10.2010, 19:05 
Заслуженный участник
Аватара пользователя


14/02/07
2648
arseniiv в сообщении #362453 писал(а):
paha в сообщении #362441 писал(а):
в полиа-сеге
А где это? :oops:

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение15.10.2010, 20:25 
Заслуженный участник


09/02/06
4401
Москва
Для этого все уравнения даже не нужны. Докажем вначале простую лемму
Если все $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$ можно разбирать отдельно.

 Профиль  
                  
 
 Re: Попытка задач
Сообщение16.10.2010, 09:16 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
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$-ая строка матрицы Вандермонда. Только непонятно, что это даёт. Пойду теорию читать :oops:

Руст в сообщении #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}$. Отсюда мораль...

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение18.10.2010, 19:36 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение18.10.2010, 20:12 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение18.10.2010, 20:19 
Заслуженный участник


27/04/09
28128
Кокой ужас. :mrgreen: Всё время я плошаю.

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

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение18.10.2010, 20:28 
Заслуженный участник
Аватара пользователя


14/02/07
2648
Что у Вас $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$ около двух (лень точно оценивать).

 Профиль  
                  
 
 Re: Попытка задач
Сообщение18.10.2010, 21:26 
Заслуженный участник


04/05/09
4589
Хорхе в сообщении #363343 писал(а):
Умножение двух $n$-битовых чисел занимает порядка $n^2$ операций.
Позвольте поправить Вас.
Сложность умножения через преобразование Фурье - $O(n \log n \log \log n)$.
Соответственно, число Фибоначчи можно вычислить за $O(n \log^2 n \log\log n)$.

 Профиль  
                  
 
 Re: Попытка задач
Сообщение18.10.2010, 22:43 
Заслуженный участник
Аватара пользователя


14/02/07
2648

(Оффтоп)

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

 Профиль  
                  
 
 Re: Попытка задач
Сообщение18.10.2010, 22:46 
Заслуженный участник


04/05/09
4589

(Оффтоп)

Хорхе в сообщении #363399 писал(а):
Я кагбэ себя и сам уже поправил.
Ага, но я уже написал. Не стирать же? ;-)

 Профиль  
                  
 
 Re: Попытка задач
Сообщение28.10.2010, 14:01 
Заслуженный участник


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

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

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



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

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


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

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