Каково наибольшее число монет, среди которых можно определить фальшивую(отличается от остальных по весу) за N взвешиваний, если у вас есть двое чашечных весов, параллельное взвешивание на которых считается одним взвешиванием?
Все совершенно не так и не так все просто.Так, как у меня написано, будет только в двух частных случаях. Когда известно, что фальш. монета легче или тяжелей и второй случай, когда случайным образом в последнем взвешивании на чашках окажутся равные монеты, а фальшивой будет пятая. А это не ответ на задачу.
Сообщение отредактировал nebo - Чт, 15.09.16, 12:21
При решении задачи надо помнить что отличие в весе фальшивой монеты не известно. Делим монеты на 5 кучек равных по кол-ву (таким образом, что бы мы получили 4 равных кучки, их взвешиваем, в 5й кучке должно быть или такое же кол-во монет, либо же их должно быть меньше чем в 4х других. для случая если общее число монет не делится на 5 на цело) Соответственно при первом взвешивании мы можем получить: А=B; C><D; E. Соответственно после этого C или D необходимо взвесить с любой другой кучкой, для определения не только того в C или D находится фальшивая монета, но и того больше она весит или меньше от не фальшивой. Частным вариантом будет что при таком взвешивании (2м) C=A, в этом случая учитываем знак первого взвешивания, при C>D фальшивая монета весит меньше, при C<D соответственно больше. Если же при втором взвешивании C><A, мы все равно определим отличие по весу фальшивой монеты в большую или меньшую сторону. При A=B; C=D, так как в Е монет столько же иди меньше чем в 4х других кучках, то берем из любой взвешенной кучки такое же число монет как в Е и производим взвешивание, чем определяем отличие веса фальшивой монеты.
Для дальнейшего решения задачи пойдем с конца. При параллельном взвешивании на 2 чашечных весах, мы можем получить интересующий нас результат только в том случае если на всех 4 чашах находится одинаковое кол-во монет (так как не используем гирьки и вес монеты нам не известен).
Предположим, что мы знаем отличие веса фальшивой монеты в большую или меньшую сторону от не фальшивой. 1. Соответственно при последнем взвешивании кол-во монет не должно превосходить 5, в этом случае мы можем получить (если обобщить) 2 варианта: а) A><B; C=D; E б) A=B; C=D; E Так как мы знаем больше или меньше весит фальшивая монета, то в обоих вариантах определяем её, в а) это или A или B, в б) это Е. 2. При предпоследнем взвешивании, для того что бы удовлетворить условиям последнего, кол-во монет для 1го взвешивания не должно превосходить 5ть, соответственно максимальное общее кол-во монет будет 5*5=52. Определение в какой из 5 групп находится фальшивая монета мы делаем как и в пред идущем случае. В итоге получаем закономерность. Для последнего измерения монет не может быть больше 51, для предпоследнего 52, соответственно для 1-го не более чем 5n. То есть можно разбить кол-во монет по соответствующим интервалам: (1;51]если монет от 50+1 до 51, то для определения фальшивой нам потребуется 1 взвешивание; (51;52] если от 51+1 до 52, соответственно 2 взвешивания; (52;53] если монет от 52+1 до 53, соответственно 3 взвешивания; (5n-1;5n] если от 5n-1+1 до 5n то n взвешиваний. То есть, если известно отличие в весе фальшивой монете, то ответом на поставленную задачу будет: Наибольшее число монет будет ровняться 5n.
Но, так как нам не известно в какую сторону отличается вес фальшивой монеты, то для гарантированного определения фальшивой монеты нам необходимо произвести дополнительное взвешивания (общее число монет для этого не должно быть меньше 3х.) Соответственно ответ на поставленную задачу будет: Наибольшее число монет будет ровняться 5n-1 ЗЫ. Как я и предполагал))
Сообщение отредактировал Race - Чт, 15.09.16, 10:06
Пойдём практическим путём. Частные случаи не рассматриваем, как тот случай из 5ти монет, когда сразу при одном взвешивании выявляется ф.монета (которая в сторонке стоит). Ясно, что для выявления ф.монеты из 5ти монет, тогда нужно 2 взвешивания. Но 5 монет - это не максимум для 2х взвешиваний. Возьмём 6 монет, поставим по одной на чашки, если оба весов будут в равновесии, значит в оставшихся двух находится фальшивая. Тогда снимаем одну нормальную монету с одной из чашек двух весов и кладём на них по одной монете, из стоявших двух при первом взвешивании в сторонке. И сразу видно, какая монета фальшивая. Если после первого взвешивания на каких либо весах не будет равновесия, значит одна из монет на них фальшивая и тогда заменяем любую из неравновесных монет на точно известную правильную и в зависимости от результата, сразу видно какая монета фальшивая. Т.е. для шести монет тоже 2 взвешивания. Так же и для 7ми монет, только после первого взвешивания заменяем на одной чашке из каждых двух весов правильную монету на неизвестную. В зависимости от результатов, будет ясно, где фальшивая монета, на одном из весов или осталась в сторонке. Т.е. опять два взвешивания. А вот 8 монет уже требуют 3 взвешивания.
Сообщение отредактировал nebo - Чт, 15.09.16, 12:30
Сейчас по работе ездил и пришел к таким же мыслям. При первом взвешивании можно делить монеты не на 5, а на 6 кучек... nebo, вы снова 1я придумали, а я в роли плагиатора) Мое уважение.
Для решения этой задачи нам необходимо учитывать, что при первом взвешивании необходимо делить монеты на 6 групп, которые в свою очередь должны быть кратными 5ти, так как на 2 и последующих взвешиваниях у нас должно быть только 5 групп. Тогда максимальное кол-во монет можно выразить как 6*5n-2=1,2*5n-1
Пришел к таким выводом, потому что на 2 взвешивании, когда определяется отличие веса фальшивой от не фальшивой, у нас простаивают одни двух чашечные весы. Это было мое решение.... Как оказалось, не верное.
Цитатаnebo ()
Так же и для 7ми монет, только после первого взвешивания заменяем на одной чашке из каждых двух весов правильную монету на неизвестную. В зависимости от результатов, будет ясно, где фальшивая монета, на одном из весов или осталась в сторонке. Т.е. опять два взвешивания. А вот 8 монет уже требуют 3 взвешивания.
PS. Дочитав до конца решение nebo, понял что она совершенно права.. 1 группу можно делить не на 6, а на 7 групп. Соответственно ответ будет 7*5n-2=1,4*5n-1 В итоге. на данный момент, максимальное кол-во монет получилось у nebo....
Стоп! Все таки, если делить 1ю группу на 7 групп, то в случае 1=2, 3=4, есть вероятность, что мы получим вариант 1=5 и 3=6, то есть мы определим что фальшивая монета находится в 7 группе, но не определим отличие её веса от не фальшивой монеты,соответственно при измерении 7й группы мы будем вынуждены делать еще 1 измерение, а это значит, что только для частного случая n=2 или 3 ответ будет иметь решение y=1.4*5n-1, для n=1 y=5, а для n больше 3 ответом будет мой предыдущий. Обобщаю: n=1 y=51; nє[2;3] y=1.4*5n-1; nє(3;бесконечность] y=6*5n-2=1,2*5n-1 Ух, оптимизация)
Сообщение отредактировал Race - Чт, 15.09.16, 13:59
Нет, Вы сами писали раньше, что для 5ти неопределённых монет нужно 2 взвешивания.
Нет, до 7ми монет я не делила на группы, а вот с 8мью монетами получается такая история. Делю на 4 группы по две монеты, кладу на весы. На одних из весов будет неравенство. Тогда 2 монеты будут казаться легче, чем на противоположной чашке. Теперь берём две эти монеты, которые легче и каждую кладём на одни весы на разные чашки, а те монеты, которые кажутся тяжелей кладём по одной на чашки других весов. Вот теперь на одних из весов будет равенство, а на других разница в весе. Мы смотрим, если перевес там, где были лёгкие монеты, то монета на чашке, которая ушла вверх, т.е. легче и есть фальшивая. Если неравенство там, где две "тяжёлые монеты", то монета ушедшая вниз и есть фальшивая. Т.е получается, что и 8 монет можно измерить 2мя взвешиваниями. А также следом и 9 монет (одна ждёт в сторонке) и 10 монет и 11монет, т.е. допустимо до 3х монет в ожидании. Дальше не знаю, пока.
1. Ух, что то не получается и думать над задачей и работать одновременно, вы безусловно правы. С формулой y=6*5n-2=1,2*5n-1 для n больше 3, вы согласны? 2. С 8, 9, 10 и 11 красиво придумали, 5 групп, 6я даже не нужна,с 12 монетами, получается 4 монеты в 5й и по идее надо уже 3 взвешивания.
Так, надо будет поразмышлять дома в спокойной обстановке. В идеале, для случайного кол-ва монет Делим на 5 или на 6 групп? Если на 5, то а)1=2 2=3; 1><5 (определили и группу где фальшивая монета и отличие от веса фальшивой монеты); б) 1><2 3=4; 1><3, 2=4. весы простаивают только в частном случае, если с 1го взвешивания удается определить группу с фальшивой монетой. Если же делить на 6 групп, то а) 1=2 3=4; 1><5 2=6, б) 1><2 3=4; 1><3 2=4, мы все равно определим группу с фальшивой монетой и то тяжелее она или легче. Соответственно для первого измерения, для случайного числа монет, можно делить на 6 групп, кратных 5ти. Получаем y=6*5n-2=1.2*5n-1 Так же имеем частные случаи, для 1 монеты на чаше весов и для 2 монет на чаше весов. Если же монет на чаще больше 2, а в 5й группе больше 3, то распределение нужно делать по моему методу.
Сообщение отредактировал Race - Чт, 15.09.16, 16:19
Вот посмотрим так. Например, возьмём 30 монет, разделим на 5 групп, взвешиваем 4ре и если на весах равенства, тогд фальшивая монета в группе 6и невзвешенных ещё, но если на одних из весов неравенство, то неопределённые получаются 12 монет, и 6 из них лёгкие и 6, как тяжёлые. Если монеты делим на 6 групп, тогда, если сразу на обоих весах равенства, то фальшивую монету надо уже искать среди 10 невзвешенных ещё монет. Если сразу неравенство, то получаем группу лёгких из 5 монет и группу тяжёлых из 5 монет, всего 10 неопределённых. Т.е непонятно, как выгодней делить, на 5 или на 6 групп. А для 12 нужно уже 3 взвешивания, да. А общие формулы я выводить не умею. Исходя из чего основанием формулы берётся число 5?
Основание 5, так как 5 основных групп для бесконечного числа взвешиваний, при 5 группах, за 1 взвешивание мы определяем группу с фальшивой монетой, при условии, что знаем больше или меньше она весит относительно не фальшивой. 30 монет, делим на 6 групп по 5. Возможно 2 результата. а. 1) 1><2 3=4 2) 2.1) 1><3 or 2.2) 1=3 в зависимости от результатов 1го измерения мы определяем и фальшивую монету и то легче или тяжелее она. Для 2.1) фальшивая в группе 1, соответственно если при 1) 1>2, то весит больше, если 1<2 весит меньше, при 2.2) фальшивая в группе 2, обратно возвращаемся к результату 1) если 1>2 то фальшивая весит меньше, если 1<2 то больше. Простой 1 весов при втором измерении. б. 1) 1=2 3=4 2) 1><5 2=6 весы не простаивают, определяем и группу с фальшивой монетой и отличие веса от не фальшивой. В обоих случаях получили группу из 5 монет, причем известно больше или меньше весит фальшивая. На 3 взвешивании возможно 2 результата, оба из которых дадут искомый ответ: а. 1><2 3=4 1 или 2 фальшивая, так как мы уже определили больше или меньше весит фальшивая. б. 1=2 3=4 5-фальшивая. Для определения фальшивой из 30 монет, необходимо 3 взвешивания.
Сообщение отредактировал Race - Чт, 15.09.16, 18:05
