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

[Smith]

Про 96 монет совсем простая. Достаточно 4 взвешивания. Самое смешное, что не то что дополнительные монеты не нужны, но вообще при первом взвешивании достаточно положить на каждую чашу по 2 монеты, а при последующих по 1.

А можно подробнее?

да, действительно очень интересно!

[Um_nik]

Про 96 монет совсем простая. Достаточно 4 взвешивания. Самое смешное, что не то что дополнительные монеты не нужны, но вообще при первом взвешивании достаточно положить на каждую чашу по 2 монеты, а при последующих по 1.

А можно подробнее?

да, действительно очень интересно!

И мне))
У меня за 5 то не получается)))

[Mr. X]

Да, весьма интересно как можно взвесть 96 монет, за 4 взешівания, по одной монете!
Это опечатка скорее всего!

[Димыч]

Там всего 78 вариантов. Или я неправильно понял условие?

[buka]

У меня есть ощущение, что можно за 4 взвешивания.
Первое взвешивание: монеты 17+26 против 71+80.
Если равенство: 19 монет среди 44 монет - от 27 до 70
Если левая легче - среди 44 монет - от 1 до 26+18=44
Если правая легче - среди 44 монет - от 71-18=53 до 96
Итак, нам за оставшиеся 3 взвешивания требуется найти 19 монет из 44.
Допустим, мы будем искать среди монет 1..44 (левая легче), так просто проще с нумерацией.
2- взвешивание: монеты 17 против 26:
17<26 -> среди 1..25 -> 8 возможностей: 1..19, 2..20,...,8..25
17>26 -> среди 18..44 -> 9 возможностей: 18..36, 19..37,...,26..44
17=26 -> среди 9..35 -> 9 возможностей
Итого, осталось 2 взвешивания для определения 1 из 9 - это троичный поиск, одно (3-е) взвешивание уменьшит кол-во возможностей с 9 до 3-х, другое (4-е) найдёт единственную верную.
Где-то так...

[buka]

Да, 78. 78 < 81, т.е. троичный поиск может определить.
Надо убедиться, что он всегда сможет сработать.
Такое впечатление, что сможет...

[Димыч]

В общем ищите не сложное хитроумное решение, а простое топорное

[Smith]

Итого, осталось 2 взвешивания для определения 1 из 9 - это троичный поиск, одно (3-е) взвешивание уменьшит кол-во возможностей с 9 до 3-х, другое (4-е) найдёт единственную верную.

точно, например, так:
3) 3 против 23:
3=23 - фальшивые 4-22
3<23 - тогда:
4) 1 против 21:
1<21 - ф. 1-19
1>21 - ф. 3-21

[Тиана]

17<26 -> среди 1..25 -> 8 возможностей: 1..19, 2..20,...,8..25
17>26 -> среди 18..44 -> 9 возможностей: 18..36, 19..37,...,26..44
17=26 -> среди 9..35 -> 9 возможностей

у меня почему-то получается при 1м раскладе 7 вариатнов (последний промежуток [7;25])
при 3м раскладе (если получили равенство) - 10 вариантов, начиная с [8;26] и заканчивая [17;35]
 

[Тиана]

точно, например, так:
3) 3 против 23:
3=23 - фальшивые 4-22
3<23 - тогда:
4) 1 против 21:
1<21 - ф. 1-19
1>21 - ф. 3-21

а если 3>23 
уже поняла 

[buka]

17<26 -> среди 1..25 -> 8 возможностей: 1..19, 2..20,...,8..25
17>26 -> среди 18..44 -> 9 возможностей: 18..36, 19..37,...,26..44
17=26 -> среди 9..35 -> 9 возможностей

у меня почему-то получается при 1м раскладе 7 вариатнов (последний промежуток [7;25])
при 3м раскладе (если получили равенство) - 10 вариантов, начиная с [8;26] и заканчивая [17;35]
 

Ну, значит мне надо быть внимательнее
Вы правы, но сути это не меняет.
Димыч дал очень хорошую подсказку.
Сейчас я должен уйти, но позже поясню подробнее фундаментальный подход.
Тиана, а как с общим случаем той задачи, с одним шаром? Вы продвинулись или хотите подсказку?

[buka]

Фундаментальный подход, подсказанный Димычем - следующий:
На каждом взвешивании обеспечить уменьшение возможных вариантов втрое.
Сначала - всего 78 вариантов (96-19+1).
Нам в принципе надо определить либо где начинается последовательность 19 фальшивых, либо где заканчивается.
Поэтому на первом взвешивании можно определить - начинается ли она среди первых 26 шаров, либо заканчивается среди последних 26 шаров, либо - ни там ни там, тогда эти 52 шара можно отбросить и у нас останутся 96-52 = 44 шара -> 44-19+1 = 26 возможностей.
Далее - действуем по такому же принципу:
Эти 44 шара (либо первые, либо последние, либо средние) подвергаем подобной проверке (26/3 = чуть менше 9, берём 9):
То есть в наших 44 шарах 19 фальшивых начинаются либо среди первых 9, либо заканчиваются среди последних 9, либо ни там ни там.
Опять сокращаем кол-во вариантов в три раза, получая 9+19-1 = 27 шаров.
И так далее Тиана, а как с предыдущей задачей? Дайте знать, если нужна подсказка

[Тиана]

Тиана, а как с предыдущей задачей? Дайте знать, если нужна подсказка

[buka]

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

1. Совершенно очевидно, что весы кроме >,< или = ничего показывать не могут.
2. Совершенно очевидно, что если у нас есть некоторое кол-во шаров Х и среди них один фальшивый, то максимум, что мы можем сделать на первом шаге, - это оставить в покое некое кол-во шаров (П), а остальные (В) - сравнить между собой: Х = В + П.
3. Если сравнение показало равенство, то фальшивый - в оставшихся П шарах и нам осталось на одно взвешивание меньше.
4. Если сравнение показало неравенство, то фальшивый - либо среди тех, что на чаше, что перевесила (таких - Т шаров), и он - тяжелее, либо среди тех, что на чаше, что легче и таких - Л шаров и фальшивый - легче. И у нас тоже осталось на одно взвешивание меньше.
5. Таким образом, если зависимость максимального кол-ва шаров Х среди которых 1 фальшивый от кол-ва взвешиваний К, обозначить через Х(К), то мы получаем уравнение:
Х(К) = В(К-1) + Х(К-1), причём В(К-1) = 3^К-1 как мы (вернее, Вы, Тиана), доказали ранее.
Поскольку 3^К-1 не делится пополам (чтобы поровну разложить на 2 чаши), нам и требуется ещё одна дополнительная, заведомо настоящая монета.
6. Тиана, Вам остаётся раскрыть рекурсию:
Х(К) = 3^К-1 + Х(К-1).

Удачи!

[Тиана]

buka, я не поняла, как вы получили в п.5 уравнение