задачкa

[Maus]

услышал задачку дла поступления в Оксфорд. у вас есть 12 монет. одна из них неизвестнои массы.(тоесть или легче или тяжелее). нужно тремя взвешиваниями определить какая из них.

[Maus]

Progressive, так легче или тяжелее?

[Homka]

Предположим, что монета тяжелее. Так-с, насколько я, гуманитарий, понимаю, нуна разделить 12 пополам и в первое взвешивание определить в какой половине находится эта тяжелая монета. Потом разделить шесть монет на кучки из трех и определить какая из этих кучек тяжелее. Ну а третьим взвешиванием выбираем любые две монеты из более тяжелой кучки и сравниваем их вес. Если одна из них тяжелее, то вот она искомая монета, а если их вес одинаков, то эта бракованная монета отложена нами в сторонку. <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) -->
Ну что, дорога в Оксфорд мне открыта? <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) -->

[biLLiBonS]

Progressive,
Делим на три партии: 4, 4 и 4.

Взвешиваем 4 и 4.
1. Одинаково.
Берем три из оставшихся 4-х и взвешиваем с любыми 3-мя из первой партии.
1.1 Одинаково. => та монета, что осталась в последней партии - искомая.
1.2. 3 из оставшихся - легче (тяжелее). Берем 2 из них и взвешиваем. Более легкая (тяжелая) - искомая. Если они одинаковы => оставшаяся 3-я искомая.

2. Отличаются по весу.
Берем 2 монеты из первой партии + 2 из второй и 4 монеты из третьей (в ней все стандартные). Сравниваем (2+2 и 4).
2.1 2+2 легче (тяжелее) чем 4. => искомая монета находится среди двух, взятых из более легкой (тяжелой) партии.

Третьим взвешиванием определяем нужную <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) -->

[Maus]

Homka, я тоже так подумал, но все оказалось сложнее.
biLLiBonS, а если в пункте 2.1 2+2 и 4 одинакового веса?

Progressive, а вот задачка для городской школьной олимпиады:
дано (3^n-1)/2 монет, из которых одна фальшивая. Остальные монеты одинаковы по весу, а фальшивая отличается. Докажите, что фальшивую монету можно найти n взвешиваниями на весах без гирь.

Наш частный случай - это n = 3.

[Homka]

Masterboy, а в чем сложность-то?

А у Билли с его вариантом все в порядке, даже если 2+2 и 4 одинакового веса. <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) -->

[Maus]

ОЛЕНИ! ТА, КОТОРАЯ МЕНЬШЕ! <!-- s:mrgreen: --><img src="{SMILIES_PATH}/icon_mrgreen.gif" alt=":mrgreen:" title="Mr. Green" /><!-- s:mrgreen: -->

[Maus]

Homka, сложность в том, что неизвестно легче или тяжелее фальшивая монета.
А у Билли, если 2+2 и 4 одинакового веса, остается четыре монеты, одна из которых фальшивая, и только одно взвешивание. Одним взвешиванием среди четырех монет фальшивую не найти. Или я что-то упустил?

[Homka]

Masterboy, я думаю, что в задании все-таки указано легче монета или тяжелее. Это просто гражданини Progressive некорректно поставил задачу <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) --> Потому что, если неивестно легче пресловутая монета или тяжелее, то это все какая-то дурь беспросветная.

И у Билли, если исходить из того, что мы знаем легче она или тяжелее - все получается. А вот если не знаем.... То, соответственно, и не получается.
Короче, Progressive, уточненное задание - в студию! Плиззз.

[biLLiBonS]

Masterboy,
[quote:37j7p3i7]biLLiBonS, а если в пункте 2.1 2+2 и 4 одинакового веса?[/quote]
Действительно... упустил.

Похоже монет маловато... Для 13 решение находится, для 12 - нет. Т.е. нужна еще одна стандартная монета. <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) -->
Формула (3^n-1)/2 за n взвешиваний работает <!-- s:( --><img src="{SMILIES_PATH}/icon_sad.gif" alt=":(" title="Sad" /><!-- s:( --> Действительно получается 13.