en   ua   🔍

Challenge


Тут будуть сформульовані деякі задачі та питання (як відомі так поки що і не розв'язані). Більшість задач і питань призначені для студентів, але деякі задачі будуть цікаві і професіоналам (знавцям теорії ймовірностей, матстату тощо), тому, якщо у Вас є бажання обговорити ту чи іншу задачу – пишіть чи приходьте.


Отже, першою розглянемо задачу про ханойські вежі. Формулюється вона дуже просто – є три стрижні, на одному з яких N дисків різного діаметру. Треба перекласти всі диски на третій стрижень, використовуючи другий як допоміжний, дотримуючись двох умов, по-перше, перекладати можна тільки по одному диску, а по-друге, ніколи більший диск не повинен бути над меншим. Розв'язання цього завдання відоме, тобто, відомий і алгоритм перекладання дисків (як рекурсивний, так і нерекурсивний) і навіть найменша необхідна кількість перекладань. Питання: а скільки в середньому буде зроблено перекладань, якщо людина, яка їх робить, не знає алгоритму і перекладає диски виключно навмання, дотримуючись при цьому двох вищевказаних правил? Спробуйте розв'язати цю задачу і отримати відповідь у явному вигляді для \(N = 3\) або \(N = 4\), а якщо зможете, то і для \(N = 24.\)


Проста задача. У турнірі кожна команда зіграла з кожною іншою командою по одному разу, причому 25% команд жодного разу не виграли. Скільки команд брало участь у турнірі?


У літак, в якому 100 місць, збираються в порядку черги зайти 100 пасажирів, першою з яких стоїть бабуся, яка сідає на перше-ліпше місце, тобто навмання обирає собі місце. Інші пасажири поводяться нормально, тобто займають місця згідно з купленими квитками, і тільки якщо чиєсь місце вже зайняте, він займає будь-яке з вільних місць. Яка ймовірність того, що останній, хто стоїть у черзі, займе своє законне місце? Як зміниться розв'язок, якщо розглянути іншу кількість пасажирів (за умови, що кількість місць завжди дорівнює кількості пасажирів)?


Яка ймовірність того, що серед навмання розставлених в ряд чисел від \(1\) до \(n\) жодне число не займе місце зі своїм номером?


Скільки є різних способів зафарбувати 8 клітин у таблиці \(5\times 4\) так, щоб у кожному рядку та в кожному стовпці була хоч одна зафарбована клітина?


Задача Ейнштейна. Є 5 будинків 5 різних кольорів. У кожному будинку живе по одній людині 5 різних національностей. Кожен п'є один і той самий напій, курить певну марку сигарет і тримає певну тварину. (Колір будинку, національність, напій, марка сигарет і тварина не повторюються). Питання: кому належить риба?
Умови:
1) Англієць живе в червоному будинку;
2) Швед тримає собаку;
3) Датчанин п'є чай;
4) Зелений будинок стоїть ліворуч від білого;
5) Мешканець зеленого будинку п'є каву;
6) Людина, яка курить Pall Mall, тримає птаха;
7) Мешканець із середнього будинку п'є молоко;
8) Мешканець із жовтого будинку курить Dunhill;
9) Норвежець живе в першому будинку;
10) Курець Marlboro живе поруч із тим, хто тримає кота;
11) Людина, яка тримає коня, живе поруч із тим, хто курить Dunhill;
12) Курець сигарет Winfield п'є пиво;
13) Норвежець живе поруч із блакитним будинком;
14) Німець курить Rothmans;
15) Курець Marlboro живе по сусідству з людиною, яка п'є воду.

Ейнштейн придумав цю задачу на початку минулого століття і вважав, що лише 2% мешканців Землі зможуть її розв'язати. Розв'язавши цю задачу, спробуйте відповісти на складніші питання:
I.   Яку одну з 15 умов можна прибрати так, щоб задача мала єдину ту саму відповідь?
II.  Скільки різних відповідей існує на попереднє питання?
III. Яке максимальне число умов (і яких саме) можна прибрати, щоб задача мала єдину ту саму відповідь?


Спробуйте отримати точну відповідь в задачі про мости для \(m = 4, n = 5.\)


Для \( 0 \lt t \lt 1 \) знайти \[ \int\limits_{0}^{\pi } { \int\limits_{\max \left\{ -1;\ \cos x-\frac{t}{\sin x} \right\}}^{\cos x} { \frac{dy}{\sqrt{1-{y^2}}}dx. } } \]

Тут "знайти" означає "подати у вигляді аналітичної функції від t (без інтеграла)".


Ось ще одна підступна задача, що сягає корінням в теорію ймовірностей, але яку можна дуже компактно і красиво сформулювати у термінах алгебри. Отже, припустимо, що у нас є квадратна бінарна матриця (тобто усі її елементи це \(0\) і \(1\)) \(A = ||a_{ij}||\;\; (i,j=1,…,n)\) (\(n \gt 2\), - це важливо!). Відомо, що на діагоналі стоять нулі, а всі недіагональні елементи \( a_{ij} \) задовольняють умову \( a_{ij} = 1 - a_{ji}.\) Відомо, що одиничний вектор \(W=(1,1,…,1)'\) є власним вектором матриці \(B=A\cdot A.\) Чи буде (завжди?/іноді?/ніколи?) \(W\) також власним вектором для матриці \(A?\)

Ця задача має дуже красивий не-алгебраїчний розв'язок (так би мовити, на пальцях його можна донести і до школяра). Цікаво, а чи є красивий розв'язок методами алгебри?



Шарапов М.М. 2007-2025