Боб решил запатентовать программно-аппаратный комплекс для блокировки своего мобильного телефона, который бы работал следующим образом. на сенсорном экране его телефона выводится квадратная решетка. код
блокировки формируется в результате "нажатия пальцем" в узлы этой решетки, так чтобы в результате был сформирован путь из верхнего-левого узла в правый-нижний. из каждого узла решетки за один шаг можно попасть
только в следующий узел справа или ниже. например, для решетки размера 4 x 4 на рисунке указан один из правильных путей построения кода: pixshock.net/pic_b/7a1050da11c35c25f90098013cb95727.gif подумайте, сколько существует кодов блокировки
(различных путей от верхнего левого угла решетки до правого нижнего угла) для квадратной решетки размера 1 х 1, 2 х 2, 3 х 3, 4 х 4 и т.д.? и бобу определить значение n - минимальный размер решетки n x n, который допускал бы не
меньше 1 000 000 различных кодов блокировки его телефона. значение n и будет ответом к

107

141

Посмотреть ответы 2

Ответы на вопрос:

SHILW

Математика

4,8(17 оценок)

я хорошенько подумал : -) и вот до чего я постараюсь изложить лаконично:

в квадрате (или решетке) 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 - где c(n, k) означает количество размещений из n по k.

итак, количество путей в квадрате nxn определяется по формуле p(n) = c(2*n, n) = (2*n)! /(n! *(2*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.: патент, на мой взгляд, довольно несуразный, хотя чем бы боб не : -) удачи тебе, боб! : -)