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

5 способов выбора шага есть
я так думаю это сойдет за ответ, чтобы его не палить пока?

UPD:
1. шаг - это один бросок одного шарика.
2. шарик начинает разбиваться с определённого этажа.

методы оптимизации гдето на 3 курсе сдавал - забыл уж все
но наверно тута нада пользоваться методом дихотомии. даже не, метод золотого сечения быстрее будет

У меня получилось 33.

33 шага включая последний.

Отказываюсь от своих слов.

Первым шариком определяем десятки, вторым - единицы.
То есть, первый бросаем с 10, 20, .., 90, 100 этажа. (Максимум 10 бросков.)
Второй бросаем с Д+1, Д+2, .., Д+9 (Максимум 9 бросков.), где Д - тот десяток, с которого первый шарик ещё не разбился (с Д+1 - разбился).
Итого 19.
Есть варианты меньше? )

Мне задали этот ребус на собеседовании и мне пришел в голову именно этот вариант. Он устроил интервьюера, но не полностью :) то есть должен быть какой-то еще способ? Я так и не понял)

Ниже в этой теме приведено и подробно обсуждено решение за 14 бросков.

18

нет
а если уж пишете ответ, то интересно бы послушать и решение.

6 шагов
это почти такая ше загадка как и про 1000 золотых монет среди которых 1 фальшивая

могу расписать, но думаю после подсказки каждый смекнет

Упс.... ашибочка вышла )))
в наиболее длинном минимальном варианте 11 бросков. Этажи: 33, 55, 60, 73, 82, 88, 92, 95, 97, осталось 3 этажа и еще 2 броска. Правильный ответ 11

А если на 33 разобьется?

Ну умеете моск замутить - 7 бросков
1,2,4,7,13,25, 50 75,87,93,96,98,100 начиная с 50 этажа первый бросок, 7 бросков НеКто2 был прав.

Согласен с eruditor ом
По-моему Zloy в последнем не прав - после 50-ого этажа с каких этажей последовательно бросать? Если, например, печальный этаж будет номером 10??

у eruditora ход мыслей правильный, но ответ неверный
Zloy не прав в обоих случаях. шарика 2.

Такой ещё вариант- 14бросков
Воспользовавшись мыслями вышеприведенными, получилося:
9,22,34,45,55,64,72,79,85,90,94,97,99,100.
p/s/ первый бросок можно делать с9 по14 этажи

7 бросков
Первый бросок с 50 этажа
если разбился с 25 бросаем, если нет с 75 и так далее
при разбитом шаре етаж понижаем, ни неразбитом повышаем
50,75,87,93,96,98,100 наиболее длинный вариант в случае если неразбиваеца
50,25,13,7,4,2,1 наиболее длинный вариант в случае если разбиваеца
что неясно?

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

Допустим, вы бросили с 25 -- разбился. Потом с какого бросаете? С 13-го? Допустим, тоже разбился. Всё, оба шарика разбиты. Что дальше?

so-ivan, igar
Мысль понял. Но нужно полное решение - с доказательством, что меньше 14 невозможно.

Zloy
это самый оптимальный метод выборки в принципе, способ давно известный, но со стеклянными шариками он не катит, как и сказал eruditor...

Доказательство минимальности
Рассмотрим количество различных исходов при бросании 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 попыток - это минимум.

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

Действительно а что дальше? Вы засоряете мозг не нужными вещами. Спрашивается минимальное количество попыток. их 2 если они разбились сразу то ВСЕ! пипец эксперименту.

14
14
э27
э39
э50
э60
э69
э77
э84
э90
э95
э99

а вообще минимум - 1.методом научного тыка догадаться

6 попыток, 7 попыток
:)
насчет минимального не согласен - правильно максимальное.
минимальное 1 максимальное 14.

минимум
Как вы представляете минимальный шаг, равный 1? По моему, даже если вы заранее знаете этаж, то один-то шарик должен разбиться ради науки:) Только второй шарик покажет этаж.
P.s. Правда, если вы знаете, что этаж 1 или 100, то это можно доказать и одним шариком)

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

Шарик может разбиться даже при падании с 1го этажа если уж на то пошло, так почему почти все начинают бросать их с 9го, 14го, 15го ?

Не понемаю
Если эти шарики стеклянные, как они не могут разбиться???

ПОТРЕБУЕТСЯ 34 БРОСКА!!!

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

Послостью согласен, что можно начинать бросать с любого этажа от 9-го до 14-го, включая оба!

что тупим
если бросить шарик в начале с 50 и он разобьется то бросать его с 75 уже не надо он тоже разобьется

Тупая логика!
Как может стеклянный шарик не разбиться в первый бросок с первого этажа???

вопрос "сколько шагов" или типа того!
шагов предется проделать не минимум а максимум 19! 10 для десятков! и 9 для этажей! к примеру если он не разбился после 90! знач кидаем с сотого (можно и не кидать) тупо кидаем 91,92, так до 100! собственно когда он на 100 разобьется мы сделаем 19 ходов! и при этом можем сохранить один шар (если критический этаж=100) минимально число ходов 2! для выяснения 1 этажа таким же способом! или один бросок если кинуть сразу с первого этажа) или тупо рассуждая логически понять что кинув шар стеклянный вниз с первого этажа на бетон он разобьется! а на нормальный газон шар не разобьется и с 100! (газончик должен быть идеален)

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

...поправка 2 броска 1% случаев (разбивается с 1-го этажа)

Семь бросков
Смысл в том чтоб каждым броском кол-во этажей делить на 2. Т. Е. 1й бросок- 50ый этаж,
2-25ый, этаж 3-13ый, этаж 4-6ой этаж, 5-3ий..., 7-1ый..., или 2ой..., разницы нет.

идея
предлагаю бросать не с этажа, а с земли, а этаж можно увидеть подбросив шарик вверх у узнав до какого этажа он долетит и разобьется ли полетев обратно

Мне эту задачку дали на интервью при поступлении на работу на должность инженера электронщика (не программиста) в Израиле. Привожу свой вариант решения.
Все этажи здания делим на неравные группы. Пусть таких групп получилось К. Первая, самая нижняя группа содержит 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 (для любого этажа любой группы, вплоть до сотого).

Это не верно, т.к. доказывается лишь то, что ответ 14 для алгоритмов определенного типа. Ни доказательства того, что эти алгоритмы как-то оптимальнее других, ни того, что ответ 14 и для остальных типов, тут нету.
Выше приведено верное доказательство оптимальности.

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

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

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

Вопрос стоит не о вероятности события, а о минимальном количестве бросков.

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

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

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

Требуется же от вас алгоритм, который вы сможете применять к любому зданию, и получать ответ, НЕ ЗНАЯ его изначально.

без формул
Очевидно, что нужно разбивать этажи на группы, для минимизации количества бросков
Проходим в 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 бросков

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

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

формулы-то и использовались для получения точного ответа.

далее
В этом решении оч хорошо высвечивается его не единственность
Действительно, ес попыток 14, то можно ведь и начинать не с 10 а с 14 этажа
14+13=27
27+12=39
....
и т.д.
а ващет и с 13 можно, с любого, от 10-14
ес исследовать количество решений легко переваливает сотню
ведь можно
10-14
23-27
...

Алгоритм уже есть, осталось доказать оптимальность.
Давайте представим эксперимент в принципе. Есть два шарика, мы их бросаем, есть 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 — правильный ответ.

Вчера мне такую задачку дали на собеседовании. Попробовала дихотомией. Делить каждый интервал на 2. Получилось 12 бросков. Сказали, нет, слишком много.И что надо начинать не сверху, а снизу идти.
Ну пока так и не дошло до меня.

Вопрос: Какое НАИМЕНЬШЕЕ количество бросков понадобится, чтобы определить этаж, начиная с которого шарик разобьётся?
Ответ: 1 бросок. Минут 10 ломал голову алгоритмами, но потом вернулся к вопросу и.....

Вариант 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й шар с каждого следующего этажа.

Но зато минимальное кол-во попыток.

Вопрос идёт о минимально возможном количестве бросков. В теории достаточно двух бросков — с 25-го, и с 26-го. Если на 26-ом шарики стали разбиваться, то всё. Но это при везении.

У меня получилось 14.
Первый шар кидаем с шагом 10.
Второй шар кидаем с шагом -2 от того этажа, на котором разбился первый шар.
Получается у первого шара максимальное кол-во бросков 10, а у второго 4.

хз, о чем я думал, когда писал это решение))
с шагом 2 не получится точно определить.
19 бросков выходит у меня.

Вот еще решение в 14 шагов:
Первый шар кидаем с шагом 10 до 90. Итого 9 попыток.
Если разбился, то бросаем на 95.
Если разбился, то проверяем с 91 по 94 (всего 4 попытки)
Если не разбился на 95м, то бросаем еще 96,97, 98, 99

у меня получилось за 12
Нужно с 100 кинуть так, чтобы шар попал в 99й, потом 97й, потом 93й, потом 85й (отнимаем 2 в степени n). Если шар разобьется на каком то из этажей не долетя до земли, запоминаем этот этаж. Остальным шаром перебираем этажи

1 бросок. Кидать можно сколько угодно. Вопрос стоит сколько нужно бросков что бы определить с какого этажа разбивается шар. Так вот, с какого бросили и он разбился и есть тем самым броском. То есть фактически бросок который определяет с какого этажа шар разбивается — 1.

Мне пока непонятно вот что. Я видел формулы и вычисления, и реально получается минимальное кол-во 14.
Но вот допустим у нас шарик разбивается с 100-го этажа. Попытки у нас такие (следуя формуле):
1) с 14 этажа
2) с 27 этажа
3) с 39 этажа
4) с 50 этажа
5) с 60 этажа
6) с 69 этажа
7) с 77 этажа
8) с 84 этажа
9) с 90 этажа
10) с 95 этажа
11) с 99 этажа
12) ну и собственно с 100 и шарик разбился
Итог — 12 раз. Вот почему так, это мне и не понятно

Скорее всего, это из-за погрешности при округлении, потому что не 14 получалось, а 13,65 по формуле.

Потому что он мог разбиться на любом броске раньще 12 (например на 11 броске с 99 этажа и Тогда придется кидать 96, 97, 98 и это 14 бросков)

Наименьшее количество бросков 2 (если угадать с соседними этажами), а наименьшее количество бросков чтобы ответить наверняка 14.
P.S. Очень хорошая задача благодаря тому, что вначале интуитивно кажется, что надо начинать кидать десятками имея 18 бросков

Задача не имеет единственного правильного ответа, потому что минимальное количество бросков будет зависеть от этажа, начиная с которого шарики разбиваются. Действуя по оптимальной стратегии и деля этажи на группы (14,13,12 и т.д.), минимальное количество бросков будет находится в диапазоне от 2 (если второй шар разобьется с 1-го этажа) до 14 (если второй шар разобьётся с 13-го этажа). Однако, бросая шарики последовательно, начиная с первого этажа, минимальное количество шагов может оказаться равным 1 (когда первый шарик разобьётся сразу). Такой «неоптимальный» подход может оказаться более эффективным и быстрым чем оптимальный (деление на группы) в случаях, когда шар начинает разбиваться на 1-13 этажах, а согласитесь, что в реальной жизни, а не в условиях невесомости или кварцевого стекла, стеклянные шарики будут разбиваться именно с первых этажей здания. То есть метод простого последовательного перечисления в реальной жизни скорее всего окажется эффективнее. Да и шарик один можно сберечь для другой задачки)

берем шарик, скидываем с 50 этажа. определяем с какой половины шарик разбивается. скидываем с 25 или с 75, смотря на результат прошлого действия (допустим 25). определяем четверть. затем скидываем с 10, 20. определяем (допустим на двадцатом разбился). далее, кидаем с 15 этажа, определяем. остается определить с какого именно из этих 5 этажей (15-10 т.к. с 10-го не бьется) шарик разбивается. итого 10 шаров, если что не верно, подправьте

Сложно тут всю формулу писать.
Конечный ответ у меня — универсальная формула для любого количества этажей.
Получил квадратное уравнение типа:
X^2 + X — 2a = 0
где а количество этажей, X — Количество попыток, а также Х — первый этаж с которого начинаем проверять, Х — шаг в последовательности ( Х + Х — 1 Х + 2 + ... + Х — (Х — 1).
Подставляйте вместо "а" любое число этажей, решайте квадратное уравнение и проверяйте :)

при самом долгом поиске 50- не разбился 100-разбился => интервал 50-100 => 67 — не разбился и 84- разбился => интервал 67-84 => 73 — не разбился 79- разбился=> интервал 73-79=> 75 — не разбился и 77- разбился=> 76 разбился. Ответ: 9 шаров