Онлайн турнір з математики matholymponline.

Задачі виявилися занадто складними, щоча непогані спроби були у кількох учнів. Наводимо розв'язки цих задач.

Задача 1. Курка Ряба знесла 20 яєць, але лише 18 з них мали золотий жовток. На жаль, невідомо, які з них із звичайним, а які з золотим. Дід і Баба мають чарівну паличку, що перетворює жовток будь-якого яйця (зі звчайного на золотий і, навпаки). Чи розділять старі всі яйця між собою, не розбиваючи їх, щоб яєць з золотим жовтком було порівно в кожного. Чарівну паличку можна використовувати неодноразово.

Розв'язання. Спочатку Дід бере 2 яйця. Звичайно, йому неможливо дізнатися, скільки яєць з золотим жовтком він отримав, позначимо це число за \(n\). Далі Бабка забирає решту 18 яєць. Оскільки спочатку було 18 яєць з золотим жовтком, вона отримала \(18-n\) яєць з золотим жовтком. Це означає, що вона має \(18-(18-n) = n\) яєць зі звичайним жовтком. Тоді вони використовують чарівну паличку на всіх яйцях Бабки. Це перетворить всі яйця з золотим жовтком на звичайні а \( n\) яєць зі звичайним жовтком на золоті жовтки. Таким чином у Бабки стає \(n\) яєць зі звичайним жовтком так само як і у Діда.

Зауваження: Запропонований алгортим буде працювати з будь-яким числом. Потрібно лише віддати Бабці кількість яєць, що дорівнює початковій кількості яєць з золотим жовтком.

Задача 2. Є 2018 комп'ютерних програм з яких лише одна є дуже небезпечним вірусом. Протягом години він обов'язково виводить з ладу комп'ютер. Є 7 тестових комп'ютерів на які можна встановлювати ці програми. За який найменший час можна гарантувати визначення вірусу серед цих програм і як це зробити?

Розв'язання. Розставимо комп'ютери в ряд: ххххххх. Якщо на якомусь з комп'ютерів запускається програма, то позначимо його як «о», отримуючи щось на кшталт: ххохохх (програма встановлюється на 3 і 5 компютери)
Скільки програм можна точно перевірити за допомогою семи комп'ютерів за годину?
1 - хххххxx - першу програму не будемо запускати на жодному комп'ютері.
2 - ххххxxо - другу програму запускаємо на сьомому комп'ютері, якщо він виходить з ладу, це і була вірусна програма
3 - хххxxох - третю програму запускаємо на шостому комп'ютері, якщо він виходить з ладу, це і була вірусна програма
...
9 - xxхххоо - девяту програму запускаємо на шостому і сьомому комп'ютерах, якщо вони обидва виходять з ладу, це і була вірусна програма
10 - xxххохо - десяту програму запускаємо на п'ятому і сьомому комп'ютерах, якщо вони обидва виходять з ладу, це і була вірусна програма
І так далі. В кінцевому рахунку можна переконатися, що однозначно перевіряються 128 програм.
Для тих, хто знайомий зі степенями, це значення дорівнює двом в сьомій степені (\(2^7 = 128\)).
Нагадаємо менші степені двійки:\(2^6 = 64\), \(2^5 = 32\), \(2^4 = 16\), \(2^3 = 8\), \(2^2 = 4\), \(2^1 = 2\), \(2^0 = 1\).
Покажемо як за 2 години можна перевірити 2187 програм.
Тепер можна перейти до першої години перевірки.
Якщо за першу годину не будуть перевірятися 128 програм, то можна буде їх повністю перевірити за другу годину.
Якщо за першу годину один будь-який з семи комп'ютерів, на якому запускалося 64 програми вийде з ладу, то можна буде повністю перевірити їх за другу годину.
Якщо за першу годину на двох з семи комп'ютерів буде встановлено по 32 програми і вони обидва зламаються, то можна буде повністю перевірити їх за другу годину.
Як підсумок отримуємо:   
ххxxххх - 128 програм (не встановлюються на жоден компютер і однозначно перевіряються на другу годину
xxххххо - 64 програми запускаються лише на сьомому комп'ютері і однозначно перевіряються на другій годині
хxхххоx - 64 програми запускаються лише на шостому комп'ютері і однозначно перевіряються на другій годині
ххххоxx - 64 програми запускаються лише на пятому комп'ютері і однозначно перевіряються на другій годині
хххоxxx - 64 програми запускаються лише на четвертому комп'ютері і однозначно перевіряються на другій годині
ххоxxxx - 64 програми запускаються лише на третьому комп'ютері і однозначно перевіряються на другій годині
хоxxxxx - 64 програми запускаються лише на другому комп'ютері і однозначно перевіряються на другій годині
оxхxxxx - 64 програми запускаються лише на першому комп'ютері і однозначно перевіряються на другій годині
хххххоо - 32 програми запускаються на сьомому і шостому комп'ютерах і однозначно перевіряються на другій годині п'ятьма комп'ютерами, що залишилися
...
ооооооо - єдина програма має бути встановлена відразу на усих семи комп'ютерах і якщо всі вони вийдуть з ладу за годину, то вірус буде знайдено відразу ще на першій хвилині.
\(128+64\cdot 7+32\cdot 21+16\cdot 35+8\cdot 35+4\cdot 21+2\cdot 7+1=2187\)
Таким чином виходячи з останньої таблиці всі 2187 програми можна протестувати у такий спосіб, що навіть більше потрібного.


Задача 3. Є три мішки подарунків: в першому 20, в другому - 1, а в третьому - 8. Дід Мороз і Снігуронька вирішили зіграти в гру за наступними правилами: за один хід кожен має брати будь-яку кількість подарунків, але лише з одного мішка, ходять почергово, програє той, хто не може зробити наступний хід. Хто виграє в грі, якщо розпочинає Снігуронька, і як має грати переможець?

Розв'язання. Першим ходом Снігуронька має взяти з першого мішка 11 подарунків і залишити набір (9,1,8). Після хода першого ходу Діда Мороза Снігуронька повинна залишити один з варіантів (8,0,8) або (7,1,6) або (5,1,4) або (2,1,3). Далі Снігуронці нескладно довести гру до остаточної перемоги. Більше можна прочитати про гру Нім.


Задача 4. Снігуронька хоче знайти найвищий поверх у 2018-поверховій будівлі, з якого не розбиваються бурульки. Відомо, якщо кинути бурульку з якогось поверху і вона розіб'ється, то вона обов'язково розіб'ється і з будь-якого вищого і якщо ж бурулька не розбивається, то й не розіб'ється з нижчого. За яку найменшу кількість спроб Снігуронька гарантовано зможе визначити цей поверх, якщо в неї є лише 3 однакових бурульки?

Розв'язання. Спочатку розберемо три більш прості задачі, щоб зрозуміти аглоритм розвязання.

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

2. Якщо будівля залишається 21-поверховою, але зявляється одна додаткова бурулька (загалом дві бурульки), тоді для визначення найвищого поверху з якого не розбивається бурулька вже необовязково перевіряти всі поверхи послідовно, можна спочатку пропустики кілька поверхів і у випадку, якщо перша бурулька розібється продовжити перевірку вже останньою бурулькою. Так можна спершу перевірити 6 поверх, якщо бурулька розібється, то в найгіршому випадку доведеться виконати ще 5 перевірок (всього 6 перевірок). Якщо при першому кидку бурулька не розбилася, то другу спробу потрібно робити з 11 поверху. І знов, якщо бурулька розібється, то в найгіршому випадку доведеться виконати ще 4 перевірки (всього 6 перевірок). Якщо ж і при другому кидку бурулька не розбилася, то третю спробу потрібно робити з 15 поверху. І знов, якщо бурулька розібється, то в найгіршому випадку доведеться виконати ще 3 перевірки (всього 6 перевірок). Четвертий кидок варто робити з 18 поверху, тоді в найгіршому випадку доведеться виконати ще 2 перевірки (всього 6 перевірок). Пятий кидок варто робити з 20 поверху, тоді в найгіршому випадку доведеться виконати ще 1 перевірку (всього 6 перевірок). І, нарешті, якщо у всіх попередніх спробах бурулька не розбилася, то шостою спробою перевіряється 21 поверх.

3. Якщо будівля залишається 21-поверховою, але в наявності є вже три бурульки, тоді для визначення найвищого поверху з якого не розбивається бурулька вже можна буде обійтися пятьма спробами. Так можна спершу перевіряється 11 поверх, якщо бурулька розібється, то задача зводиться до 10 поверхів і двох бурульок (і розвязується аналогічно попередній) Якщо при першому кидку бурулька не розбилася, то другу спробу потрібно робити вже з 17 поверху, а третю - вже можна з 21.

Виконуючи перевірку за аналогічним алгоритмом можна перевірити, що для 2018 поверхів і трьох бурульок достатньо буде 23 спроб.


Задача 5. Скільки різних дільників має число 2018?

Розв'язання. \(20^{18}=(2 \cdot 2 \cdot 5)^{18} = 2^{36}\cdot 5^{18}\).
Дільники числа \(20^{18}\) виду \(2^n\) (де \(n=1;2;...36\)) їх всього 36.
Дільники числа \(20^{18}\) виду \(5^m\)(де \(m =1; 2;… 18\)) їх всього 18.
Дільники числа \(20^{18}\) виду \(2^n \cdot 5^m =18\cdot 36=648\).
Всього: 36+18+648+1 = 703 дільників.