Anatoly Vorobey (avva) wrote,
Anatoly Vorobey
avva

задачка (математическое)

Давно у меня не было интересных задач!

У вас есть N монет, и вес каждой монеты равен либо X, либо Y (два заранее фиксированных числа). У вас есть весы с двумя чашами, позволяющие за одно взвешивание сравнить - но не измерить - вес любого количества монет на левой и правой чашах. Вы хотите узнать: верно ли, что все монеты одного веса? Сколько взвешиваний вам надо в худшем случае, чтобы это определить?

Можно перевернуть вопрос и задать его так: если в вашем распоряжении есть k взвешиваний, какое количество монет вы сможете гарантированно проверить (т.е. узнать, все ли они одного веса)?

1) Найдите алгоритм, позволяющий для любого k проверить за k взвешиваний 2^k монет.

2) Докажите, что есть верхний предел для числа монет N, которые можно проверить с помощью данного числа k взвешиваний (это кажется тривиальным, но только кажется).

3) Найдите алгоритм, позволяющий с помощью 3 взвешиваний проверить больше, чем 8=2^3 монет.

Комментарии скрывать не буду - учтите, если сами хотите решить. Сам я ответил еще пока не на все из этих вопросов :)
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 26 comments