12 шариков (самая лучшая задачка)

[buka]

слишком легкая..  а 9 шарика с 2 взвешиванем, берем по 3 и т.д.

Это в случае, когда известно, что фальшивый шар легче (или тяжелее). А если неизвестно?

[Smith]

Так что, никто не берётся?
Задача не такая уж сверхсложная...

От любви к туманной поэтике,
До любви к бытовой математике,
Если были мы теоретики,
То теперь безусловно практики.
Было дело, и я в это кинулся,
А только видно стал староват,
Еще вчера я любил Калининский,
А теперь выбираю Арбат... (с) А. Макаревич

[buka]

Вы меня расстроили, Смит

[Тиана]

А теперь - общий случай
Из скольких монет можно определить фальшивую за К взвешиваний?

больно не бейте 
Показать скрытый текст

1 взвешивание 2/3 монет А и В+Н (Н – настоящая), если неравенство, то фальшивка либо среди А монет (т или л), либо среди В монет (т или л)
3^k-1 < A+B <=3^k
Если при 1м взвешивание равенство, то фальшивка среди оставшихся С монет (С=Д+Е)
2м взвешиванием будет Д и Е+Н. Фальшивка будет среди Д монет (т или л) или среди Е монет (т или л)
3^k-1 < Д+Е <=3^k

[buka]

У Вас хорошая интуиция, Тиана. Очень хорошая.
Вы дали неплохую оценку границ.
Если хотите, могу подсказать подход для определения точной зависимости и даже стратегии.

[Тиана]

подскажите, может что-то и получится

[buka]

1. Сначала докажите, что за К взвешиваний можно определить 1 фальшивый шар из 3К шаров, если известно заранее, что он легче/тяжелее остальных. Это просто.
2. Затем надо доказать, что за К взвешиваний можно определить фальшивый шар, если он находится среди Т шаров и более тяжёлый или среди Л шаров - и более лёгкий, если Л+Т = 3К.
Это доказать сложнее, но я на Вас надеюсь
3. Пользуясь второй леммой можно получить выражение для нашего случая. Подумайте как это сделать.
Удачи!
Кстати, задача - определить 1 фальшивый шар из 12 и определить легче он или тяжелее - по-моему, сложнее... По крайней мере в общем виде я не знаю пока решения...

[Тиана]

1. Сначала докажите, что за К взвешиваний можно определить 1 фальшивый шар из 3К шаров, если известно заранее, что он легче/тяжелее остальных. Это просто.

если К=1, то шаров у нас тоже 3
если К=2, то шаров у нас 6
кажись тут что-то не так

[buka]

1. Сначала докажите, что за К взвешиваний можно определить 1 фальшивый шар из 3К шаров, если известно заранее, что он легче/тяжелее остальных. Это просто.

если К=1, то шаров у нас тоже 3
если К=2, то шаров у нас 6
кажись тут что-то не так

Вы правы, не 3К, а 3^К
Я просто забыл вставить тэги
Извините. везде, где 3К д/б 3^К

[Тиана]

попытка номер раз

Показать скрытый текст

1. С каждым взвешиванием необходимо уменьшать число возможных фальшивых шаров в 3 раза. Для 1го взвешивания берем 2/3 шаров, возможны три варианта: больше/меньше/равно. Если получим неравенство, то фальшивка в одной из кучек на весах, если же равенство – в кучке, которая осталась в стороне. В любом случае нужно будет исследовать только 1/3 шаров

[almas_a]

Немного подумав, я пришел к следующему выводу:
Самый простой способ решения данной задачи - это результат первого взвешивания, т.е.  вероятность 50 на 50 того, что вы на чашу весов положите по 5 шаров при первом взвешивании и чтобы были равны по весу. При таком раскладе задача решается в три взвешивания
Пометим шары номерами 01 02 03 04 05 06 07 08 09 10 11 и 12 (пусть 11 или 12 он будет легким или тяжелым)
Первое взвешивание: возьмем шары 01 02 03 04 05 и 06 07 08 09 10  выложим на весы
Если они равны, тогда
- выкидываем вторую группу 06 07 08 09 10 и оставляем 01 02 03 04 05

Второе взвешивание:
- кладем на одну чашу весов 01 02 03 и 04 05 + 11 шар
Если они равны, тогда
- выкидываем вторую группу 04 05 11 и оставляем 01 02 03
- следовательно мы знаем, что 01 02 03 они одинаковые по весу и имеем наш 12 шар
- переходим к пункту Третье взвешивание.

Если не равны, тогда
- выкидываем первую группу 01 02 03 и оставляем 04 05 11
- следовательно 11 шар является искомым шаром
- чтобы проверить и доказать, что 11 шар является искомым, взвешиваем любой кроме 11 шара с 12 шаром, они должны быть равны.

Третье взвешивание:
- кладем на одну чашу весов 01 02 и 03 + 12 шар
в любом случае перевесит или недовесит этот 12 шар он будет у нас искомым шаром.

[buka]

попытка номер раз
Показать скрытый текст

1. С каждым взвешиванием необходимо уменьшать число возможных фальшивых шаров в 3 раза. Для 1го взвешивания берем 2/3 шаров, возможны три варианта: больше/меньше/равно. Если получим неравенство, то фальшивка в одной из кучек на весах, если же равенство – в кучке, которая осталась в стороне. В любом случае нужно будет исследовать только 1/3 шаров

Правильно.
Показать скрытый текст

Вы доказали, что если у нас есть 3^К шаров из которых один фальшивый и известно что он легче/тяжелее настоящих, то каждое взвешивание позволяет уменьшать кол-во кандидатов в 3 раза.
Отсюда и получается зависимость К -> 3^К
Остаётся Вам доказать, что если у нас есть Л+Т = 3^К шаров и известно, что 1 фальшивый либо среди Л  шаров и он легче, либо среди Т шаров и он тяжелее, то мы тоже сможем одним взвешиванием уменьшить кол-во кандидатов в 3 раза.
А затем связать это с нашей основной задачей

Удачи!

[Smith]

Вы меня расстроили, Смит

бросьте, buka, это сиюминутное и настроенческое с моей стороны, что, право, не заслуживает даже пристального внимания с Вашей стороны, не говоря уже об эмоциональной стороне вопроса
впрочем, должен признать, что мне всегда были ближе приземленные, если хотите - "на пальцах", расчеты в решениях многих мат/задач. 
даже тогда, когда требовалось найти или обосновать нечто в системе "n" и "k" я пытался перевести всё в вещественные корни, решить задачу и вернуть в "энно-катое" состояние, не говоря уже об обратных представлениях. отсюда "туманная поэтика" и "бытовая математика".
вероятно сказывается отсутствие академического мат/образования, либо это естественно-персонифицированная поведенческая реакция - мне трудно судить.
но это ни коим образом не отражается на моем интересе к решению и "энно-катому" представлению доказательств решения мат/задач, так что в этом смысле можете ничтоже сумняшеся "иметь меня ввиду"!

[Smith]

2Tiana: респект и уважуха

[Тиана]

2. Затем надо доказать, что за К взвешиваний можно определить фальшивый шар, если он находится среди Т шаров и более тяжёлый или среди Л шаров - и более лёгкий, если Л+Т = 3К.
Это доказать сложнее, но я на Вас надеюсь

Показать скрытый текст

2. Для 1го взвешивания опять-таки берем 2/3 шаров, причем стараемся полностью задействовать те шары, которых четное количество (если будет равенство в 1м взв, то получится сразу же определить, каким является фальшивый шар – т или л ). Если же получим в 1м взв неравенство: Ат+Вл > Ат+Вл, то будем знать, что фальшивый либо среди Ат (слева), либо Вл (справа), а сумме это будет 1/3 всех шаров, то есть количество мы уменьшили все равно в 3 раза