Я подумал... Хорошенько подумал :-) И вот до чего я додумался... Постараюсь изложить лаконично:
В квадрате (или решетке) NxN имеется N строк и N колонок. Предположим, что мы кодируем ход вправо как единицу "1", а ход вниз - как ноль "0". Любой допустимый путь из левого верхнего угла квадрата (т.е. решетки) в нижний состоит из N переходов вправо и N переходов вниз. Тогда каждому допустимому пути будет соответствовать двоичная последовательность длины 2*N, в которой обязательно будут присутствовать N единичек "1" и N нулей "0". Остается только определить, сколько таких последовательностей можно построить для квадрата NxN.
Попытаемся, к примеру, расставить только N единичек "1" на соответствующие позиции в последовательности из 2*N символов. Оставшиеся места мы автоматически заполним нулями "0". Первую "1" можно поставить на любую из 2*N позиций, вторую - на любую из оставшихся 2*N - 1 позиций и т.д. Количество таких размещений, как известно, будет (2*N)*(2*N - 1)*(2*N - 2)*...*(2*N - (N - 1)) = C(n=2*N, k=N) = (2*N)!/(N!*(2*N - N)!), где C(n, k) означает количество размещений из n по k.
Итак, количество путей в квадрате NxN определяется по формуле P(N) = C(2*N, N) = (2*N)!/(N!*(2*N - N)!) = (2*N)!/(N!*N!) = (2*N)!/((N!)^2) (*)
Подставляя в формулу последовательно значения N = 1, 2, 3 и 4, находим количество путей для квадратов 1x1, 2x2, 3x3 и 4x4: P(1) = 2, P(2) = 6, P(3) = 20 и P(4) = 70.
По условию нам нужно также найти такое минимальное N, при котором P(N) > 1000000 = 10^6.
Найдем его при вычисления на компьютере (альтернативно можно использовать формулы для приближенного вычисления факториала):
P(N) = (2*N)!/((N!)^2) > 1000000 = 10^6
Вычислением нескольких последовательных значений P(N) мы убеждаемся, что P(N=11) = 705432 < 1000000 < P(N=12) = 2704156. Следовательно, Бобу нужно взять квадрат (или решетку) размером 12x12.
ответ: N = 12
P.S.: Патент, на мой взгляд, довольно несуразный, хотя чем бы Боб не тешился... :-) Удачи тебе, Боб! :-)
Я подумал... Хорошенько подумал :-) И вот до чего я додумался... Постараюсь изложить лаконично:
В квадрате (или решетке) NxN имеется N строк и N колонок. Предположим, что мы кодируем ход вправо как единицу "1", а ход вниз - как ноль "0". Любой допустимый путь из левого верхнего угла квадрата (т.е. решетки) в нижний состоит из N переходов вправо и N переходов вниз. Тогда каждому допустимому пути будет соответствовать двоичная последовательность длины 2*N, в которой обязательно будут присутствовать N единичек "1" и N нулей "0". Остается только определить, сколько таких последовательностей можно построить для квадрата NxN.
Попытаемся, к примеру, расставить только N единичек "1" на соответствующие позиции в последовательности из 2*N символов. Оставшиеся места мы автоматически заполним нулями "0". Первую "1" можно поставить на любую из 2*N позиций, вторую - на любую из оставшихся 2*N - 1 позиций и т.д. Количество таких размещений, как известно, будет (2*N)*(2*N - 1)*(2*N - 2)*...*(2*N - (N - 1)) = C(n=2*N, k=N) = (2*N)!/(N!*(2*N - N)!), где C(n, k) означает количество размещений из n по k.
Итак, количество путей в квадрате NxN определяется по формуле P(N) = C(2*N, N) = (2*N)!/(N!*(2*N - N)!) = (2*N)!/(N!*N!) = (2*N)!/((N!)^2) (*)
Подставляя в формулу последовательно значения N = 1, 2, 3 и 4, находим количество путей для квадратов 1x1, 2x2, 3x3 и 4x4: P(1) = 2, P(2) = 6, P(3) = 20 и P(4) = 70.
По условию нам нужно также найти такое минимальное N, при котором P(N) > 1000000 = 10^6.
Найдем его при вычисления на компьютере (альтернативно можно использовать формулы для приближенного вычисления факториала):
P(N) = (2*N)!/((N!)^2) > 1000000 = 10^6
Вычислением нескольких последовательных значений P(N) мы убеждаемся, что P(N=11) = 705432 < 1000000 < P(N=12) = 2704156. Следовательно, Бобу нужно взять квадрат (или решетку) размером 12x12.
ответ: N = 12
P.S.: Патент, на мой взгляд, довольно несуразный, хотя чем бы Боб не тешился... :-) Удачи тебе, Боб! :-)
всего 576 таких чисел.
1) обозначим первую цифру через x, она не может быть нулем, поэтому возможно 9 вариантов выбора
2) другую цифру обозначим через y, ее тоже можно выбирать она может быть нулем, но не может быть равна x)
3) нужно отдельно рассмотреть три случая: xy··, xxy· и xxx·; для каждого из этих случаев нужно подсчитать количество вариантов и эти числа сложить
4)в варианте xy·· две последних цифры могут быть (независимо друг от друга) выбраны равными x или y (по 2 варианта выбора)
поэтому всего получаем 9·9·2·2 = 324 варианта
5)в варианте xxy· последняя цифра может быть равна только x или y (2 варианта)
поэтому всего получаем 9·1·9·2 = 162 варианта
6)в варианте xxx· последняя цифра может быть любой (10 вариантов)
поэтому всего получаем 9·1·1·10 = 90 вариантов
7) общее количество вариантов равно сумме
324 + 162 + 90 = 576
Всю эту работу можно нарисовать с таблицы, но если нужен просто ответ- то 576 чисел