Фальшивая монета

[Xenia1996]

Имеется $n$ монет, ровно одна из которых - фальшивая.
Настоящие весят по 10 грамм, а фальшивая - 9 грамм.
У нас есть весы, одно плечо которых вдвое длиннее другого.

а) За какое наименьшее число взвешиваний можно определить фальшивую монету при $n=11$?

б) При каком наибольшем $n$ можно за три взыешивания определить фальшивую монету?

[Руст]

a)3
b) 20.

[Xenia1996]

Руст в сообщении #437131 писал(а):

a)3
b) 20.

а) верно
б) не-а!

Вам написать контрпример с 21 или дать время подумать?

-- Ср апр 20, 2011 21:17:44 --

Кому не терпится, тыкайте сюды

[w0robey]

Я уже хотел распрягать, почему нельзя найти в 22 монетах фальшивую (типа по принципу Дирихле и пару рассуждений в одной из кучек будет не менее 10 монет, бла-бла-бла)... но взглянул на контрпример, ничего не понял, может быть нарисуете худший случай...

[Xenia1996]

w0robey в сообщении #437156 писал(а):

Я уже хотел распрягать, почему нельзя найти в 22 монетах фальшивую (типа по принципу Дирихле и пару рассуждений в одной из кучек будет не менее 10 монет, бла-бла-бла)... но взглянул на контрпример, ничего не понял, может быть нарисуете худший случай...

(Оффтоп)

Я шо Вам, рисовалка механическая?

Кладём на длинное плечо 4 монеты, на короткое - 8.
Худший вариант - равновесие. Тогда бяка будет среди 9 оставшихся.
Разбиваем эти 9 на 3 тройки: абв, где, ёжз.
Кладём на длинное плечо абв, а на короткое - ёжз и ещё 3 настоящих монеты.
При любом из трёх возможных исходов имеем 3 монеты, из которых одна - бяка. Предроложим, это абв.
Кладём на длинное плечо б, а на короткое - в и ещё 1 настоящую монету.
При любом из трёх возможных исходов имеем 1 монету, из которых одна - бяка.