[Perm]

Для 13 монет определяется фальшивая
Правда, на матбое около 2000 года, задача звучала так:
господину судье, который знает что 1 из 13 фальшивая
адвокат доказывает за 3 взешивания, что именно эта,
решил ее парень из Чел, международник,
если из 13 монет если неважно, кто кого тяжелее? то
1 === 000
2 >== или <== 200
3 =>= или =<= 020
4 ==> или ==< 002
5 >>= или <<= 110
6 >=> или <=< 101
7 =>> или =<< 011
8 <>= или ><= 120
9 <=> или >=< 201
10 =<> или =>< 012
11 ><< или <>> 122
12 <>< или ><> 212
13 <<> или >>< 221
не влезает 14-я, эталон нужен
14 >>> или <<< ???
0-отдыхает, 1-на первой чашке, 2-на второй

[Odissey]

На самом деле крайне интересно.
Ощущение, что решение задачи для 13 эквивалентно доказательству, что P=NP.
3 взвешивания дают 27 бит информации. значит бит должно хватать для 13 монет.
однако, съезжая на уровень вниз - 9 бит не хватает для 4-х монет.
чудовищно.
есть 9 вариантов двух взвешиваний
==
=>
=<
>=
><
>>
<=
<<
<>
но поставить в соответствие каждому варианту событий вариант распределения - не получается.
съехать еще на уровень вниз не получается, потому что за одно взвешивание вообще ничего нельзя определить.

--------------------

чем больше я узнаю людей - тем чаще сомневаюсь в правильном выборе второго слова в термине "homo sapiens"

[Odissey]

вообще смутное ощущение такое, что формула должна выглядеть:
м-колво монет
н-колво взвешиваний
2*м + 1 < н^3 - 1

--------------------

чем больше я узнаю людей - тем чаще сомневаюсь в правильном выборе второго слова в термине "homo sapiens"

[Odissey]

однако, куда теряются 3 бита информации - непонятно
для любого "н" - ровно 3 бита информации.

Это сообщение отредактировал Odissey - 11/11/2006, 01:33

--------------------

чем больше я узнаю людей - тем чаще сомневаюсь в правильном выборе второго слова в термине "homo sapiens"

[Pyotr]

Известно две постановки задачи о монетах: 1. Просто определить фальшивую монету. 2. Определить фальшивую монету и тип ее дефекта (легче, или тяжелее она настоящей). Задача в постановке 2 решена в общем виде, описание решения можно найти здесь: http://ega-math.narod.ru/Quant/Shestpl.htm
Для случая 12 монет и трех взвешиваний, опять же в постановке 2, задача обсуждалась здесь
http://www.energy.org.ru/modules.php?name=...viewtopic&t=493
Там же обсуждается вопрос о том, куда деваются три бита информации.
Что касается обсуждаемой на этом форуме задачи в постановке 1, она представляется более сложной и менее академичной по сравнению с задачей в постановке 2.

[Odissey]

Петр.

Ознакомился.
В вашем варианте решения два бита уходят на невозможную смену показаний.
Но я не зря упомянул про P=NP.
Напомню, что в общем виде проблема (за которую кстати тоже назначен лимон баксов, как был назначен за теорему Ферма, например) звучит так:
"Сущетсвуют ли какие-либо задачи, для которых проверка правильности решения займет больше времени, чем само решение, НЕЗАВИСИМО от алгоритма проверки."
применив его к задаче о 12 монетах (котороя кстати решается несколькими способами), можно сформулировать вопрос так:
"Существует ли алгоритм нахождения фальшивой монеты и определения ее типа, при котором 2 бита информации не будут потеряны"?

--------------------

чем больше я узнаю людей - тем чаще сомневаюсь в правильном выборе второго слова в термине "homo sapiens"

[Odissey]

Ух. еще раз переформулировал.
потеря одного тривиального бита информации на самом деле не потеря.
все равновесия при трех взвешиваниях фактически показывают отсутствие фальшивой монеты.
то есть: 3 взвешивания с тремя исходами, 27 вариантов:
13 монет, легче/тяжелее - 26 исходов
фальшивой монеты нет - 1 исход.

"Докажите, что не существует алгоритма нахождения фальшивой монеты, определения типа изъяна, или доказательства, что фальшивой монеты нет для 13 монет и трех взвешиваний."

--------------------

чем больше я узнаю людей - тем чаще сомневаюсь в правильном выборе второго слова в термине "homo sapiens"