LINEBURG


<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

# A
1!
с координатами x, ! перейдёт в точку с координатами (1, 1),
!
x
# A # A
1! ! — в точку с координатами y, 1 !.
!
!  y!
а точка с координатами xy,  
xy
Значит, криволинейная трапеция под гиперболой от x до xy пе-
рейдёт в криволинейную трапецию от 1 до y. При этом, как мы
помним, площадь при проведённом нами преобразовании сохра-
няется, отсюда имеем равенство S(xy)?S(x)=S(y), что и требова-
лось. (Внимательный читатель помнит, что мы доказали инвари-
антность, т. е. неизменность, площади при таких преобразованиях
только для прямоугольника. Доказательство для криволинейных
фигур несколько сложнее и упирается непосредственно в определе-
ние площади, однако всё-таки факт остаётся верным и для криво-
линейной фигуры, если её площадь может быть сколь угодно точ-
но приближена суммарной площадью каких-нибудь покрывающих
эту фигуру прямоугольников.)
Такие свойства напоминают свойства одной из функций, хоро-
шо известных по школьной программе. Что же это за функция?
Логарифмическая! Сейчас мы это докажем.
В школе до логарифмической изучается сначала показательная
функция, являющаяся обратной к логарифмической. Давайте запи-
шем свойство обратной к S(x) функции, которую обозначим за F(x),
получающееся из уже известного четвёртого свойства самой S(x):
F(x+y)=F(x)·F(y). Отсюда тут же получаем, что F(x) — пока-
зательная. Действительно, пусть F(1)=a. Тогда F(2)=a2 , F(3)=
#A v
3 , F 1 ! = a=a1/2 , и т. д., для всех рациональных x имеем:
!
2!
=a
F(x)=ax . Поскольку F(x) монотонна (что следует из соответствую-
щего свойства функции S(x)), равенство F(x) и ax имеет место для
всех действительных чисел, откуда и получаем, что F(x)=ax для
всех x (доказательство, как видно, не совсем
y полное, предоставляем читателю возможность
y=F(x)
2
провести полное и строгое доказательство са-
a
мостоятельно). Эти рассуждения удобно вос-
принимать, имея перед собой картинку. Изо-
бразим графики функций S(x) и F(x) (рис. 18).
Кстати, легко доказать ещё одно интересное
свойство S(x), не имеющее, правда, непосред-
a ственного отношения к излагаемому матери-
y=S(x) алу. А именно, можно доказать (и это вид-
a1/2
но из рисунка), что функция S(x) бесконечно
возрастает, т. е. принимает сколь угодно боль-
x шие значения. Действительно, если S(2)=c,
O 11 2
2 то S(4)=2c, S(8)=3c, и вообще, S (2n )=n·c.
Поэтому S(x) неограниченно возрастает. От-
Рис. 18
16
y y y
а) б) в)




x 2 2,5 x x
O O O
1 2 1 1 2 3
Рис. 19


сюда мы получили интересный факт: площадь под гиперболой от 1
и до бесконечности сама бесконечна, что вообще говоря, не следу-
ет только из того, что эта фигура неограничена и бесконечно уда-
ляется вдоль оси Ox; существуют бесконечные фигуры с конечной
площадью.
Итак, мы доказали, что F(x)=ax . Отсюда получаем, что обрат-
ная к ней функция S(x)=loga (x). Что такое a? Это F(1), т. е. чи-
сло, для которого функция S(x) (обратная к F(x)) равна 1. Значит,
S(a)=1, т. е. a — то самое число, найти которое мы условились
ещё в самом начале поиска суммы S. Оно нам нужно было, что-
бы знать, когда принцессе делать свой выбор. Попробуем это чи-
сло оценить.
Для оценки числа a нужно пытаться оценивать различные пло-
1
щади под графиком y= . Посмотрим, например, на площадь кри-
x
волинейной трапеции под этим графиком от 1 до 2, которая изобра-
жена на рис. 19, а. Её площадь строго меньше площади квадрата,
изображённого на том же рисунке, а площадь квадрата — едини-
ца. Значит, S(2)<1 и поэтому a>2. Попробуем сравнить a и 2,5.
Для этого оценим площадь S(2,5), изображённую на рис. 19, б. Эта
площадь строго ограничена сверху суммарной площадью трапеции
и квадрата, изображённых на том же рисунке, а их площадь равна
3 1
+ =1, значит, S(2,5)<1 и a>2,5. Попробуем оценить a свер-
4 4
ху. Это несколько сложнее, потому что теперь нужно приближать
площадь фигурами, которые содержатся в криволинейной трапе-
ции, а не содержат её. Из рис. 19, в видно, что

1 1 1 1 1 1 1 1 1 1 1 1
+ + +++++> + + + +
S(3)>
12 11 10 9 8 7 6 5 12 10 10 10
1 1 1 1 70+252+105+120+140+168 855
++++= = >1,
8 7 6 5 840 840

поэтому a<3. Таким образом, мы только что установили, что a —
некоторое число из отрезка [2,5; 3]. Догадливые уже давно
17
p
поняли, что на самом деле чи-
1
сло a — не что иное, как из-
gt
вестное из школьного курса
или из курса математического
ht
1
анализа число e, равное при-
e
мерно 2,718281828...
Таким образом, стало по-
nt
1 ·n
e ht
нятно, когда =1 (в реаль-
gt
Рис. 20
ности этого, как мы помним,
скорее всего не случится, так как t целое, поэтому будет лишь
A
!
!
ht 1
n t
?1!. Это происходит, когда =e или = . Вспомним наш ри-
!

g t n e
t
сунок, на котором были изображены графики функций ht и gt
(рис. 20).
Как мы только что выяснили, то число, которое соответствует
n
точке пересечения на графике, равно t= . При этом
e

1
t
ht =gt = = ,
n e

т. е. вероятность успеха принцессы, которую мы искали с само-
1
?0,368. Таким образом, ответ на поставленную
го начала, равна
e
вначале задачу выглядит так: принцесса должна сначала пропу-
1
стить первую часть женихов (в случае n=1000 это примерно 368
e
человек), только запоминая их для будущего сравнения, а дальше
она должна брать в мужья первого же, который обладает тем свой-
ством, что он лучше всех своих предшественников. При этом веро-
ятность получить в конце концов самого лучшего жениха из всех
n претендентов равна примерно 0,368.

***
Как уже говорилось выше, здесь был рассказан метод решения
задачи, отличный от первоначального, придуманного Е. Б. Дынки-
ным. Этот метод довольно легко обобщается на ряд близких задач.
Например, можно предположить, что принцесса не настолько при-
вередлива, чтобы требовать только самого лучшего жениха, а её
устроит и второй по качеству или, например, один из трёх луч-
ших. В более общем случае она ставит своей целью выбор одного
18
из m лучших женихов (m — фиксированное заранее число), при
этом какой именно из этих m женихов ей достанется — безраз-
лично. (Задача, которую мы подробно рассмотрели, соответствует
m=1.)
Ещё более общей постановкой (чуть более сложно формулиру-
емой) является следующая. Принцесса заранее решает, насколько
счастлива (удовлетворена) она будет, если ей достанется k-й по ка-
честву среди всех женихов. При этом уровень её удовлетворения
может измеряться в баллах или в условных единицах (не путать
с у. е. в магазинах). Естественно предполагать, что уровень сча-
стья тем выше, чем лучше жених (в смысле его рейтинга в об-
щем смысле). Так, принцесса может решить, что если ей достанет-
ся самый лучший жених, она будет счастлива на 1000 баллов, ес-
ли второй по качеству — на 500, третий — на 330 и т. п. Опти-
мальной в этом случае является стратегия принцессы, при кото-
рой в среднем количество полученных ей баллов было бы макси-
мально возможным. Некоторую сложность здесь составляет объяс-
нить, что значит <в среднем>. В теории вероятностей понятие сред-
него (или, как его ещё называют, математического ожидания)
определяется через понятие вероятности. Мы здесь не обсужда-
ли определение вероятности, предпочитая использовать некоторые
её свойства, объясняемые <на пальцах>. Поэтому определять по-
нятие среднего, описывать его свойства и обсуждать сколь-нибудь
подробно последнюю постановку задачи представляется несколько
затруднительным. (Впрочем, в описанной ситуации средний балл
равен сумме
?
n
bi pi ,
i=1

где pi — вероятность того, что выбранный жених окажется i-м
по качеству среди всех претендентов, а bi — количество баллов
<зарабатываемых> в этом случае.)
Поэтому ограничимся случаем, когда принцесса хочет полу-
чить одного из m лучших женихов, неважно какого. Схема, опи-
санная выше, будет работать следующим образом. Если принцес-
са дождалась последнего — n-го претендента, её стратегия оче-
видна. Если он оказался одним из m лучших, она его выбирает
и она выиграла. Если нет, она проиграла (и отправляется в мо-
настырь). Предположим, что мы уже разобрались как должна ве-
сти себя принцесса, если она не сделала выбора до t-го претенден-
та включительно. Пусть перед ней предстал t-й претендент. Обо-
значим через ht вероятность того, что принцесса сделает удачный
выбор, если она откажет t-му претенденту, а дальше будет поль-
зоваться оптимальной стратегией (мы предположили, что эта стра-
тегия уже известна). Вероятность ht , конечно, не зависит от того,
19
какой по рангу среди предшествующих был t-й претендент: пер-
вый, последний, ... А вот вероятность того, что принцесса вы-
играет, остановив свой выбор как раз на t-м претенденте, от этого
зависит. Если он был хуже, чем m-й (по качеству) среди уже про-
шедших, никаких шансов, что принцесса выиграет, выбрав его,
нет. Если он лучший среди первых t, то вероятность сделать
удачный выбор, остановившись на нём, по-видимому, выше, чем
если он второй (по качеству) среди них. Обозначим через gt (k)
вероятность удачи, если принцесса остановит свой выбор на t-м
претенденте при условии, что он является k-м по качеству среди
первых t. Здесь k может быть любым (целым) числом от 1 до t, од-
нако, очевидно, что если k>m, то gt (k)=0. Мы знаем (см. выше),
что gn (k)=1 при k?m и gn (k)=0 при k>m.
Одна из стратегий принцессы, отвергнувшей t-го претенден-
та (возможно, и даже вероятно, не оптимальной), является от-
каз (t+1)-му претенденту в любом случае. Отсюда следует, что
вероятность ht (которая равна вероятности удачного выбора при
оптимальном поведении принцессы после того, как был отвергнут
t-й претендент), по крайней мере не меньше, чем вероятность ht+1
(вероятность удачного выбора, если и (t+1)-й претендент отверг-
нут): ht ?ht+1 .
Попробуем разобраться как ведёт себя вероятность gt (k) как
функция от t и k. Более-менее очевидно следующее. Во-первых,
при фиксированном t вероятность gt (k) не возрастает с ростом k,
т. е. она тем больше (или, точнее, не меньше), чем меньше k.
Во-вторых, при фиксированном k вероятность gt (k) не убывает
с ростом t: при выборе из 1000 претендентов лучше остановиться
на третьем по качеству среди прошедших, если таковым оказал-
ся 990-й, чем если таковым оказался 10-й (здесь, конечно, пред-
полагается, что m?3). Строго эти свойства могут быть выведены
из равенств (*) и (**) ниже.
Если мы (или, точнее, принцесса) уже знаем ht и gt (k), то,
как это нетрудно понять из рассуждения, приведённого выше для
m=1, оптимальная стратегия выглядит следующим образом. Пред-
положим, что перед принцессой предстал t-й претендент на её ру-
ку (предыдущих t?1 она отвергла) и он оказался k-м по каче-
ству среди первых t. Тогда принцесса сравнивает вероятности ht
и gt (k). Если вероятность ht оказалась больше, то она претендента
отвергает. Если больше оказалась вероятность gt (k), она даёт ему
своё согласие. (Если случайно оказалось, что вероятности ht и gt (k)
в точности равны, то она может поступить любым образом. Выше
в подобной ситуации мы предлагали принцессе не тянуть время,
а принять предложение претендента.) Вероятность успеха принцес-
сы в этом случае оказывается равной max(ht , gt (k)) (наибольшему
из двух указанных чисел). Кстати, нетрудно сообразить, что ис-
20
ходная вероятность успеха принцессы (до начала смотрин) может
быть вычислена как h0 .
Из описанных выше свойств монотонности вероятностей ht
и gt (k) как функций от t и k (невозрастание ht с ростом t, неубыва-
ние gt (k) с ростом t и её невозрастание с ростом k) вытекает следу-
ющее общее описание оптимальной стратегии. Существуют неотри-
цательные (целые) числа t1 ?t2 ?...?tm <n (зависящие от n и m),
через которые оптимальная стратегия описывается так. Принцесса
должна пропустить первые t1 человек, не давая согласия на брак
ни в коем случае (только оценивая их для будущего сравнения
с остальными). Претенденту с номером от t1 +1 до t2 она даёт со-
гласие на брак если (и только если) он лучше всех предыдущих.
Претендента с номером от t2 +1 до t3 она выбирает, если он не ху-
же чем второй по качеству среди всех прошедших (включая его
самого), и т. д. Претендента с номером больше tm она выбирает,
если он оказывается одним из m лучших среди прошедших. Если
претендент, удовлетворяющий описанным свойствам, не встретит-
ся, то принцесса проиграла.
Возникает естественный вопрос: как могут быть найдены ве-
роятности ht и gt (k)? Их, как и раньше, можно вычислить по-
следовательно (начиная с конца!). Очевидно, что hn =0, gn (k) рав-
но единице при k?m, и нулю при k>m. Предположим, что мы
уже знаем (вычислили) вероятности ht+1 и gt+1 (k) для всех k. Вы-
числим ht . (В этом месте можно даже допустить, что t=0. В ре-
зультате мы получим вероятность h0 , которая равна абсолютной
вероятности успеха принцессы на момент начала смотрин.) Если
принцесса пропустила t-го претендента, перед её глазами пред-
стаёт (t+1)-й. Он может быть лучшим среди всех предыдущих
(включая, естественно, его самого), либо вторым по качеству, либо
третьим, и т. д., вплоть до (t+1)-го. Легко сообразить, что веро-
1
ятность каждого из этих случаев одна и та же и равна . Если
t+1
(t+1)-й претендент оказался k-м по качеству, вероятность успеха
принцессы при оптимальной стратегии выбора равна, как мы зна-
1
ем, max(ht+1 , gt+1 (k)). Таким образом, с вероятностью вероят-
t+1
ность успеха равна max(ht+1 , gt+1 (1)), с той же вероятностью она
равна max(ht+1 , gt+1 (2)), и т. д. Применяя обсуждавшуюся выше
формулу полной вероятности, получаем, что
?
t+1
1
ht = max(ht+1 , gt+1 (k))=
t+1 k=1
?
m
1 t+1?m
= max(ht+1 , gt+1 (k))+ (*)
ht+1
t+1 k=1 t+1
21
(последнее равенство имеет место, поскольку при k>m заведомо
gt+1 (k)=0 и, значит, max(ht+1 , gt+1 (k))=ht+1 ).
Обсудим теперь вычисление вероятностей gt (k). Предположим,
что принцесса решила остановить свой выбор на претенденте с но-
мером t, который оказался k-м по качеству среди предыдущих
(включая его самого). Чтобы вычислить вероятность её успеха,
представим себе, что (уже сделав свой выбор) принцесса решила
(любопытства ради) посмотреть и на (t+1)-го претендента. С ве-
1
роятностью этот претендент оказался бы самым лучшим
t+1
1
из прошедших, с вероятностью — вторым, и т. д. В списке
t+1
из первых t+1 претендентов избранник принцессы (предложение
которого она уже приняла на предыдущем шаге) может либо сохра-
нить свои позиции и остаться k-м по качеству, либо уступить одну
позицию в рейтинге и оказаться (k+1)-м. Легко видеть, что веро-
ятность второго исхода (избранник теряет свои позиции и оказы-
k
вается (k+1)-м в списке из t+1 претендентов) равна (это —
t+1
вероятность того, что (t+1)-й претендент окажется не хуже чем
k-м по качеству), а вероятность первого исхода (избранник сохра-
t?k+1
няет свои позиции) равна . Нетрудно сообразить, что при
t+1
первом исходе вероятность успеха принцессы оказывается равной
gt+1 (k), а при втором — gt+1 (k+1). Применяя всё ту же формулу
полной вероятности, получаем
t?k+1
k
gt (k)= gt+1 (k+1)+ gt+1 (k). (**)
t+1 t+1
Формулы (*) и (**) позволяют последовательно, начиная с кон-
ца, т. е. с t=n, вычислить вероятности ht и gt (k) и, таким обра-
зом, найти оптимальную стратегию принцессы. Для небольших n
это можно сделать, например, заполняя таблицу вроде той, кото-
рая приведена на рис. 21 для n=9, m=2.
Из таблицы и графика, изображённого на рис. 22, можно
увидеть, что в указанном случае t1 =3, t2 =6, т. е. оптимальная
стратегия принцессы состоит в том, чтобы отвергнуть первых трёх
претендентов в любом случае, остановить свой выбор на четвёртом,
пятом или шестом, если он окажется лучше всех предыдущих,
а далее (т. е. при знакомстве с претендентами, начиная с седьмого)
соглашаться и на второго по качеству среди прошедших. При этом
вероятность удачного выбора (h0 ) оказывается равной
233
?0,65.
360
22
k
E
"
"
"
" 2 5 7 13 5 11 35
"
" 1 1 1
"
" 9 12 12 18 6 12 36
"
gt (k): $
"
"
"
"
" 1 1 1 5 5 7 7
"
"
" 2 0 1

<< Пред. стр.

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

ОГЛАВЛЕНИЕ

След. стр. >>

Copyright © Design by: Sunlight webdesign