?

Log in

No account? Create an account
задачка (математическое) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

задачка (математическое) [мар. 8, 2009|03:41 pm]
Anatoly Vorobey
Давно у меня не было интересных задач!

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

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

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

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

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

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

Comments:
[User Picture]From: gera
2009-03-08 03:14 pm
Вы хотите узнать: верно ли, что все монеты одного веса? Сколько взвешиваний вам надо в худшем случае, чтобы это определить?

Хммм. При такой постановке вопроса и чётном количестве монет - одно.
(Ответить) (Thread)
[User Picture]From: avva
2009-03-08 03:18 pm
это как?
(Ответить) (Parent) (Thread)
[User Picture]From: gera
2009-03-08 03:21 pm
Ага, только сейчас обратил внимание, что количество разных монет - произвольное :) Почему-то заклинило на известном варианте с одной фальшивой монетой.
(Ответить) (Parent) (Thread)
[User Picture]From: p_govorun
2009-03-08 03:15 pm
1. Допустим, что у нас есть 2k-1 монет заведомо одного веса. Тогда чтобы проверить ещё столько же монет, достаточно сравнить их суммарный вес с весом уже имеющихся. После этого получаем 2k проверенных монет.

То, что 2 монеты одного веса, можно установить за одно взвешивание.

По индукции получаем, что за k взвешиваний можно проверить 2k монет.

(Если монет не ровно 2k, то при последнем взвешивании на весы надо класть все ещё не проверенные монеты и такое же количество уже проверенных.)
(Ответить) (Thread)
[User Picture]From: avva
2009-03-08 03:19 pm
Ага, это верно. 1:2, 12:34, 1234:5678 и так далее.
(Ответить) (Parent) (Thread)
[User Picture]From: kouzdra
2009-03-08 04:13 pm
С первым-то понятно - если у нас есть способ проверить n монет за k(n) взвешиваний, то есть способ проверить n*m монет за k(n)+k(m) взвешиваний - cначала выяснив равновесность m кучек по n монет, а потом проверив одну кучку.

Для 2 достаточно одного взвешивания. Дальше понятно.
(Ответить) (Thread)
From: renatm
2009-03-08 04:50 pm
По третьему пункту: можно за 3 взвешивания проверить 9 монет.

123=456
124=789
1256=4789

Доказательство:

Будем обозначать группы одинаковых монет последовательностью цифр, т.е. 123 и 5678 означает, что монеты 1, 2 и 3 имеют один вес, а монеты 5, 6, 7, 8 - другой.

Если все монеты в первом равенстве одинаковые (123456), то из второго равенства следует 123456789.

Если в первом равенстве одинаковые 14 и одинаковые 2356. Из третьего равенства следует 2356789. Тогда во втором получаем противоречие.

Если в первом 15 и 2346. Тогда из второго равенства следует, что среди монет 789 одна такая же, как 15, а две как 2346. Из третьего следует, что две такие же, как 15, а одна как 2346. Противоречие

Если в первом 16 и 2345. Аналогично в силу симметрии 5 и 6.

Случаи 24, 25 и 26 доказываются аналогично в силу симметрии 1 и 2.

Если в первом 34 и 1256. В третьем противоречие.

Если в первом 35 и 1246. Из второго 1246789. В третьем противоречие.

Аналогично 36 и 1245.
(Ответить) (Thread)
From: renatm
2009-03-08 04:57 pm
Можно и 10 за 3 взвешивания (нумерация монет с 0):
012=345
0123=6789
01245=36789
(Ответить) (Parent) (Thread)
[User Picture]From: falcao
2009-03-08 05:56 pm

быстрая проверка

Корректность предложенной Вами схемы можно проверить быстро, без перебора случаев.

Из второго условия следует 01233=36789 (добавили к обеим частям мысленную копию монетки, по весу равной 3), а это равно 01245 согласно третьему условию. Сокращение на 012 даёт 33=45, то есть 4 и 5 весят столько же, сколько 3. Первое условие переписывается в виде 012=333, поэтому 0=1=2=3. А тогда во втором условии 3333=6789, то есть все веса равны.

Получается довольно забавное исчисление -- коммутативная полугруппа с сокращением, и дополнительными условиями вида "a_1...a_n=a^n влечёт a_1=...=a_n=a". Отсюда, видимо, можно извлечь оценку для задачи из пункта 2.
(Ответить) (Parent) (Thread)
From: renatm
2009-03-08 06:29 pm

Re: быстрая проверка

Да, так гораздо проще. Я вообще находил перебором с помощью программы.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2009-03-08 06:44 pm

Re: быстрая проверка

Замечательное наблюдение!
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2009-03-08 06:44 pm
Браво! :)
(Ответить) (Parent) (Thread)
From: anonymous8216
2009-03-10 04:32 pm
Так как там с верхним пределом, нашелся?
(Ответить) (Thread)
[User Picture]From: avva
2009-03-10 04:34 pm
я пока не знаю.
(Ответить) (Parent) (Thread)
From: anonymous8216
2009-03-10 05:16 pm
Я уж совсем было собрался вытаскивать его из условий, которые привел falcao. Вознамерился оценить сверху их количество и степень. Но тут внезапно оказалось, что условия бывают не только такие. Например, $a^2b^4=c^3d^3⇒a=b=c=d$.
(Ответить) (Parent) (Thread)
[User Picture]From: falcao
2009-03-17 10:53 am

верхняя оценка (part 1)

Мы с markvs начали обсуждать Вашу задачу, и получили оценку сверху. А именно, существует такая функция f, что при N>=f(k) проверка в общем случае невозможна.

Пусть имеется n монет. Введём переменные a(i) при i=1,...,n, полагая a(i)=0, если монета имеет вес X, и a(i)=1, если вес равен Y. (Если на самом деле X=Y, то все значения a(i) будем считать равными чему-то одному.)

Каждому взвешиванию сопоставим уравнение вида

a(i)+...+a(j)=a(s)+...+a(t),

в соответствии с тем, какие монеты лежат на левой и на правой чаше весов. Число слагаемых в каждой части полагаем одинаковым для каждого уравнения; одна и та же переменная не входит сразу в обе части никакого из уравнений.

Для серии из k взвешиваний имеем систему из k уравнений.

Решениями системы считаем упорядоченные наборы нулей и единиц длиной n. Решение назовём тривиальным, если это набор из одних нулей или из одних единиц.

Будем рассматривать системы из k уравнений описанного вида. Если для данного n удалось построить систему, имеющую только тривиальные решения, то серия взвешиваний будет удачной, и наоборот. То есть задача нахождения оценки состоит в том, что при n>=f(k), любая система описанного вида будет иметь хотя бы одно нетривиальное решение.

Итак, пусть дана система для параметров n и k. Каждую переменную отнесём к одному из типов. Для начала -- на примере. Пусть система имеет вид

a=b
ab=cd

Тогда a имеет тип LL, b имеет тип RL, с -- тип 0R, и d --тоже тип 0R.

Общее правило таково: переменной a(i) сопоставляем последовательность из k символов 0, L, R. На j-м месте пишем 0, если в j-м уравнении эта переменная отсутствует; L -- если она входит в левую часть, и R -- если в правую.

Всего имеется ровно 3^k типов переменных, и "нулевой" тип соответствует переменной, которая ни в одно уравнение не входит. Если такая переменная есть, то система имеет нетривиальные решения, и далее можно поэтому считать, что типов переменных имеется строго меньше 3^k.

Далее однотипные переменные в каждом уравнении сгруппируем в одно слагаемое и обозначим через z(T), где T есть соответствующий тип переменной. В нашем примере выше это будет вот что:

z(L,L)=z(R,L)
z(L,L)+z(R,L)=z(0,R)

Если переменных типа T нет, то полагаем Z(T)=0.

Важно отметить, что для каждого k имеется одна универсальная система уравнений. Например, для k=2 это есть

z(L,L)+z(L,R)+z(L,0)=z(R,L)+z(R,R)+z(R,0)
z(L,L)+z(R,L)+z(0,L)=z(L,R)+z(R,R)+z(0,R)

Переменная z(0,0) в запись системы не входит.

Легко понять, как должна выглядеть такая универсальная система для любого значения k. Переменных будет 3^k-1, а в каждой из частей каждого из k уравнений будет в точности по 3^{k-1} слагаемых. Например, левая (правая) часть i-го уравнения есть сумма всех z(T), где у вектора T на i-м месте стоит L (R).

Будем обозначать описанную однородную систему линейных уравнений через U(k). Она имеет как нулевое, так и единичное решение.

ПРОДОЛЖЕНИЕ СЛЕДУЕТ; ПРОСЬБА ОТВЕЧАТЬ НИЖЕ!
(Ответить) (Thread)
[User Picture]From: falcao
2009-03-17 11:01 am

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

ПРОДОЛЖЕНИЕ

На пространстве R^m зададим частичное отношение порядка, где u<=v означает, что для всех i от 1 до m,
i-я координата вектора u не превосходит i-й координаты вектора v. Если u<=v, и при этом u не равно v, то полагаем u < v.

Ненулевое решение системы U(k) назовём минимальным, если не существует меньшего ненулевого решения этой системы (в целых неотрицательных числах). Например, при k=2 решение z(L,L)=z(R,R)=1 при нулевых значениях остальных переменных, будет минимальным. Другой пример: z(L,L)=z(R,0)=z(0,R)=1 при нулевых значениях остальных переменных. Минимальное решение не обязано состоять из нулей и единиц: достаточно рассмотреть пример z(L,L)=1, z(R,L)=1, z(0,R)=2.

Утверждается, что минимальных решений системы U(k) имеется конечное число. Это следует из такой леммы: если имеется бесконечное множество S векторов в Z_+^m, то среди них найдутся два вектора u, v такие, что u < v.

Это доказывается при помощи индукции по m. Если m=1, то всё очевидно. Если m>1, то рассмотрим какой-то вектор из множества S. Пусть это u=(u_1,...,u_m). Если условие u < v не выполнено ни при каком v=(v_1,...,v_m), то найдётся i такое, что v_i<=u_i. Тогда хотя бы для одного i подмножество в S, состоящее из всех v таких, что v_i<=u_i, будет бесконечным. При этом v_i принимает одно из значений конечного списка 0, 1, ..., u_i. Следовательно, при некотором b из этого списка, подмножество всех v из S с условием v_i=b, бесконечно. Осталось спроектировать это подмножество на Z_+^{m-1} и применить к нему предположение индукции.

Теперь поступаем так: берём множество всех минимальных решений системы U(k) и находим сумму компонент каждого решения. Пусть f(k) есть натуральное число, превосходящее каждую из сумм. Тогда f есть искомая функция; проверим это.

Если n>=f(k), то всякая система из k уравнений от x(1), ..., x(n), соответствующая взвешиваниям, обязана иметь нетривиальное решение. В самом деле, если для каждого типа T обозначить через r(T) число неизвестных типа T в данной системе, то (3^{k}-1)-мерный вектор, состоящий из компонент r(T), будет решением системы U(k). Оно соответствует единичному решению системы от x(1), ..., x(n). При этом сумма компонент решения равна n>=f(k), и это больше, чем сумма компонент любого минимального решения. Поэтому решение, состоящее из значений z(T)=r(T) не будет минимальным. Это означает, что существует ненулевое решение системы U(k) из компонент p(T) такое, что p(T)<=r(T) для всех T, и хотя бы одно из этих неравенств является строгим.

Из этого очевидным образом строится нетривиальное решение рассмотренной нами системы от n переменных. А именно, надо взять все r(T) переменных типа T, и ровно p(T) из них положить равными 1, а остальные сделать нулевыми.

Нахождение явного вида функции f(k) связано с анализом всех минимальных решений системы U(k). Для их нахождения, скорее всего, можно как-то применить симплекс-метод. Интересно было бы в явном виде найти хотя бы значение f(3) с использованием компьютерных вычислений.

P.S. Прошу прощения за то, что пришлось несколько раз удалять и помещать один и тот же коммент ввиду неполадок с "тегами".
(Ответить) (Thread)
[User Picture]From: avva
2009-03-17 11:50 am

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

Очень красиво :) большое спасибо!
(Ответить) (Parent) (Thread)
From: markvs
2009-03-17 03:09 pm

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

Я думаю, что задача может сводиться к reachability problem для сетей Петри или к разрешимости универсальной теории коммутативных полугрупп. Это может дать супер-експ. нижнюю оценку на f(k).
(Ответить) (Parent) (Thread)
From: markvs
2009-03-27 05:30 pm

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

Анатолий, я хочу послать Вашу задачу (при к = 3) и наше с falcao решение на студенческую олимпиаду в Уральском Гос. Униветрситете (Екатеринбург). Там будет указано, что задача придумана А. Воробьем и Ваше affiliation (Google-Israel?). Вы не против? Меня попросили люди из УрГУ прислать им задачи.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2009-03-27 05:39 pm

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

Я совершенно не против, но не указывайте меня, пожалуйста - я в данном случае не более чем посредник. Задача попала ко мне от Ноги Алона (Noga Alon, affiliation - Tel-Aviv University). Я не знаю, он ли ее придумал; если это важно, можно у него спросить.
(Ответить) (Parent) (Thread)
From: markvs
2009-03-27 05:43 pm

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

Спасибо! Здорово (насчет Алона)! Я сейчас спрошу у него.
(Ответить) (Parent) (Thread)
From: markvs
2009-03-27 11:18 pm

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

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 из б).


(Ответить) (Parent) (Thread)
[User Picture]From: avva
2009-03-27 11:29 pm

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

Замечательно! Не дадите ссылки на эти статьи, если они уже у вас под рукой?
(Ответить) (Parent) (Thread)
From: markvs
2009-03-28 12:13 am

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

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).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2009-03-28 12:30 am

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

Спасибо!
(Ответить) (Parent) (Thread)