Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.mccme.ru/circles/oim/materials/sbasympt.ps Дата изменения: Thu Apr 15 18:34:08 2004 Дата индексирования: Sat Dec 22 16:45:04 2007 Кодировка: koi8-r

Асимптотика.
Составитель Кудряшов Ю. Г.
Определения и полезные факты.
Определение 1. Говорят, что последовательность an > 0 растёт асимптотически не быстрее последователь-
ности b n > 0, если для любого " > 0 найдётся лишь конечное множество индексов k таких, что an > (1 + ")b n .
Обозначение: an . b n .
Определение 2. Говорят, что an  b n , если an =b n ! 1 при n !1.
Задача 1. Докажите, что если an . b n и b n . c m , то an . c n .
Задача 2. Докажите, что an  b n тогда и только тогда, когда an . b n и b n . an .
Определение 3. Говорят, что an  b n , если an =b n ! 0 при n !1.
Задача 3. Докажите, что если an . b n и b n  c m , то an  c n .
Задача 4. Докажите, что ln n  n  для любого  > 0.
Задача 5. Докажите, что n   a n для любых  > 0, a > 1.
Примеры применения.
Задача 6. Может ли конь обойти бесконечную шахматную доску, побывав на каждой белой клетке по одному
разу, а на каждой чёрной клетке по два раза?
Задача 7. На плоскости расположено 10 точек и 10 прямых. Докажите, что можно найти такую точку, рас-
стояние от которой до любой прямой будет меньше, чем до любой из точек.
Задача 8. Докажите, что если натуральные числа k 1 ; k 2 ; : : : ; k s таковы, что
1
k 1
+
1
k 2
+


+
1
k s
< 1;
то существует бесконечно много натуральных чисел, не представимых в виде n k1
1
+ n k2
2
+


+ n ks
s .
1