Задачи на сообразительность – декабрь 2011

Опубликовано Dec 9, 2011 в Олимпиадные задачи | 30 коммент.

, ,

Задачи на сообразительность – декабрь 2011

Пост для любителей логических задач (math puzzles)

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

Среди 12 монет есть ровно одна фальшивая. Она отличается от остальных по весу (в какую сторону — неизвестно). Необходимо определить фальшивую монету с помощью аптекарских весов и трёх взвешиваний.  Аптекарские весы позволяют сравнить веса взвешиваемых предметов.

Задача Гарднера. Найти угол между двумя смежными диагоналями куба.

Почему пожарные ведра конической формы, то есть дно ведра заострено.

Некто загадал число 1,2 или 3. Этот человек всегда говорит правду. Необходимо задать этому человеку вопрос, ответ на который может быть либо “да” либо “нет”, выслушать ответ и определить, что за число он загадал.

В бесконечном закольцованном поезде в одном из вагонов находится человек, в руке которого тряпка и мел. Ему нужно посчитать число вагонов. Он может переходить из вагона в вагон. Внутри вагонов мусор, вагоны как-то раскрашены, таким образом, человек не может поставить уникальную метку. Как ему определить число вагонов?

В группе туристов, состоящей из 4 человек, имеется ровно один фонарик. Всем ее членам необходимо перейти через мост. Вокруг – темнота, и двигаться по мосту можно только с фонариком. Через мост может переходить одновременно не более двух человек. У каждого из членов группы своя скорость пересечения моста. Если через мост переходят два человека, то пара движется со скоростью самого медленного из них. В какой последовательности нужно переходить мост, чтобы группа сделала это как можно быстрее.

10 преступников сидят в одиночных камерах. В первый день надзиратель дает им возможность поговорить между собой. Далее в каждый из следующих дней он выбирает одного из преступников и ведет в карцер. В карцере есть лампочка, она может быть включена или выключена. Преступник, находясь в карцере, может изменить состояние лампочки, а может и не изменять. В один из дней один из преступников может сообщить надзирателю, что все уже побывали в карцере. Тогда, если он сказал правду, всех выпускают, в противном случае всех казнят. Гарантируется, что если никто не будет говорить надзирателю, что все уже побывали в карцере, каждый побывает в нем бесконечное количество раз. Как нужно действовать преступникам?

N гномиков стоят в колонне. На голове у каждого гномика шапка черного или белого цвета. Гномик не видит цвета своей шапки, но видит цвета шапок стоящих перед ним. Каждый гномик, начиная с конца колонны, называет цвет: черный или белый. Если он угадал цвет своей шапки, он остается в живых, в противном случае – гибнет. Какое количество гномиков может спастись?

Два абсолютно одинаковых робота спускаются на железнодорожное полотно на своих парашютах. После этого они отстегивают парашюты и начинают движение в соответствии с заложенной в них программой. В программе есть операторы НАПРАВО, НАЛЕВО, GOTO НОМЕР_СТРОКИ, IF ПАРАШЮТ GOTO КОЛИЧЕСТВО_ШАГОВ. Команды НАПРАВО и НАЛЕВО изменяют направление движения роботов на противоположное. По команде GOTO КОЛИЧЕСТВО_ШАГОВ робот делает КОЛИЧЕСТВО_ШАГОВ в том направлении, которое установлено на момент выполнения команды. IF ПАРАШЮТ проверяет, не оказался ли робот в позиции, где лежит парашют. Какая должна быть заложена программа (одинаковая для обоих роботов), чтобы они встретились?

 


30 Коммент. : “Задачи на сообразительность – декабрь 2011”

  1. В задаче про загаданное число – что мешает задать вопрос “Какое число Вы загадали?”

  2. Про фонарик – нужно, очевидно, подразумевать, что при переходе моста используется фонарик? Из фразы “необходимо перейти мост в темноте” – может нужно сделать вывод, что они диверсанты и фонарик должны как раз выключить?

  3. Яков says:

    Спасибо, исправлю

  4. Trusov Denis says:

    Скорее всего мешает то, что этот человек отвечает только “да” или “нет”. Часть загадок взята из книги, которая посвящена прохождению собеседований, там и ответы есть на некоторые. ^.^

  5. Условия уточнены, в соответствии с комментариями. Ожидаем новых комментариев.

  6. Anonymous says:

    “Ожидаем новых комментариев” очевидно означает, что можно обсудить решения?
    1-3 и 6 эт легко:D
    а про числа, что мешает ввести “троичную” логику? имеем право задать один вопрос, на который “может”(!) ответить да/нет, а может соответственно вообще не отвечать. И что понимать под “ответ может быть да\нет”?. Если четко определено, что нельзя использовать никакие уловки, т.е. можно передать лишь один бит информации, то задача не имеет решения и число можно лишь угадать с определенной долей вероятности. Или это слишком примитивное решение?
    Про поезд немного не понятно: “В бесконечном(!) закольцованном поезде … определить число вагонов?”. И что значит метку поставить нельзя? Нельзя поставить метку, значит необходимо определить какие-либо характеристики по которым можно идентифицировать 0-й вагон; раз уж они все разукрашены и напичканы всяким мусором, то это очевидно не составит труда. Есть еще масса вариантов в безумном и алогичном стиле, присущем некоторым решениям головоломок.
    В задаче же про преступников не уточнено есть ли окно в карцере, и могут ли его видеть все заключенные; либо могут ли они видеть окна друг друга, если таковые существуют; если да, тогда все элементарно. И я, наверное, чушь сейчас начну нести, но если в карцере есть свет, то что мешает сделать каждому заключенному соответствующие метки( на стене в конце концов), о том что оный был в карцере. Да даже если нету света, можно что-нибудь да придумать в таком-то положении!:)
    И про гномиков мне совсем понятно. “Шапка черного или белого цвета” означает ,что по-сути то могут быть хоть либо все белые и одна черная, либо все черные и одна черная. И что означает, “какое количество гномиков может спастись”? N гномиков. Может какова вероятность спасения всех гномиков?
    зы. знаю, что похожая задача была в “книг..[е], которая посвящена прохождению собеседований, там и ответы есть на некоторые”( by Trusov Denis). Но, признаюсь честно, решения прочитаны мною еще не были.
    А по поводу задачи про роботов, общая логика построения программы то очевидна, но хотелось бы поинтересоваться: синтаксисом предусмотрено ли использование математических операций и выделена ли память для хранения переменных? Т.е. возможно ли указать GOTO еах, предварительно определив еах и можно ли совершать операции над сей ячейкой памяти( как минимум инкрементировать)? И если честно, то мне не совсем понятно как вообще можно адекватно такую программу реализовать без операторов перехода, но джампы синтаксисом, очевидно, не предусмотрены. Можно, конечно, писать повторяющийся код сколько памяти хватит( к тому же, известно ведь хоть приблизительно на каком максимальном количестве шагов они могут друг от друга приземлиться). И количество шагов может быть только положительным или отрицательным тоже( но это не так важно)? Но может я много хочу? Я сегодня не усну:)
    Спасибо большое за разминку для мозга!

  7. Максим says:

    Задача про 12 монеток.

    enum Mark //Метка подлинности
    {
        None,   //Неизвестно
        Light,  //Предположительно легче
        Heavy,  //Предположительно тяжелее
        Real    //Точно настояшая
    }
    struct Coin
    {
        public float Weight { get; set; }
        public Mark Mark { get; set; }
    }
    //Взвешивает группы монет и возвращает "1" если 1-я группа больше 2-й,
    // "-1" если меньше и "0" если равны.
    int Weigh(Coin[] left_scale, Coin[] right_scale)
    {
        float left_scale_weight = 0;
        foreach (Coin c in left_scale)
            left_scale_weight += c.Weight;
        float right_scale_weight = 0;
        foreach (Coin c in right_scale)
            right_scale_weight += c.Weight;
        if (left_scale_weight == right_scale_weight)
            return 0;
        else
        {
            if (left_scale_weight < right_scale_weight)
                return -1;
            else return 1;
        }
    }
    Coin GetRealCoin(Coin[] coins)
    {
        if (coins.Length != 12) throw new Exception("Должно быть ровно 12 монет");
        int first_weighing = Weigh(new Coin[] { coins[0], coins[1], coins[2], coins[3] },
            new Coin[] { coins[4], coins[5], coins[6], coins[7] });
        if (first_weighing == 0)//первое взвешивание -- равны
        {
            //Взвешенные 8 монет точно настояшие
            for (int i = 0; i < 8; ++i)
                coins[i].Mark = Mark.Real;
            //Сравниваем 2 из 4х оставшихся с двумя точно настояшими
            int second_weighing = Weigh(new Coin[] { coins[8], coins[9] },
                new Coin[] { coins[0], coins[1] });
            if (second_weighing == 0)//второе взвешивание -- равны
            {
                //9я и 10я монеты точно настоящие
                coins[8].Mark = coins[9].Mark = Mark.Real;
                //Взвешиваем одну из 2х оставшихся с точно настоящей
                int third_weighing = Weigh(new Coin[] { coins[10] }, 
                    new Coin[] { coins[0] });
                if (third_weighing == 0)//третье взвешивание -- равны
                {
                    coins[10].Mark = Mark.Real;
                    //Последняя фальшивая, но к сожелению мы не можем
                    //сказать тяжелее она или легче
                    return coins[11];
                }
                else //третье взвешивание -- не равны
                {
                    //следовательно взвешенная монета фальшивая
                    coins[11].Mark = Mark.Real;//оставшаяся
                    if (third_weighing == -1)//исследуемая монета легче
                    {
                        coins[10].Mark = Mark.Light;
                        return coins[10];
                    }
                    else //исследуемая монета тяжелее
                    {
                        coins[10].Mark = Mark.Heavy;
                        return coins[10];
                    }
                }
            }
            else //второе взвешивание -- не равны
            {
                //оставшиеся монеты точно настоящие
                coins[10].Mark = coins[11].Mark = Mark.Real;
                if (second_weighing == -1)//исследуемые(9,10) монеты легче
                {
                    coins[8].Mark = coins[9].Mark = Mark.Light;
                }
                else //исследуемые монеты(9,10) тяжелее
                {
                    coins[8].Mark = coins[9].Mark = Mark.Heavy;
                }
                int third_weighing = Weigh(new Coin[] { coins[8] },
                    new Coin[] { coins[0] });
                if (third_weighing == 0)//3е взвешивание -- равны
                {
                    coins[8].Mark = Mark.Real;
                    return coins[9];
                }
                else //3е взвешивание -- не равны
                {
                    coins[9].Mark = Mark.Real;
                    return coins[8];
                }
            }
        }
        else //первое взвешивание -- не равны
        {
            for(int i = 8; i < 12; ++i)//оставшиеся
                coins[i].Mark = Mark.Real;
            if (first_weighing == -1)//легче
            {
                for (int i = 0; i < 4; ++i)
                    coins[i].Mark = Mark.Light;
                for (int i = 4; i < 8; ++i)
                    coins[i].Mark = Mark.Heavy;
            }
            else//тяжелее
            {
                for (int i = 0; i < 4; ++i)
                    coins[i].Mark = Mark.Heavy;
                for (int i = 4; i < 8; ++i)
                    coins[i].Mark = Mark.Light;
            }
     
            //по одной из каждой группы откладываем в сторону(3,7) 
            //по одной меняем местами(2,4) и одну заменяем настоящей(6 на 8)
            int second_weighing = Weigh(new Coin[] { coins[0], coins[1], coins[4] },
                new Coin[] { coins[2], coins[5], coins[8] });
            if (second_weighing == 0)//второе взвешивание равны
            {
                //значит все они настоящие(0,1,2,4,5)
                //проблема в оставшихся(3,6,7)
                //взвешиваем 2 из ни одну "легкую" и одну "тяжелую"
                //с двумя точно настоящими
                int third_weighing = Weigh(new Coin[] { coins[3], coins[6] },
                    new Coin[] { coins[8], coins[9] });
                if (third_weighing == 0)//третье взвеш. равны
                {
                    //фальшивая -- оставшаяся(7)
                    for (int i = 0; i < 7; ++i)
                        coins[i].Mark = Mark.Real;
                    return coins[7];
                }
                else//третье взвеш. не равны
                {
                    //если легче, то фальшивая -- "легкая" и наоборот
                    if (third_weighing == first_weighing)
                        return coins[3];
                    else return coins[6];
                }
            }
            else//второе взвешивание не равны
            {
                if (second_weighing != first_weighing)
                {
                    //если чаши весов встали наоборот, то причина в тех монетах
                    //которые мы поменяли местами(2 и 4)
                    int thirdd_weiging = Weigh(new Coin[] { coins[2], coins[4] },
                        new Coin[] { coins[8], coins[9] });
                    if (thirdd_weiging == first_weighing)
                        return coins[2];
                    else return coins[4];
                }
                else//если весы стоят также то причина в 0,1 или 5
                {
                    //взвешиваем ону "легкую" и одну "тяжелую" с 2мя настоящими
                    int third_weighing = Weigh(new Coin[] { coins[0], coins[5] },
                        new Coin[] { coins[8], coins[9] });
                    if (third_weighing == 0)//равны
                        return coins[1];
                    else//не равны
                    {
                        if (third_weighing == first_weighing)
                            return coins[0];
                        else return coins[5];
                    }
                }
            }
        }
    }
    • Галина says:

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

    • Максим says:

      Словесное описание в коментариях.

    • Галина says:

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

    • Максим says:

      Я, конечно, в тестировании ничего не понимаю, но согласно условию здесь всего 24 варианта – проще врукопашную проверить(но, конечно, не так интересно).

      • Галина says:

        Идею вы уловили правильно – как раз и нужно написать скрипт, который вызовет программу для ВСЕХ вариантов с правильными исходными данными, раз их конечное число. Очень удачный пример для автоматического теста.

  8. Максим says:

    Задача Гарднера.
    Если сделать срез куба по смежным диагоналям, то получится пирамида, то есть, соответственно, плоскость в которой небходимо вычислить углы является равносторонним треугольником. Следовательно искомый угол 180/3 = 60.

    • Галина says:

      Разрезать куб получится по диагоналям смежных ГРАНЕЙ КУБА, например, по GD и DB. Как раз между ними и будет 60 градусов (и равносторонний треугольник).
      Смежные диагонали куба не пересекаются – нужно найти угол, например, между красными линиями HB и DF. И это еще не все варианты.
      Смежные диагонали куба

  9. Максим says:

    Про пожарное ведро.
    Я думаю легче перевернуть чтобы высыпать и песок легче вытряхивается (в обычном ведре песок на дне спресовывается и там и остается).

    • Галина says:

      Наверное, это соображение верное. Хотя на подобные вопросы однозначно правильных ответов в принципе нет.
      Например, про ведро – я знаю такой ответ (для нашего местного менталитета,может и актуальный).
      “Ведро с коническим дном неудобно в хозяйстве, поэтому его меньше соблазна унести (украсть) с пожарного щита”.

  10. Максим says:

    Про туристов.
    -переходят двое самых быстрых
    -один из них возвращается назад
    -переходят двое самых медленных
    -второй быстрый возвращается с фонариком
    -оставшиеся двое переходят

    • Галина says:

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

    • Максим says:

      Не совсем согласен. Главнее чтобы разница в скорости переходящих одновременно была минимальной.

  11. Максим says:

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

  12. Anonymous says:

    Про преступников.
    Я вижу только один маловероятный способ им спастись: если им повезет и они побывают в карцере все по очереди в определенную десятидневку.
    Им нужно аспределить между собой номера и каждый будет вести отчет дней. “Своим днем” считается каждый n-й день. То есть например для пятого заключенного “своим” будет первый 5-й день и потом каждый 10-й.
    Если первый заключенный попал в карцер в свой день то он оставляет свет включенным. Заключенные со 2го по 9й попадая в карцер поступают так: если свет включен и сегодня его день он его оставляет включенным, а если не его день то выключает. Таким образом 10й заключенный попав в свой день и увидев включенный свет может с уверенностью сказать что все там побывали.

  13. Максим says:

    Про заключенных.
    Спастись они могут только если побывают в карцере каждый день поочереде в строго определенном порядке начиная с определенного дня(маловероятно но шанс есть). Заключенные получают по номеру каждый от 1-го до 10-и. Каждый соответсвенно своему номеру отсчитывает дни. “Своим” считается день например для 5го заключенного 5-й день с начала отсчета и потом каждый через10. 1й заключенный в свой день оставляет свет включенным а в чужой выключает. Заключенные со 2го по 9й попадая в свой день ничего не меняют а в чужой день выключают свет. 10й попав в карцер в чужой день выключает свет а в свой ден, если свет включен он может с уверенностью сказать что все побывали в карцере

  14. Максим says:

    Смешно. Думал в первый раз не отправилось. Зря два раза писал :-)

  15. Владимир says:

    про гномиков меня спрашивали на собеседовании, я решил.
    гарантированно спасаются все кроме первого, а он с вероятностью 50%.

  16. Так какой же правильный ответ про числа? Сижу уже час голову ломаю и все никак не додумаюсь до решения…

    • Галина says:

      Первый шаг решения, сообразить, что имеются вопросы, на которые нельзя дать ответ “Да” или “Нет”. Ну, например: “Если к вашему числу прибавить число забитых мячей в финале чемпионата мира по футболу в 2014 году, то получится семь?” Честный ответ на этот вопрос – “Не знаю”. Вот это и нужно использовать.

  17. Предполагаю что постановка задачи про 3 числа не корректна. Т. к. 1 числу должен соответствовать 1 вариант ответа, а в условии сказано что могут быть только 2 варианта. Выходит должен быть третий вариант. Значит спросить нужно что-то чтобы в 1 из случает ответа не было. И тогда мне пришел в голову такой варианты:
    допустим загаданное число n.
    1. n % (n – 1) == 0
    “Если вычислить остаток от деления загаданного числа на число, меньшее на единицу, ответ будет равен нулю”?
    Да – 2
    Нет – 3
    Ответа нет – 1
    2. n/(n-1) == n
    Да – два
    Нет – три
    Ответа нет – единица.
    3. Еще такая странная конструкция сработала ХД

    try
                {
                    int test = Convert.ToInt32(textBox1.Text) + 253;
                    byte res = Convert.ToByte(test);
                    if (res == 255)
                        label1.Text = "Two";
                    else
                        label1.Text = "One";
                }
                catch
                {
                    label1.Text = "Three";
                }

    Вопрос можно сформулировать так: “Если в переменную byte записать сумму загаданного числа и числа 253. То при выводе на экран содержимое будет меньше 255?” =)))
    Да – единица
    Нет – двойка
    Ответа нет так как нет выводимого результата – тройка

    • Идея правильная, важно найти постановку вопроса, в которой будет три варианта ответа – да, нет и (не знаю = отсутствие ответа).

      Ваш вариант с делением на ноль может быть не совсем правильным, т.к. бесконечность точно не ровна некоторой константе. Итого – можно ответить нет.

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

      Вот пример варианта – который гарантированно содержит ответ = “нет ответа”: Я выбрал одно число из набора 1,2,3. Это число точно отличается от вашего. Мое число больше вашего?”

Оставить комментарий

Ваш адрес email не будет опубликован.


*