Проект основателей компании «Ваш репетитор»
ERUDITOR.RU

81. 100 этажей vs. 2 шарика

У вас есть два одинаковых стеклянных шарика. Вы можете бросать их с любого этажа 100-этажного дома.

Вопрос: Какое наименьшее количество бросков понадобится, чтобы определить этаж, начиная с которого шарик разобьётся?
2008-08-28

Обсуждение


Задачи :: 100 этажей + 2 шарика
↓↓ +5 ↑↑   igar (10 / 119)   29 авг 2008 17:09   »»


5 способов выбора шага есть
я так думаю это сойдет за ответ, чтобы его не палить пока?
↓↓ 0 ↑↑   neoromans (0 / 4)   29 янв 2008 02:52   «« #2 »»   Ответить


UPD:
1. шаг - это один бросок одного шарика.
2. шарик начинает разбиваться с определённого этажа.
↓↓ 0 ↑↑   igar (10 / 119)   29 янв 2008 09:26   «« #3 »»   Ответить


методы оптимизации гдето на 3 курсе сдавал - забыл уж все
но наверно тута нада пользоваться методом дихотомии. даже не, метод золотого сечения быстрее будет
↓↓ 0 ↑↑   HeKTo2 (0 / 27)   29 янв 2008 20:27   «« #4 »»   Ответить


У меня получилось 33.
↓↓ 0 ↑↑   Enclave (3 / 140)   30 янв 2008 21:37   «« #5 »»   Ответить


33 шага включая последний.
↓↓ 0 ↑↑   Enclave (3 / 140)   30 янв 2008 21:37   «« #6 »»   Ответить


Отказываюсь от своих слов.
↓↓ 0 ↑↑   Enclave (3 / 140)   30 янв 2008 23:13   «« #7 »»   Ответить


Первым шариком определяем десятки, вторым - единицы.
То есть, первый бросаем с 10, 20, .., 90, 100 этажа. (Максимум 10 бросков.)
Второй бросаем с Д+1, Д+2, .., Д+9 (Максимум 9 бросков.), где Д - тот десяток, с которого первый шарик ещё не разбился (с Д+1 - разбился).
Итого 19.
Есть варианты меньше? )
↓↓ +3 ↑↑   eruditor (129 / 439)   31 янв 2008 05:48   «« #8 »»   Ответить


Мне задали этот ребус на собеседовании и мне пришел в голову именно этот вариант. Он устроил интервьюера, но не полностью :) то есть должен быть какой-то еще способ? Я так и не понял)
↓↓ 0 ↑↑   Михаил (0 / 1)   22 июн 2016 14:42   «« #57 »»   Ответить


Ниже в этой теме приведено и подробно обсуждено решение за 14 бросков.
↓↓ 0 ↑↑   Кузнецов Сергей Германович (264863 / 13798)   22 июн 2016 17:32   «« #58 »»   Ответить


18
↓↓ 0 ↑↑   so-ivan (4 / 28)   31 янв 2008 08:47   «« #9 »»   Ответить


думаем ещё..
↓↓ 0 ↑↑   igar (10 / 119)   31 янв 2008 09:23   «« #10 »»   Ответить


нужно 7 шагов
↓↓ 0 ↑↑   Zloy (0 / 69)   31 янв 2008 14:05   «« #11 »»   Ответить


нет
а если уж пишете ответ, то интересно бы послушать и решение.
↓↓ 0 ↑↑   igar (10 / 119)   31 янв 2008 17:27   «« #12 »»   Ответить


6 шагов
это почти такая ше загадка как и про 1000 золотых монет среди которых 1 фальшивая
↓↓ 0 ↑↑   Zloy (0 / 69)   05 фев 2008 19:41   «« #13 »»   Ответить


могу расписать, но думаю после подсказки каждый смекнет
↓↓ 0 ↑↑   Zloy (0 / 69)   05 фев 2008 19:42   «« #14 »»   Ответить


Упс.... ашибочка вышла )))
в наиболее длинном минимальном варианте 11 бросков. Этажи: 33, 55, 60, 73, 82, 88, 92, 95, 97, осталось 3 этажа и еще 2 броска. Правильный ответ 11
↓↓ 0 ↑↑   Zloy (0 / 69)   05 фев 2008 20:08   «« #15 »»   Ответить


Ну умеете моск замутить - 7 бросков
1,2,4,7,13,25, 50 75,87,93,96,98,100 начиная с 50 этажа первый бросок, 7 бросков НеКто2 был прав.
↓↓ 0 ↑↑   Zloy (0 / 69)   05 фев 2008 20:15   «« #16 »»   Ответить


Согласен с eruditor ом
По-моему Zloy в последнем не прав - после 50-ого этажа с каких этажей последовательно бросать? Если, например, печальный этаж будет номером 10??
↓↓ 0 ↑↑   Amatti (0 / 9)   05 фев 2008 22:50   «« #17 »»   Ответить


у eruditora ход мыслей правильный, но ответ неверный
Zloy не прав в обоих случаях. шарика 2.
↓↓ 0 ↑↑   igar (10 / 119)   06 фев 2008 09:10   «« #18 »»   Ответить


Такой ещё вариант- 14бросков
Воспользовавшись мыслями вышеприведенными, получилося:
9,22,34,45,55,64,72,79,85,90,94,97,99,100.
p/s/ первый бросок можно делать с9 по14 этажи
↓↓ 0 ↑↑   so-ivan (4 / 28)   06 фев 2008 10:12   «« #19 »»   Ответить


so-ivan, верно!
↓↓ 0 ↑↑   igar (10 / 119)   06 фев 2008 13:44   «« #20 »»   Ответить


so-ivan, верно!
↓↓ 0 ↑↑   igar (10 / 119)   06 фев 2008 13:44   «« #21 »»   Ответить


7 бросков
Первый бросок с 50 этажа
если разбился с 25 бросаем, если нет с 75 и так далее
при разбитом шаре етаж понижаем, ни неразбитом повышаем
50,75,87,93,96,98,100 наиболее длинный вариант в случае если неразбиваеца
50,25,13,7,4,2,1 наиболее длинный вариант в случае если разбиваеца
что неясно?
↓↓ 0 ↑↑   Zloy (0 / 69)   06 фев 2008 17:19   «« #22 »»   Ответить


omg
Zloy, вы условие хорошо прочитали? Шарики -- стеклянные. Они -- разбиваются. И их -- ДВА.

Допустим, вы бросили с 25 -- разбился. Потом с какого бросаете? С 13-го? Допустим, тоже разбился. Всё, оба шарика разбиты. Что дальше?
↓↓ 0 ↑↑   eruditor (129 / 439)   06 фев 2008 18:59   «« #23 »»   Ответить


so-ivan, igar
Мысль понял. Но нужно полное решение - с доказательством, что меньше 14 невозможно.
↓↓ 0 ↑↑   eruditor (129 / 439)   06 фев 2008 19:03   «« #24 »»   Ответить


Zloy
это самый оптимальный метод выборки в принципе, способ давно известный, но со стеклянными шариками он не катит, как и сказал eruditor...
↓↓ 0 ↑↑   Decadent (0 / 2)   19 сен 2008 14:32   «« #25 »»   Ответить


Доказательство минимальности
Рассмотрим количество различных исходов при бросании 2-х шариков с различных этажей при ограницении в N раз, брасая их сначало первый, а когда первый разбился, то второй. Очевидно, что первый (в самом лучшем случае) может разбится на любой из N попыток (x) или не разбиться вообще, а второй на любой из оставшихся N-x попыток или не разботься вообще. Итого, получается 1 + SUM i=1..N (N-i+1) или N*(N+1)/2+1. Таким образом для 14 бросков мы можем различить 106 исходов, а для 13 - 92, поэтому для 100 этажей 14 попыток - это минимум.
↓↓ 0 ↑↑   zimin2000 (0 / 4)   01 окт 2008 09:44   «« #26 »»   Ответить


6 ПОПЫТОК ДОСТАТОЧНО!
↓↓ 0 ↑↑   Mir@sh (0 / 12)   03 окт 2008 22:50   «« #27 »»   Ответить


50 75\25 63\88/12/38 и тд. На 6 попытку уже точно знаешь с какого этажа разбиваеться!!! и бросать 7й раз чтобы разбить не обязательно =)
↓↓ 0 ↑↑   Mir@sh (0 / 12)   03 окт 2008 22:53   «« #28 »»   Ответить


Великие оптимизаторы!2 попытки!
Цитата:"omg //eruditor : (274 дн. назад)
Zloy, вы условие хорошо прочитали? Шарики -- стеклянные. Они -- разбиваются. И их -- ДВА. Допустим, вы бросили с 25 -- разбился. Потом с какого бросаете? С 13-го? Допустим, тоже разбился. Всё, оба шарика разбиты. Что дальше?"

Действительно а что дальше? Вы засоряете мозг не нужными вещами. Спрашивается минимальное количество попыток. их 2 если они разбились сразу то ВСЕ! пипец эксперименту.
↓↓ 0 ↑↑   BuBBa (1 / 12)   07 ноя 2008 00:47   «« #29 »»   Ответить


14
14
э27
э39
э50
э60
э69
э77
э84
э90
э95
э99
↓↓ 0 ↑↑   дум (0 / 6)   23 дек 2008 20:21   «« #30 »»   Ответить


а вообще минимум - 1.методом научного тыка догадаться
↓↓ 0 ↑↑   дум (0 / 6)   23 дек 2008 20:23   «« #31 »»   Ответить


6 попыток, 7 попыток
:)
насчет минимального не согласен - правильно максимальное.
минимальное 1 максимальное 14.
↓↓ 0 ↑↑   Nord (0 / 9)   14 янв 2009 16:40   «« #32 »»   Ответить


минимум
Как вы представляете минимальный шаг, равный 1? По моему, даже если вы заранее знаете этаж, то один-то шарик должен разбиться ради науки:) Только второй шарик покажет этаж.
P.s. Правда, если вы знаете, что этаж 1 или 100, то это можно доказать и одним шариком)
↓↓ 0 ↑↑   gkeks (0 / 1)   21 янв 2009 20:34   «« #33 »»   Ответить


хы
минимальное 1 - это из ряда фантастики. нужно знать наверняка, что при падении с такого-то этажа шарик не разбивается. вы пытаетесь угадать, и "угадываете" - допустим это 50ый этаж. залезли на 50ый этаж, бросили шарик и он действительно не разбился. всё, одна попытка исчерпана, но где гарантия, что он не разобьется и при падении с 49го этажа?

Шарик может разбиться даже при падании с 1го этажа если уж на то пошло, так почему почти все начинают бросать их с 9го, 14го, 15го ?
↓↓ 0 ↑↑   widerS (0 / 1)   15 мар 2009 10:00   «« #34 »»   Ответить


Не понемаю
Если эти шарики стеклянные, как они не могут разбиться???
↓↓ 0 ↑↑   j~u~l (0 / 1)   04 апр 2009 18:09   «« #35 »»   Ответить


ПОТРЕБУЕТСЯ 34 БРОСКА!!!
↓↓ 0 ↑↑   Rus_17-91 (0 / 12)   06 май 2009 15:22   «« #36 »»   Ответить


Гиганты Мысли!
Лучше подсчитайте количество различных(!) способов бросить минимальное количество раз, те.14.

Послостью согласен, что можно начинать бросать с любого этажа от 9-го до 14-го, включая оба!
↓↓ 0 ↑↑   Верёвочник (0 / 2)   08 май 2009 04:30   «« #37 »»   Ответить


что тупим
если бросить шарик в начале с 50 и он разобьется то бросать его с 75 уже не надо он тоже разобьется
↓↓ 0 ↑↑   Димидролл (0 / 1)   30 июн 2010 17:50   «« #38 »»   Ответить


Тупая логика!
Как может стеклянный шарик не разбиться в первый бросок с первого этажа???
↓↓ 0 ↑↑   Ролл!!! (0 / 1)   06 окт 2010 20:59   «« #39 »»   Ответить


вопрос "сколько шагов" или типа того!
шагов предется проделать не минимум а максимум 19! 10 для десятков! и 9 для этажей! к примеру если он не разбился после 90! знач кидаем с сотого (можно и не кидать) тупо кидаем 91,92, так до 100! собственно когда он на 100 разобьется мы сделаем 19 ходов! и при этом можем сохранить один шар (если критический этаж=100) минимально число ходов 2! для выяснения 1 этажа таким же способом! или один бросок если кинуть сразу с первого этажа) или тупо рассуждая логически понять что кинув шар стеклянный вниз с первого этажа на бетон он разобьется! а на нормальный газон шар не разобьется и с 100! (газончик должен быть идеален)
↓↓ 0 ↑↑   lavsvip (-124 / 40)   18 окт 2010 17:51   «« #40 »»   Ответить


~10 попыток, в среднем. Вопрос немного странновато звучит, но тем не менее, можно дать ответы
Если использовать систему бросков по этажам: 13,25,36,46,55,64,72,79,85,90,94,97,99,100
То получаем следующее:
Максимум - 14 бросков и это уже было отвечено... Это будет 17% от всех случаев при равномерной вероятности
Минимум - 2 броска (2% случаев)
До 55 этажа включительно, обойдёмся не более чем 13-ю бросками.
Среднестатистическое количество бросков 10,22 если не ошибся с расчётах...
↓↓ 0 ↑↑   SergeyASh (4 / 36)   27 ноя 2010 07:53   «« #41 »»   Ответить


...поправка 2 броска 1% случаев (разбивается с 1-го этажа)
↓↓ 0 ↑↑   SergeyASh (4 / 36)   27 ноя 2010 07:55   «« #42 »»   Ответить


Семь бросков
Смысл в том чтоб каждым броском кол-во этажей делить на 2. Т. Е. 1й бросок- 50ый этаж,
2-25ый, этаж 3-13ый, этаж 4-6ой этаж, 5-3ий..., 7-1ый..., или 2ой..., разницы нет.
↓↓ 0 ↑↑   злостный Beaver (0 / 5)   27 дек 2010 20:09   «« #43 »»   Ответить


там шесть
↓↓ 0 ↑↑   злостный Beaver (0 / 5)   27 дек 2010 20:11   «« #44 »»   Ответить


идея
предлагаю бросать не с этажа, а с земли, а этаж можно увидеть подбросив шарик вверх у узнав до какого этажа он долетит и разобьется ли полетев обратно
↓↓ 0 ↑↑   Lasto4ka (0 / 8)   24 мар 2011 17:15   «« #45 »»   Ответить


Мне эту задачку дали на интервью при поступлении на работу на должность инженера электронщика (не программиста) в Израиле. Привожу свой вариант решения.
Все этажи здания делим на неравные группы. Пусть таких групп получилось К. Первая, самая нижняя группа содержит N этажей. Бросаем шарик с верхнего этажа этой группы. Если он разбился - бросаем второй шарик с нижнего этажа этой группы (т.е. с первого), и последовательно повторяем броски поднимаясь на один этаж. Если шарик с верхнего этажа не разбился - идем на верхний этаж второй группы. Одна попытка уже использована, поэтому во второй группе должно быть на один этаж меньше, т.е N-1. Рассуждая анологично, в третью группу включим N-2 этажа, в четвертую N-3 и т.д. Общее количество этажей равно
N+(N-1)+(N-2)+(N-3)+... +(N-К+1)
Сумма этой арифметической прогрессии равна
(2N-K+1)K/2
и равна 100.
(2N-K+1)K/2=100,
откуда
N=100/K+K/2- 1/2
Ищем минимум этой функции, для чего продиффернцируем N по К и приравняем производную к нулю.
dN/dK=-100/K^2 + 1/2 = 0
К равно корень кв. из 200, т.е 14 (в целых числах)
Т.е. в первой группе 14 этажей. Максимальное возможное количество бросаний равно, соответственно, тоже 14 (для любого этажа любой группы, вплоть до сотого).
↓↓ 0 ↑↑   Марк (0 / 1)   09 авг 2011 19:08   «« #46 »»   Ответить


Это не верно, т.к. доказывается лишь то, что ответ 14 для алгоритмов определенного типа. Ни доказательства того, что эти алгоритмы как-то оптимальнее других, ни того, что ответ 14 и для остальных типов, тут нету.
Выше приведено верное доказательство оптимальности.
↓↓ 0 ↑↑   Виталик (5 / 3)   27 мар 2013 11:09   «« #50 »»   Ответить


Всё проще.
Не понимаю, почему всех так тянет прибегнуть к математическим формулам.

1 бросок не может быть, это очевидно. Весь если мы бросим шарик, допустим, с 5 этажа, и он не разобьётся, то этого нам всё равно не будет достаточно, чтобы понять: так с какого же он разобьётся? Аналогично, если и разобьётся.

Бросив же два раза, мы (при удачном раскладе) понять-таки сможем. Например, бросаем с 4 — разбивается; бросаем с 3 — нет. Вот и граница. Ответ прост, и он — 2.

Вопрос стоит не о вероятности события, а о минимальном количестве бросков.
↓↓ −5 ↑↑   Forward (-5 / 2)   01 мар 2012 15:29   «« #47 »»   Ответить


Прочитал такой подход уже в куче сообщений выше.
Вы неверно понимаете вопрос.
Ответ может быть и 1 в вашем случае, если шарик не разбивается с 100, и вы его оттуда кинули.

Однако вопрос не в том, как может быть, а в том, какое минимальное количество бросков будет достаточно для того, чтобы ответить на вопрос при ЛЮБОМ этаж.

Вы решаете такую задачу: есть дом, два шарика, и вы знаете этаж, который будет ответом. Вы просто доказываете, что это именно тот этаж.

Требуется же от вас алгоритм, который вы сможете применять к любому зданию, и получать ответ, НЕ ЗНАЯ его изначально.
↓↓ +5 ↑↑   Виталик (5 / 3)   27 мар 2013 12:13   «« #51 »»   Ответить


без формул
Очевидно, что нужно разбивать этажи на группы, для минимизации количества бросков
Проходим в 2 этапа
1) определение группы этажей
2) определение этажа в группе
Т.о. количество состоит из суммы=кол-во на определение группы+количество на определение этажа
На определение группы самый жесткий вариант - шар разбивается только при броске с 100-го этажа - остается один который мы тратим на исследование 99-го этажа, значит 98-й должен быть уже исследован
Т.о. предпоследний бросок на определение группы должен быть произведен с 98-го этажа и у нас сэкономлен 1 бросок на определение этажа
Значит до 98-го можно исследовать уже 95-й, т.к. имеем уже 2 броска на исследование этой группы этажей 96 и 97-й этажи
Очевидна закономерность по которой можно определять этажи для определения группы
100-2=98
98-3=95
95-4=91
91-5=86
86-6=80
80-7=73
73-8=65
65-9=56
56-10=46
46-11=35
35-12=23
23-13=10
10-14=????? приплыли
Значит начинаем бросать с 10-го этажа, при разбитом шаре начинаем с 1-го
При не разбитом шаре бросаем с 23, если разобьется - начинаем с 10-го
Получаем этажи для определения групп - 10, 23, 35, 46, 56, 65, 73, 80, 86, 91, 95, 98, 100
При подсчете любого жесткого варианта получаем - 14 бросков
↓↓ 0 ↑↑   Alexa (0 / 2)   21 мар 2012 09:20   «« #48 »»   Ответить


Без формул, вы ответили, что минимальное число не больше 14. А это не точный ответ.

А нужен точный.

формулы-то и использовались для получения точного ответа.
↓↓ 0 ↑↑   Виталик (5 / 3)   27 мар 2013 11:15   «« #52 »»   Ответить


далее
В этом решении оч хорошо высвечивается его не единственность
Действительно, ес попыток 14, то можно ведь и начинать не с 10 а с 14 этажа
14+13=27
27+12=39
....
и т.д.
а ващет и с 13 можно, с любого, от 10-14
ес исследовать количество решений легко переваливает сотню
ведь можно
10-14
23-27
...
↓↓ 0 ↑↑   Alexa (0 / 2)   21 мар 2012 14:51   «« #49 »»   Ответить


Алгоритм уже есть, осталось доказать оптимальность.
Давайте представим эксперимент в принципе. Есть два шарика, мы их бросаем, есть N попыток. Результат бросания — 0, если шарик не разбился, и 1, если разбился. Результат эксперимента — либо последовательность из N-2 нулей и 2 единиц (если оба шарика разбились, а последовательность еще не достигла размера N, то просто дополним её нулями), либо из N-1 нулей и 1 единицы (один шарик может не разбиться), либо из N нулей (вообще ни один не разбился). Посчитаем количество возможных результатов эксперимента: C(N, 2) + C(N, 1) + С(N, 0), где C это количество сочетаний из n по k. Заметим, что в результате эксперимента мы должны получить один единственный вариант ответа (этаж), то есть количество результатов эксперимента равно количеству этажей, которые мы можем "просмотреть" за N попыток (если этажей больше, то по принципу Дирихле в результате какого-то эксперимента мы не получим исчерпывающего ответа). Посчитаем кол-во результатов для N = 13, это будет 78+13+1=92, что меньше 100. Значит, никаким алгоритмом в принципе нельзя получить ответ за 13 бросков. Так что 14 — правильный ответ.
↓↓ +5 ↑↑   PetrK (14 / 7)   14 апр 2013 15:15   «« #53 »»   Ответить


Вчера мне такую задачку дали на собеседовании. Попробовала дихотомией. Делить каждый интервал на 2. Получилось 12 бросков. Сказали, нет, слишком много.И что надо начинать не сверху, а снизу идти.
Ну пока так и не дошло до меня.
↓↓ 0 ↑↑   Григорьева Арина (0 / 1)   09 окт 2014 14:34   «« #54 »»   Ответить


Вопрос: Какое НАИМЕНЬШЕЕ количество бросков понадобится, чтобы определить этаж, начиная с которого шарик разобьётся?
Ответ: 1 бросок. Минут 10 ломал голову алгоритмами, но потом вернулся к вопросу и.....
↓↓ 0 ↑↑   Лёха (0 / 1)   03 июн 2015 00:03   «« #55 »»   Ответить


Вариант 1. Оптимальный алгоритм. Минимальное кол-во бросков ВСЕГО, но не меньше 2х.
Исходя из того что шариков всего 2, а результат надо получить гарантированно алгоритм получается такой:
1. Поднимаемся на этаж вверх
2. Бросаем 1й шар
2.1 Если шар разбивается, спускаемся на 1 этаж и бросаем 2й шар
2.1.1 Если шар разбивается, ответ — текущий этаж
2.1.2 Иначе: ответ — следующий этаж
2.2. Иначе: сдвигаемся на 2 этажа вверх и повторяем с п 2.

Вариант 2. Неоптимальный алгоритм, Максимальное кол-во бросков, но минимальное возможное кол-во: 1.
Бросаем 1й шар с 1го этажа, если разбивается получаем ответ с 1й попытки. Если нет начинаем бросать 2й шар с каждого следующего этажа.

Но зато минимальное кол-во попыток.
↓↓ 0 ↑↑   Михаил (0 / 1)   25 окт 2015 12:00   «« #56 »»   Ответить


Вопрос идёт о минимально возможном количестве бросков. В теории достаточно двух бросков — с 25-го, и с 26-го. Если на 26-ом шарики стали разбиваться, то всё. Но это при везении.
↓↓ 0 ↑↑   Роман (-5 / 5)   28 окт 2016 18:27   «« #59 »»   Ответить


У меня получилось 14.
Первый шар кидаем с шагом 10.
Второй шар кидаем с шагом -2 от того этажа, на котором разбился первый шар.
Получается у первого шара максимальное кол-во бросков 10, а у второго 4.
↓↓ 0 ↑↑   hamsterfriday (0 / 2)   24 мар 2017 02:31   «« #60 »»   Ответить


хз, о чем я думал, когда писал это решение))
с шагом 2 не получится точно определить.
19 бросков выходит у меня.
↓↓ 0 ↑↑   hamsterfriday (0 / 2)   24 мар 2017 03:11   «« #61   Ответить



Ваше имя
Email
Текст ответа
© 2006-2017   Авторы