задачка (математическое)
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 монет.
Комментарии скрывать не буду - учтите, если сами хотите решить. Сам я ответил еще пока не на все из этих вопросов :)
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-03-08 03:14 pm (UTC)Хммм. При такой постановке вопроса и чётном количестве монет - одно.
no subject
Date: 2009-03-08 03:18 pm (UTC)no subject
Date: 2009-03-08 03:21 pm (UTC)no subject
Date: 2009-03-08 03:15 pm (UTC)То, что 2 монеты одного веса, можно установить за одно взвешивание.
По индукции получаем, что за k взвешиваний можно проверить 2k монет.
(Если монет не ровно 2k, то при последнем взвешивании на весы надо класть все ещё не проверенные монеты и такое же количество уже проверенных.)
no subject
Date: 2009-03-08 03:19 pm (UTC)no subject
Date: 2009-03-08 04:13 pm (UTC)Для 2 достаточно одного взвешивания. Дальше понятно.
no subject
Date: 2009-03-08 04:50 pm (UTC)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.
no subject
Date: 2009-03-08 04:57 pm (UTC)012=345
0123=6789
01245=36789
быстрая проверка
Date: 2009-03-08 05:56 pm (UTC)Из второго условия следует 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.
Re: быстрая проверка
Date: 2009-03-08 06:29 pm (UTC)Re: быстрая проверка
Date: 2009-03-08 06:44 pm (UTC)no subject
Date: 2009-03-08 06:44 pm (UTC)no subject
Date: 2009-03-10 04:32 pm (UTC)no subject
Date: 2009-03-10 04:34 pm (UTC)no subject
Date: 2009-03-10 05:16 pm (UTC)верхняя оценка (part 1)
Date: 2009-03-17 10:53 am (UTC)Пусть имеется 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). Она имеет как нулевое, так и единичное решение.
ПРОДОЛЖЕНИЕ СЛЕДУЕТ; ПРОСЬБА ОТВЕЧАТЬ НИЖЕ!
верхняя оценка (part 2)
Date: 2009-03-17 11:01 am (UTC)На пространстве 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. Прошу прощения за то, что пришлось несколько раз удалять и помещать один и тот же коммент ввиду неполадок с "тегами".
Re: верхняя оценка (part 2)
Date: 2009-03-17 11:50 am (UTC)Re: верхняя оценка (part 2)
Date: 2009-03-17 03:09 pm (UTC)Re: верхняя оценка (part 2)
Date: 2009-03-27 05:30 pm (UTC)Re: верхняя оценка (part 2)
Date: 2009-03-27 05:39 pm (UTC)Re: верхняя оценка (part 2)
Date: 2009-03-27 05:43 pm (UTC)Re: верхняя оценка (part 2)
Date: 2009-03-27 11:18 pm (UTC)Задача 3. Фальшивомонетчик-скрлеротик Абу изготовлял фальшивые копейки образца 1961 года. Отнощение веса фальшивой монеты к весу настоящей выдерживалось строго и было в точности \pi/3 (трансцендентное число). Фальшивые и настоящие копейки валялись вперемешку в одном ведре, Абу не помнил, какая монета фальшивая, а какая - нет. Однажды он взял из ведра горсть монет, и задумал, в виде развлечения, проверить с помощью чашечных весов, все ли эти монеты одного типа (все настоящие или все фальшивые). Абу хочет использовать лишь три взвешивания. За каждое взвешивание, он кладет на обе чашки весов одинаковое число монет из горсти, и проверяет, уравниваются ли чашки. Он хочет проверить, все ли монеты в горсти одинакового веса. Доказать, что
а) Существует стратегия проверки, если в горсти n = 8 или 9 монет.
б) Доказать, что существует число n, для которого искомой стратегии не существует.
в) Оценить n из б).
Re: верхняя оценка (part 2)
Date: 2009-03-27 11:29 pm (UTC)Re: верхняя оценка (part 2)
Date: 2009-03-28 12:13 am (UTC)-----------
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)
Date: 2009-03-28 12:30 am (UTC)old navy coupons free shipping
Date: 2011-08-13 02:34 am (UTC)