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

[avva]

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

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

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

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

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

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

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

Comments

Re: верхняя оценка (part 2)

[markvs.livejournal.com]

Here is Alon's answer:

-----------
I have a few papers on that and some versions, see (in my webpage):

N. Alon and V. H. Vu, Anti-Hadamard matrices, coin weighing,
threshold gates and indecomposable hypergraphs, J. Combinatorial
Theory, Ser. A 79 (1997), 133-160.

N. Alon, D. N. Kozlov and V. H. Vu, The geometry of coin-weighing
problems, Proc. $37^{th}$ IEEE FOCS, IEEE (1996), 524-532.

N. Alon and D. N. Kozlov, Coins with arbitrary weights, J.
Algorithms 25 (1997), 162-176.
---------
I then asked about the explicit upper bound and here is what he wrote:

We get that n(k) is at most some k^{k/2+o(1)} and that's tight (up to
the o(1) term). There are several proofs that give finiteness. Maybe easiest to look at the FOCS paper. Of course you can send the problem
to any student Olympiad. n(3), by the way, is 10, if I remember correctly
(but getting the tight upper bound here was done with the help of a computer, and is not mentioned in the papers).

Re: верхняя оценка (part 2)

[avva.livejournal.com]

Спасибо!