|
Имеется $%n$% одинаковых на вид монет. Известно, что одна из них фальшивая, легче остальных настоящих. Надо, используя чашечные весы без гирь, найти фальшивую монету за $%m$% взвешиваний, при чем каждую монету можно взвешивать не более $%k$% раз. задан 2 Окт '12 2:55 
chameleon |
|
У меня рекуррентная формула получилась такая: $$f(k,m)=2f(k-1,m-1)+f(k,m-1)$$ при $%k,m\ge1$%. Начальные значения равны $%1$%, если хотя бы один из аргументов равен нулю. Возможно, что это эквивалентно тому, что получилось у Вас, но я не сверял. Доказательство такое: если ни одну монету не разрешено использовать, или если нельзя проводить взвешиваний, то монета может быть всего одна. Далее, если $%k,m\ge1$%, то при первом взвешивании мы кладём на чаши весов одинаковое число монет, и сколько-то оставляем в стороне. Если одна из чаш окажется легче, но на ней должно быть столько монет, сколько мы имеем возможность "оприходовать" при значениях параметров $%k-1$% и $%m-1$%. Это значит, что на каждой чаше лежит не более $%f(k-1,m-1)$% монет, а с таким количеством мы умеем справляться. Наконец, если чаши в равновесии, то фальшивая монета среди оставшихся. Здесь у нас в запасе $%m-1$% взвешивание, а класть на весы монету мы имеем право $%k$% раз. То есть остаться должно $%f(k,m-1)$% монет, откуда следует рекуррентная формула. Ответом для $%f(k,m)$% будет сумма $$C_m^0+2C_m^1+4C_m^2+\cdots+2^kC_m^k.$$ Это легко проверить при помощи индукции, с использованием простейших свойств сочетаний. При $%m\le k$% получается ответ $%3^m$% (известная задача, когда ограничений на количество взвешиваний одной монеты фактически не имеется). В общем случае данная сумма вряд ли "сворачивается". Многочлен от $%m$% уже при $%k=3$% оказывается "некрасивый". отвечен 13 Фев '13 10:11 
falcao |
$%m \in \mathbb{N} \wedge f(1,m) = 1 + 2m \wedge f(2,m) = 1 + 2m^2 \rightarrow f(2,m) = 1 + 2 \cdot \sum_{i = 1}^{m} f(1,i-1)$%