Форум умных людей

Есть 12 шаров, одинаковые по геометрическим размерам. Среди них один (1) имеет вес отличный от других, при этом неизвестно тяжелее он или легче.
Имеются чашечные весы.

()

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

Задача очень легкая и наверняка не один раз здесь встречалась (я, правда, только один раз видел).

Она с монетами
http://nazva.net/2/

Какая разница?))

Да никакой разницы.  :beer:
Ссылка в подтверждение твоего поста.

:beer:

Ну не такая она уж и "очень легкая" ))

Я считаю, что задача легкая, если ее может решить четырнадцатилетний мальчик в уме.

так с 13ю  тяжелее  :-\ пришлось подумать хорошенько над ней  :read:

ну и мальчики пошли  :yesgirl:

Что тебе не нравится?

разве я говорила о том, что мне что-то не нравится? :tianchik:

Ну, знаешь,
звучит немножко вызывающе)))

не придумывай  :peace:
это был типа комплимент 14летнему мальчику  ;)

А-а-а... Ну тогда спасибо))  ;) Люблю комплименты)))  :cool3: :cool3: :cool3:

Я когда был маленький решил задачку про 9 шариков и 2 взвешивания
Но эта задачка покруче! ))

Молодец!

Ну и что? Все равно она легкая))

Я наткнулся на решение этой задачки здесь: http://ega-math.narod.ru/Quant/Shestpl.htm

Я бы не сказал, что здесь все тривиально просто!

Я по-другому решил...

вот и скинули бы свои ответы, а то только говорите о том, какая она простая

Хе-хе. Проверил на бумаге - оказалось ошибка. Приношу свои извинения.

Это задача из игры"Путишествие к центру землии"!!

я ее решил так 
1. Возмем 1,2 и 3. и положим на одну чашу весов и 10,11,12 на другую. Взвесим.
2. А) Если стрелка отклонилась снимайте шары с любой чашки и меняете их на три не взвешаных ( среди которых ключа нет) если весы уравнавешены значит шар в снятой группе весов а если какой-нибудь тежелее то тагда среди первых трех положеных шаров.
б) если весы равны то снимаем одну из них с весов и кладем три следуюшие. если стрелка отклонилась значит шар в новой группе весов и мы знаем легче он или тежелее. Если осталась на месте шар в последней не взвешеной группе.
3. Теперь мы знаем в какой группе шар и легче он или тежелее кладем на весы по одному шару и смотрим если весы отклонились берем нужный шар если остались неподвижными нужный шар последний. 8) 8) 8)

не поделитесь решением про 2 из 9?

Имеется в виду, что фальшивый тяжелее (или легче).

а если неизвестно (легче/тяжелее), то за 2 из скольки можно?

Больше 4-ех никак.  :wall:

Так сколько максимально возможно? ???

Валерий, так Вы правильно ответили, и Тиана с Вами солидарна, и я присоединяюсь :)
вообще, имхо это мжно доказать, но я такой целью не задавался..

Спасибо. Доказательств не нужно.  :beer: :beer:

Решение для 12:
Показать скрытый текст
Решение для 13:
Показать скрытый текст
P.S. Обе задачи довольно сложны.

Есть решение и для 14 за три взвешивания. Фальшивый определяется всегда, но не всегда будет известно, он легче или тяжелее. И ещё требуется один, 15-й нефальшивый.

непонял. просто для 14? или для 14 но с каким-то магическим 15-м?

У Вас 14 шаров, 1 фальшивый, отличающийся по весу неизвестно в какую сторону.
Кроме этого у Вас есть ещё один нефальшивый шар.
Как определить фальшивый шар за 3 взвешивания?
Можно ли найти формулу общего вида? то есть из какого макс. числа шаров можно найти 1 фальшивый за К взвешиваий?

похоже на мое решение с 12 шариками  :tianchik: :tianchik: :tianchik: :no!:

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

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

Так что, никому не интересно? Нет никаких идей?

а ЭХО в ответ:

- так что никто?
     - так что  никому?
            - так что никто?
                  - так что  никому?
                          - так что никто?
                                 - так что  никому?

                                            .   .   . . . . .   ..     ... :)

у

 Это эхо?

Это флуд, который, я надеюсь, закончится моим сообщением.

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

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

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

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

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

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

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

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

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

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

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

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

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

Немного подумав, я пришел к следующему выводу:
Самый простой способ решения данной задачи - это результат первого взвешивания, т.е.  вероятность 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, это сиюминутное и настроенческое с моей стороны, что, право, не заслуживает даже пристального внимания с Вашей стороны, не говоря уже об эмоциональной стороне вопроса ;)
впрочем, должен признать, что мне всегда были ближе приземленные, если хотите - "на пальцах", расчеты в решениях многих мат/задач.  :cool4:
даже тогда, когда требовалось найти или обосновать нечто в системе "n" и "k" я пытался перевести всё в вещественные корни, решить задачу и вернуть в "энно-катое" состояние, не говоря уже об обратных представлениях. отсюда "туманная поэтика" и "бытовая математика". :music:
вероятно сказывается отсутствие академического мат/образования, либо это естественно-персонифицированная поведенческая реакция - мне трудно судить. ???
но это ни коим образом не отражается на моем интересе к решению и "энно-катому" представлению доказательств решения мат/задач, так что в этом смысле можете ничтоже сумняшеся "иметь меня ввиду"! :)

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

Показать скрытый текст
да уж ....и вправду, объяснили "на пальцах"  ;D

чтобы не быть голословным, перефразирую задачу, почерпнутую мною на другом ресурсе, которую я не стал бы приводить здесь, не будь данного топика, и не будь она мне достаточно интересна для обсуждения в нем, ...итак:
имеется 96 монет, расположенных в ряд, из которых 19 монет (расположенных подряд) - фальшивые. каждая фальшивая монета легче любой настоящей. имеется также ресурс отдельно взятых 19 настоящих монет. задача состоит в том, чтобы обнаружить данные 19 фальшивок за минимальное количество взвешиваний.
зы: если кто-нить еще сможет обосновать указанный минимум взвешиваний - тому отдельный респект и уважуха! :beer:

Умница!!!
То есть как бы ни соотносились Т и Л, всегда можно выбрать 2/3 шаров так, чтобы в каждой 1/3 было одинаковое соотношение шаров из Л и Т.
И тогда одно взвешивание этих 2-х третей позволит уменьшить число кандидатов втрое.
Молодчина! Ведь правда - несложно?
А теперь надо это как-то увязать с нашей основной задачей. Это - чуть сложнее...

Всё ОК, Смит! У меня настроение тоже волнами ходит :)

У меня выходит 5-6 взвешиваний, но дополнитеьного ресурса не требуется...
Ведь весы показывают только >=<, а не саму разницу...

у меня получается за 6, интуитивно чувствую, что можно меньше, но пока не знаю как, а какой потенциальный минимум - вообще не имею понятия..

У меня тоже пока за 6, но без использования "бонусных" монеток. Вообще не понимаю, куда их впихнуть можно. Думаю, минимум - 5 взвешиваний.

Сегодня на всех уроках думал об этой задачке)))

Делим шары на 4 кучи по 3 шара.
1-е взвешивание:
Берем 1ю и 2ю кучки, возможны 2 варианта:
           - кучки равны, в этом случае производим второе взвешивание, но уже 1й и 3й кучки.      Если равны, то искомый шар в четвертой кучке, если не равны, то в третьей (при этом мы определяем, легче или тяжелее шар)
           - Кучки не равны, в этом случае производим второе взвешивание, но уже 1й и 3й кучек. если они равны, то искомый шар во второй кучке, если не равны, то искомый шар в первой кучке. В Этих случаях мы так же определяем, тяжелее или легче искомый шар.

Таким образом, мы выбрали кучку из 3х шаров, в которой собержится искомый шар, при этом мы уже знаем, легче он или тяжелее.

Осталась задача, с помощью одного взвешивания определить, какой из трех шаров - искомый.
Берем любых 2 шара, взвешиваем: если они равны, то искомый шар - третий, если не равны, то тот, который легче или тяжелее (мы определили ранее легче он или тяжелее)

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

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

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

Я тоже вчера думал над этой задачей и пришел к такому же решению!
НО! Допустим случай первое взвешивание 1 и 2 кучек дает равенство, далее 2 взвешивание 1 и 3 дает равенство, тем самым мы определяем что искомый шар в 4 кучке, но мы тут так и не узнаем при взвешивании двух шаров из 4 кучки, шар тяжелее или легче. При взвешивании 2 шаров из 4 кучки и при их равенстве, мы узнаем что последний шар есть искомый, а если весы дали неравенство? То в этом случае не возможно определить какой у нас искомый шар.

Да, я тоже долго думала над этой ситуацией, не смогла найти решение из нее((((
В любом случае так можно уже за 4 взвешивания найти искомый шар, а не за шесть.

Ленка, полистайте данный топик сначала, ну или со средины хотя бы :D
Илья привел решения для определения фальшивого шара (монеты) за три взвешивания из 12 и из 13, а buka показал решение за 3 для 14 +1 настоящий

Да я уж заметила)))) только что прошла по теме))))

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

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

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

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

У меня есть ощущение, что можно за 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-е) найдёт единственную верную.
Где-то так...

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

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

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

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

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

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

Фундаментальный подход, подсказанный Димычем - следующий:
На каждом взвешивании обеспечить уменьшение возможных вариантов втрое.
Сначала - всего 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 шаров.
И так далее :)

---

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

:help:

ОК :)
Показать скрытый текст
Удачи!

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

Итак, из какого максимального кол-ва Х шаров можно за К взвешиваний определить один фальшивый?
Другими словами, нам следует найти зависимость Х(К).
1. Мы выделяем из Х шаров П, оставляем их в покое, а оставшиеся В сравниваем на весах (деля на 2 равные части если В чётно или на В/2 и В/2 -1 и добавляем один заведомо настоящий, если В - нечётно.
2.1 Если весы показали равенство, то фальшивый шар - среди П. Следовательно, П не должно быть больше некоторого кол-ва шаров, среди которых надо определить 1 фальшивый за К-1 взвешивание (ведь одно взвешивание мы уже произвели).
Следовательно, П <= Х(К-1). Саму формулу (зависимость) мы ещё не знаем, но в общем виде она такая, что если подставить туда К, мы получим Х1 = Х(К), а если подставить К-1 получим П=Х(К-1).
2.2 Если весы показали неравенство, то фальшивый шар - либо среди Т шаров и он тяжелее (Т - на той чаше, что перевесила), либо среди Л шаров и он - легче.
3. Но мы уже выяснили зависимость от K в этом случае и она равна 3^К, т.е. за К взвешиваний мы можем в этом случае выделить один фальшивый шар среди 3^К шаров, если известно, что он либо среди Т и более тяжёлый, либо среди Л и более лёгкий.
Но ведь на это у нас уже ушло одно взвешивание, т.е. осталось К-1 взвешивание и мы можем определить один фальшивый шар из 3^К-1 шаров.
Отсюда: В = 3^К-1 и Х(К) = В + П = 3^К-1 + X(K-1)

buka, вам большое спасибо за объяснения  :good: я как бы понимаю о чем вы говорите, но вот мат.запись ..... не совсем  :(
:-\ это как получили? объясните плиз, если есть еще желание  ;)

Хорошо, я попробую зайти с другого боку.
1. Среди скольких шаров (максимум) Х можно определить фальшивый, отличающийся от настоящего по весу, но неизвестно, в какую сторону, если у нас есть дополнительно один заведомо настоящий шар за К=1  взвешиваний (т.е. за одно взвешивание)?
Ответ: среди 2-х: кладём один из них на одну чашу, на другую - заведомо настоящий. Если весы в равновесии, то фальшивый - оставшийся. Если весы не в равновесии, то фальшивый - тот, что мы положили на весы.
Итак: К=1, Х=2 Запишем это так: Х(1) = 2.
2. Тот же вопрос, если К=2.
Рассуждаем следующим образом: какое-то кол-во шаров мы должны в первом взвешивании оставить в покое (не взвешивать), а остальные - сравнить взвешиванием.
Сколько можно оставить в покое максимум? Очевидно, не более 2, поскольку если среди сравниваемых фальшивого не будет, то нам останется одно взвешивание, а за одно взвешивание мы мошем определить фальшивый шар из двух (см. п.1)
Итак, П = Х(1) = 2.
А сколько шаров (В) можно сравнить взвешиванием?
Если фальшивый шар - среди В (т.е. весы - не в равновесии), то после первого взвешивания, мы знаем, что наш шар - либо среди тех, которые перевесили (Т) и тогда он - тяжелее, либо среди тех, которых перевесили (Л) и тогда он легче.
И вот на то, чтобы определить фальшивый среди В = Т+Л у нас осталось одно взвешивание (ведь одно уже "ушло") на то, чтобы определить - которые Т и которые Л.
А среди скольких шаров можно определить 1 фальшивый за одно взвешивание, если известно что наш шар - либо среди тех, которые перевесили (Т) и тогда он - тяжелее, либо среди тех, которых перевесили (Л) и тогда он легче?
Мы выяснили - что среди 3¹ шаров. Т.е. В = 3¹
Итак, если К=2, то Х = В+П = 3+2 = 5 (2 - если весы в равновесии, т.е. шар - среди П и 3 - если наоборот).
Запишем это: Х(2) = 5.
3. Аналогично можно убедиться, что Х(3) = 14 (Вы, Тиана, сами это расписали, помните?)
Как мы получили 14?
14 = 9 + 5 : 5 шаров в случае если шар среди тех, что мы оставляем в покое на 1-м взвешивании и 9 = 3².
Т.е. Х(3) = 3² + Х(2) = 3^3-1 + Х(3-1).
Т.е. при К=3: Х(К) = 3^К-1 + Х(К-1). (если К=3, то К-1=2)
И так далее.
Общая формула:
Х(К) = 3^К-1 + Х(К-1).
Но эта формула ещё не говорит нам - а какой вид у этой зависимости. Она рекурсивная и её надо раскрыть.
Не стесняйтесь, Тиана, спрашивайте, что Вам не понятно. Я постараюсь объяснить.

buka, теперь почти все понятно, спасибо  :peace:
но .... я думала, что на общей формуле все закончится, а тут похоже только все начинается  :D

Да нет, мы почти у финиша. Раскрыть эту рекурсию очень просто.
Показать скрытый текст

класс  :good:
это уже финиш?  :pinkgirl:

продолжайте


нам нравится :crazy:

Для этой задачи - да :)
Но за это время я решил и другую задачу - для случая, когда надо определить и фальшивый шар и в какую сторону он отличается :)

Тиана - это намек. ;)
Новое домашнее задание. :D

Илюха, я в 10-м классе решил задачу - как можно за 3 взвешивания определить фальшивую монету из 10-ти, причем в отличие от моих товарищей, решавших в последствии ее в институте уже, мое решение предусматривало безусловно однозначное определение фальшивой монеты в плане легче/тяжелее..
так что я вполне "прохавал тему" от buka :good3:

делов-то  :rest: еще одно взвешивание (К+1) и все  :D Показать скрытый текст

ой не бегай, кандидат! (с) ММЖ :tianchik:

Вас может удивить, но решение также простое:
если у нас есть дополнительный заведомо настоящий шар, то в этом случае:
Х(К) = (3^К - 1)/2, если нет, то Х(К) = (3^К - 1)/2 - 1.

buka, если я правильно поняла, то  при помощи
Х(К) = (3^К - 1)/2 - 1
можно рассчитать количество шаров, когда у нас нету заведомо настоящего шара и точно сказать тяжелый он или легкий, так?
если да, то при 3 взвешиваниях максимум будет 12 шаров, а ведь есть способ и для 13
или же я опять чего-то недопонимаю  :tormoz:

Для 13 - нет возможности - и определить фальшивый и узнать лёгче он или тяжелее во ВСЕХ случаях...
Есть ситуация, когда какой шар - фальшивый определить можно, но при этом не узнать - легче он или тяжелее...
Только 12 ... :)

та да,  13й шар выпадает местами ...  :pinkgirl: