LINEBURG


<< Пред. стр.

страница 2
(всего 4)

ОГЛАВЛЕНИЕ

След. стр. >>

победы в этих случаях совершенно одинакова и совпадает с ht .
1
Таким образом, заключаем, что до момента t1 функция ht оста-
ётся постоянной и имеет вид, примерно изображённый на рис. 6.
Для решения задачи осталось только посчитать ht , а значит,
и t1 , чем мы сейчас и займёмся. Делать это мы тоже будем с кон-
ца, причём в силу вышеприведённого замечания будем считать ht
только для t?t1 . Как уже отмечалось, hn =0 (рис. 7). Посмотрим,


0
ht

t n?3 n?2 n?1 n
Рис. 7
9
1
0
ht
n

t n?3 n?2 n?1 n
Рис. 8

что у нас с hn?1 . Это вероятность того, что принцесса получит луч-
шего жениха, если пропустит (n?1)-го претендента. Но это про-
изойдёт в единственном случае — если последний окажется лучше
1
всех. Вероятность этого мы уже считали. Она равна (рис. 8). По-
n
пробуем разобраться с hn?2 . Здесь будет уже не столь простая вы-
кладка. Предположим, что принцесса пропустила претендента с но-
мером n?2 и дальше действует по оптимальной стратегии. Тогда
возможны два варианта: (n?1)-й является лучшим среди первых
n?1 претендентов (вероятность этого, как уже неоднократно отме-
A
1! ! и (n?1)-й не является лучшим среди первых
!
n?1 
чалось, равна
# A
n?2 !!.
!
n?1 претендентов вероятность этого, соответственно, равна
n?1 
В первом случае очевидно, что этого последнего нужно брать, это
соответствует оптимальной стратегии (напомним, что мы догово-
рились вычислять ht в предположении, что t?t1 ), причём веро-
n?1
ятность победы просто равна gn?1 = . Во втором случае прин-
n
цесса должна автоматически отказать царевичу, и тогда шансы
1
на победу равны hn?1 = . По уже обсуждавшейся формуле полной
n
вероятности получаем, что
1 n?2 1 (n?2)+(n?1)
n?1
· ·=
hn?2 = +
n?1 n n?1 n n(n?1)
(оставим пока это в таком виде, рис. 9).
Сформулировать гипотезу насчёт общего вида ht пока затруд-
нительно. Однако нам всё равно придётся потом сравнивать ht и gt .
ht
Сделать это можно, к примеру, проследив за величиной . Если
gt
она больше 1, то ht больше, чем gt , если она меньше 1, то, соответ-
ственно, наоборот, gt больше ht . Поделив числа из таблицы рис. 9

(n?2)+(n?1) 1
0
ht
n(n?1) n

t n?3 n?2 n?1 n
Рис. 9
10
ht 1 1 1
+ 0
gt n?2 n?1 n?1

t n?3 n?2 n?1 n
Рис. 10

на числа из таблицы рис. 4, несложно получить результаты, пред-
ставленные на рис. 10 (проделайте это!). Закономерность, бросаю-
щаяся в глаза при рассмотрении этих данных, неслучайна. Давай-
те попробуем доказать, что
# A
1!!
t1 1 !
ht = ·  +
n?1 
+...+
nt t+1
(здесь мы использовали уже известный нам факт о том, что gt =
A
t!
= !. Будем рассуждать по индукции с конца. База (t=n, n?1
!
n
и n?2) у нас есть. Предположим, что для ht формулу мы уже
получили, получим её для ht?1 . Итак, пусть на шаге t?1 прин-
цесса пропустила претендента и перешла на шаг t. Тогда воз-
можны два случая: t-й претендент может оказаться лучше всех
# A
1!
предыдущих  вероятность этого равна ! и может не оказаться
!
t
# A
t?1 !
!. В первом случае вероятность
!
таковым  вероятность этого
t
t
в итоге победить равна =gt (потому что, напомню, мы счита-
n
ем ht для тех t, которые больше t1 , а для них оптимальная стра-
тегия поведения принцессы заключается в том, чтобы выбирать
претендента в женихи, как только он лучше всех предыдущих).
Во втором случае вероятность итоговой победы принцессы равна
# A
1!!
t1 1 !
ht = ·  +
n?1 
+...+
nt t+1
(эта формула нам уже <известна> по предположению индукции).
Таким образом,
# A
1! !=
1t t?1 t 1 1 !
ht?1 = · + · +
n?1 
+...+
tn t nt t+1
# A
1! !
1 t?1 1 1
 t + t+1 +...+ n?1 ! = 
=+
n n
# A
1! !=
t?1 1 1
t?1 !
n t n?1 
= + + +...+
n(t?1) t+1
# A
1! !.
1 1 1
t?1 !
n  t?1 n?1 
= ++ +...+
t t+1
Формула для ht доказана.
11
Теперь для окончательного решения задачи нужно сравнить
ht и gt . Чтобы это сделать, мы некоторое время назад пытались
ht
сравнить величину с единицей. Как сейчас уже понятно, для
gt
t?t1 имеет место формула
ht 1 1 1
=+ +...+ .
gt t t+1 n?1

Поэтому способ нахождения t1 нами получен: нужно, постоянно
1
уменьшая t, складывать , начиная с t=n?1, пока сумма не ста-
t
нет больше 1; то самое t, при котором это произойдёт, и есть t1
(а при каком-то t это заведомо произойдёт, если конечно у нас
не крайний случай и n не равно 1, впрочем, в этом случае у прин-
1 1
цессы нет никаких проблем). Например, если n=5, то + <1,
4 3
1 1 1
а + + >1, т. е. стратегия такая: первого пропустить, второ-
4 3 2
го пропустить, а дальше, начиная с третьего, брать в мужья пер-
вого попавшегося, который лучше всех предыдущих. Такой способ
в принципе всегда может привести к ответу, но всё же хотелось бы
ещё упростить его, тем более что, как сейчас окажется, это дей-
ствительно возможно. Попробуем посчитать сумму, которая у нас
ht
записана в правой части формулы для . При этом сразу необ-
gt
ходимо оговориться, что сумму эту мы будем считать лишь при-
ближённо, а для этого требуется предположить, что и t, и n — до-
статочно большие числа (в оригинале задача была сформулирова-
на для большого n=1000, а из предыдущих рассуждений следует,
что t1 — также большое, поэтому наше предположение оправдано).
1 1 1
Итак, будем считать сумму S= + +...+ . Для нача-
tt+1 n?1
1
ла сделаем следующее. Нарисуем график функции y= . Отметим
x
на нём точки с абсциссами t, t+1, t+2, ..., n. А дальше будем
рисовать прямоугольники. Первый расположен между t и t+1,
1
причём его основание лежит на оси Ox, а высота равна . Второй
t
расположен аналогичным образом между t+1 и t+2, а его вы-
1
сота равна . Аналогично третий, четвёртый, и т. д., послед-
t+1
ний будет расположен между n?1 и n (рис. 11). Прямоугольников
будет много, потому что, как мы помним, t и n — большие числа.
12
y
y
y= 1
x

y= 1
x



x x
O O
t n
Рис. 11 Рис. 12


Заметим следующее: площадь изображённой фигуры, являю-
щейся объединением всех прямоугольников, в точности равна сум-
ме S, которую нам нужно посчитать.
Теперь будем делать совсем странные вещи. Нарисуем опять
1
отдельно график функции y= (рис. 12). Сделаем с ним такую
x
операцию: сожмём его вдоль оси Ox в 10 раз. Что это значит?
А просто приблизим каждую точку графика к оси Oy на расстоя-
ние, в 10 раз меньшее того, на котором она находится от этой оси
сейчас (точка при этом будет двигаться вдоль оси Ox, поэтому та-
кое преобразование и называется сжатием). График станет узень-
ким, прижимающимся к осям координат (рис. 13). Теперь растя-
нем получившийся график вдоль оси Oy в 10 раз, т. е. удалим
каждую точку графика от оси Ox на расстояние, в 10 раз большее
того, на котором она находится от этой оси сейчас (рис. 14). Спра-
шивается, что же у нас получилось? Оказывается, что после этих

y y
а) а)
растяжение
в 10 раз




сжатие
в 10 раз



x x
O O
y y
б) б)




x x
O O
Рис. 13 Рис. 14
13
1
двух преобразований график функции y= переходит сам в себя,
x
1
т. е. в график функции y= . Действительно, после первого пре-
x
# A
1!
образования точка графика с координатами x, ! переходит в точ-
!
x
# A
!
x 1!
ку с координатами  , !, а уже эта точка после второго преобра-
10 x 
# A
x 10 !
!, которая лежит на исходном
!
зования переходит в точку  ,
10 x 
графике. (На самом деле мы лишь проверили, что точки исходно-
го графика переходят в какие-то другие точки исходного графи-
ка, но мы не проверили, что каждая точка графика является обра-
зом какой-то точки, т. е. что в каждую точку графика перешла
какая-то другая. Однако важно только понимать, что эта провер-
ка необходима, так как проделать её можно абсолютно аналогично
той, которую мы провели.)
Добавим к исходному графику фигуру из прямоугольников
(см. рис. 11) и проделаем те же операции. Что произойдёт с графи-
ком, мы уже знаем. Перейдёт в себя. А вот что произойдёт с фи-
гурой? Понятно, что она как-то будет сжиматься и растягиваться,
поэтому форму не сохранит. Но зато можно смело утверждать, что
её площадь (как раз то, что нас интересует) не изменится. Действи-
тельно, возьмём один какой-нибудь прямоугольник из этой фигу-
ры. Сначала первым преобразованием мы его площадь уменьша-
ем в 10 раз, а потом вторым увеличиваем в 10 раз, т. е. она ста-
новится такой же, как и была. Значит, и площадь всей фигуры
не меняется.
Для чего же нам всё это было надо? Вот для чего. Сделаем
опять те же операции с картинкой на рис. 11, но только сжи-
мать и растягивать будем не в 10, а в t раз. Посмотрим, что по-
лучится. Если раньше мы изображали график с непонятными мас-
штабами по осям, потому что, с одной стороны, t — очень боль-
1
шое, — очень маленькое, и адекватно их изобразить сложно,
t
а с другой стороны, хочется иметь хоть сколько-нибудь наглядную
картинку, то теперь можно спокойно объявить Aмасштабы по осям
#
1!
равными, так как точка с координатами t, ! переходит в точ-
!
t
ку с координатами (1, 1). Все прямоугольники теперь очень узень-
1
кие, ширины (потому что t — большое), расположены они от 1
t
n
до (рис. 15). Из-за того, что все прямоугольники такие узень-
t
кие, та часть фигуры, которая расположена над гиперболой (гра-
14
y y
y= 1 y= 1
x x


1 1

S(x)
S(x)
S(x)
S(x)
n x x
O O
1 1 x
t
Рис. 15 Рис. 16

A
1!
фиком функции y= !, имеет очень маленькую площадь, поэтому
!
x
площадь фигуры, равная нашей сумме S, практически в точности
n
равна площади под гиперболой от 1 до . Введём обозначение: бу-
t
дем обозначать через S(x) площадь криволинейной трапеции, огра-
ниченной гиперболой, от 1 до x (рис. 16). Таким образом, имеем:
#A
n!
S?S  !. Наша задача, напомню, заключается в том, чтобы найти
!
t
первое такое t, что сумма S для него больше 1. Это, как только что
стало понятно, равносильно задаче о решении уравнения S(x)=1.
Для решения этого уравнения попробуем сначала выяснить
некоторые свойства функции S(x). Первое очевидное свойство за-
ключается в том, что S(1)=0. Действительно, при x=1 криво-
линейная трапеция вырождается в отрезок, а его площадь —
ноль. Второе свойство: при x>1 выполняется неравенство S(x)>0.
Третье свойство заключается в том, что функция S(x) монотонно
возрастает. Четвёртое свойство ключевое: утверждается, что для
любых x, y>1 имеет место равенство S(xy)=S(x)+S(y). Для дока-
зательства сначала изобразим, что эта формула означает. Нарисуем
1
в который раз уже график функции y= , отметим на нём точки
x
с абсциссами 1, x, y и xy (рис. 17). Заметим, что площадь криволи-
нейной трапеции от x до xy в точ- y
ности равна S(xy)?S(x) (по опре-
y= 1
делению функции S(x)). Теперь x
сделаем такое преобразование
всей картинки: сначала сожмём 1
её вдоль оси Ox в x раз, а потом
растянем вдоль оси Oy в x раз.
Как мы помним, при таком пре- O x
1 x y xy
образовании график перейдёт
сам в себя. Кроме того, точка Рис. 17
15

<< Пред. стр.

страница 2
(всего 4)

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign