задачка (математическое)
Mar. 8th, 2009 03:41 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaДавно у меня не было интересных задач!
У вас есть N монет, и вес каждой монеты равен либо X, либо Y (два заранее фиксированных числа). У вас есть весы с двумя чашами, позволяющие за одно взвешивание сравнить - но не измерить - вес любого количества монет на левой и правой чашах. Вы хотите узнать: верно ли, что все монеты одного веса? Сколько взвешиваний вам надо в худшем случае, чтобы это определить?
Можно перевернуть вопрос и задать его так: если в вашем распоряжении есть k взвешиваний, какое количество монет вы сможете гарантированно проверить (т.е. узнать, все ли они одного веса)?
1) Найдите алгоритм, позволяющий для любого k проверить за k взвешиваний 2^k монет.
2) Докажите, что есть верхний предел для числа монет N, которые можно проверить с помощью данного числа k взвешиваний (это кажется тривиальным, но только кажется).
3) Найдите алгоритм, позволяющий с помощью 3 взвешиваний проверить больше, чем 8=2^3 монет.
Комментарии скрывать не буду - учтите, если сами хотите решить. Сам я ответил еще пока не на все из этих вопросов :)
У вас есть N монет, и вес каждой монеты равен либо X, либо Y (два заранее фиксированных числа). У вас есть весы с двумя чашами, позволяющие за одно взвешивание сравнить - но не измерить - вес любого количества монет на левой и правой чашах. Вы хотите узнать: верно ли, что все монеты одного веса? Сколько взвешиваний вам надо в худшем случае, чтобы это определить?
Можно перевернуть вопрос и задать его так: если в вашем распоряжении есть k взвешиваний, какое количество монет вы сможете гарантированно проверить (т.е. узнать, все ли они одного веса)?
1) Найдите алгоритм, позволяющий для любого k проверить за k взвешиваний 2^k монет.
2) Докажите, что есть верхний предел для числа монет N, которые можно проверить с помощью данного числа k взвешиваний (это кажется тривиальным, но только кажется).
3) Найдите алгоритм, позволяющий с помощью 3 взвешиваний проверить больше, чем 8=2^3 монет.
Комментарии скрывать не буду - учтите, если сами хотите решить. Сам я ответил еще пока не на все из этих вопросов :)
