Интересная математическая задача

@Exiti · Регистрация: 26.11.2017

Студворк — интернет-сервис помощи студентам

На очень большом листе клетчатой бумаги нарисовали систему координат. В точке (0; 0) маленький робот. Он может выполнять команды RIGHT, LEFT, UP, DOWN, смещаясь на единичный отрезок в соответствующем направлении. Вася пишет программу для робота, состоящую ровно из 12 команд и приводящую его в точку с координатами (6; 4). Ему стало интересно: а сколько всего существует таких программ? Помогите ему ответить на этот вопрос. В качестве ответа укажите одно натуральное число — количество таких команд.

Комментарий. Если робот находится в начале координат и выполнил команду RIGHT, он окажется в точке (1; 0). Если после этого он выполнит команду LEFT, то вернется обратно в точку (0; 0). Если теперь он выполнит команду UP, то окажется в точке (0; 1), а если затем выполнит команду DOWN, то опять вернется в точку (0; 0). Программа робота – это набор команд. Программы, отличающиеся перестановкой команд, считаются различными.

Например, есть 9 различных программ, состоящие ровно из 3 команд, приводящие робота из точки (0; 0) в точку (1; 0): RIGHT LEFT RIGHT; UP DOWN RIGHT; DOWN UP RIGHT; UP RIGHT DOWN; DOWN RIGHT UP; RIGHT UP DOWN; RIGHT DOWN UP; RIGHT RIGHT LEFT.
Может кто подкинет идейку?

@кот Бегемот · 04.01.2018, 14:56

Понятно, что из 12 команд 6 обязательно будут RIGHT, а 4 обязательно будут UP. Оставшиеся две команды будут противоположны, то есть LEFT-RIGHT (или наоборот) или UP-DOWN (или наоборот)- 4 варианта. Остаётся методами комбинаторики посчитать количество различных перестановок 6 команд RIGHT и 4 команд UP, не забывая вставить две противоположные команды.

@JuriiMW · 05.01.2018, 06:53

Pascal

var steps := 12; // За кол-во ходов
var Xend  := 6; // В точку с координатой X
var Yend  := 4; // ... и Y
 
var vars := 0;
 
procedure Find(step, X, Y : Integer);
begin
  if step = 0 then
    vars += (X = Xend) and (Y = Yend) ? 1 : 0
  else
    begin
      Find(step - 1, X + 1, Y    );
      Find(step - 1, X - 1, Y    );
      Find(step - 1, X    , Y + 1);
      Find(step - 1, X    , Y - 1);
    end;
end;
 
begin
  Find(steps, 0, 0);
  Print(vars);
end.

@Exiti 3 / 3 / 0 Регистрация: 26.11.2017 Сообщений: 30
		1
	Интересная математическая задача 04.01.2018, 14:25. Показов 1538. Ответов 2 Метки нет (Все метки) На очень большом листе клетчатой бумаги нарисовали систему координат. В точке (0; 0) маленький робот. Он может выполнять команды RIGHT, LEFT, UP, DOWN, смещаясь на единичный отрезок в соответствующем направлении. Вася пишет программу для робота, состоящую ровно из 12 команд и приводящую его в точку с координатами (6; 4). Ему стало интересно: а сколько всего существует таких программ? Помогите ему ответить на этот вопрос. В качестве ответа укажите одно натуральное число — количество таких команд. Комментарий. Если робот находится в начале координат и выполнил команду RIGHT, он окажется в точке (1; 0). Если после этого он выполнит команду LEFT, то вернется обратно в точку (0; 0). Если теперь он выполнит команду UP, то окажется в точке (0; 1), а если затем выполнит команду DOWN, то опять вернется в точку (0; 0). Программа робота – это набор команд. Программы, отличающиеся перестановкой команд, считаются различными. Например, есть 9 различных программ, состоящие ровно из 3 команд, приводящие робота из точки (0; 0) в точку (1; 0): RIGHT LEFT RIGHT; UP DOWN RIGHT; DOWN UP RIGHT; UP RIGHT DOWN; DOWN RIGHT UP; RIGHT UP DOWN; RIGHT DOWN UP; RIGHT RIGHT LEFT. Может кто подкинет идейку? 0

@кот Бегемот Платежеспособный зверь 8821 / 4248 / 1618 Регистрация: 28.10.2009 Сообщений: 11,389
	04.01.2018, 14:56	2
	Понятно, что из 12 команд 6 обязательно будут RIGHT, а 4 обязательно будут UP. Оставшиеся две команды будут противоположны, то есть LEFT-RIGHT (или наоборот) или UP-DOWN (или наоборот)- 4 варианта. Остаётся методами комбинаторики посчитать количество различных перестановок 6 команд RIGHT и 4 команд UP, не забывая вставить две противоположные команды. 1

Опции темы

Интересная математическая задача

Решение