Question

Помогите ,срочно!!!Очень,прошу!!! Имеется квадрат в клеточку размером 16 на 16 клеток. В его угол (на угловую клетку) поставили умного робота, умеющего делать шаги вперед, назад, вправо и влево ровно на 1 клетку. Роботу дали задание переместиться в противоположный угол квадрата, пройдя через все клетки и побывав в каждой из них ровно по 1 разу. В прямоугольнике 3 на 2 клетки робот смог бы это сделать ровно одним способом (существует ровно один маршрут, удовлетворяющий условию). Сколькими способами умный робот сможет выполнить свое задание в квадрате 16х16? Обоснуйте Ваш ответ!

Answer 1

При прямоугольнике 3х2 он движется по змейке, начиная по короткой стороне.

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

Answer 2

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

Кроме того, на каждом шаге роботу необходимо двигаться либо вправо, либо влево, либо вверх, либо вниз, то есть он имеет 4 возможных направления движения на каждом шаге. Следовательно, общее количество возможных маршрутов робота равно 4 в степени 255, т.е. 1,157920892 × 10 в степени 154.

Ответ: количество возможных маршрутов робота равно 1,157920892 × 10 в степени 154.