Задачи в Пятницу. С Новым Годом и Рождеством!

Аватар пользователя serghey

Прошлогодняя задача про радиоактивные шары и Гейгера НЕ решена. Дерзайте)

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 разных правильных алгоритма!

ЗЫ. Если эти подсказки Вам лично ничего не говорят - забудьте про них и не обращайте внимания, к формулировке самой задачи они не имеют никакого отношение....

Комментарии

Аватар пользователя ramazanov
ramazanov(11 лет 6 месяцев)

последняя задача очень интересная

Аватар пользователя kotovas
kotovas(12 лет 3 месяца)

Последняя задача:

4+4+4+3 (3 замера)

(2+2) и (2+2) или (1+2) (2 замера)

(1+1) и (1 +1) (2 замера)

Итого 7.

Аватар пользователя Савва
Савва(12 лет 3 месяца)

Рассматриваем худший вариант. Вы имеете 4 Элемента(Э), которые дали положительный результат и 3 Э которые вы не проверяли. При этом вы не знаете, где находятся искомые Активные Элементы (АЭ). Возможные варианты: они оба находятся в группе 4 Э или по одному в каждой группе.

Разбиваете первую четверку пополам 2+2 и тройку 2+1. При этом вы имеете 4 имзмерения (для краткости - замера). Итак, имеем 4 замера в загашнике.

Замеряем первую пару. Получаем +. Замеряем пару Э из второй группы. Получаем " - ". Осталось два измерения. И на руках у нас одна пара измеренная, там есть один или два АЭ, вторая пара из первой четверки непроверенная, а там вполне может быть второй АЭ и еще один Э от второй тройки, тоже непроверенный, который может быть АЭ. Измерений осталось только два! Я не вижу выхода из этого положения.

2+2+1. Точно известно, что первая двойка содержит АЭ (и неизвестно сколько). Т.е. вы не можете даже отбросить второй элемент из первой пары, если при измерении первого получили положительный сигнал. Ведь он тоже может быть Активным. А если вы его проверите, а он окажется пустышкой - Что тогда? у вас на руках один АЭ точно проверенный и тройка элементов , среди которых есть 1 АЭ но замеров уже не осталось. Это не есть решение.

Аватар пользователя kotovas
kotovas(12 лет 3 месяца)

Ладно. подумаем ещё.

Аватар пользователя Кот Баюн
Кот Баюн(11 лет 2 месяца)

Как справедливо заметил один из предыдущих докладчиков, вариантов размещения 2-х шаров в группе из 15 меньше, чем 2^7-1. Это означает то, что если мы сумеем закодировать все комбинации пар с помощью 7-и разрядного двоичного числа, то задача будет решена.

Решение.

Расположим шары по порядку номеров.

1. Возьмем шары с 1 по 10 в одну группу. Проверим её счетчиком Гейгера. Запишем результат в первый разряд двоичного представления числа.

2. Возьмем шары со 2 по 11 в одну группу. Запишем результат во второй разрад.

И т.д.

7. Возьмем шары 15 и с 1 по 9 в одну группу. Запишем результат в 7-й разряд.

Очевидно, что любая пара шаров участвовала в пробах хотя бы один раз. А это значит, что каждой паре шаров соответствует хотя бы одно число.

Аватар пользователя serghey
serghey(12 лет 2 месяца)
"Участник 32 минуты 22 секунды" ! Похоже, для того, чтобы опубликовать свое решение, Вам пришлось зарегистрироваться на Афтершоке))) Поздравляю.
...Подобные варианты были исследованы еще неделю назад. У них есть одно общее свойство и они НЕ могут дать результата
Аватар пользователя serghey
serghey(12 лет 2 месяца)

ОБЩЕЕ ЗАМЕЧАНИЕ: Большинство предложений ПОКА носит характер наброска, без проверки и без глубины идеи предлагаемого решения. А банального решения НЕ будет. К сожалению для одних и удовольствию для других наших коллег.

ЕЩЕ РАЗ, всем-всем-всем, ЗАДАЧА СЛОЖНА нетривиальна, несмотря на всю простоту ее формулировки. В этом ее прелесть. Трудно находить такие задачи, которые требуют для своего решения только интеллекта и методично применяемого системного подхода, и не требуют никаких специальных знаний. И не нужно рассчитывать, что такую задачу (о которую "сломали зубы" многие) можно решить лихо, за часок-другой, наскоком.

Извините за совет: Приступайте к решению только в том случае, если у Вас есть время и возможность и умение сосредоточиться. Иначе все кончится тратой времени и разочарованием.

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

Аватар пользователя ramazanov
ramazanov(11 лет 6 месяцев)

Три раз за день садился подумать, почти по часу.

сначала нашел вариант с 66% вероятности, на данный момент нашел решение, с 80% вероятности нахождения. Буду искать дальше.

Если кому поможет, скидываю текущий уровень.

1. Делишь 15 шаров на 3 части по 5. Двумя замерами исключаешь одну кучку из пяти шаров. Остается 2 кучки по 5 шаров, в каждой из которых точно есть по одному радиоактивному шару. А если вдруг оказалось, что вы имеете кучку из 5 шаров, в которой 2 радиоактивных шара, то решение упрощается. Мы двигаемся по сложному, и более вероятному пути.

  1. Каждую из 2 кучек по пять делим на 2+2+1 шара. Два шара по 1 изымаем и объединяем в отдельную кучку из 2 шаров. Таким образом вы имеете две кучки, разделенные по принципу 2+2. Двумя замерами мы отделяем из этих двух кучек по 2 нефонящих шара. И еще мы имеем третью кучку из 2, в которой неизвестно, есть ли фонящий шар или нет.

  2. Важный момент:

    • если при проверке двух кучек 2+2 мы выявили дважды фонящие кучки по 2 шара, то третью кучка, образованную из 2 шаров по одному из каждой пятерки, можно сразу исключить.

    • если при проверке двух кучек 2+2 мы выявили фонящую кучку из 2 один раз, а второй раз мы выявили не фонящую кучку, то нужно запомнить фонящую из 2, а на третью кучку тратим еще один замер для исключения одной нефонящей кучки.

    • Если мы при проверке двух кучек 2+2 выявили 2 нефонящей кучки, то также нужно проверить третью кучку. Если она не фонит, то исключаете ее, если фонит, то, поздравляю, у вас сработала 20% вероятность события.

    Таким образом, с 80% вероятностью данный подход позволит за 7 замеров выявить 2 фонящих шара. А с 20% вероятностью при данном подходе вам понадобится 8-ой замер.

Мне нужно где-то в алгоритме освободить еще одну попытку замера. Или исключить большее количество шаров за замер. Буду думать.



 

    Аватар пользователя Йорген
    Йорген(11 лет 3 месяца)

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

     

    Страницы