Я подумал… Хорошенько подумал И вот до чего я додумался… Постараюсь изложить лаконично: В квадрате (или решетке) 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.: Патент, на мой взгляд, довольно несуразный, хотя чем бы Боб не тешился… Удачи тебе, Боб!
