Категорія: Головоломки

[Задача] Воїни та меч

Задача

Сама задача відома з прадавніх часів під назвою “задача Йосифа Флавія“. На співбесідах її можна почути в такому вигляді.

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

В більш загальному випадку кількість воїнів може бути довільною так само як порядок вбивств.

Рішення

Наївним рішенням буде створити у пам’яті колекцію флагів для кожного воїна і по колу позначати вбитих доки не лишиться один не позначений елемент. Таке рішення звісно буде працювати, але воно вимагатиме додаткової пам’яті і процесорного часу щоб зробити всі ітерації.

Щоб знайти номер воїна який вижив дешевшим способом можна спробувати наступне. Спочатку з’ясуємо для якої кількості воїнів перший виживе гарантовано. Це звісно буде парна кількість. Тепер щоб гарантувати що перший воїн виживе на наступні і  наступній ітерації і так далі нам теж треба щоб кількість елементів на кожній з них була парною. Таким чином якщо кількість воїнів дорівнює ступеню двійки то виживе перший воїн.

Для довільної кількості елементів N знайдемо найбільший ступінь двійки X такий що X <= N (це можна зробити, наприклад, модифікувавши алгоритм з Знайти найближчий ступінь двійки). Індекс з якого коло з N елементів перетвориться на коло з елементів кількість яких дорівнюватиме ступеню двійки і буде нашою відповіддю. Тобто нам треба знайти скільки елементів M треба пройти (половину з яких буде “вбито”) таких що M/2 + (N-M)=X. Просте рівняння з якого знаходимо що M=(N-X)*2.

Тобто для 100 воїнів (N=100) найближчим ступенем двійки не більшим за 100 буде 64 (X=64) і таким чином залишиться в живих 73-й воїн (M=(100-64)*2=72).

[Задача] Двоє ув’язнених і монетки

Задача

Двох друзів було ув’язнено і посаджено в різні камери. Перед ними поставили таку умову: кожного дня для кожного з них кидають монету і після цього кожен з них має сказати “реверс” чи “аверс” для монети яку кидали в іншій камері. Кожне з них не знає як монета випала в іншій камері. Якщо хоч один вгадав то їх залишають в спокої до наступного дня. Якщо ж обидва помиляться то їх обох негайно стратять. Не відповідати, або давати іншу відповідь крім “аверс” та “реверс” не можна. Друзі можуть узгодити свою стратегію до того як їх розведуть по камерах.

Як друзям гарантовано вижити?

Рішення

Перше на що треба звернути увагу це те що для виживання достатньо вгадувати лише одну з двох монет. Таким чином треба щоб кожна відповідь давала 50% шансів вгадати.

Нехай перший в’язень завжди повторює той результат який випав на його монеті. Таким чином ми покриваємо 50% варіантів для другої монети. Другий в’язень має дати відповідь яка покриє інші 50%: якщо перший в’язень не вгадав другу монету то значить перша монета випала не так як друга – перший просто повторює те що бачить, тобто другий в’язень має казати значення протилежне тому що бачить.

Виграшна стратегія в результаті виглядає так: один в’язень повторює результат своєї монети, а другий каже протилежний результат для своєї монети.

Табличка показує як це працює:

Монета 1 В'язень 1 каже: Монета 2 В'язень 2 каже: Результат
аверс аверс аверс реверс В'язень 1 вгадав монету 2
аверс аверс реверс аверс В'язень 2 вгадав монету 1
реверс реверс аверс реверс В'язень 1 вгадав монету 2
реверс реверс реверс аверс В'язень 2 вгадав монету 1

Троє дітей та їх вік

Задача

Зустрілися двоє знайомих що не бачилися вже дуже багато років. Ось один і питає:

– Скільки в тебе дітей?

– Троє.

– А який у них вік?

– Якщо перемножити їх вік то вийде 36.

– Потрібна підказка.

– Сума їх віку дорівнює кількості вікон он у тому будинку.

– Все одно потрібна підсказка.

– Найстарший з моїх дітей ходить в музичну школу.

– А, тепер точно знаю скільки їм років!

 

Відповідно треба визначити вік дітей і пояснити як це рішення знайдено.

Рішення

Почнемо з найспростішого

Якщо перемножити їх вік то вийде 36

Запишемо усі комбінації з трьох натуральних чисел результат множення яких дасть 36:

  1. 1*1*36
  2. 1*2*18
  3. 1*3*12
  4. 1*4*9
  5. 1*6*6
  6. 2*2*9
  7. 2*3*6
  8. 3*3*4

Сума їх віку дорівнює кількості вікон он у тому будинку

Спочатку просто обчислимо суми:

  1. 1+1+36=38
  2. 1+2+18=21
  3. 1+3+12=16
  4. 1+4+9=14
  5. 1+6+6=13
  6. 2+2+9=13
  7. 2+3+6=11
  8. 3+3+4=10

Тепер подумаємо про те що хоча нам кількість вікон не відома учасники діалогу можуть їх порахувати. Тому один зі співрозмовників не може дати остаточну відпоавіть через те що є більше ніж один варіант який дає таку суму. А варіантів з однаковою сумою у нас два:

    1. 1+6+6=13
    2. 2+2+9=13

Найстарший з моїх дітей ходить в музичну школу

З двох варіантів до яких ми скоротили вибір тепер можна вибрати один знаючи що є одна найстарша дитина. Тобто наша відповідь:

2 + 2 + 9.

Аліса, Боб, Єва та ліки

Задача

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

Як передати ліки з острова на острів? Людей перевозити Єва не візьметься, і в скриньку людина не влізе.

Рішення

Можна помітити що задача подібна до проблеми яку вирішує шифрування з відкритим ключем – як передати зашифровані дані, але не передавати ключ шифру. Для цього треба шифрувати обома ключами (які у кожної сторони різні і не передаються взагалі) і так само розшифровувати.

У випадку скрині послідовність приблизно така:

  1. Боб кладе у скриню ліки, замикає її і віддає Єві.
  2. Аліса додає свій замок на скриню, замикає його і віддає назад.
  3. Боб відкриває і знімає свій замок і віддає скриню Єві.
  4. Аліса відкриває свій замок і дістає ліки зі скрині.

У випадку ж шифрування важливо щоб зашифровувати і розшифровувати обома ключами можна було у різній послідовності з тим же самим результатом.

Ув’язнені і кольорові ковпаки

Задача

В одній кімнаті зібрали 10 ув’язнених. Їх вишикували в ряд так що кожен з них бачить лише інших в’язнів перед собою, але не бачить тих що стоять позаду.

На кожного в’язня одягають білий чи чорний ковпак (в’язень свій ковпак побачити не може). Кількість ковпаків кожного кольору довільна – від 0 до 10.

Далі до кожного з них починаючи з останнього (того хто бачить 9 інших перед собою) підходить кат. В’язень може сказати лише “білий” або “чорний” і якщо він вгадає колір свого ковпака то залишається в живих, інакше його страчують. Далі кат переходить до наступного в’язня і так далі.

Треба знайти таку стратегію при якій гарантовано виживає максимальна кількість в’язнів.

Рішення

Останній у черзі в’язень може підрахувати кількість білих (або чорних) ковпаків у інших дев’яти осіб перед собою і сказати “біле” якщо їх кількість непарна, та “чорне” якщо парна. Або навпаки – головне щоб усі знали як інтерпретувати слова останнього у черзі. Далі 9-й точно знає свій колір бо знає парна чи ні кількість білих ковпаків перед ним і може порівняти з тим що він почув від 10-го в’язня.

Наприклад, якщо ковпаки одягли так:

1б, 2б, 3ч, 4б, 5ч, 6б, 7ч, 8ч, 9ч, 10б.

  • 10-й каже “чорний” що означає “бачу парну кількість білих” і його страчують
  • 9-й каже “чорний” бо 10-й бачив парну кількість білих і він теж бачить парну їх кількість – виживає
  • 8-й каже “чорний” бо 10-й бачив парну кількість білих і 9-й чорний, тож він теж чорний – виживає
  • 7-й каже “білий” бо 10-й бачив парну кількість білих, 9-й тв 8-й чорні, а сам він бачить непарну кількість білих – виживає
  • 6-й каже “чорний” бо 10-й бачив парну кількість білих, після того був лише один білий (7-й) і сам він бачить непарну кількість білих – виживає
  • і так далі.

Як бачимо у найгіршому випадку гине лише один ув’язнений – 10-й.

Відкриті і закриті шафки

Задача

У холі є 100 закритих шафок. Прибиральник спочатку відкриває їх усі. Потім закриває кожну другу. Потім проходить по кожній третій і закриває відкриті та відкриває закриті. Далі кожну четверту, п’яту і так далі до сотої.

Які шафки в кінці залишаться відкриті?

Рішення

Стан шафки міняється коли значеня кроку є дільником номеру шафки. Наприклад шафка 15 мінятиме свій стан при кроках 1, 3, 5 та 15.

Відповідно шафка залишиться відкритою коли кількість змінів стану є непарною. А кількість змін буде непарною коли номер шафки є квадратом, Наприклад для шафки 36 стан мінятиметься 9 разів – кроки 1, 2, 3, 4, 6, 9, 12, 18 та 36.

В диапазоні 1..100 є 10 квадратів – 1*1, 2*2, …, 10*10.

Значить 10 шафок залишаться відкритими – 1, 4, 9, 16, 25, 36, 49, 64, 81, 100.

Монетки: орли та решки

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

Хлопчик зацікавлений не дозволити сестрі отримати більше монет, чим він сам. Отже, він має поділити монети на дві купи таким чином, щоб це гарантувало йому, байдуже яку саме купку вибере сестра, що вони обоє отримають однакову кількість монет. Що має утворити з монетами хлопик?

Рішення:

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

Хлопчик має навмання відраховать кількість монет і перевернути. Яку саме кількість? Треба вияснити.

Стратегія заснована на тому, що Tb=Hs. Хлопчик має поділити монети так, щоб кількість решок у його купі дорівнювала кількості орлів у купі сестри.

А оскільки за умови Hb+Hs=60 – відома кількість орлів на столі, тоді маємо  Hb+Hs=Hb+Tb=60.

Тож, 60 монет повино бути у одній купі  і тільки таким чином після перевертання хлопчик і сестра будуть з равноцінними виграшами.

(де

T – tail-on coin – решка,

H – head-on coin – орел,

b – brother – брат,

s – sister – сестра).

(; kind’a too simple …. and none equation system needed (;

Вежа і скляні кулі

Задача

Є вежа на 100 поверхів і дві скляні кулі. Треба за мінімальну гарантовану кількість кроків визначити починаючи з якого поверху куля, якщо її впустити, розбивається.

Рішення

Зрозуміло що коли перша куля розбивається треба знаходити точний поверх простим лінійним перебором.

Таким чином рішення повинно бути таким що кількість спроб для кулі 1 + кількість спроб для кулі 2 завжди б дорівнювала лдному і тому ж числу у найгіршому випадку.

Отже маємо X + (X – 1) + (X – 2) + … + 1 = 100,

звідки X*(X + 1) / 2 = 100.

Маємо X = 14.

Це означає що починаємо ми з поверху 14 і якщо кулька розбилася то за допомогою іношої кулі перевіряємо послідовно усі 13 попередніх поверхів. Якщо ж вона не робилася то переходимо до поверху 27 і так далі. Таким чином роблячи кожну наступну спробу першою кулею ми зменшуємо кількість кроків для другої кулі на одиницю.

Тепер те ж саме рішення, але з іншого боку Smile

Якщо ми підемо зверху то можемо почати з поверху 99 (вважаємо що всі попередні ми вже перевірили). А от до 99 поверху ми можемо одразу перейти з 97-го – бо у будь-якому варіанті розвитку подій нам знадобиться не більше 2 спроб.

Відповідно до 97-го можна перейти з 94-го (максимум 3 спроби у будь-якому варіанті).

До 94-го відповідно переходимо з 90-го (4 спроби), до 90-го з 85-го (5 спроб) і так далі.

В кінці кінців ми дійдемо таки до того що починати нам треба з поверху 14.

Люди на острові і чарівні капелюхи

Задача

Група людей опинилася на безлюдному острові. Раптом з’явився джин який запропонував їм зіграти у наступну гру.

На деяких з нгих, мінімум на одного, він одягне чарівного капелюха якого видно усим іншим, але не видно тому на кому він є.

Для того щоб звільнитися треба усим на кому капелюх, і лише їм, зануритися рівно у північ у воду.

Спілкуватися між собою учасники не можуть ні словами, ні жестами.

Як їм вибрати виграшну стратегію і через скільки ночей вони зможуть вибратися?

Рішення

Розглянемо варіант коли є усього лише один капелюх. Тоді той хто не бачить жодного капелюха розуміє що на ньому єдиний капелюх і занурюється у воду в першу ж ніч.

Коли капелюхів два жоден з людей не може бути певен чи є на ньому капелюх. При цьому кожен з тих на кому капелюх розуміє що якщо нічого не сталося в першу ніч значить на ньому другий (бо бачить він лише один) і обоє занурюються у воду на другу ніч.

Таким чином для N капелюхів власник кожного капелюха (який бачить N-1 капелюхів) знає що раз нічого не сталося на N-1 ніч то на ньому є капелюх і йде у воду з іншими у ніч N.

Таким чином звільнення відбувається нва ту за рахунком ніч номер якої відповідає кількості капелюхів.