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

[avva]

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

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

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

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

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

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

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

Comments

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

[avva.livejournal.com]

Очень красиво :) большое спасибо!

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

[markvs.livejournal.com]

Я думаю, что задача может сводиться к reachability problem для сетей Петри или к разрешимости универсальной теории коммутативных полугрупп. Это может дать супер-експ. нижнюю оценку на f(k).

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

[markvs.livejournal.com]

Анатолий, я хочу послать Вашу задачу (при к = 3) и наше с falcao решение на студенческую олимпиаду в Уральском Гос. Униветрситете (Екатеринбург). Там будет указано, что задача придумана А. Воробьем и Ваше affiliation (Google-Israel?). Вы не против? Меня попросили люди из УрГУ прислать им задачи.

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

[avva.livejournal.com]

Я совершенно не против, но не указывайте меня, пожалуйста - я в данном случае не более чем посредник. Задача попала ко мне от Ноги Алона (Noga Alon, affiliation - Tel-Aviv University). Я не знаю, он ли ее придумал; если это важно, можно у него спросить.

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

[markvs.livejournal.com]

Спасибо! Здорово (насчет Алона)! Я сейчас спрошу у него.

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

[markvs.livejournal.com]

Alon answered. There are three papers on his Web site devoted to the subject. By the way, here is the problem as it was sent to the student olympiad:

Задача 3. Фальшивомонетчик-скрлеротик Абу изготовлял фальшивые копейки образца 1961 года. Отнощение веса фальшивой монеты к весу настоящей выдерживалось строго и было в точности \pi/3 (трансцендентное число). Фальшивые и настоящие копейки валялись вперемешку в одном ведре, Абу не помнил, какая монета фальшивая, а какая - нет. Однажды он взял из ведра горсть монет, и задумал, в виде развлечения, проверить с помощью чашечных весов, все ли эти монеты одного типа (все настоящие или все фальшивые). Абу хочет использовать лишь три взвешивания. За каждое взвешивание, он кладет на обе чашки весов одинаковое число монет из горсти, и проверяет, уравниваются ли чашки. Он хочет проверить, все ли монеты в горсти одинакового веса. Доказать, что

а) Существует стратегия проверки, если в горсти n = 8 или 9 монет.

б) Доказать, что существует число n, для которого искомой стратегии не существует.

в) Оценить n из б).

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

[avva.livejournal.com]

Замечательно! Не дадите ссылки на эти статьи, если они уже у вас под рукой?

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]

Спасибо!