Категорія: Математичні головоломки

У деякому Королівстві прийшов час принцесі вибирати собі нареченого. У призначений день з’явилися 1000 принців. Їх побудували в чергу у випадковому порядку і стали по одному запрошувати до принцеси. Про будь-яких двох претендентів принцеса, познайомившись з ними, може сказати, який з них краще. Познайомившись з претендентом, принцеса може або прийняти пропозицію (і тоді вибір зроблений назавжди), або відкинути його (і тоді претендент втрачений: принци горді і не повертаються). Якої стратегії повинна дотримуватися принцеса, щоб з найбільшою ймовірністю вибрати кращого?
У 1960 році її придумав Мартін Гарднер, автор величезної кількості книг із захоплюючими завданнями і головоломками, пов’язаними з математикою. У 1963 році професор Євген Борисович Динкін запропонував рішення цієї задачі для окремого випадку саме в 1000 принців. Загальне рішення було знайдено студентом цього професора Сабіром Гусейн-Заде в 1966 році, який згодом і сам став доктором математичних наук. А дисертація Бориса Березовського на здобуття наукового ступеня доктора наук, захищена в 1983 році, є узагальненням задачі про розбірливу чи навіть перебірливу наречену.

Сформулюємо задачу таким чином:
Молодиця шукає собі нареченого (існує єдине вакантне місце).
Є відоме число n претендентів.
Про кожного претендента можна сказати, що він кращий чи гірший від іншого.
Молодиця спілкується з претендентами у випадковому порядку.
В результаті спілкування з кожним нареченим молодиця повинна йому відмовити або прийняти його пропозицію.
Рішення приймається тільки виходячи з оцінки претендента в порівнянні з попередніми.
Знехтувані женихи не повертаються.
Мета: вибрати найкращого претендента.
Припустимо, що принцеса пропустила 999 претендентів і зараз зустрічається з останнім. Тоді у неї немає ніякої альтернативи, все абсолютно ясно. Якщо останній і є найкращий, то принцеса виграла, домоглася свого, якщо він не найкращий, то принцеса програла і йде в монастир. У будь-якому випадку відкидати останнього претендента безглуздо, це до перемоги точно не приведе. Тепер припустимо, що принцеса знає, як поводитися на 601-му кроці. Спробуємо зрозуміти, що робити при зустрічі з 600-м, тобто за крок до цього. Ясно, що якщо 600-й претендент не краще за всіх попередніх, то і думати нічого, йому потрібно відмовляти. Взагалі в нашому завданні принцеса буде зупинятися тільки на тих, хто краще за всіх попередніх, інакше вона точно програє, адже її влаштовує тільки найкращий. Якщо ж він дійсно краще за всіх попередніх, то у принцеси є вибір. Наприклад, коли приходить перший, то, природно, він краще всіх попередніх, так як і попередніх-то ніяких не було, але зупинятися на ньому якось дуже дивно, шансів перемогти мало, з таким же успіхом можна і на десятому зупинитися, краще ще почекати хоч трохи, може, хто-небудь краще з’явиться. Отже, нехай 600-й краще за всіх попередніх, і принцесі потрібно оцінити (вона, напевно, і не може, але ж для цього математики і існують), що краще: вибрати цього самого 600-го або відмовити йому, перейти до наступного, а там, як ми пам’ятаємо, вже все відомо, зрозуміло, як потрібно чинити, і шанси на отримання кращого нареченого ми порахувати зможемо.
𝑛 – кількість женихів
𝑡 – номер кроку
𝑔(𝑡) – ймовірність перемоги в момент 𝑡 за умови, що 𝑡 – ий наречений краще за всіх попередніх
ℎ(𝑡) – ймовірність перемоги за умови, що наречена пропустить 𝑡 перших кандидатів і далі (починаючи з кроку 𝑡 + 1) буде діяти оптимально
Зауваження. ℎ(𝑡) монотонно не зростає
Отже, оголосимо для початку, що 1000 ми позначимо за n, тобто вирішимо завдання для довільної кількості претендентів. Далі, нехай принцеса знаходиться на кроці t (це номер кроку, тобто натуральне число). Перше, що їй потрібно знати — це ймовірність перемоги в разі вибору нареченого в момент t, за умови, що він краще всіх попередніх, тобто ймовірність того, що він не тільки краще всіх попередніх, а взагалі краще за всіх. Позначимо цю ймовірність за g(t) . Крім того, необхідно знати ще одну величину — це ймовірність того, що вона врешті-решт отримає найкращого нареченого, за умови, що вона пропустить перших t претендентів і далі буде користуватися оптимальною стратегією (тут мається на увазі наше припущення про те, що принцеса знає, як себе оптимально вести починаючи з кроку t+1). Позначимо цю ймовірність за h(t). Знаючи ці дві величини для будь-якого t, ми можемо легко зрозуміти оптимальну стратегію поведінки для принцеси: якщо на кроці t претендент не краще всіх попередніх, то, ясна річ, його потрібно відкинути, якщо ж він дійсно кращий серед перших t претендентів, то потрібно порівняти g(t) і h(t) , якщо більше g(t) , то потрібно зупинитися на претенденті t, якщо більше ht , то потрібно його відкинути і перейти до наступного, така стратегія випливає прямо з визначення цих ймовірностей. Що ж робити в разі рівності? Зрозуміло, що це неважливо, так як ймовірність перемоги в кожному з випадків однакова, тому давайте домовимося, що в разі рівності g(t) і h(t) принцеса буде, наприклад, весь час зупинятися на поточному претенденті.
Натуральний логарифм — це логарифм з основою e, де e — ірраціональна константа, що дорівнює приблизно 2,718281828.
Ймовірність успіху принцеси, яку ми шукали з самого початку, дорівнює 0,368. Таким чином, відповідь на поставлене спочатку завдання виглядає так: принцеса повинна спочатку пропустити першу e частина женихів (в разі t = 1000 це приблизно 368 чоловік), тільки запам’ятовуючи їх для майбутнього порівняння, а далі вона повинна брати в чоловіки першого ж, який володіє тією властивістю, що він краще за всіх своїх попередників. При цьому ймовірність отримати в кінці кінців найкращого нареченого з усіх t претендентів дорівнює приблизно 0,368.

Якщо подивитися на календар, та поставити собі питання на які дні тижня припадає 1 січня то можна прийти до висновку, що на всі дні по черзі.
А дослідники встановили що при теперішніх календарних правилах перший день сторіччя ніколи не припаде на неділю, середу чи п’ятницю.
Давайте спробуємо довести або спростувати цю тезу?

Згадаємо що, майже кожен рік, що ділиться націло на 4 є високосним. З цього правила є виключення.
Якщо рік ділиться націло на 100 – він не високосний. Але і з цього правила є виключення, – роки що поділяються націло на 400 – високосні.
1800, 1900 не були високосними, а ось 2000 – був.
В 20 сторіччі було 25 високосних років, так як 2000 був високосним. Тобто, 365*100+25=36525 днів. Або 5217 тижнів та 6 днів.
1 січня 1901 року – вівторок.
Тому 1 січня 2000 року було на 6 днів пізніше, та припало на понеділок.
В свою чергу, 1 січня 2101 року – субота, на 5 днів пізніше.
1 січня 2201 року – четвер, на 5 днів пізніше.
1 січня 2301 року – вівторок, на 5 днів пізніше.
І 1 січня 2401 року – понеділок, на 6 днів пізніше, бо 2400 – високосний.
Таким чином, легко бачити, що перші дні сторіччя циклічно повторюються: вівторок, понеділок, субота, четвер, і знову вівторок.
Тому нам не відсвяткувати початок сторіччя у п’ятницю )

9 жовтня 1926 року в газеті «The Saturday Evening Post» було надруковано невелике оповідання під назвою «Кокосові горіхи». Сюжет цієї розповіді зводився до того, що якийсь будівельний підрядник хотів будь-що-будь перешкодити своєму конкурентові отримати важливий замовлення. Винахідливий клерк підрядника, знаючи пристрасть конкурента до цікавої математики, підсунув тому задачу настільки захоплюючого змісту, що конкурент, цілком поглинений її рішенням, не подав заявку у встановлений термін і втратив контракт.
Ось це завдання в тому вигляді, як її сформулював клерк. П’ять матросів і мавпа після кораблетрощі висадилися на безлюдному острові. Весь перший день вони займалися збиранням кокосових горіхів. Увечері вони склали всі горіхи до купи і лягли спати. Вночі, коли всі заснули, один з матросів, вирішивши, що вранці під час розподілу горіхів може спалахнути сварка, встав, щоб взяти свою частку горіхів. Він поділив всі кокосові горіхи на п’ять рівних частин, а один горіх віддав мавпі. Потім матрос сховав свою частку, а всі інші горіхи знову склав до кучі. Через деякий час прокинувся інший «робінзон» і зробив те ж саме. У нього теж залишився один зайвий горіх, і він віддав його мавпі. І так один за одним вчинили всі п’ятеро. Кожен з них взяв собі одну п’яту горіхів з тієї купи, яку він знайшов при пробудженні, і кожен віддав один горіх мавпі. Вранці вони поділили залишки горіхів, і кожному дісталося порівну – по одній п’ятій частині. Зрозуміло, кожен з матросів не міг не знати, що частини горіхів не вистачає, але так як у кожного з них совість була однаково нечиста, тому жоден нічого не сказав. Скільки кокосових горіхів було спочатку?
Кажуть, що вже протягом першого тижня після публікації оповідання редакція отримала близько 2000 листів. Протягом ще 20 років редакція продовжувала отримувати листи з проханням повідомити відповідь, або з новими рішеннями. І сьогодні можна зустріти це завдання в збірках математичних головоломок. Задача про розподіл кокосових горіхах існувало і до 1926 року. Більш стара версія завдання майже повністю збігається з наведеною в оповіданні. Єдина відмінність полягає в тому, що вранці при остаточному розділі горіхів в старому варіанті завдання один горіх знову виявляється зайвим і дістається мавпі, в той час як в оповіданні остаточний поділ проводиться точно, без залишку.
Відповідь на задачу допускає нескінченно багато рішень в цілих числах. Наше завдання полягає в тому, щоб знайти серед них найменше позитивне число.

P.S. Число кокосових горіхів з задачі в газеті дорівнює 3121. З нашого відео розбору задачі відомо, що 5^5=3125, а 3125— 4 = 3121 є найменше число горіхів, яке можна п’ять разів ділити на п’ять рівних частин, віддаючи при кожному розподілі один кокосовий горіх мавпі. Після п’ятикратного поділу залишиться 1020 горіхів. Це число ділиться на 5, що і дозволяє зробити шостий поділ на п’ять рівних частин так, щоб мавпа не отримала жодного горіха.