Прошлогодняя задача про радиоактивные шары и Гейгера НЕ решена. Дерзайте)
1. Чем бег отличается от ходьбы? tokomak(15:49:36 / 04-01-2013): тем, что при ходьбе в любой момент времени хоть одна нога да опирается на поверхность
Почему хрустит свежий снег под ногами?nictrace(16:04:57 / 04-01-2013: хрустит когда ломаются миллионы лучиков у снежинок.
2.1 Один из работников настаивает на том, чтобы ему платили шоколадом. Есть плитка шоколада, стоимость которой соответствует семидневной зарплате этого сотрудника. Она уже размечена на семь равных кусков. Если разрешено сделать всего два разреза плитки, а работнику нужно платить в конце каждого дня, как можно решить эту проблему? Чего не хватает в условии?
2.2 Один из работников настаивает на том, чтобы ему платили шоколадом. Есть плитка шоколада, стоимость которой соответствует 15-тидневной зарплате этого сотрудника. Если разрешено сделать всего два разреза плитки, а работнику нужно платить в конце каждого дня, как можно решить эту проблему? Чего не хватает в условии?
tokomak(16:36:56 / 04-01-2013) иbaa1964(16:39:08 / 04-01-2013) Первая шоколадка 7 делиться двумя разрезами на 1, 2 и 4. В первый день выдаем 1, во-второй день выдаем 2 и 1 забираем, в третий день выдаем 1, в четвертый день выдаем 4, а 1 и 2 забираем, в пятый день выдаем 1, в шестой день выдаем 2 и 1 забираем, в седьмой день выдаем 1. В условии надо дописать что работник не съедает шоколад.
Вторую шоколадку двумя разрезами надо разделить на 1, 2, 4 и 8. Алгоритм выдачи такой же.
3. Как переправить через реку волка, козу и капусту? Этой задаче более 1000 лет. Вот ее новое издание.
Четырем туристам нужно ночью переправиться через реку по подвесному мосту. Мост уже сильно обветшал, в настиле есть дыры, и он может выдержать одновременно не более двух человек - если на мосту окажется более двух человек, мост обрушится. Туристам нужно освещать дорогу фонариком — иначе они могут провалиться в дыры в настиле моста и погибнуть, но у них есть только один фонарик. Эти четыре человека передвигаются с разной скоростью. Иван может перейти мост за одну минуту, Степан — за две минуты, Богдану нужно пять минут, самый медлительный из всех Абрам — ему потребуется десять минут, чтобы перейти мост. Ровно через семнадцать минут мост обрушится, установлена часовая мина. Каким образом все четверо могут успеть через него переправиться?
Правильный ответ от bom100(17:54:43 / 04-01-2013): Иван + Степан = 2 минуты; Иван возвращается = 1 минута; Абрам + Богдан = 10 минут ( Иван остается ждать ); Степан возвращается за Иваном = 2 минуты;Иван + Степан = 2 минуты
Итого = 17 минут
4. В одной школе есть такой ритуал в последний день занятий: ученики выходят в холл и стоят около своих шкафчиков, в которых хранится одежда. По первому свистку каждый ученик открывает свой шкафчик, по второму свистку ученики закрывают четные шкафчики (то есть шкафчики номер 2, 4, 6 и т. д.). По третьему свистку ученики меняют положение дверцы каждого третьего шкафчика, то есть если она была открыта, ее закрывают, а если закрыта — открывают. Это происходит со шкафчиками номер 3, 6, 9 и т.д. По четвертому свистку меняется состояние дверцы каждого четвертого шкафчика, по пятому свистку каждого пятого и т.д. Это небольшая школа и шкафчиков всего 100. По сотому свистку ученик, который стоит рядом со шкафчиком под сотым номером (и только этот ученик), меняет положение дверцы этого шкафчика. Сколько шкафчиков после этого оказываются открытыми?
Правильный ответ дал inno(17:51:51 / 04-01-2013): Шкафы с номерами, совпадающими с квадратами чисел от 1 до 10: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100
пояснение приводится в редакторской правке
Понятно, что открытыми останутся шкафы после НЕЧЁТного числа операций (открываться/закрываться). Для каждого числа от 1 до 100 следует рассмотреть его Делители, а это всегда пары (единицу и само такое число включаем!), то есть делителей ЧЁТное число, за исключением полных квадратов, для которых, наоборот, число делителей НЕЧЁТное число.
Поясним: 17=1х17 - 2 делителя, шкаф будет закрыт; 30=1х30=2х15=3х10=5х6 - 8 делителей, шкаф будет закрыт; 9=1х9=3х3 - 3! делителя, шкаф будет открыт
5. У вас три корзины с фруктами. В одной из них — только яблоки, в другой — только апельсины, наконец, в третьей — и яблоки, и апельсины. Вы не видите, какие фрукты внутри корзин. На каждой корзине есть хорошо заметный ярлык, но информация на нем неверна. Вам разрешено (с закрытыми глазами) вынуть из одной корзины один фрукт и потом рассмотреть его. Как можно определить, что в каждой из корзин? За одну попытку!
Federal(16:27:37 / 04-01-2013): Ищем ярлык "яблоки и апельсины", лезем туда и достаем то, что там лежит. Это корзина с тем фруктом, что достали. Осталось два ярлыка на двух корзинах. Один совпадает с фруктом, который достали, но в этой корзине фрукт другого вида. Третья корзина с двумя видами фркутов.9. Эта 9-я задача прошлой пятницы. Прошлогодняя, можно сказать, задача не решена. Возвращаем условие: "Это Челябинск. Челябинские мужики настолько суровы, что"(с) катают чугунные шары в свинцовых трусах. Работа у них тяжелая. Дано:
На рабочем месте Челябинского Мужика (ЧМ) 15 перенумерованных шаров, 2 из которых - радиоактивные. Неизвестно, какие именно. Есть простенький счетчик Гейгера и определенный алгоритм, благодаря которому удается для любой партии найти 2 радиоактивных из 15 шаров, используя не более 7 замеров.
Сформулируйте этот алгоритм.
Задача сложная. Если решать самому, без гугла, то очень. Поэтому
Подсказка1. "ЧМ" формирует различные группы из перенумерованных шаров. В группу может входить от одного до пятнадцати шаров. Затем производится ЗАМЕР на наличие активности в группе, для чего используется Гейгер. Счетчик простенький, он измеряет только наличие радиоктивности или ее отсутствие (Да/Нет), а не величину. С его помощью НЕЛЬЗЯ определить, сколько активных шаров в группе!
Подсказка2. Для того, чтобы решить эту задачу, нужно уметь решать более простые, но методически близкие задачи на взвешивание "монет", типа "1 монета фальшивая из 13 за 3 взвешивания на весах Фемиды" (или про ТРИ корзины с фруктами в этом выпуске). Но при решении данной задачи от "монетной методики" нужно будет вовремя отказаться)))!
Подсказка3. Данную задачу предложил к публикации уважаемый коллега Савва. И оказалось, что задача имеет минимум 2 разных правильных алгоритма!
ЗЫ. Если эти подсказки Вам лично ничего не говорят - забудьте про них и не обращайте внимания, к формулировке самой задачи они не имеют никакого отношение....
Комментарии
1. Кажется очень простые вопросы.
Бег от ходьбы отличается тем, что при ходьбе в любой момент времени - хоть одна нога да опирается на поверхность... а при беге - есть такая фаза, когда обе ступни "парят" аки птицы...
Хрустит снег... хм, наверное, из-за большого кол-ва воздуха, снег то свежий, ему есть куда уплотняться и хрустеть...
нет. хруст - это когда ломаются миллионы лучиков у снежинок.
Может быть, но, с другой стороны - они по тому и ломаются, что им есть куда ломаться - кристаллы льда вперемешку с воздухом.
Если бы звук издавали бы только кристаллики льда - возможно, это был бы звон, а не хруст...
+
Про бег все правильно. Спортивная ходьба от бега отличается тем, что в любой момент времени одна нога должна касаться земли иначе дисквалификация.
+
2. Видимо шоколад низя съедать сразу... а разменивать его назад, верно?
верно, но что дальше?
Дальше всё элементарно :)
Вот, после двух изломов (резов) получаем три кусочка шоколадки, я все семь кусков пронумеровал:
(1) (23) (4567)
В первый день даём (1), во второй (23) и отымаем (1), в третий даём опять (1), в четвёртый отымаем усё и даём (4567)... ну, и т.д. опять добавляем (1), потом отымаем но даём (23)... в седьмой день - отдаём всё.
+
Класс! Но такой расклад возможен только если работник не любит шоколад :)
Первая шоколадка 7 делиться двумя разрезами на 1, 2 и 4. В первый день выдаем 1, во-второй день выдаем 2 и 1 забираем, в третий день выдаем 1, в четвертый день выдаем 4, а 1 и 2 забираем, в пятый день выдаем 1, в шестой день выдаем 2 и 1 забираем, в седьмой день выдаем 1. В условии надо дописать что работник не съедает шоколад.
Вторую шоколадку двумя разрезами надо разделить на 1, 2, 4 и 8. Алгоритм выдачи такой же.
+
А в задаче 2.2 - резать шоколад видимо нужно уже в двух осях... но шоколадка должна быть 3 на 5...
9. Элементарная задача...
Обычным половинным деление решается, и если идёт тотальная невезуха и шары (два радиоактивных) всегда попадают в разные разделённые группы, то, как раз, нужно семь измерений, что б добиться уменьшения путём деления на две части каждой из групп - до одного шара.
PS на скока я понимаю, если шаров будет 16 - то решается так же, за 7 измерений максимум...
действительно, не понятно в чем прикол
Ув. Токомак. Требуется 100-процентное решение, т.е. абсолютная надежность. Как от этого зависит ваша жизнь. Ну, скажем, вам нужно взять в полет только два Активных Элемента ( предположим, что они достаточно тяжелые), а выбрать какие можно взять с собой можно только "на далекой космической базе". Вот вы выбрали и полетели. К середине полета один АЭ кончился, вы вставляете второй - а он не фурычит. Вы ошиблись. Всё, псец, приплыли...
А простым "пополамом" задачка не решается. Я сейчас вам покажу почему.
Вы получаете две группы элементов, положим 8 и 7. Вы подносите к ним счетчик Гейгера - и он в обоих случаях показывает наличие АЭ. Т.е. искомые элементы разделились. При этом 2 измерения вы уже использовали, у вас осталось только пять. С первой восьмеркой вы разобрались с помощью 3-х измерений. У вас остается два измерения и 7 элементов, только два! измерения... Это не решение. Вы в конце получаете два элемента, один из которых излучает, а второй - нет. В полет какой брать будете? Наугад? а если ошибетесь... Короче. это не решение. Есть решение, более того, как мы с автором пятничных задач недавно выяснили, даже два, которые дают однозначное решение - вот эти два элемента активные. И никаких угадаек. Вот такая фишка.
Да, верно, с 16 - не выйдет, только с 15!!!
Там при последнем разделении начатом с 8-ми шаров - оставшийся последний, вроде не радиоактивный шар нужно подложить в разделённую на две части первую группу из 7.... и она станет уже из 8 (т.е. 4 на 4)...
У вас на последнюю группу остается ДВА! измерения. А двумя измерениями задача не решается.
Да, с делением чисто на две кучи - так нормального решения я и не нашёл... но там, ниже - я написал вариант... похож на верный...
Задача 9...
Возможный вариант:
1. Делим на 5 кучек по 3 шара... Тратим 4-ре измерения и выявлем две радиоактивные кучи, т.е. 6-ть шаров;
2. Шесть шаров делим на три кучи по два шара... Тратим 2-ва измерения и снова выявляем две радиоактивные кучи, т.е. 4-ре шара;
3. Теперь пронумеровав 4 шара по двум кучам: 1,2 и 3,4 и зная, что радиоактивный есть в обоих из них - нужно только одно измерение (последнее), что бы понять, чё по чём... переставляем шары и получаем: 1,3 и 2,4 - если куча 1,3 радиоактивная, то вот они искомые, а если нет... то искомые - это 2,4.
Вы делите 6 шаров на три группы. Первое измерение дает плюс. Второе - минус. И получается, что вы не знаете, у вас оба шара в первой двойке или один в первой, а второй в последней, которую вы еще не измерили. А если вы ее измеряете, и она дает снова плюс. Получается две пары шаров по 2 элемента и только одно измерение - задача не решается.
Кошмар... сложная задача :)
Пятая самая простая. Ищем ярлык "яблоки и апельсины" лезем туда и достаем то, что там лежит. Это корзина с тем фруктом, что достали. Осталось два ярлыка на двух корзинах. Один совпадает с фруктом, который достали, но в этой корзине фрукт другого вида. Третья корзина с двумя видами фркутов.
+
5. Решить можно, если разрешается узнать из корзины (или выбрать корзину) с каким ярлыком вы вытаскиваете фрукт... Решение двумя словами не объяснить, придётся расписывать подробно:
Имеем корзины с ложными надписями: (Я)блоки, (А)пельсины, (С)месь.
Теперь из первой корзины (Я) мы вытаскиваем:
(1) яблоко -> значит в корзине (Я) = смесь, а в корзине (С) = апельсины, так как апельсины не могли по определению быть в корзине (А), там = яблоки;
(2) апельсин -> значит в корзине (Я) = апельсины, в корзине (А) = смесь (так как реальная смесь не может быть в корзине (С)), ну а в корзине (С) = яблоки.
Если залезть в корзину с ярлыком (А) - то решение аналогичное...
А вот, если лазить в корзину с ярлыком (С), то варианты таковы:
(1) яблоко -> значит в корзине (С) = яблоки, а в корзине (Я) = апельсины, так как апельсины не могли по определению быть в корзине (А), там = смесь;
(2) апельсин -> значит в корзине (С) = апельсины, в корзине (А) = яблоки (так как реальные яблоки не могут быть в корзине (Я)), ну а в корзине (Я) = смесь.
Нарисовать на листке бумиги - и решается просто...
5. Если достали яблоко (Я), это точно не корзина апельсинов. смотрим ярлык - там может быть написано А или АЯ. Если АЯ - это корзина с яблоками, тогда А-смесь, и Я-апельсины. Если А - это смесь, под Я будут апельсины, яблоки под АЯ.
Если поймали апельсин, рассуждаем аналогично
4 закрыты будут шкафчики с номерами имеющими нечётное число делителей (без 1)
25 шт являющимися простыми числами 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
30 шт произведением 2-х простых чисел 2* 3 5 7 11 13 17 19 23 29 31 37 41 43 47; 3*5 7 11 13 17 19 23 29 31 5*7 11 13 17 19; 7* 11 13
5 шт произведением трёх простых чисел 2*3*5=30, 2*3*7=42, 2*3*11=66, 2*3*13=78, 2*5*7=70
15 шт произведением квадрата простого числа и простого числа 2*2* 3 5 7 11 13 17 19 23; 3*3* 2 5 7 11; 5*5*2 3; 7*7*2
4 шт произведением квадрата простого числа и двух простых чисел 2*2*3*5 2*2*3*7 2*2*3*11 3*3*2*5
3шт кубом или пятой простого числа 2^3, 3^3, 2^5
8 шт произведением 3 или 4 или 5 степени простого числа и простого числа 2^3* 5 7 11 13; 3^3* 2; 2^4*3 5; 2^5*3
100 -25 -30 -5 - 15 - 4 - 3 - 8 = 10
В общем остаются только 1, квадраты простых чисел 4, 9, 25, 49 и произведения квадратов простых чисел 100 и четвёртые и восьмые степени простых чисел: 16 64 81 = 10 шт
БРАВО, это действительно квадраты чисел от 1 до 10:
1, 4, 9, 16, 25, 36, 49, 64, 81, 100
1. Бег - три буквы, ходьба - 5 букв. :) Снег по морозу хрустит. ;)
ходьба - 6, в 2 раза больше)
видать Ь - не буква ;) а закЪ!!!
угу, зак ив кусто! :))
Блин, как же я умудрился неправильно посчитать количество букв :(
3. 1(запоминает дорогу) и идет с 10, возвращается с фонарем, потом идут 2 с 5, после них 1 без фонаря по памяти. Получаем: 10+1+5+1 = 17 минут. по другому никак)
_
да, мозги пора на помойку
задача 3
Иван + Степан = 2 минуты
Иван возвращается = 1 минута
Абрам + Богдан = 10 минут ( Иван остается ждать )
Степан возвращается за Иваном = 2 минуты
Иван + Степан = 2 минуты
Итого = 17 минут
+
Ваш ответ, как и другие правильные ответы, в верхней части данного поста)
Хм... А возвратиться может не только Иван. )) Два решения.
Вопрос по третьей задаче - почему бомба часовая, а мост разрушится за 17 минут?
Бомба часовая потому что в одном часе содержится 60 минут = ( 17минут + 3 задача ) х ( 4 человека - 1 мост )
логично
а смысл задачи с шоколадкой также объяснить ? ))))
зачем работяга требует ежедневную плату и не тратит ?
))) смысл на разрушение шаблонов. Получая деньги - не обязательно же их в этот же день тратить :) Более того - скорее всего вы их будете копить, так и с шоколадом.
к сожалению, наблюдаю противоположную тенденцию, - кто берет з/п каждый день, тот больше тратит на всякую ерунду, и меньше остаётся на крупные траты ежемесячно.
Решение задачи с шарами. У нас шаров 15, два из них «меченые». Следовательно число возможных способов выбрать 2 шара из 15 будет равно C215 = 15 × 14 / (1 × 2) = 105 (напомню, Ckn — это число сочетаний). Поскольку 105 < 128, 7 бит достаточно чтобы закодировать каждый из возможных вариантов (одно измерение несёт только один бит информации). Что от нас и требуется по условию задачи.
Как и в случае задач на монетки, каждое измерение должно давать максимум информации, т.е. каждое разделение должно разбивать множество возможных решений на равные части (для задач на монетки это должны быть две или три кучи в зависимости от весов — весы могут показывать равно-неравно или равно-больше-меньше в разных задачах). В данном случае измерение может дать ответ «да/нет», т.е. набор вариантов за каждым измерением должен разбиваться по возможности пополам. К этому и будем стремиться.
Очевидная лемма. Если в наборе из N шаров у нас только один радиоактивный, то нам требуется ОкрВверх(log2(N)) измерений, например, для N=6 требуется не более 3-х измерений. Доказательство очевидно: поскольку «меченый» шар один, то при разбиении группы на две части «фонить» будет только одна из них. Соответственно, делить набор надо на две равные (или почти равные для нечётных) части. На эту лемму я буду ниже ссылаться как на лемму об одном «меченом» шаре.
В ситуации с двумя «меченными» шарами интереснее: при разбиении набора N на две группы n + m = N шаров и измерении фона группы из n шаров, мы получаем две ситуации:
1) группа n «чистая» и в группе m два «меченых» шара и
2) каждая из групп содержит по одному «меченному» шару.
Для второй ситуации каждая из групп сводится к лемме о «меченом» шаре. Первая ситуация требует, чтобы после разбиения группа из m шаров могла быть составлена C2m ≈ C2N / 2 вариантами
За задачу большое спасибо, получил немало удовольствия, решая её!
Интересно было бы узнать второй алгоритм.
Подскажите, пожалуйста, какой алгоритм для п.4 при фонящих двух шарах? Не соображу, каким образом исключается вариант того, что как раз оба шара являются радиоактивными. Спасибо.
Извините, за деревьями я не разглядел леса.
Если отбросить все умные слова и математические термины, ваше решение выглядит так: разбиваем группу на 4+3+2+2+4
Вы делаете первый замер - получаете +
Второй замер " - "
Третий " - "
Четвертый " - "
И вот тут ваша логика не срабатывает. Потому что вы подсознательно выбираете лучший вариант. А тут надо сознательно загонять себя в худшие рамки. А если замер последней четверки тоже дает + - что тогда делать? Вы имеете две четверки давшие вам наличие 1 Активного Элемента (АЭ) в каждой группе; а измерений у вас осталось только два. По моему, вы где-то ошиблись. Практического способа правильно определить 2 из 15 я не увидел. Но, возможно, я вас как-то не так понял. Я готов выслушать ваши аргументы. Но постарайтесь их изложить в виде пошаговой инструкции; чтобы было ясно видно, как из 15 одинаковых элементов вычленяются 2 активных.
Всё бы хорошо, но лемма работает, если в группе только один шар. А где гарантия, что в малой группе только 1 шар? Большую группу вы же не проверяете
1. Если 4 фонят - делим на две А и Б - замеряем только А - фонит, делим на две -находим 1 шар. А группа Б то не проверена. (3 замера)
2. Разбиваете на 3 + 8, 3 - чистые (+1 замер)
3. Разбиваете 2 +6, 2 - чистые (+1 замер)
4. Разбиваете на 2 + 4, 2 0 чистые (+1 замер)
5. Разбиваете на 2+2, 2 чистые (+1 замер) .
Всё замеры кончились. А у вас на руках 4 не обследованных шара. Что-то не сходится.
===================
Даже если не замерять сразу первую группу
Получается 4(+),3(-),2(-),2(-),2(-),1(-),1(?) - в запасе один замер и при этом не исследована группа из 4 и последний шар непонятный.
Всё правильно — тут у меня фундаментальная ошибка. То, что группа из n шаров «фонит» никак не гарантирует, что в каждой из групп находится по одному активному шару. Буду дальше думать.
Страницы