Загадка двох яєць, що падають зі 100-го поверху
Зміст цієї сторінки
>>> Підхід - 2 або 3 поверхи
>>> З 5 тестами на 5 поверхів ...
>>> На 100 поверхів
>>> Баланс у таблиці
ЯЙЦЯ, ЩО ПАДАЮТЬСЯ З 100 ПОЛ
Головоломка з кришталевої кулі
Головоломка, яка запитує, з якого поверху яйце, що падає, обов’язково розбивається. На тестування пропонують два яйця. Питання: скільки спроб потрібно в кращому випадку?
Проблема оптимізації рухів, а не спільного використання.
Англійська: Головоломка, що скидає яйця, головоломка 2 яйця-100 поверхів, проблема двох яєць
У нас є два абсолютно однакових яйця.
Ми знаємо, що цілком можливо, що вони розриваються, коли їх випускають між першим поверхом і 100 поверхом.
Проблема полягає в тому, щоб знати, з якого поверху це відбувається. Сказав інший спосіб, випущений з нижніх поверхів, вони не зламаються.
Скільки спроб потрібно максимум, щоб знайти відповідь? Оптимальна відповідь - 14. Як знайти цей результат?
Примітка: з одним яйцем досить зробити усі послідовні етапи, починаючи з першого, і зупинятися, коли яйце розбивається. У гіршому - потрібно 100 спроб. Запропонована головоломка ставить у ваше розпорядження два яйця, і мова йде про мінімізацію кількості випробувань. Яка найкраща стратегія?
Для пуристів: якщо яйця ламаються з даного поверху, вони розбиваються на всі верхні поверхи. Якщо вони не ламаються, вони не ламаються за нижні поверхи. Вони можуть зламатися на першому поверсі або ж протистояти до останнього поверху. Все залежить від природи яєць.
Цей фокусник висотою п’ять футів і тримає в руці свіже яйце. Яйце падає приблизно на два метри, не розбиваючись. Як воно ? Відповідь: він заліз на стіл!
Підхід - 2 або 3 поверхи
ФОРМА \ * MERGEFORMAT
Очевидно, що яйце може розбитися з першої спроби, але в гіршому випадку знадобиться 2 спроби.
Бухгалтерський баланс: для двоповерхового будинку (В = 2) потрібно максимум два випробування (Е = 2).
З 2 етапів достатньо 2 спроб
Алгоритм тесту з двома етапами
Дякую а Фрейдрик Смієтанський за його внесок
Тут виникає кілька можливостей:
Перше яйце вивільняється з третього: воно розбивається, тоді розбивне дно - 3-е .
Він чинить опір, тоді другого звільняють з другого поверху. Не з 3-го, тому що, якщо він зламається, було б неможливо дізнатися, чи є етап розбиття 2-м чи 3-м .
У критичному випадку, коли стадія розбиття є другою, необхідно провести два тести з яйцем № 2.
Зверніть увагу, що якщо, врешті-решт, яйце не розбивається, це тому, що ці яйця стійко розсипані на одній з трьох стадій.
Бухгалтерський баланс: для триповерхового будинку (B = 3) потрібно максимум три випробування (E = 3). Тому зауважимо, що B = E.
З 3 етапів потрібно 3 спроби
З 5 тестами для 5 поверхів ...
ФОРМА \ * MERGEFORMAT
Насправді у будинку багато поверхів, але спочатку ми протестуємо блок. перших п’яти поверхів.
Критичним випадком буде те, що яйця зламаються з 4-го поверху.
1-м яйцем тестуємо 5-й поверх. Критичний випадок, він ламається. Потім ми повинні продовжити випробування, випробувавши найнижчий поверх і поступово піднятися на 4-й .
У самому крайньому випадку потрібно 5 тестів.
Зверніть увагу, що якщо, зрештою, яйце не розбивається, це тому, що ці яйця стійкі до 5 поверхів.
5 поверхів, критичний корпус
Для блоку з 5 поверхів потрібно 5 спроб
Якщо при випробуванні на 5 поверхах перше яйце не розбивається, це означає, що дно розбиття вище.
Друге яйце доступне для тестування верхніх поверхів.
Обмеження: не використовуйте більше тестів, ніж попередні 5. Так, але залишилось лише 4 можливих випробування.
Отже, яйце, випущене з 5 поверху, чинить опір:
Після цієї першої спроби з 5-го, перше яйце випускається з 9-ї. Він чинить опір.
Залишилося 3 випробування для тестування етапів 6, 7 і 8. Або, на гірший результат, 3 випробування.
Бухгалтерський баланс: з п’ятьма накладеними тестами можна випробувати 9-поверхову будівлю (крок 10).
Після: якщо яйце n ° 1 не зламається з другої спроби з 9-го поверху, це тому, що поверх розбиття знаходиться вище. Випробування тривають ...
За допомогою 5 спроб ми можемо протестувати блок
5 поверхів, потім блок 4 поверхи
Правило блоку
Ці міркування показують, що кожного разу, коли перше яйце чинить опір, можна піднятися на блок поверхів, але на один поверх менше, ніж у попередньому блоці.
З таблиці видно, що за 5 тестів ми можемо пройти до 5 блоків, що ведуть на 15 поверхів.
Примітка: кількість підлог у стартовому блоці визначає кількість випробувань: B = E.
За допомогою 5 випробувань ми можемо протестувати 5 блоків
загальною площею 15 поверхів, і
15 = 1 + 2 + 3 + 4 + 5.
На 100 поверхів
ФОРМА \ * MERGEFORMAT
Висновок наших спостережень
Якщо на один поверх менше у кожному верхньому блоці, сукупність (T) поверхів, що досягнуті, є сумою цілих чисел до E.
З тестами E = 10 ми починаємо тестувати блок B = 10 поверхів, що призводить до можливості тестування будівлі, що має до T = 55 поверхів.
Ми наближаємось до 100 запитуваних.
З 5 спроб, отже перший блок із 5 поверхів
T = 1 + 2 + 3 + 4 + 5 = Ѕ x 5 x 6 = 15
Можна протестувати 15 поверхів
З 10 спроб, отже перший блок із 10 поверхів
T = 1 + 2 + 3 +… + 10 = Ѕ x 10 x 11 = 55
Можна протестувати 55 поверхів
Рецептура для k поверхів
Йдеться про пошук суми цілих чисел, яка сягає Т = 100.
Т 2 = E (E + 1) 2
Для Т = 100 поверхів
Рішення: дві можливості
Фактично, за 14 випробувань можна випробувати 105 поверхів.
З 3 яєць потрібно всього 9 спроб
Таблиця суми T
цілі числа до E
Розв’язування рівняння
Рівняння другого ступеня, корінням якого є:
Ми зберігаємо позитивний корінь та його верхнє округлення, тобто 14 тестів.
На 100 поверхів знадобиться лише 9 спроб.
Т 3 = E ( Е 2 + 5) 6
Оцінка: таблиця проведених випробувань (у гіршому випадку) для 104 поверхів
Англійський куточок
ФОРМА \ * MERGEFORMAT
Проблема двох яєць:
Вам дають 2 яйця.
Ви маєте доступ до 100-поверхової будівлі.
Яйця можуть бути дуже твердими або дуже крихкими, це означає, що вони можуть розбитися при падінні з першого поверху, а можуть навіть не зламатися, якщо їх впасти зі 100-го поверху. Обидва яйця однакові.
Вам потрібно розібратися на найвищому поверсі 100-поверхового будинку, яйце можна кинути, не розбившись.
Тепер питання в тому, скільки крапель потрібно зробити. Ви можете розбити 2 яйця в процесі.
Загадки переміщень
Спільний доступ - класичні головоломки (включаючи яйця для спільного використання або кури, які несуть)
Розділити на десять
Ігри - покажчик
Загадки бананів і верблюдів
Спільне використання та повернення
Спільне користування під час спільного харчування
Обмін Паскалем
Номер 14
Пазли Bibm @ ths
Проблема двох яєць - DataGenetics - Див. Таблицю та графік для до 1000 поверхів та 10 яєць
Проблема з яйцем - Спенсер Мортенсен - Математичне вирішення загальної проблеми: яйця і t-тести.
Це сторінки
ФОРМА \ * MERGEFORMAT