• Скачки

      Задача известная (решение нагуглить можно), но, как мне кажется, достаточно интересная.

      У нас есть 25 лошадей, мы должны выбрать из них 3х лучших. Для этого мы можем устроить несколько забегов. В каждом забеге могут участвовать не более 5 лошадей.
      Все лошади разные (т.е. никакие две не бегут с одной и той же скоростью), скорость лошади от забега к забегу не меняется.
      Требуется минимизировать число забегов.
      UPDATE: Время измерять мы не умеем, после забега мы узнаем только порядок участвовавших в нем лошадей.

      Формальное описание: есть множество из 25 элементов, на котором задан линейный порядок. За один запрос мы можем узнать часть этого порядка на выбранных нами 5 элементах. Требуется найти 3 минимальных элемента за минимально возможное число запросов.
    • Пройти лабиринт

        Клеточный лабиринт — это прямоугольник из квадратных комнат, между некоторыми из них есть перегородки.
        НЛО забросило Вас в клеточный лабиринт MxN (M и N известны), без входов и выходов. В одной из комнат лежит приз.
        У Вас есть сколь угодно много времени и памяти. Ваша цель — добраться до приза. Гарантируется, что это сделать можно.
        Что Вы будете делать?
        UPD: мои извинения, варианты, предложенные Tails и Brotherofken указали, что я ошибся при переформулировке.
        Канонически нужно было составить программу для робота, который умеет только ходить — вперед, назад, вправо, влево. Условия он проверять не умеет, то, что уперся в стену — не замечает, что взял приз — тоже. Нужно составить программу (конечной длины), действуя по которой он гарантированно побывает в клетке с призом и остановится.
      • Сколько комнат в коридоре?

          Вы находитесь в кольцевом коридоре, состоящем из N комнат. В каждой комнате две двери — «вперед» и «назад». Пройдя N комнат в любом из направлений — побываете во всех и вернетесь в исходную.
          В каждой комнате есть лампочка и выключатель от этой лампочки, т.е. находясь в комнате вы можете включить/выключить лампочку по своему желанию. Изначально они включены хаотично.
          Бить лампочки, ломать выключатели, рисовать мелом на стенах и т.д. запрещено.
          Требуется определить число N.
          UPD: задача совсем простая, в комментариях уже есть ответ.