Имеется $%n$% одинаковых на вид монет. Известно, что одна из них фальшивая, легче остальных настоящих. Надо, используя чашечные весы без гирь, найти фальшивую монету за $%m$% взвешиваний, при чем каждую монету можно взвешивать не более $%k$% раз.
При каких тройках $%{n,m,k}$% данная задача является решаемой? (выразить в виде $%n \leq f(k,m)$%)
Данный вопрос является обобщением вопроса "Задача на взвешивания".
Уже найдено: $%f(0,m)=1;f(1,m)=2m+1; f(2,m)=2m^2+1$% (см. решение исходного вопроса).

задан 2 Окт '12 2:55

$%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)$%

(2 Окт '12 16:54) Галактион
10|600 символов нужно символов осталось
2

У меня рекуррентная формула получилась такая: $$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

10|600 символов нужно символов осталось
0

Рекурсивная формула: $%f(0,m)=1;f(k,m)=1+2\sum_{i=1}^m f(k-1,i-1)$%. Выведена при помощи "здравого смысла" (см. задачу). Может, кто-то поможет доказать ее правильность формально и выразить $%f(k,m)$% без рекурсии?

ссылка

отвечен 2 Окт '12 17:16

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×349
×32
×20

задан
2 Окт '12 2:55

показан
1022 раза

обновлен
13 Фев '13 10:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru