пятница, 26 апреля 2013 г.

Лабиринт

На рисунке показана схема лабиринта, в клетку A которого поместили мышь, а в клетку B положили кусочек сыра. Мышь всегда двигается между клетками лабиринта так, что с каждым шагом приближается к сыру. Шагом будем считать перемещение из одной клетки в другую. Маршрутом будем называть совокупность клеток, в которых побывала мышь прежде, чем добраться до сыра. Сколько возможных маршрутов есть у мыши в этом лабиринте?
Головоломка про мышь и сыр
update
Ответ
126.
Число путей, ведущих к любой клетке, равно сумме числа путей двух клеток, из которых мышь приходит в выбранную клетку. Таким способом можно подсчитать возможные варианты.
Ответ на головоломку про мышь и кусочек сыра

14 комментариев:

  1. 116.
    Число возможных путей к клетке равно сумме чисел возможных путей к клетке сверху от нее и к к клетке слева от нее, а число путей к клеткам верхнего и левого рядом равняется единице.
    http://s017.radikal.ru/i444/1304/fa/4e4f28f22952.png

    ОтветитьУдалить
  2. 126.
    Решил полным перебором.
    Решил заполняя клеточки таблицы начиная с клеточек имеющих общую сторону с пунктом B. Число в клетке - количество маршрутов соединящих данную клетку и пункт B.
    Аналитическую формулу лень выводить.

    ОтветитьУдалить
    Ответы
    1. Этот комментарий был удален автором.

      Удалить
    2. "Решил полным перебором." - лишнее. Тут нет тега зачёркивание (((

      Удалить
  3. Длина = 9, 4 вниз, 5 вправо. Число сочетаний
    С^4_9 = C^5_9 = 9!/4!*5! = 126

    ОтветитьУдалить
  4. хехе)) изложу свои домыслы)) я так понял по диагонали двигаться нельзя. Возвращаться назад на клетку по горизонтали или вертикали в процессе тоже нельзя. Рискну предположить, что любой путь это 9 шагов. Обозначив клетки как координаты начнем перебирать шаги

    11 - след. шаг на 12 или 21
    из 21 шаги на 31 или 22
    из 12 шаги на 22 или 13 и т.д.
    на каждой итерации количество шагов удваивается
    и на 9 итерации получается
    2^9 = 512 шагов

    ОтветитьУдалить
    Ответы
    1. может и не верно, но у меня больше всех пока)))

      Удалить
    2. как сообщения удалять?

      Удалить
    3. Если входить не через аккаунт google, то может быть кнопка для удаления сообщения не появляется, не знаю.

      Удалить
  5. Способ решения на картинке dbsergey показан правильно, просто ошибка в числах. Должно получиться 126.

    ОтветитьУдалить