Ну-с. Давайте признаем, что задачу с этажами мои ПЧ провалили полностью. Мда, как ни прискорбно, но факт, народ меня очень сильно удивил и разочаровал.
Не известно, сколько человек пытались решить задачу, но о шести из них я точно знаю. И из этих пяти решил задачу только один, и тот со второй попытки и не очень удовлетворил меня своими объяснениями, которые просятся в задаче.
Дополнение
Ну а за неимением решивших с первой попытки и и давших хорошее объяснение решения, выигравшим в этой задаче признается пользователь
Поздравляем победителя! ))))
Повторно условие задачи, все решения и пояснения приводятся в комментариях к топику. Не хотите глянуть, как это надо было?)))
Не известно, сколько человек пытались решить задачу, но о шести из них я точно знаю. И из этих пяти решил задачу только один, и тот со второй попытки и не очень удовлетворил меня своими объяснениями, которые просятся в задаче.
Дополнение
Ну а за неимением решивших с первой попытки и и давших хорошее объяснение решения, выигравшим в этой задаче признается пользователь
Cara
Поздравляем победителя! ))))
Повторно условие задачи, все решения и пояснения приводятся в комментариях к топику. Не хотите глянуть, как это надо было?)))
-
-
17.01.2007 в 00:08Имеем стоэтажный дом. А еще у нас два волшебных стеклянных шарика. Шарики эти волшебны уже тем, что разбираются строго с определенного этажа. Так вот нам надо с их помощью найти ту границу, выше которой шарики бьются. По предложению Алекса пограничным этажом будем считать низший, с которого шарики бьются.
Примечания. Разбившийся шарик уже нельзя использовать, а не разбившийся можно кидать повторно сколько угодно раз и он не изменяет своих свойств при этом.
Наша задача состоит в том, чтобы найти НАИМЕНЬШЕЕ число попыток (выкидываний шариков из окон), которого при любом пограничном этаже должно хватить для нахождения этого этажа.
Более того, желательно найти самую оптимальную схему решения задачи, самое строгое и универсальное решение.
А теперь я привожу решения двух моих крутейших в математике ПЧ (имен я назвать не могу, но если они сочтут нужным, сами авторизуются). Обратите внимание на схожесть мысли решающих. Главным общим свойством является математизированность логики, уход от эмпирики в формулы и абстрактные математические механизмы.
Обычно любая логическая задача с привлечением математического аппарата делится на стадию построения модели и стадию математической обработки модели. Оба участника прошли первую стадию в момент, у них сразу появилась определенная модель, и ни один не стал выяснять, является ли эта модель самой оптимальной, а сразу перешли к обработке полученной наобум модели качественным математическим аппаратом. Также обратите внимание и на особенности решений.
Первый решающий порадовал силой математической мысли. Ради решения детсадовской задачи с дискретным множеством из сотни членов этот человек дифференцировал уравнения и находил вторые производные!!! Решение настолько умное, что я даже не смогла точно ответить, верное оно, или нет, так как не была уверена, что поняла, где здесь вообще ответ на вопрос (напомню, задача главным образом спрашивает именно число. См выше)
Итак привожу решение первого участника:
Имеем два шарика. Разобьем дом на n УЧАСТКОВ. В каждом из которых будет m ЭТАЖЕЙ.
Первый шарик будем бросать с вершины каждого из УЧАСТКОВ до того момента, пока шарик не разобьется.
Затем будем бросать второй шарик с каждого ЭТАЖА этого Участка, постепенно наращивая высоту.
Число "шагов" z=n+m-1. Очевидно, что n=100/m.
Следовательно z=(100/m)+m-1.
Дифференцируя функцию z по m найдем, что минимум* функции достигается при m=+10 (и m=-10).
Максимально возможное число шагов при этом (максимум функции z) = 18 (если пограничным** этажом является 98).
*)Вторая произвордная z`` положительна в точке m=+10.
Обидно, что этот участник до самого конца не смог даже приблизиться к решению задачи, я очень долго терзала его, делала ему подсказки, но потом сдалась и дала полное решение. Ей богу, проблемы с кем-нибудь другим, возможно, вызвали бы во мне некоторое злорадство, дескать вот, хе-хе, какая я умная, решила за десять минут то, до чего ты за столько времени не допираешь, но тут мне прямо-таки обидно стало как за собственные проблемы или проблемы сына в школе )))))
-----------
Второй участник не стал заморачиваться со вторыми производными, но порадовал скрупулезным разбором.
Стратегия такая. 100-этажный дом делится на N равных отрезков. Первым шаром жертвуем для того, чтобы определить, в каком из отрезков находится пограничный этаж. Например, делим дом на 5 равных частей и бросаем шар, двигаясь снизу вверх, сначала с 20 этажа, потом с 40, потом с 60... Если шар разобъётся, к примеру, на 60-м этаже, это значит, что пограничный этаж находится в интервале с 41 по 60.
Вторым шаром определяем пограничный этаж в пределах найденного отрезка. В нашем примере бросаем шар с 41, потом с 42, 43 и т.д. этажа, пока он не разобъётся.
Вопрос в том, на сколько частей делить. В случае N отрезков для определения отрезка нам понадобится максимум (N-1) бросков, для определения этажа в пределах отрезка (100/N-1) бросков. Задача, следовательно, сводится к нахождению минимума функции x = (N-1)+(100/N-1)=N+100/N-2 на множестве N={1,2,4,5,10,20,25,50}. Находим N(min)=10, при этом x=18 бросков.
Выше мы исходили из того, что наперёд не известно, разбивается ли шар при броске с 1 этажа или с 100
этажа. Если же нам точно известно, что существует хотя бы один этаж, с которого шар не разбивается (или разбивается), то этажей будет не 100, а 99. Тогда, однако, минимум получаем при N=9=11, а х остаётся равным 18 бросков.
Ответ: 18 бросков.
Но это не так потрясающе. Больше всего меня порадовало дополнение, которое было прислано спустя некоторое время:
А вообще да. Нашёл ошибку.
В отрезке нужно будет сделать не 100/N-1, а 100/N-2 бросков. Мы ведь знаем уже последний этаж отрезка, бьётся на нём или нет. Например, если на 10 этаже не бьётся, а на 20 бьётся, то нужно будет сделать броски на этажах 11, 12, 13, 14, 15, 16, 17, 18. 19 этаж определяем методом исключения.
Итого правильный ответ 17 бросков.
Прошу прощения за невнимательность.
это просто пипец. Человек узнал, что его решение неправильное, анализирует свое решение еще почти ДВА ЧАСА (правда дело ночью было, но для нас, полуночников это не оправдание). И в результате этих двух часов дает коррективу просто бредовейшую!!! Ну блин! За две минуты можно было понять, что нету там никакого метода исключения, что на девятнадцатом этаже шарик может как разбиться, так и не разбиться! Ежу же ведь понятно, что каким бы макаром мы ни действовали, единственный способ доказать, что здесь есть граница - это проверить два СОСЕДНИХ этажа, на нижнем не разбивается, на верхнем - разбивается.
Ну ладно, я слишком строга. Как заметил Кара, со всяким бывает, бывает и такое, что щелкаешь как орешки гиперсложные задачи, а столкнулся с каким-то пустяком и тупишь по черному.
Так что перейдем к делу. Вот как надо решать эту задачу правильно.
-
-
17.01.2007 в 00:08Так вот первый шарик мы используем как грубый индикатор. С помощью него мы определяем тот интервал всего множества этажей, внутри которого находится искомая граница.
Этот интервал мы находим, кидая первый шарик с определенных этажей. Ну, например, как показал второй отвечающий, если мы кинули с десятого этажа, и шарик не разбился – значит, граница не в интервале 1-10 этаж, а вот если на двадцатом этаже шарик разбился - вот он, тот интервал, значит, наша граница находится на интервале 11-20
Пока все идентично тому, как решали приведенные мною участники? Ага ))) За одним малюсеньким исключением. Роль играет всего одно единственное слово, которого вы не найдете у меня, но которое по умолчанию присутствует в первом варианте и даже зачем-то специально оговорено во втором варианте. Это слово "одинаковых"
Родные вы мои! Любимые! Разве не учила вас жизнь, ВУЗ и даже школа, что самое оптимальное решение при индикации, это сделать все возможные варианты при индикации равной СЛОЖНОСТИ!
Возьмем вариант решения второго участника. Итак, если граница находится в первом интервале, сколько нам в самом неудачном случае бросков придется сделать? Правильно, десять - это если пограничный этаж десятый или девятый (не важно). А если граница в девятом интервале? Вот-вот, восемнадцать - девять бросков первым индикатором для определения интервала, еще девять бросков до девяносто девятого этажа, ну а последний, ладно уж, методом исключения )))
И что мы видим? Мы видим разницу в 8 этажей! Мы видим неодинаковые случаи, то есть неравномерное распределение количества работы в разных случаях! И естественно в таком неравномерном распределении самый неудачный случай окажется весьма большим! Единственный способ оптимизировать - распределить работу равномернее! Тогда, простите за каламбур, мы минимизируем максимум! Вот оно-то нам и надо!
Итак я доказала, что интервалы должны быть не равные. Но какие?
Ребенок догадается, что общее число попыток в интервале с номером N равно сумме номера этого интервала, то есть N и длины этого интервала, то есть числа этажей в этом интервале. Что надо сделать, чтобы эта сумма была одинаковой везде? Тоже элементарно, для сохранения суммы при увеличении одного слагаемого, должно столь же уменьшиться второе. То есть если первый интервал N=1 имеет длину k, то второй интервал будет иметь какую длину? Угадали, k-1. Сложно? Очень. Ну а интервал с номером N будет иметь длину k-N+1. Пока все понятно? Ясно откуда единица взялась?
Ну а теперь мы приходим к единственному участку решения, где требуется ну хоть какая-то простейшая база математики. Арифметическая прогрессия. Не трудно видеть, что здесь получается арифметическая прогрессия с разностью единица (новый член отличается на единицу) и начальным членом - тоже единица. (Почему начальный член единица? Потому что мы должны на всякий случай использовать нашу последовательность интервалов до конца, до самого последнего возможного интервала из одного этажа) Нам не известно одно - число интервалов и размер интервала (я сказала "одно" потому, что в последовательности такого вида данные параметры совпадают - k-тый интервал состоит из k этажей, надо найти только k)
Сумма всех наших интервалов - это есть сумма найденной арифметической прогрессии, правильно? Выводим простое свойство суммы арифметической прогрессии с шагом в единицу и первым членом = 1.
S = k(k+1)/2
А что нам известно про сумму в нашей задаче? Что она должна быть не меньше 99, но при этом быть минимальной. Логично? Вот и наша формула
k(k+1)/2 = 100
Решая это уравнение (находя его корень при положительном дискриминанте, если решать через дискриминант), и находя первое натуральное число, большее, чем корень, мы получаем ответ задачи. Этот ответ - 14 бросков.
За четырнадцать бросков мы смогли бы прочесать аж до 14*15/2 = 105 этажей (плюс один методом исключения)!
А теперь проверим решение. Имея в распоряжении два шарика, мы первый бросаем с четырнадцатого этажа. Если он бьется - то проходим вторым шаром от первого до 13-го. Первый разбившийся будет пограничным. Если не разобьется никто - пограничным признается 14-й. Если первый шарик не бьется при первом бросании, поднимаемся на 27-й этаж (14+13), ситуация повторяется, потом поднимаемся на 39-й (14+13+12), потом на 50-й, на 60-й, 69, 77, 84, 90, 95, 99.
Воть и все )))
Как видите, с такой формулой жить гораздо веселее. Во-первых, формулы - это вообще признак хорошего тона, это гораздо красивее, чем мы просто подбирали бы цифры и считали бы, получится с нею дойти до сотого этажа, или не получится, даже если по времени это меньше, чем на вывод формулы. Во-вторых, так гораздо универсальнее. Мы должны привыкать находить самые универсальные пути, которые можно применить при максимальном числе подобных задач. Так, например, теперь, если меня спросят про тысячеэтажный дом и с таким же условием, я не буду долго думать, а просто подставлю в готовую формулу вместо сотни - тысячу. Даже более того, усвоив простейшие принципы при решении такой задачи можно решить гораздо более сложную - при условии, что шара у нас три, четыре, p шаров; что было бы просто невероятно сложно, не дойди мы до описанных принципов. (кстати, кому интересно, может ради прикола вывести общую формулу для Х этажей и р шаров, теперь это очень легко)
Ну что, товарищи, я вам скажу на последок. Учиться, товарищи, учиться, и еще раз учиться! всем спасибо за внимание )))))))
-
-
18.01.2007 в 11:20А заодно максимизируем минимум!
А вообще видимо, я это решал так же, как и все =) И так же как и все оказался более-менее близко к решению, но в то же время недостаточно близко =)
ЗЫ картинка... кстати... совсем тут не кстати... Зачем такие гадости выкладывать?
-
-
18.01.2007 в 16:09-
-
18.01.2007 в 17:11-
-
18.01.2007 в 17:41-
-
18.01.2007 в 18:30-
-
18.01.2007 в 18:51-
-
18.01.2007 в 19:04-
-
18.01.2007 в 19:18нет, ну ты посмотри на этот шедевр! Ты посмотри на это! Старая короткостриженная алкоголичка абсолютно голая с ребрами наружу и тощими бедрами развалилась в позе Данаи на капоте старого классического милицейского уазика с открытой дверцей, и радостно и светло улыбается беззубой улыбкой!!! Все это в темноте ночи. Это ж просто пипец!! Более замечательного шедевра я не видела в сети месяца три! )))
-
-
18.01.2007 в 19:28А может быть в тебе?
-
-
18.01.2007 в 19:29-
-
18.01.2007 в 21:08так недолго нормального человека импотентом сделать...
ой, прости, об этом я не подумала )))
впрочем ладно тебе, встретятся в твоей жизни красивые девушки )))
-
-
18.01.2007 в 22:46-
-
20.01.2007 в 10:56-
-
20.01.2007 в 13:13-
-
20.01.2007 в 17:44Товарищи, вы название топика вообще читали? По-моему картинка не только шедевральная, но и вполне уместная.
-
-
20.01.2007 в 18:13-
-
20.01.2007 в 18:25-
-
20.01.2007 в 19:32-
-
22.01.2007 в 11:08Он прав. Тебе не может всерез это нравится, у меня даже нет слов для описания этого ужаса. Чувство красоты у человека напрямую связано с душевным здоровьем... Конечно, с моей точки зрения. Поэтому тебе, как хорошему человеку это нравится не может. Категорически.
-
-
22.01.2007 в 16:06Ну разумеется, я не имею ввиду что испытываю эстетическое наслаждение от вида этой картинки, нет же, мне нравится карикатурность и комичность сцены. Что касается эстетизма - это я, конечно же, шутила. Я и помыслить не могла, что кто-то не поймет этого.
Ведь я же пишу:
Старая короткостриженная алкоголичка абсолютно голая с ребрами наружу и тощими бедрами развалилась... улыбается беззубой улыбкой!!!
Что не ясно?
Killen Lepra Где? =) В твоем личном архиве =) (и только там!)
а тебе вообще можно было бы и перестать хныкать. В конце концов я же не вставляю эту картинку на свой аватар, и не флужу у тебя на личном дайрике с этим аватаром. Так что вместо нытья и оффтопов о картинках лучше бы участвовал по-существу. Хотя бы по поводу задач. Я тебе клятвенно обещаю, что когда ты окажешься победителем в одной из моих задач, я под твоим ником выставлю самую лучшую и реально эстетичную картинку из тысяч в моей коллекции, а если и она тебе не понравится, ты сам выберешь какую угодно картинку по вкусу, и я ее поставлю под твоим ником. А пока, вот, даже победитель согласился с данной картинкой к топику, что уж тебе возмущаться.
LAW Тебе не может всерез это нравится
хе-хе))) вижу, я так тебя достала с этими мягкими знаками в -тся/-ться, что ты решила вообще без них обойтись на всякий случай ))))))
-
-
22.01.2007 в 17:08Тогда уж мы =))))))
-
-
30.01.2007 в 14:45Lepra Знаешь, я никогда не любил математических задач. Как-то не сложилось. Но в твоем исполенении они набираются какого-то особенно нерпиятного смысла. Издевательского. Который я в них, правда, и так раньше видел... Хотя... в целом это фигня
Тут я написал потом два абзаца своей оценки тебя как личности сквозь призму математических задачек и всего с этим связанного, но потом решил это тут не публиковать по причине того, что это в общем не касается темы и очень личное...
А картинка... занятная и забавная.
Каре наши поздравления!
-
-
07.08.2008 в 12:37Оба участника прошли первую стадию в момент, у них сразу появилась определенная модель, и ни один не стал выяснять, является ли эта модель самой оптимальной,
Очень верно.
Как говорится, "мало вешали, зато много дифференцировали"... вот и результат.