Вход на сайт

МЕДИАМЕТРИКА

Облако тегов

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

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

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

Фонд поддержки авторов AfterShock

Комментарии

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(17:49:36 / 04-01-2013)

1. Кажется очень простые вопросы.

Бег от ходьбы отличается тем, что при ходьбе в любой момент времени - хоть одна нога да опирается на поверхность... а при беге - есть такая фаза, когда обе ступни "парят" аки птицы...

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

 

Аватар пользователя nictrace
nictrace(5 лет 9 месяцев)(18:04:57 / 04-01-2013)

нет. хруст - это когда ломаются миллионы лучиков у снежинок.

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(18:08:46 / 04-01-2013)

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

Если бы звук издавали бы только кристаллики льда - возможно, это был бы звон, а не хруст...

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(18:16:13 / 04-01-2013)

+

Аватар пользователя baa1964
baa1964(5 лет 10 месяцев)(18:43:20 / 04-01-2013)

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

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:02:29 / 04-01-2013)

+

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(17:52:09 / 04-01-2013)

2. Видимо шоколад низя съедать сразу... а разменивать его назад, верно?

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(18:16:59 / 04-01-2013)

верно, но что дальше?

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(18:36:56 / 04-01-2013)

Дальше всё элементарно :)

Вот, после двух изломов (резов) получаем три кусочка шоколадки, я все семь кусков пронумеровал:

(1) (23) (4567)

В первый день даём (1), во второй (23) и отымаем (1), в третий даём опять (1), в четвёртый отымаем усё и даём (4567)... ну, и т.д. опять добавляем (1), потом отымаем но даём (23)... в седьмой день - отдаём всё.

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:01:54 / 04-01-2013)

+

Аватар пользователя nictrace
nictrace(5 лет 9 месяцев)(19:52:51 / 04-01-2013)

Класс! Но такой расклад возможен только если работник не любит шоколад :)

Аватар пользователя baa1964
baa1964(5 лет 10 месяцев)(18:39:08 / 04-01-2013)

Первая шоколадка 7 делиться двумя разрезами на 1, 2 и 4. В первый день выдаем 1, во-второй день выдаем 2 и 1 забираем, в третий день выдаем 1, в четвертый день выдаем 4, а 1 и 2 забираем, в пятый день выдаем 1, в шестой день выдаем 2 и 1 забираем, в седьмой день выдаем 1. В условии надо дописать что работник не съедает шоколад.

Вторую шоколадку двумя разрезами надо разделить на 1, 2, 4 и 8. Алгоритм выдачи такой же.

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:01:28 / 04-01-2013)

+

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(18:45:27 / 04-01-2013)

А в задаче 2.2 - резать шоколад видимо нужно уже в двух осях... но шоколадка должна быть 3 на 5...

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(18:04:57 / 04-01-2013)

9. Элементарная задача...

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

PS на скока я понимаю, если шаров будет 16 - то решается так же, за 7 измерений максимум...

Аватар пользователя CCAPMX
CCAPMX(5 лет 10 месяцев)(18:21:04 / 04-01-2013)

действительно, не понятно в чем прикол

Аватар пользователя Савва
Савва(5 лет 11 месяцев)(18:48:56 / 04-01-2013)

Ув. Токомак. Требуется 100-процентное решение, т.е. абсолютная надежность. Как от этого зависит ваша жизнь. Ну, скажем, вам нужно взять в полет только два Активных Элемента ( предположим, что они достаточно тяжелые), а выбрать какие можно взять с собой можно только "на далекой космической базе". Вот вы выбрали и полетели. К середине полета один АЭ кончился, вы вставляете второй - а он не фурычит. Вы ошиблись. Всё, псец, приплыли...

А простым "пополамом" задачка не решается. Я сейчас вам покажу почему.

Вы получаете две группы элементов, положим 8 и 7. Вы подносите к ним счетчик Гейгера - и он в обоих случаях показывает наличие АЭ. Т.е. искомые элементы разделились. При этом 2 измерения вы уже использовали, у вас осталось только пять. С первой восьмеркой вы разобрались с помощью 3-х измерений. У вас остается два измерения и 7 элементов, только два! измерения... Это не решение. Вы в конце получаете два элемента, один из которых излучает, а второй - нет. В полет какой брать будете? Наугад? а если ошибетесь... Короче. это не решение. Есть решение, более того, как мы с автором пятничных задач недавно выяснили, даже два, которые дают однозначное решение - вот эти два элемента активные. И никаких угадаек. Вот такая фишка. 

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(18:54:34 / 04-01-2013)

Да, верно, с 16 - не выйдет, только с 15!!!

Там при последнем разделении начатом с 8-ми шаров - оставшийся последний, вроде не радиоактивный шар нужно подложить в разделённую на две части первую группу из 7.... и она станет уже из 8 (т.е. 4 на 4)...

Аватар пользователя Савва
Савва(5 лет 11 месяцев)(19:36:08 / 04-01-2013)

У вас на последнюю группу остается ДВА! измерения. А двумя измерениями задача не решается.

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(19:39:18 / 04-01-2013)

Да, с делением чисто на две кучи - так нормального решения я и не нашёл... но там, ниже - я написал вариант... похож на верный...

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(19:30:38 / 04-01-2013)

Задача 9... 

Возможный вариант:

1. Делим на 5 кучек по 3 шара... Тратим 4-ре измерения и выявлем две радиоактивные кучи, т.е. 6-ть шаров;

2. Шесть шаров делим на три кучи по два шара... Тратим 2-ва измерения и снова выявляем две радиоактивные кучи, т.е. 4-ре шара;

3. Теперь пронумеровав 4 шара по двум кучам: 1,2 и 3,4 и зная, что радиоактивный есть в обоих из них - нужно только одно измерение (последнее), что бы понять, чё по чём... переставляем шары и получаем: 1,3 и 2,4 - если куча 1,3 радиоактивная, то вот они искомые, а если нет... то искомые - это 2,4.

Аватар пользователя Савва
Савва(5 лет 11 месяцев)(19:39:56 / 04-01-2013)

Вы делите 6 шаров на три группы. Первое измерение дает плюс. Второе - минус. И получается, что вы не знаете, у вас оба шара в первой двойке или один в первой, а второй в последней, которую вы еще не измерили. А если вы ее измеряете, и она дает снова  плюс. Получается две пары шаров по 2 элемента и только одно измерение - задача не решается.

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(20:23:45 / 04-01-2013)

Кошмар... сложная задача :)

Аватар пользователя Federal
Federal(5 лет 10 месяцев)(18:27:37 / 04-01-2013)

Пятая самая простая. Ищем ярлык "яблоки и апельсины" лезем туда и достаем то, что там лежит. Это корзина с тем фруктом, что достали. Осталось два ярлыка на двух корзинах. Один совпадает с фруктом, который достали, но в этой корзине фрукт другого вида. Третья корзина с двумя видами фркутов.

 

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:00:58 / 04-01-2013)

+

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(18:29:29 / 04-01-2013)

5. Решить можно, если разрешается узнать из корзины (или выбрать корзину) с каким ярлыком вы вытаскиваете фрукт... Решение двумя словами не объяснить, придётся расписывать подробно:

Имеем корзины с ложными надписями: (Я)блоки, (А)пельсины, (С)месь.

Теперь из первой корзины (Я) мы вытаскиваем:

(1) яблоко -> значит в корзине (Я) = смесь, а в корзине (С) = апельсины, так как апельсины не могли по определению быть в корзине (А), там = яблоки;

(2) апельсин -> значит в корзине (Я) = апельсины, в корзине (А) = смесь (так как реальная смесь не может быть в корзине (С)), ну а в корзине (С) = яблоки.

 

Если залезть в корзину с ярлыком (А) - то решение аналогичное...

А вот, если лазить в корзину с ярлыком (С), то варианты таковы:

(1) яблоко -> значит в корзине (С) = яблоки, а в корзине (Я) = апельсины, так как апельсины не могли по определению быть в корзине (А), там = смесь;

(2) апельсин -> значит в корзине (С) = апельсины, в корзине (А) = яблоки (так как реальные яблоки не могут быть в корзине (Я)), ну а в корзине (Я) = смесь.

Нарисовать на листке бумиги - и решается просто...

 

Аватар пользователя nictrace
nictrace(5 лет 9 месяцев)(18:34:17 / 04-01-2013)

5. Если достали яблоко (Я), это точно не корзина апельсинов. смотрим ярлык - там может быть написано А или АЯ. Если АЯ - это корзина с яблоками, тогда А-смесь, и Я-апельсины. Если А - это смесь,  под Я будут апельсины, яблоки под АЯ.

Если поймали апельсин, рассуждаем аналогично

Аватар пользователя inno
inno(5 лет 8 месяцев)(20:03:36 / 04-01-2013)

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 шт

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:57:34 / 04-01-2013)

БРАВО, это действительно квадраты чисел от 1 до 10:

1, 4, 9, 16, 25, 36, 49, 64, 81, 100

Аватар пользователя kotovas
kotovas(5 лет 11 месяцев)(19:25:22 / 04-01-2013)

1. Бег - три буквы, ходьба - 5 букв. :) Снег по морозу хрустит. ;)

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:27:24 / 04-01-2013)

ходьба - 6, в 2 раза больше)

Аватар пользователя tokomak
tokomak(5 лет 11 месяцев)(19:33:23 / 04-01-2013)

видать Ь - не буква ;) а закЪ!!!

Аватар пользователя kotovas
kotovas(5 лет 11 месяцев)(20:28:30 / 04-01-2013)

угу, зак ив кусто! :))

Блин, как же я умудрился неправильно посчитать количество букв :(

Аватар пользователя likeguest
likeguest(5 лет 11 месяцев)(19:25:51 / 04-01-2013)

3. 1(запоминает дорогу) и идет с 10, возвращается с фонарем, потом идут 2 с 5, после них 1 без фонаря по памяти. Получаем: 10+1+5+1 = 17 минут. по другому никак)

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:30:35 / 04-01-2013)

_

Аватар пользователя likeguest
likeguest(5 лет 11 месяцев)(21:56:30 / 04-01-2013)

да, мозги пора на помойку

Аватар пользователя bom100
bom100(5 лет 10 месяцев)(19:54:43 / 04-01-2013)

задача 3

Иван + Степан = 2 минуты

Иван возвращается = 1 минута

Абрам + Богдан = 10 минут ( Иван остается ждать )

Степан  возвращается за Иваном = 2 минуты

Иван + Степан = 2 минуты

Итого = 17 минут

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(20:27:09 / 04-01-2013)

+

Ваш ответ, как и другие правильные ответы, в верхней части данного поста)

Аватар пользователя Nikochem
Nikochem(4 года 10 месяцев)(10:23:22 / 05-01-2013)

Хм... А возвратиться может не только Иван. )) Два решения.

Аватар пользователя kotovas
kotovas(5 лет 11 месяцев)(20:19:43 / 04-01-2013)

Вопрос по третьей задаче - почему бомба часовая, а мост разрушится за 17 минут?

Аватар пользователя bom100
bom100(5 лет 10 месяцев)(20:28:08 / 04-01-2013)

Бомба часовая потому что в одном часе содержится 60 минут = ( 17минут + 3 задача ) х ( 4 человека - 1 мост )

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(20:29:29 / 04-01-2013)

логично

Аватар пользователя Читаювсё
Читаювсё(5 лет 11 месяцев)(00:53:30 / 05-01-2013)

а смысл задачи с шоколадкой также объяснить ?  ))))

зачем работяга требует ежедневную плату и не тратит ?

Аватар пользователя kotovas
kotovas(5 лет 11 месяцев)(09:13:02 / 05-01-2013)

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

Аватар пользователя Читаювсё
Читаювсё(5 лет 11 месяцев)(09:45:32 / 05-01-2013)

к сожалению, наблюдаю противоположную тенденцию, - кто берет з/п каждый день, тот больше тратит на всякую ерунду, и меньше остаётся на крупные траты ежемесячно.

Аватар пользователя Маздайщик

Решение задачи с шарами. У нас шаров 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 вариантами

  1. Мы имеем набор из 15 шаров с двумя «мечеными», что даёт C215 = 105 вариантов. Надо за одно измерение разбить пространство вариантов на два примерно равных с 105 / 2 = 52,5 ≈ С211 = 55 вариантами. Следовательно, разбиваем так: 15 = 4 + 11. Если 4 шара «фонят», то по лемме достаточно ОкрВверх(log2(4)) + ОкрВверх(log2(11)) = 2 + 4 = 6 оставшихся замеров. Если же 4 шара «чистые», то два «меченых» скрываются в группе 11 шаров.
  2. C211 / 2 = 55 / 2 = 27,5 ≈ C28 = 28. Соответственно, 11 = 3 + 8. Если 3 шара «фонят», то по лемме достаточно 2 + 3 = 5 замеров. Если 3 шара «чистые», разбираемся 8 шарами.
  3. C28 / 2 = 28 / 2 = 14 ≈ C26 = 15. Соответственно, 8 = 2 + 6. Для 2 «фонящих» шаров по лемме достаточно 1 + 3 = 4 замера. Для 2 «чистых» — разбираемся с 6 шарами.
  4. C26 / 2 = 15 / 2 = 7,5 ≈ C24 = 6. 6 = 2 + 4. 2 «фонят» — по лемме log2(2) + log2(4) = 3, как раз 3 оставшихся замера. 2 «чистые» — на 4 шара с двумя «мечеными» остаётся 3 измерения.
  5. Тут уже комбинаторику привлекать не обязательно. Первые три шара меряем по отдельности, если среди них обнаружился лишь один «меченый», то оставшийся — тоже «меченый».

За задачу большое спасибо, получил немало удовольствия, решая её!

Интересно было бы узнать второй алгоритм.

Аватар пользователя Nikochem
Nikochem(4 года 10 месяцев)(09:09:07 / 05-01-2013)

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

Аватар пользователя Савва
Савва(5 лет 11 месяцев)(10:07:59 / 05-01-2013)

Извините, за деревьями я не разглядел леса.

Если отбросить все умные слова и математические термины,  ваше решение выглядит так: разбиваем группу на 4+3+2+2+4

Вы делаете первый замер - получаете +

 Второй замер " - "

Третий  " - " 

Четвертый " - "

И вот тут ваша логика не срабатывает. Потому что вы подсознательно выбираете лучший вариант. А тут надо сознательно загонять себя в худшие рамки. А если замер последней четверки тоже дает + - что тогда делать? Вы имеете две четверки давшие вам наличие 1 Активного Элемента (АЭ) в каждой группе; а измерений у вас осталось только два. По моему, вы где-то ошиблись. Практического способа правильно определить 2 из 15 я не увидел. Но, возможно, я вас как-то не так понял. Я готов выслушать ваши аргументы. Но постарайтесь их изложить в виде пошаговой инструкции; чтобы было ясно видно, как из 15 одинаковых элементов вычленяются 2 активных.

Аватар пользователя kotovas
kotovas(5 лет 11 месяцев)(15:04:27 / 05-01-2013)

Всё бы хорошо, но лемма работает, если в группе только один шар. А где гарантия, что в малой группе только 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 на две группы n + m = N шаров и измерении фона группы из n шаров, мы получаем две ситуации:
1) группа n «чистая» и в группе m два «меченых» шара и
2) каждая из групп содержит по одному «меченному» шару.

Для второй ситуации каждая из групп сводится к лемме о «меченом» шаре. Первая ситуация требует, чтобы после разбиения группа из m шаров могла быть составлена C2m ≈ C2N / 2 вариантами.

Всё правильно — тут у меня фундаментальная ошибка. То, что группа из n шаров «фонит» никак не гарантирует, что в каждой из групп находится по одному активному шару. Буду дальше думать.

Аватар пользователя ramazanov
ramazanov(5 лет 1 месяц)(11:14:53 / 05-01-2013)

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

Аватар пользователя kotovas
kotovas(5 лет 11 месяцев)(15:08:10 / 05-01-2013)

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

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

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

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

Итого 7.

Аватар пользователя Савва
Савва(5 лет 11 месяцев)(15:15:07 / 05-01-2013)

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

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

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

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

Аватар пользователя kotovas
kotovas(5 лет 11 месяцев)(15:46:01 / 05-01-2013)

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

Аватар пользователя Кот Баюн
Кот Баюн(4 года 10 месяцев)(18:35:34 / 05-01-2013)

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

Решение.

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

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

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

И т.д.

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

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

Аватар пользователя serghey
serghey(5 лет 10 месяцев)(18:34:54 / 05-01-2013)
"Участник 32 минуты 22 секунды" ! Похоже, для того, чтобы опубликовать свое решение, Вам пришлось зарегистрироваться на Афтершоке))) Поздравляю.
...Подобные варианты были исследованы еще неделю назад. У них есть одно общее свойство и они НЕ могут дать результата
Аватар пользователя serghey
serghey(5 лет 10 месяцев)(19:02:59 / 05-01-2013)

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

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

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

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

Аватар пользователя ramazanov
ramazanov(5 лет 1 месяц)(19:20:01 / 05-01-2013)

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

сначала нашел вариант с 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-ой замер.

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



 

    Аватар пользователя Йорген
    Йорген(4 года 11 месяцев)(08:33:32 / 09-01-2013)

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

     

    Лидеры обсуждений

    за 4 часаза суткиза неделю

    Лидеры просмотров

    за неделюза месяцза год

    СМИ

    Загрузка...