Задача

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

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

– Троє.

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

– Якщо перемножити їх вік то вийде 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 і так далі. Таким чином роблячи кожну наступну спробу першою кулею ми зменшуємо кількість кроків для другої кулі на одиницю.

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

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

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

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

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

Задача

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

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

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

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

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

Рішення

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

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

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

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