Примерно 40 лет тому назад М.Гарднер придумал такую задачу: "В некотором царстве, в некотором государстве пришло время принцессе выбирать себе жениха. В назначенный день явились 1000 царевичей. Их построили в очередь в случайном порядке и стали по одному приглашать к принцессе. Про любых двух претендентов принцесса, познакомившись с ними, может сказать, какой из них лучше. Познакомившись с претендентом, принцесса может либо принять предложение (и тогда выбор сделан навсегда), либо отвергнуть его (и тогда претендент потерян: царевичи гордые и не возвращаются). Какой стратегии должна придерживаться принцесса, чтобы с наибольшей вероятностью выбрать лучшего?". В 1965 году формулировку этой задачи и ее решение рассказал на своем семинаре Е.Б.Дынкин. Но его метод был необобщаем на другие варианты задачи: например, когда целью является выбор не наилучшего, а одного из трех лучших. В таком виде задача была решена автором при помощи метода, который легко переносится и на ряд близких...
Primerno 40 let tomu nazad M.Gardner pridumal takuju zadachu: "V nekotorom tsarstve, v nekotorom gosudarstve prishlo vremja printsesse vybirat sebe zhenikha. V naznachennyj den javilis 1000 tsarevichej. Ikh postroili v ochered v sluchajnom porjadke i stali po odnomu priglashat k printsesse. Pro ljubykh dvukh pretendentov printsessa, poznakomivshis s nimi, mozhet skazat, kakoj iz nikh luchshe. Poznakomivshis s pretendentom, printsessa mozhet libo prinjat predlozhenie (i togda vybor sdelan navsegda), libo otvergnut ego (i togda pretendent poterjan: tsarevichi gordye i ne vozvraschajutsja). Kakoj strategii dolzhna priderzhivatsja printsessa, chtoby s naibolshej verojatnostju vybrat luchshego?". V 1965 godu formulirovku etoj zadachi i ee reshenie rasskazal na svoem seminare E.B.Dynkin. No ego metod byl neobobschaem na drugie varianty zadachi: naprimer, kogda tselju javljaetsja vybor ne nailuchshego, a odnogo iz trekh luchshikh. V takom vide zadacha byla reshena avtorom pri pomoschi metoda, kotoryj legko perenositsja i na rjad blizkikh...
