Математические и логические задачи



  • В скандинавских древних сказах
    Есть забавные примеры.
    Гномы падки до алмазов,
    Что найдут — несут в пещеры.

    Так как знал лесной народец,
    Что поблизости их нету,
    То построили заводец,
    Спрятанный в горе от света.

    Там алмазного конвейра
    Было вечное гуденье,
    А народ благоговейно
    Думал, что землетрясенье.

    Но однажды злые тролли
    Дождались-таки момента:
    Все приборы раскололи
    Испытательного стенда.

    Чтоб камней проверить прочность
    И никто не видел чтобы,
    Гномы стали тёмной ночью
    Их бросать из небоскрёба —

    Выяснять этаж, с какого
    (Значит, выше и подавно)
    Камень, брошенный с балкона,
    Будет биться постоянно.

    Но алмаз — на вес алмаза,
    Жалко бить такие камни.
    Добровольцам дали сразу
    Только два для испытаний.

    Пусть на каждое бросанье
    Полагается минута.
    Сколько в стоэтажном зданьи
    Гномы максимум пробудут,

    Если под покровом ночи,
    Пока люди не глазеют,
    Каждый гном до смерти хочет
    Сделать это побыстрее?



  • Постоянно они могут не биться даже с сотого этажа, но как это определить ? Или сделать погрешность для определения" постоянно"- допустим 90% случаев ( или 95), тогда уже можно посчитать, сколько статистически экспериментов для этого нужно ( но очень долго и долго счяитать придется).
    Если принять условие, что они бьются "постоянно"( 100% случаев) с какого-то уровня ( хотя на практике этого не будет), упростив задачу, то можно попробовать посчитать..



  • самая близкая степень двойки для 100-это 7, т.е двоичный логарифм из 100 окгругляем до 7. Можно еще прибавить 1 попытку на проверку нижнего( верхнего ) этажа на всяукий случай( хотя это не нужно). Те. ответ 7 ( или 8☺ )



  • @xajik ответ неверный



  • Участник @xajik написал в Математические и логические задачи:

    Если принять условие, что они бьются "постоянно"( 100% случаев) с какого-то уровня

    Это и имелось в виду, скорее всего


  • T

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

    Определения

    Назовём этаж плохим, если его номер не ниже номера уже проверенного этажа, с которого разбился алмаз.
    Назовём этаж хорошим, если его номер не выше, чем наивысший уже проверенный этаж, с которого алмаз не разбился.
    Назовём остальные этажи подозрительными - они выше всех хороших и ниже всех плохих.
    Примечание: если первый алмаз ещё не кидался, то хороших или плохих этажей нет - все подозрительные.
    Примечание: если первый алмаз разбился сразу, то хороших этажей нет - все или плохие (с какого разбился и выше), или подозрительные (ниже этажа, с какого разбился).
    Примечание: если подозрительных этажей нет - это значит, что эксперимент закончился успешно (не значит оптимально) - гномы точно знают, где проходит граница между хорошими и плохими этажами. Если остались подозрительные этажи, это значит, что их задача не решена.

    Разобьём время пребывание гномов в доме на два этапа: первый этап длиной T1, когда они кидают первый алмаз и второй этап длиной T2, когда первый алмаз потрачен, и они кидают второй.
    Если представить себе, что первый алмаз уже потрачен, то гномы обязаны, тут никуда не денешься, второй алмаз кидать с каждого подозрительного этажа по порядку, начиная с нижнего подозрительного (иначе есть вероятность потратить и второй алмаз, не получив точного ответа). В этом случае T2 равно максимум количеству оставшихся подозрительных этажей. Теперь задача гномов сводится к тому, чтобы оставить как можно меньше подозрительных этажей для второго этапа и в то же время не растягивать по времени первый этап.
    Они могут на первом этапе, например, действовать методом дихотомии, а именно кинуть с 50-го этажа, потом с 75-го, потом с 87-го и т.д. Т.е., делить оставшийся отрезок примерно пополам. Не факт, что именно этот метод оптимален - нужно проверять. Допустим, мы знаем оптимальный метод для первого этапа. Тогда можно найти T1 как наиболее вероятное кол-во сделанных попыток до разбивания первого алмаза, а как найти T2 - см. выше. Останется сложить T1 и T2.
    На самом деле я знаю, что есть неточность в рассуждениях выше - "оптимизировать" на самом деле нужно оба этапа одновременно.
    Дальше я продолжать сейчас не буду, потому что нужно работать.



  • Ну так оптимально по- "дихотомии" ( двоичному разбиению) и должно быть. Двоичный логарифм( по основанию два) от 100 будет приерно 7.(6,644)-столько бросков нужно сделать ( столько алмазов потратить, если они такие дорогие). Но гномов можно поставить одновременно, и если алмазов не жалко и можно отследить результаты каждого броска при одновременном бросании- то можно сделать это сразу одновременно за 1 минуту, но тогда все 100 алмазов.
    Иначе я не понимаю одно из условий( легко запутаться при таком количестве текста и нечеткости ). Часто пропускаю такие длинные условия, например, не понял, что вычисляется затраченное время, а не количество алмзов, но все равно не ясно четко условие...



  • Метод дихотомии неправильный, если кинуть сразу с 50 этажа, потом 49 раз кидать? многовато



  • Метод дихотомии- деление пополам. Если сначала кинуть с 50, то потом ( если разбилось) - с 25 этажа ( или другого, близкого к середине отрезка от нуля до 50). Пример. Кидаем с 64-32-16-8-4-2 этажей. И каждый раз , предположим, будет разбиваться.Бросили 6 раз, и предположительно, на 1 этаже может не разбиться, но мы должны и это проверить, поэтому не менее 7 бросков ( затрат алмазов) в теоретически самой длиннй серии попыток мы должны использовать. В случае, если где-то в серии не разбивается, мы делаем попытку "дихотомии" наверху отрезка, который еще не исследовали ( например на 16 этаже уже не разбилось, поэтому наш следующий бросок- середина от 32 и 16- то есть 24 этаж и так далее), продолжая делить его пополам- и те же 7 максимальных попыток ( часто 6).
    Если есть зависимость цены времени от цены алмазов ( то тоже по логарифму, но уже с другими основаниями можно быстро вычислить число одновременных попыток), то мы можем кидать разное число камней одновременно ( тогда это будет троичное и так далее разбиения). Можно кинуть сразу 100 одновременно со всех 100 этажей и потом тупо посчитать количество целых камней, если время 1 минута времени намного ценнее стоимости 99 алмазов.
    Н я, возможно, просто не понял условий полностью. В чем сложность подобных приукрашенных условий- часто непонятно, что требуется найти и при каких ограничениях.


  • T

    @xajik по условию алмаза ровно два. Можно разбить оба, но не больше.



  • Добровольцам дали сразу
    Только два для испытаний.
    я понял, что каждому из добровольцев ( а их несколько) дали по 2 камня, те. камней не 2
    хотя условие нечектое, о чем я уже предупредил хотя бы сам себя



  • если всего 2, то просто кидаем со 2-го, потом с 4-го, максимальная последовательность 50


  • T

    Участник @xajik написал в Математические и логические задачи:

    Добровольцам дали сразу
    Только два для испытаний.
    я понял, что каждому из добровольцев ( а их несколько) дали по 2 камня, те. камней не 2

    Если было бы так, то решение простое - 100 добровольцев - по 1 на каждый этаж и каждому по алмазу. Занимает ровно минуту.



  • Это если стоимость минуты времени намного ценнее стоимости 99 алмазов, а если нет?
    Пусть Химичка потом уточнит, сколько алмазов. Всего 2?
    А , я понял, если 2 всего, то кидаем сначала на 33 этаже. и потом снизу если разбился-33 попытки. Если не разбился- то на 66 и так далее.
    34 попытки должно выходить максимально.
    Тогда это разбиение на 3, и достаточно частый случай, наверно, в общем случае это переформулируется на разбиение на "эн плюс 1" в подобных примерах. Наример, задача взвесить 27 монет на весах. найти 1 бракованную монетку из той же серии.



  • @xajik можно и меньше, чем 33
    Да, два алмаза на все опыты



  • Пусть х- количество частей. на которые мы отсекаем" 100 ( делим). Тогда 100/х количество оставшихся попыток, когда первый камень разобьется. Уравнение ( функция) х+100/х и нам надо решить ее минимально, Блин, тут надо вспоминать производные ))
    Так что ль? Может быть лучше есть метод, но я пока на этот только смог надумать.
    В Вольфрам Альфа, чтобы никаких производных не вспоминать, сказано. что локальный минимум при х=10, т.е максимальное количество попыток 19
    Но я не уверен., что правильно.
    На всякий случай, поясню метод. Мы кидаем с того этажа, который после оптимального "разбиения/отсечения из уравнения. Если оптимально 10, то делим 100 на 10-10 этаж. При разбитии камня, нам остается 10 попыток пробежаться снизу по всем отсеченным этажам. Если не разбился, то идем на 10 этажей выше и повторяем.



  • @xajik ответ 19 неправильный



  • Ну тогда я не решил ☺ 👎 👨‍🏫 👩‍🏫 🔢 💯 И сегодня вряд ли решил бы, задачка сложная и плюс трудный день).
    Там еще хитрость, что на последнем этапе "вверху" когда могут остаться 2 камня перебрать получается быстрее, чем по одному этажу. И еще я банально ошибся в уравнении-делить надо на х-1, т. е 100/(х-1)+х решаем
    локальный минимум 11 и тогда ответ 17
    но хитрость последних двух камней может перечеркнуть и это, и я не уверен, что нет метода получше
    методом перебора решать не хочу. а пока ничего больше на ум не приходит
    подумал, что надо решать "с последних этапов- к первым", и что-то типа рекурсивным методом, ведь соотношение- разбились, не разбились дает разную скорость при разбитых и неразбитых камнях, но это нужно время и мозги ☺ , которых у меня пока не предвидится



  • чтоб не оставялть на потом, последняя попытка. если не решил, то сдаюсь ☺ ))
    Рекурсивным методом решаю, это не перебором, но достаточно муторно-но надежнее( вряд ли ошибусь сильно), на последнем этапе должно остаться ( оптимально ) 4 этажа, тогда нам нужно всего 2 минуты ( 2 попытки)
    Тогда приходим к такому методу-сначала бросаем на 15 этаже, если не разбился- то повышаем на 15-1 этаж и бросаем выше-т.е на 29, потом на 42-54-65-75-84-92 этажах ( каждый раз повышая на последнее повышение минус 1), если где-то камень разбивается, то последним за суммарные 15 попыток проходим по одному снизу оставшиеся. В идеале, здание должно иметь 109 этажей, тогда точно 15 попыток требуется( если ни один камень не разбился, то в последний раз можно сбросить оба, сэкономив время)
    ответ при таком методе 15
    хотя если начать с 14 тем же методом, то получится 14 всего, странно☹ , опять криво решал, кароче , ответ 14 и сдаюсь ☺



  • @xajik ответ 14, ход мыслей кривоват, но близок, начинать надо не с 14-го этажа
    На 109 действительно нужно уже 15
    С ходом мыслей помогу: если разрешается сделать N бросаний, какова максимальная этажность здания, для которого эта задача имеет решение?



  • Если начинать с 13, то не получается у меня таким методом. 13-25-36-46-55-63-70-76-81-85 сделали 10 бросков ( попыток), осталось 3 ( до полных 13) и надо 15 оставшихся этажей проверить- не сходится.( или 14 если не кидать на 100).
    Если отступить на шаг назад -бросили на 81 этаже, осталось проверить 19 этажей за 4 попытки...Мы не можем отсечь больше 3 этажей снизу, ведь если камень первый разбивается, нам не хватит более 3 попыток, чтобы уложиться в 13. Поэтому это тоже безрезультатно. Даже если предположить, что на 100-том кидать не нужно.
    Не вижу как улучшить метод, да и подустал от задачи ))
    По максимальной этажности здания- пока не могу вывести общую формулу рекурсии. На первом этапе 5 этажей....а, теперь начинаю что-то понимать ☺ ; значит, у меня ошибка в подходе была, нам не нужно проверять с точностью все этажи, в формуле рекурсии у меня тогда была ошибка. На первом этапе ( в решении задом наперед) если камень разбился, нам нужно, чтобы осталось 2 этажа и мы кидаем на одном из оставшихся...ТОгда для 2 бросков нам нужно 6 этажей, для 3 бросков-10, 15-4 броска ( минуты)
    далее 10-15-21-28-36-45-55-66-78-91-105, те. 12 попыток нужно, т.е. кидать нужно начинать с 12 этажа, потом с 24-35-....
    пока не могу изобразить формулу рекурсии ( лень, да и трудновато), из Вольфрам Альфа показана формула a_n = 1/2 (n^2 + 5 n + 6) (for all terms given)
    хотя у меня бы другая формула была бы, через эн от эн минус 1

    А откуда такая задача? Хоть я в математике профан, но все равно сложная....)( ну или хотя бы требующая достаточно времени) Еще и в стихотворной форме, наверно из какого-то сборника взята...



  • Мне кажется, если опять не ошибся, есть "запас" в 3 этажа, поэтому можно начинать бросать хоть с 9, хоть с 12 этажей включительно ( и скорее всего даже с 13, если потом в случае разбития бросать со 2-го вверх), далее прибавляем +13 этажей, потом +12 и т.п, каждый раз минус один этаж к прибавлению ( чтобы в случае разбития первого камня оставалось ровно 12-количество истраченных попыток+1 этаж для пробегания оставшихся , начиная со 2-го снизу еще неисследуемого на каждом из бросаемых последовательностей этажей)
    т. е 9-22-34-45-35-64-72-79-85-90-94-97 этажи кидаем если камни не разбиваются, 13 попыток ( 13 минут), соответсвенно можно сдвинуть с 9 до 13 этаж вначале, подстроив все остальное ( сдвинув)
    но в этот момент я опять начал сомневаться ☺ , поэтому завершаю решение, не уверен в абсолютной точности

    С интересом посмотрю за подробным правильным ответом и решением, но я на этом-пас, слишком много времени потратил на задачу ( часа полтора в общей сложности-даже больше), хотя освежил голову- было на пользу даже в случае совершенно неверного решения.))



  • Я решал неправильно, спасибо Химичке)). Хотя метод я понял в общих чертах самостоятельно ( с какой попытки -ужас?? ☺ )

    Но в связи с этой задачей возникла другая формулировка задачи, изменение условий. Все то же самое-2 камня алмаза, 100 этажей, но алмазы обладают тремя качествами- не разбиваются, разбиваются и "светятся"- то есть на каком-то конкретном этаже они от удара начинают светиться( ну или что-то такое...).
    На каком-то определенном этаже они светятс. этажом ниже-не разбиваются, а одним этажом выше- уже разбиваются. задание- найти этот "светящийся этаж. И сколько времени ( попыток ) займет?



  • @xajik я бы просто снизу вверх кидала, но это не самый оптимальный вариант



  • Жил-был кот у тёти Вали,
    Котофеем, помню, звали.
    Занял целую террасу
    И ни в чём не знал отказу —

    Ни в сосиске, ни в сметане,
    А меж тем под ним в чулане
    Жил мышонок-невидимка
    В пятикомнатной квартирке.

    Все пять комнаток, конечно,
    Были там попарно смежны,
    И из всех своих каморок
    Он прогрыз пятёрку норок.

    Слух у Котофея тонок:
    Слыша, как скребёт мышонок,
    Он стряхнул с себя дремоту
    И помчался на охоту.

    Два прыжка — и он в чулане;
    В нос мышиным духом тянет,
    А в стене подряд пять норок,
    Не поймёшь, откуда шорох.

    Где мышонок, кот не знает —
    В середине или с краю,
    Но, просунув в норку лапу,
    Угадает — может сцапать.

    Если он не угадает,
    Мышь всегда перебегает
    Из каморки, где сидела,
    Рядом вправо или влево.

    Расскажи, в каком порядке
    Надо в норки лазить лапкой,
    Если наш котяра хочет
    Всё закончить покороче,

    Ну а мышь дрожит за шкуру
    И притом совсем не дура?
    Сколько сделает ходов
    Самый умный из котов?