17 дек 2020 в 20:00

Решение задачи про хрустальные шары в общем виде

Ожидает приглашения

Условие:

У вас есть два хрустальных шара. Необходимо выяснить, падение с какого из 100 этажей здания шар еще выдерживает не разбиваясь. Более того, нужно найти стратегию требующую минимальное количество попыток полагая результаты попыток максимально не благосклонными выбранной методике и оценить это количество. Можно разбить оба шара в плодотворных поисках.

Решение:

Решим вариант данной задачи в общем виде – за какое минимальное число попыток возможно определить нужный этаж в k - этажном здании, имея n шаров. Для этого инвертируем условие задачи, будем определять этаж, до которого (включительно) мы сможем гарантированно найти нужный, имея на руках n шаров и m попыток их бросить. Обозначим это число a_n,_m .

Исследуем это число для простейших случаев:

Если n = 0 или m = 0, то, очевидно, что $a_{0,m}=0$ и $a_{n,0}=0$ , нет шаров или попыток.

При n = 1, нам нужно бросать с самого нижнего этажа (бросив с пропуском этажа, шар разобьётся и этаж узнать не получится) поэтому $a_{1,m}=m$ .

Каждая использованная попытка дает нам дополнительную информацию о нужном этаже, поэтому оптимальным будет алгоритм для заданных n и m, который задействует все шары и все попытки. При этом, чтобы каждая попытка давала максимум информации, бросок нужно осуществлять с максимально возможного этажа для данной попытки, но так, чтобы оставшихся попыток и шаров хватило на нахождения решения в протестированном интервале этажей броском данной попытки. При n=2 таким максимальным этажом для первого шара будет этаж m остальными (m-1) попытками и вторым шаром мы проверим нижние этажи, если шар разбился. Если же он не разбился, то у нас все еще два шара и (m-1) попытка, следовательно вернулись к исходным условиям задачи, но с использованной попыткой. Значит, теперь можем бросить на (m-1) этаж вперед, остальными (m-2) попытками в любом случае найдем нужный этаж. Если же шар разобьется, то бросим снова на (m-3) этаже и так далее, пока попытки не закончатся. Итого, получаем, что этаж будет представлять из себя сумму членов арифметической прогрессии от 1 до m:

$a_2,_m=\frac{(1+m)m}{2}$

На этом шаге можно получить решение исходной задачи для n=2 и k=100 , подбирая так, чтобы a_2,_m оказалось больше или равно 100. При m=13 получаем 91, а при m=14 получаем 105, поэтому ответ 14.

Теперь рассмотрим условие задачи для n=3 и попыток. Если при броске первого шара он разобьется, то оставшимися 2 шарами мы можем проверить максимум $a_{2,m-1}$ этажей снизу, следовательно первую попытку можно делать максимум с $a_{2,m-1}+1$ этажа. Если шар не разбился, то у нас все еще 3 шара и (m-1) попытка, а, следовательно, имеет место следующее рекуррентное соотношение, которое, очевидно, можно записать для произвольного числа шаров:

$a_{n,m}=a_{n-1,m-1}+a_{n,m-1}+1$

Найдем выражение для $a_{n,m}$ используя метод производящих функций, производящую функцию будем искать в виде:

$G\left(x,y\right)=\ \sum_{n,m=0}^{\infty}{a_{n,m}x^ny^m}$

Умножая левую и правую часть рекуррентного соотношения на x^ny^m и используя то, что $a_{0,m}=0$ и $a_{n,0}=0$ получим:

$G\left(x,y\right)=\ \sum_{n,m=1}^{\infty}{a_{n,m}x^ny^m=\sum_{n,m=1}^{\infty}{a_{n-1,m-1}x^ny^m+\sum_{n,m=1}^{\infty}{a_{n,m-1}x^ny^m+\sum_{n,m=1}^{\infty}{x^ny^m}}}}$

Вынося за скобку в первом слагаемом, во втором слагаемом и сдвигая индекс суммирования получим, что:

$G\left(x,y\right)=xyG\left(x,y\right)+yG\left(x,y\right)+\sum_{n,m=1}^{\infty}{x^ny^m}$

Выражая G(x,y) , получаем:

$G\left(x,y\right)=\frac{1}{1-y-xy}\sum_{n,m=1}^{\infty}{x^ny^m}$

используя то, что функция $\frac{1}{1-y-xy}$ является двумерной производящей функцией для биномиальных коэффициентов, получаем:

$G\left(x,y\right)=\sum_{k,i=0}^{\infty}{C_i^kx^ky^i}\sum_{n,m=1}^{\infty}{x^ny^m}$

Раскрывая произведение сумм и объединяя члены с одинаковыми степенями и используя то, что C_i^k=0 при k > i, получаем:

$G\left(x,y\right)=\sum_{n,m=1}^{\infty}{\left(\sum_{k,i=0}^{m-1,n-1}C_k^i\right)x^ny^m}$

И, следовательно:

$a_{n,m}=\sum_{k,i=0}^{m-1,n-1}C_k^i$

Для нашего случая, n = 2, m = 14 получаем:

$a_{2,14}=\sum_{i=0}^{13}{C_i^0+\sum_{i=1}^{13}{C_i^1=14+\left(1+2+3+4+5+6+7+8+9+10+11+12+13\right)=105\ }}$

Задача про шары и этажи свелась к сложениям биномиальных коэффициентов.

А как вы считаете, уместна ли подобная задача на собеседованиях?

Теги:

Хабы: