задачка (математическое)
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}
верхняя оценка (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)