Сложная задача на логику

    Предлагаю желающим решить следующую задачу:

    Есть 15 шариков, 2 из них радиоактивны. Есть прибор с лампочкой, в который можно поместить любое количество шариков (хоть все пятнадцать), и который покажет наличие радиации. То есть, если среди положенных в прибор шариков есть хотя бы один радиоактивный — лампочка загорится, если нет — не загорится.
    Необходимо найти 2 радиоактивных шарика, используя прибор не более 7 раз.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 100

      0
      Надо проверять по 2 шарика. Если лампочка не горит, то оба отбрасываем, если горит, то один и берем еще один (не радиоктивный). Если среди первых не будет "чистой" пары то еще легче. Проверить оба, а потом разделить оставшиеся на 2 кучи и еще на 2 кучи. 7 это наверное при худшем раскладе.

      Послесловие:
      И почему вам минусов наставили??
        +1
        решить не смогли =)
          0
          Нуу... Ну и чёрт с ними, с шариками. Пусть будут так, в перемешку.
          0
          За 6 раз мы проверим 12 шариков. На седьмой раз (положили 13 и 14 шары) загорелась лампочка.
          Скажите, 15й шар радиоактивен? Проверять уже нельзя.
          0
          А по половинке проверять? С начала Сем и сем. Если в них один не засветился - значит он остался. Дальше их по половинкам и так далее.
            0
            Не выйдет если оба первых теста засветились. Это классическая задача из теории кодирования.
              0
              А, к стати да. Тут тогда надо уже на везение их отбирать, если оба засветились.
            +1
            Прикольная задача. Два часа времени как не бывало. Ответ писать не буду. ;)
              0
              Поздравляю! Надеюсь, вы решили правильно, и не жалеете о двух часах :)
              0
              проверить первые восемь, потом остальные.
              дальше половину из первых восьми, если они засветились.
              потом половину из тех семи.
              и так далее, половинками.

              я думаю, можно уложиться в семь проверок.
                0
                половинки не катят - в каждой из них может быть по радиоактивному шарику.
                  0
                  шарика всего два. в проверках половинками можно шестью ходами решить!
                    0
                    Нельзя 6ю, вариантов 105, а 2^6 это 64.
                      0
                      как это нет?
                        OOO® OOOO | OOOO O®O
                        OOO®|OOOO
                        OO|O®
                        O|® — четыре проверки

                        OOOO|O®O
                        O|®O
                        ®|O — еще три
                      так, в двух половинах радиактивные шары могут быть в любом месте.
                        0
                        Чтоб понять, что у нас OOO® OOOO | OOOO O®O, надо 2 проверки. Итого у вас 8.
                          0
                          ну, имелось в виду, что мы это учли во второй части (OOOO|O®O).
                          в первый раз — даже если у нас OOO® OOOO | OOOO OOO, то это нормально.
                          0
                          OOO® OOOO | OOOO O®O (это две проверки.)
                          OOO®|OOOO
                          OO|O®
                          O|® — четыре проверки пять проверок

                          OOOO|O®O - это вы не учли, это отдельная проверка.
                          O|®O
                          ®|O — еще три

                          Итого 8 по данному алгоритму
                            0
                            если не считать нахождение радиактивного шарика в первой строке, во второй ее половине, то мы находим его в той, "отдельной проверке". так что, все же семь.
                              0
                              Та "отдельная проверка" с около 50% вероятностью может вам дать чистую тройку/четвёрку. Это будет означать что оставшийся радиоактивный шарик хрен знает где (или в оставшейся паре второй проверки первой части или в оставшейся паре первой проверки второй части). В данном случае алгоритм даст больше 7-ми проверок.
                                0
                                я, между прочим, написал выше:
                                так, в двух половинах радиактивные шары могут быть в любом месте.

                                это и означает, что, в случае, если радиактивные шары находятся в разных половинах, только тогда это решение работает.
                                а работает именно семью проверками
                                0
                                К сожалению, ваше решение неправильно уже с самого первого хода. Всего может быть 105 вариантов расположения двух шариков среди пятнадцати. Если первым ходом вы проверите восемь, то положительный результат оставит вам 84 варианта, а отрицательный - 21. То есть в первом случае, вы заведомо не сможете за 6 попыток (а это максимум 2^6 = 64 варианта) найти ответ.
                            0
                            вот это правильный подход
                              0
                              я про "Нельзя 6ю, вариантов 105, а 2^6 это 64."
                    • НЛО прилетело и опубликовало эту надпись здесь
                        0
                        К сожалению, есть только один правильный первый ход, и это не восемь и не семь шариков.
                        И еще, эту задачу нельзя решить в уме, без бумажки не обойтись. Я предупредил, задача сложная.
                          0
                          А есть общий "базис" хотя бы на первые 4 хода? А то дерево я сразу нарисовал, но это скучно.
                            0
                            По-моему, первых ходов правильных два.
                              0
                              Всё-таки один, похоже.
                                0
                                Да, правильный первый ход только один, а дальше становится сложнее. Самое главное - найти правильный второй ход.
                                  0
                                  Я рисовал дерево, если результат 1, то ..., если результат 0, то ...

                                  А есть универсальный второй ход?
                                    0
                                    Во-первых, второй ход зависит от результата первого. При положительном результате первого есть несколько вариантов, но только один дает решение. Так же и при отрицательном. А дерево всех возможных ходов, похоже, немаленькое.
                                      0
                                      Похоже у нас решения разные :)
                                        0
                                        Наверное, ваше неверное :)
                                          0
                                          Видимо, неверное :) изложите первые два хода - проверим
                                            0
                                            Два шарика отлаживаем.
                                            Потом отлаживаем ещё один.
                                            Оставшиеся три кучки по 4 шарика по очереди суём в коробку вместе с отдельно отложенным шариком...
                                              0
                                              не очень понял ход мысли с откладываниями, но судя по всему, решение неправильное. Если я правильно понял, что первый ход - два шарика, а второй - еще один, то при двух отрицательных результатах вы не найдете 2 шара из 12 за пять попыток.
                                                +1
                                                Два шара откладываем в сторону и про них забываем. в коробку не суём. Потом берём ещё один - он будет "козырным". Его тож пока в коробку не суём.

                                                Ставшиеся 12 делим на три кучки.

                                                Первые три хода:
                                                Суём в коробку по очереди каждую четвёрку шариков вместе с козырным.

                                                Дальше по ситуации:
                                                1) Прибор ни разу не сработал. Радиоактивные отложенные
                                                2) Прибор сработал три раза. Козырный шарик радиоактивный, из оставшихся 14-ти находим второй*.
                                                3) Прибор сработал 1 раз. У нас 4 попытки, 6 шариков два из которых радиоактивны*.
                                                4) прибор сработал два раза. В каждой из двух кучек по 4 по одному атомному шарику, на каждую кучку по 2 попытки*.

                                                *-решения простых вытекающих задач разжёвывать не стал.
                                                  0
                                                  Как мне кажется, задача найти 2 шарика из 6 за 4 попытки не такая уж простая (3-ий пункт). Я бы даже сказал невыполнимая.
                                                    0
                                                    я перебрать по одному ? ;)
                                                      0
                                                      а если первые три не загорятся, а четвертый загорится? :)
                                                        0
                                                        Блин :) как абыдн.
                                                      0
                                                      Простите, надеюсь вас не напряжет привет из осени в старый топик, но вы убили мне весь вечер))
                                                      Решение rybnadzorro верное! 2 шарика из шести легко находятся за 4 попытки, т.к. мы уже знаем, что первые четыре шара дали плюс.
                                                      1 - меряем оставшиеся два
                                                      а) +
                                                      2 - выбираем из двух
                                                      3, 4 - выбираем из 4
                                                      б) -
                                                      три шара из четвёрки поочереди

                                                      Так что разбиение на группы вполне действенно) Это красивое, простое и логичное решение, очень понравилось, спасибо автору)
                                                        0
                                                        Да, вы правы. Это - решение так называемым "пропеллером" :)
                                • НЛО прилетело и опубликовало эту надпись здесь
                                    0
                                    Поздравляю! Хотя 35 минут - это как-то подозрительно быстро. Видимо, вы или быстро мыслите (и рисуете), или сделали что-то не так :)
                                      –1
                                      Я просто минут за 10 написал программу, которая генерит список всех вариантов, а потом показывает, сколько осталось в каждом множестве, если в Nй проверке мы проверяем множество шаром {...}
                                        0
                                        понятно. а мне вот было как-то интереснее на бумажке
                                      • НЛО прилетело и опубликовало эту надпись здесь
                                          0
                                          Дык есть теория, что что помышлено, то уже было :) А Вам не все одно?
                                          • НЛО прилетело и опубликовало эту надпись здесь
                                      +1
                                      по моему так, не понимаю почему половинки не катят
                                      1. разбиваем на кучи из 7 и 8.
                                      а. засветились обе (худший случай)
                                      б. засветилась одна из них
                                      2а. разбиваем одну из них, пусть 8 на 2, получаем 4 и 4, в любом случае одна не светится, ее отбрасываем остается 7 и 4.
                                      3а. тоже самое делаем с 7 и в итоге получаем в худшем случае 4 и 4.
                                      4а. разбиваем одну из них на две и тоже одна не светится, остается 2 и 4.
                                      5а. тоже самое со второй кучей остается 2 и 2.
                                      6а. 1 и 2
                                      7а. 1 и 1

                                      2б. в худшем случае 7 не светится, тогда светится 8. делим в на две, и в худшем случае в итоге светятся обе 4 и 4.
                                      3б. 2-4
                                      4б. 2-2
                                      5б. 1-2
                                      6б. 1-1.
                                        0
                                        блин туплю, невнимательность
                                          0
                                          и вправда легче програмку написать
                                          0
                                          засветились обе - это уже 2 замера
                                          0
                                          Решила за 15 минут (если все верно конечно).
                                          Первый ход - шарики разбиваются на 3 группы по 5, и двумя ходами шариков становится уже 10. Дальше тоже все вроде сошлось.
                                            0
                                            Не становится их 10 двумя ходами ;).

                                            Пример:
                                            Первая пятёрка загорелась
                                            Вторая пятёрка не загорелась.
                                            Мы не знаем как поведёт себя третья пятёрка, ибо в первой может быть как один так и два мегашарика.
                                              0
                                              Становится :). Сторая пятерка не загорелась - сразу исключаем ее. В итоге за 2 хода остается 2 кучки по 5 шариков.
                                              Если загорелись две первые пятерки - исключаем без проверки третью. Опять - 2 хода - 10 шариков.
                                                0
                                                Согласен :).

                                                Но из кучки в 5 шариков за две попытки гарантированно мегашарик не достанешь ;)

                                                Итого решение 8-ми ходовое.
                                                  0
                                                  Да, Вы правы, сейчас поэкспериментировала - нужно 8 ходов для такого способа. Где-то ошиблась :(
                                                    0
                                                    Ошиблись в том, что в любом случае впервый раз придется делать 3, а не как посчитали 2 хода. а так Ваше решение первое что пришло в голову=) странно, может быть женская логика;) шутка конечно, но все равно странно)))
                                            0
                                            Суть решения в том, что НЕ надо делить шарики на групы и пытаться решить все простым отсеиванием.
                                              0
                                              К сожалению, из опубликованных решений правильного пока нет. Но осталось немного :)
                                              +2
                                              Вроде давно висит? Можно ответ писать?

                                              Сначала проверка, что над нами не надругиваются. 7 экспериментов с бинарным исходом позволяют нам распознать до 128 ситуаций. Количество вариантов расположения шариков - 105, матрица 15x15 минус диагональ и половина. Т.е. принципиальной невозможности не видно.

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

                                              Короче, я спать пошел. Если я где-то ошибся - прошу сообщить.
                                                0
                                                P.S. s/взвешивания/проверки k крайних/
                                                Уже сплю и Ян Тирсен терзает мою душу.
                                                  0
                                                  Подход абсолютно правильный и вы нигде не ошиблись. Можно сказать, что две трети задачи вы решили, осталось собственно найти дерево решения (а его просчет куда сложнее, чем может показаться на первый взгляд).
                                                    0
                                                    что значит левое и правое взвешивание?
                                                      0
                                                      Помещение в прибор k левых или k правых шариков. Думаю, этого недостаточно. Я побаловался с разрезанием той косынки и быстрого решения не нашёл.
                                                    0
                                                    Есть блог задачки. Может быть туда?
                                                    http://habrahabr.ru/blog/zadachki/
                                                      0
                                                      переместил
                                                      0
                                                      уф... решил, да совчем неочевидное решение :) Но круто, спасибо за задачу!
                                                        +1
                                                        Оказалось, что я ее все таки не решил. Подсодил на нее кучу народа. 2 дня думал, и на второй день вместе с чуваком зарешал ее за 5 часов (теперь уж правильно :).
                                                        Удовольствия получил немерено, а еще в споре выйграл с товарищем ящик пива :)
                                                        Homer, пару тостов будет за тебя. Еще раз спасибо за задачу.
                                                          0
                                                          Рад, что задача понравилась :)
                                                        0
                                                        Делим шары на 4 группы: 1) 4 шара, 2) 4 шара, 3) 4 шара, 4) 3 шара.
                                                        Производим 3 замера: 1 и 2 группы (1), 1 и 3 (2), 2 и 3 (3).
                                                        Опираясь на эти измерения можно узнать в которых группах шары (1, 2 или 3; в случае если из этих трех групп положительна одна группа или ни одной вовсе, тогда берем на дальнейшую проверку группу 4 и положительную группу, если такая имеется).
                                                        Произвести по 2 измерения в каждой из двух выбранных групп.
                                                        Шары найдены.
                                                          0
                                                          Не согласен! А если загорится лампочка на всех трёх измерениях? Мы всего лишь будем знать что в двух из этих 3-х группах по одному шарику? а в каких точно мы не сможем узнать, для этого потребуется ещё один замер, а следовательно не хватит одного замера на вычленение мега шара из одной из груп, состоящих из 4-х шаров, решение не верно...
                                                            0
                                                            Это решение заведомо неправильно, хотя бы потому, что первым замером можно мерять только 5 шаров, а иначе вы уже не сможете наверняка определить искомые шары.
                                                            0
                                                            Кстати именно я тот чувак, без которого бы отстой не нашёл верного решения... Я даже скажу мы практически отыскали второе решение, но сведя задачу к более простой, не смогли её решить)) Но доделать и второй способ можно).. Ответ Клёвый! Очень не логичное действие надо произвести!
                                                              0
                                                              venil, решение вроде бы не верно.
                                                              допустим у нас комбинация 1(0000) 2(1000) 3(0000) 4(100)
                                                              ты проверяешь так:
                                                              1. 1(1000)+2(0000)=1
                                                              2. 1(1000)+3(0000)=1
                                                              3. 1(1000)+4(100)=1
                                                              У тебя остало
                                                              итого ясно, что в группе 1 - радиоактивный и в группах 2+3+4(это 11 шариков) тоже один.

                                                              Число возможных положений первого радиоактивного = 4(то есть 0001,0010,0100 и 1000)
                                                              Число возможных положений втрого шарика = 11(00000000001,000000000010 и т.д.)
                                                              Общее число возможных вариантов = 4*11=44
                                                              А у тебя всего четыре хода осталось 2^4=16
                                                                0
                                                                Блин...что-то два дня решения этой задачи не прошли даром...всмысле туплю(мозговые ресурсы кончаются)...Предыдущий мой пост - просьба не читать.
                                                                Попробую завтра проверить решение venil'а.

                                                                А всем кому интересно узнать решение моё - стучитесь в аську #206362216.
                                                                Кстати первым ходом я проверяю 4 шарика. Решение рабочее!
                                                                  0
                                                                  Решал примерно часа полтора, совсем без компьютера. Ещё столько же рисовал решение :-)
                                                                  http://lany.gorodok.net/C_15_2.jpg (171Kb, смотреть на страх и риск!)
                                                                  Большое спасибо за задачку, растрясла немного мозг =)
                                                                    0
                                                                    Вроде все правильно, поздравляю :)
                                                                      0
                                                                      а если шарики 4 и 5 ?
                                                                      Алгоритм не покажет правильного ответа
                                                                      0
                                                                      Почему-то вспомнилась задачка из школы:
                                                                      Есть 8 бильярдных шаров и весы. Один шар тяжелее остальных. Надо его найти за 2 взвешивания.
                                                                      Помню тогда я ее первый решил :) надолго запомнилось. Вечером в метро подумаю над этой )
                                                                        0
                                                                        Про бильярдные шары:
                                                                        Сначала откладываем в сторону 2 шара, взвешиваем 3 и 3. Одно взвешивание уже есть. Если кучки с тремя и тремя шарами равны, то взвешиваем 2 шара. В ином случае откладываем из кучки с 3 шарами один и взвешиваем 2, всё просто.
                                                                        Спасибо, порадовало)
                                                                        0
                                                                        Объясните плиз, в чем у меня ошибка (т.к. тут говорили, что 6 раз нельзя).

                                                                        1) Разбиваем на группы 3 - 4 - 4 - 4. Самый плохой вариант, когда в 2-х груупах из 4-х шаров находится по одному искомому.
                                                                        2) Рассматриваем этот случай. Берем группы по 2 - 2 - 2 - 2. Самый плохой вариант, когда в 2-х груупах из 2-х шаров находится по одному искомому.
                                                                        3) Рассматриваем этот случай. Разбиваем на группы по 1 - 1 - 1 - 1. Чтобы найти радиоактивные шары на данном этапе требуется 2 проверки.

                                                                        В результате достаточно 6 проверок в самом неудачном варианте!???
                                                                          0
                                                                          В задаче не взвешивания, а замеры. Вы кладете набор шаров в прибор - и он выдает вам наличие радиации. Т.е. в худшем случае в п.1 вы уже потратите 4 попытки на определение того, что ваши шары легли в разные группы по 4. Чтобы найти один из четырех в каждой группе - нужно два замера. Всего восемь.
                                                                          0
                                                                          А условия хоть правильные даны? 7, а не 8 раз?
                                                                          Потому-что по моим подсчетам при самой худшей ситуации необходимо 8 проверок
                                                                          т.к. при проверке может быть два варианта
                                                                          1й - лампочка горит
                                                                          2й - лампочка не горит
                                                                          и этот вариант может быть в любом месте!
                                                                          к примеру
                                                                          + прибор загорелся
                                                                          - прибор не реагирует
                                                                          _______________________________1100 0000...........0000 000
                                                                          ________________________________/+2......................\-1
                                                                          ____________________________10000000....................1000000
                                                                          ____________________________/+1...\-1...................+1/..\-1
                                                                          __________________________1000...0000..................1000...000
                                                                          _________________________+1/\+1.......................+1/\-1
                                                                          _________________________10..00______________________10...00
                                                                          _______________________+1/\-1............................................+1/\-1
                                                                          ________________________1__0_______________________1__0
                                                                          ______________________________________________________Итого считаем: при первой проверке если загорается лампа, то нам необходимо узнать сколько в куче шариков с радиацией! Для этого необходимо проверить 2ю кучу! Если при проверки 2й кучи лампа горит, то получается что в каждой из куч по одному шару и исходя из этого при каждой следующей проверки если лампа загорается сразу то мы знаем, что 2я кучка чистая!
                                                                          ИМХО: при карявом варианте по моим подсчетам 8 проверок, ну а если нам очень, очень повезло и при каждой проверке прибор не будет загораться, то минимальный вариант 3 проверки!
                                                                            0
                                                                            Условие правильное, за 7 замеров можно всегда управиться. Никто не заставляет делить шары поровну и производить замеры именно так, как вы указали.
                                                                              0
                                                                              Ну да. Согласен =) может быть и другой вариант =) Что-то туплю
                                                                            +1
                                                                            Понял как решать (в основном из комментов) но руками решения не нашел - строить дерево показалось слишком муторно.

                                                                            Меня заинтересовал другой вопрос - сколько всего деревьев решений ?

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

                                                                            Кто-то может помочь оценить количество деревьев решений на каждом уровне ? Насколько это реально просчитать их до самого низа ?.
                                                                              0
                                                                              Что-то мне подсказывает, что программа плохо отсекает неверные варианты, потому что уж слишком много веток на втором уровне.
                                                                              После единственно правильного первого хода (замер 5 шаров) имеет две ветки. Для ветки + имеем 3 варианта хода (6, 1 + 4, 2 + 1), для ветки - имеем 3 варианта хода (2, 3, 4). Итого после второго уровня у нас 12 веток.
                                                                                0
                                                                                нууу ты ошибаешься. первых ходов 2 - 5 и 4.
                                                                                так вот после второго хода 114 вариантов.... ужость.

                                                                                Было б круто если б ты помог понять в чем дело. а то я подсел на задачу. друг пробовал полный перебор. получилось что надо 2512308552583217
                                                                                миллионов лет чтобы просчитать все. :)
                                                                                  0
                                                                                  Знаешь я, кажется, понял что ты имел ввиду - что проверка первым ходом 4 ведет потом в тупик, так ? но чисто теоретически он возможен - он делить + 50 - 55
                                                                                    0
                                                                                    да, но эта ветка обрывается, что легко доказать, если рассматривать варианты НЕТ. После первого хода осталось 11 шаров. На втором ходу только один вариант хода - 3 шара. В случае НЕТ - на третьем ходу только один вариант - 2 шара. В случае НЕТ получаем 6 шаров и 4 попытки и здесь уже ходов нет.
                                                                                      0
                                                                                      да, Гомер, это правда.
                                                                                    0
                                                                                    Третье сообщение от меня.

                                                                                    Знаешь ты действительно помог - я стал смотреть руками :) что он считает и понял.
                                                                                    Например мы проверили 5 на первом шаге, смотрим в ветку НЕТ.
                                                                                    Теперь включать эти 5 в какие-либо проверки нет смысла.
                                                                                    Но они не мешают и раз я проверял все варианты то их я тоже включал. вот откуда столько деревьев решений.
                                                                                    Сейчас исправлю, чтобы шары из проверок НЕТ не могли попадать в дальнейшие проверки.
                                                                                    Спасибо тебе!
                                                                                      0
                                                                                      Этого скорее всего не хватит, так ты просто отсечешь лишнее в ветках НЕТ. нужно еще и учитывать результаты ДА.
                                                                                        0
                                                                                        поясни ? я не понял тебя.
                                                                                        То что я добавил это то, что те шары которые входили в проверку с результатом НЕТ, уже не войдут в другие проверки. (иначе к любой хорошей проверке можно добавлять такие шары и будут получаться новые проверки с таким же результатом)

                                                                                        Получается деревьев решений 1 - 9 - 50 - 1500 - это после 4х проверок.
                                                                                        Блин дальше просчитать не получается пока, очень много их на 5й проверке уже. Почему-то не отсеиваются.. Наверное гдде-то еще ошибка.
                                                                                        Сейчас приведу 9 деревьев второго уровня, может быть поможешь советом.
                                                                                          0
                                                                                          Вот варианты второй проверки, если после первой да/нет
                                                                                          ДА НЕТ
                                                                                          126 6789
                                                                                          16789 678
                                                                                          6789 10 11 67

                                                                                          Кажется что-то проясняется - по каждой ветке 3 варианта, но так как я смотрю каждый с каждым их получается 9.
                                                                                          Да уж я много лишнего счета делаю. Буду исправляться. :)
                                                                                    0
                                                                                    Можно обойтись и без всяких деревьев решений: представить номера шаров в троичной системе счисления, начиная с 000. Засовываем в коробку попеременно сначала три цифры младшего разряда, затем две цифры второго и две последнего.
                                                                                      0
                                                                                      А я уж и забыл про эту задачу.
                                                                                      В общем, так просто не получится, потому что будет три цифры второго разряда, а проверить вы предлагаете только две (видимо, только 0 и 1). Привожу очевидный контрпример: радиоактивны шары 010 и 022. После предложенных замеров вы никак не отличите этот случай от 010 и 012.

                                                                                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                                    Самое читаемое