|
Взвешивания.
|
|
| Race | Дата: Чт, 15.09.16, 22:09 | Сообщение # 31 |
Просветленный  Сообщений: 459
| Хорошо, пробуем (2*5+1)*4+11=55. Не понимаю как больше. Добавлено (15.09.2016, 22:09)
---------------------------------------------
Цитата nebo (  ) Сразу имеем 59 из них по 12 в чашках и 11 в стороне, ведь это понятно?
ок 4*12+11
1=2 3=4 решено
1><2
1/21>1/22
Определили 6 монет в которых фальшивая, определили больше или меньше весит? Дальше что?
|
| |
| |
| nebo | Дата: Чт, 15.09.16, 22:10 | Сообщение # 32 |
Высший разум  Сообщений: 3636
| Нет не так. в столбик ,как Вы не умею. Мне надо детально расписать.
|
| |
| |
| Race | Дата: Чт, 15.09.16, 22:13 | Сообщение # 33 |
Просветленный Сообщений: 459
| Цитата nebo ( ) Нет не так. в столбик ,как Вы не умею. Мне надо детально расписать.
Пока, только благодаря вам, получилось решить для 55 монет за 3 взвешивания. 4*11+11
|
| |
| |
| nebo | Дата: Чт, 15.09.16, 22:14 | Сообщение # 34 |
Высший разум Сообщений: 3636
| Распишу, приду напишу Добавлено (15.09.2016, 22:14)
---------------------------------------------
Я спать ложусь в 1 ночи. Спасибо за пожелание.
|
| |
| |
| Race | Дата: Чт, 15.09.16, 22:17 | Сообщение # 35 |
Просветленный Сообщений: 459
| А формула то какая интересная должна быть))) ведь для 4 взвешиваний будет уже минимум +55, а если вы объясните про 59 то + 59)))))
|
| |
| |
| nebo | Дата: Чт, 15.09.16, 23:38 | Сообщение # 36 |
Высший разум Сообщений: 3636
| Вот с формулами у меня тяжело, не умею обобщать.
Потом, когда ответим в этой задаче, я Вам ещё тут не решённых две интересных покажу, авторством Kreativshik.
Добавлено (15.09.2016, 23:38)
---------------------------------------------
Для 59 монет.
Делим на 5 групп, четыре по 12 на чашки, 11 в стороне. Если равновесие , то в 11ти за 2 взвешивания находим ф.монету.
При неравенстве получаем 12 лёгких, 12 тяжёлых., 4 =2тяж.+2 лёг. в сторону. Получаем по 5 в каждую чашку, но на одних весах одинаково в чашках и 5=2лёг.+3тяж., на других весах 5=3лёг.+2 тяж. в каждой чашке.
Предположим неравновесно, где по 5=2лёг.+3 тяж., тогда на той чашке, что ушла вниз непонятны 3 тяж., на той, что ушла вверх непонятны 2 лёг., всего 5 непонятных. Берём 2 тяж и каждую кладём на чашку одних весов,а 2лёгк на другие весы по одной в чашку, 1тяж. в стороне. отсюда понятно, как находим фальшивую. Если перевес , где тяжёлые, то фальш. на ушедшей вниз чашке., если перевес, где лёгкие, то фальш., где вверх ушла chашка.. если равенство, то фальш, которая в сторонке пятая была. Так же похоже разбираемся и с другими весами, если там перевес. Если на двух весах равенство, то разбираемся с 4=2тяж+2лёгк , тут элементарно.
Вот так за 3 раза 59 монет.
Сообщение отредактировал nebo - Чт, 15.09.16, 23:42 |
| |
| |
| Race | Дата: Пт, 16.09.16, 11:12 | Сообщение # 37 |
Просветленный Сообщений: 459
| Так, все понял кроме монеты в ожидании при 3 взвешивании откуда она взялась?
59=12*4+11
После первого взвешивания, получаем или 11 - заранее решенная задача, или 12 легких, 12 тяжелых.
Оставляем 4 монеты в ожидании, 2 легких, 2 тяжелых.
Перемешивать легкие и тяжелые монеты нету смысла.
Просто взвешиваем 5 легких и 5 легких и 5 тяжелых и 5 тяжелых.
5л1>5л2 1Фє5л2, к тому же она легче;
5л1<5л2 1Фє5л1, к тому же она легче;
5т1>5т2 1Фє5т2, к тому же она тяжелее;
5т1<5т2 1Фє5т1, к тому же она тяжелее.
Смысл в перемешивании? В обоих случаях мы получаем выборку из 5 монет, при известном отклонении в весе ф. монеты, соответственно имеем решенную ранее задачу.
Для оставшихся 2т и 2 л в ожидании, при равенстве на втором взвешивании, так же определяем по предложенной Вами процедуре.
1л1>1л2 1Ф=1л2;
1л1<1л2 1Ф=1л1;
1т1>1т2 1Ф=1т2;
1т1<1т2 1Ф=1т1.
Рассмотрим предложенный Вами вариант с перемешиванием монет.
2т+3л><3т+2л
1Фє2т+3л>3т+2л=2т+3л>3т+1Фє2л
2т+1Фє3л<3т+2л=1Фє2т+3л<3т+2л
Видим что результат равно возможен.
Может я снова, что то не понимаю, но как нам поможет перемешивание легких и тяжелых, если при взвешивании мы получим неопределенный результат, причем какой бы знак нам не показало, это не позволит нам определить группу в которой находится фальшивая монета.
Представим, что в ожидании мы оставили в ожидании по 3 монеты.
То есть в итоге получили 3л и 3 т, при равенстве попарного взвешивания, ф. м. не определяется. Значит надо менять стратегию, или же для 13 задача не решается за 3 взвешивания.
Возьмем тогда 14 монет.
14*4+11=67 монет.
для 11 - задача решена
имеем 6*2+2т и 6*2+2л
решая аналогично с задачей для 59 монет получим выборку из 6 монет, причем будем знать ф.м. тяжелее или легче.
Если я не ошибаюсь, то за 1 взвешивание при известном отличие веса ф.м. максимальная выборка может быть ровна 5.
Значит данный способ подходит для максимального числа монет равного 59 при N=3
Вырисовывается формула.
N=1 результат возможен, только для 1 монеты, она явно фальшивая.
N=2 y2=yх1+y1=2*4+3
N=3 y3=yх2+y2=12*4+11=(2*5+2)*4+11
Добавлено (16.09.2016, 09:39)
---------------------------------------------
Попробуем для N=4
y3=59
Определим yx3
Предположим что мы определили отличие в весе ф. монеты за 2 первых взвешивания, тогда по формуле y=5n получаем:
4 вз.5 м
3 вз. 25 м.
То есть на 2 взвешивании в идеале мы можем получим 25 или меньше монет и определенное отличие веса ф.монеты.
по приведенной ранее формуле получаем:
2 вз. 25л><25л
25т><25т
1 вз. 50т>50л
Предварительно при N=4 y=50*4+59=259 монет.
Проверяем:
при 1=2 3=4 59 за 3 взвешивания - задача решена.
при 1><2 получили 50л и 50 т
25л1><25л2 или 25т1><25т2
Получили выборку из 25 монет при определенном отличие веса ф.м., задача тоже решена ранее.
Осталось вычислить кол-во монет оставленных в ожидании для N=4.
имеем 50+х, при х=1 на 2 взвешивании 25л1=25л2 и25т1=25т2 получаем 1л и 1 т и еще 2 взвешивания, задача решается за 3 взвешивания.
х=10, получаем 10л и 10т и 2 взвешивания, пробуем
5л1><5л2 или 5т1><5т2
Получаем выборку из 5 монет, с определенным отличием веса ф.м.
Но для 2 взвешивания мы тоже можем оставить ожидание, как уже было вычесленно ранее это 2 монет, 2л и 2 т., а значит получается:
y4=(50+10+4)*4+59=315 проверяем.
1=2 3=4 59 монет, решено ранее
1><2 получаем 64т и 64 л, оставляем 14 в ожидании 64=25*2+10+4
25л1><25л2
25т1><25лт - задача решена ранее за 3 взвешивания
25л1=25л2
25т1=25т2
Осталось 14л и 14 т и 2 взвешивания 14=5*2+4
5л1><5л2
5т1><5лт- задача решена ранее за 2 взвешивания
5л1=5л2
5т1=5т2
Осталось 2л и 2т и 1 взвешивание,
взвешиваем попарно, получаем результат.
1л1><1л2
1т1><1т2
Итого получили:
при N=4
y4=[(5*5*2+5*2+2*1)*4]+[(5*2+2)*4+(2*4+3)]=307
Добавлено (16.09.2016, 09:49)
---------------------------------------------
В принципе формула вырисовывается, каждый следующий член будет биться на 4 части и 5ю, которая равна предыдущей. Сам член будет состоять из 5*5*..*2 + монеты в ожидании, для y5 к примеру это будет 5*5*5*2, для y6 5*5*5*5*2 соответственно, с ожиданием надо будет пока повозиться, для этого решим задачу при N=5.
Как мы уже определили задача решается для члена 5*5*5*2=250
То есть y4=(250+Xм.о.)*4+y3
Определим Xм.о.
Поделили на 4 группы равные 250+Х и 5ю равную 315
для 1=2 3=4 у=315, уже решенная задача за 4 взвешивания.
1 вз. 1><2 получили 250т и 250л
2 вз. 125л1><125л2
125т1><125т2
Определили группу из 125 монет и тяжелее или легче ф.м.
Далее задача решается за 3 взвешивания,делим на 5 групп по 25, затем на 5 групп по 5 и в конце получаем группу из 5. 125=5*5*5
Соответственно определим Х
Х=Х1+Х2+Х3
Х1=2*1
Х2=2*5
Интуиция подсказывает, что Х3=2*5*5, проверим это.
Yx4=(250+5*5*2+5*2+2*1)*4=314*4=1248
Y4=Yx4+Y3=1563
Проверим)
1571=(5*5*5*2+5*5*5*2+5*2+2*1)*4+307
Делим на 5 групп 4 по 312 и 1 307.
1=2 3=4 315 за 4 взвешивания определено ранее
1 вз. 1><2 имеем 314*2 тяжелых и 314*2 легких
2 вз. делим на 125*2 и 62 в ожидание, как л так и т.
125л1><125л2
125т1><125т2 определяем выборку из 125 монет, причем с известным отличием веса ф.м., задача решена ранее 5*5*5.
125л1=125л2
125т1=125т2
Имеем 62л и 62т 64=5*5*2+5*2+2*2=25*2+5*2+2*1, бьем и легкие и тяжелые на 2 группы по 25 и 14 оставляем в ожидании.
3 вз. 25л1><25л2
25т1><25т2 определяем выборку из 25 монет, причем с известным отличием веса ф.м., задача решена ранее 5*5.
25л1=25л2
25т1=25т2
Имеем 12л и 12 т. бьем и легкие и тяжелые на 2 группы по 5 и 2 в запасе
4 вз. 5л1><5л2
5т1><5т2 определяем выборку из 5 монет, причем с известным отличием веса ф.м., задача решена ранее 5.
5л1=5л2
5т1=5т2
Имеем 2л и 2 т, задача решена ранее, взвешиваем попарно, получаем результат.
1л1><1л2
1т1><1т2
Итого Х5=5*5*2+5*2+2*1=62
Для N=5
Y5=(5*5*5*2+5*5*2+5*2+2*1)*4+(5*5*2+5*2+2*1)*4+(5*2+2*1)*4+(2*1)*4+3=1248+248+48+8+3=1555
Соответственно
Y6=Y5+(5*5*5*5*2+5*5*5*2+5*5*2+5*2+2*1)*4
И так далее.
Запишем в степенях
Y6=(2*54+2*53+2*52+2*51+2*50)*4+Y5=8[(54+53+52+51+50)+(53+52+51+50)+(52+51+50)+(51+50)+50]+2*1+1
Добавлено (16.09.2016, 10:59)
---------------------------------------------
Видим, что из общей формулы выбивается 2*1 и 1. На мой взгляд 2*1, это наши ожидающие монеты, для N=2, а 1 это фальшивая монета для N=1, к сожалению под общий знаменатель они не вносятся(
Проверяем.
Y1=1
Y2=8*50+2*1+1=11
Y3=8[(51+50)+50]+2*1+1=59
Y4=8[(52+51+50)+(51+50)+50]+2*1+1=307
Y5=8[(53+52+51+50)+(52+51+50)+(51+50)+50]+2*1+1=1555
Y6=8[(54+53+52+51+50)+(53+52+51+50)+(52+51+50)+(51+50)+50]+2*1+1=7803
Добавлено (16.09.2016, 11:12)
---------------------------------------------
Общая формула, на данный момент, для случайного числа монет.
YN=8[(N-1)50+(N-2)51+(N-3)52...+2*5N-3+1*5N-2]+2*1+1
Решение получилось объемным, уже лень выискивать ошибки и помарки. На данный момент это окончательная формула.
Сообщение отредактировал Race - Пт, 16.09.16, 11:15 |
| |
| |
| nebo | Дата: Пт, 16.09.16, 11:29 | Сообщение # 38 |
Высший разум Сообщений: 3636
| Цитата Race ( ) Так, все понял кроме монеты в ожидании при 3 взвешивании откуда она взялась?
Монета взялась из той самой выборки последней, а именно
Цитата Race504Цитата мы получаем выборку из 5 монет, при известном отклонении в весе ф.
Чуть назад вернусь. При 40 монетах, сразу делим на 4 группы по 10 монет. Определятся 10 лёгких и 10 тяжёлых. Делим по 5, определяем группу неизвестных, но с известным отклонением - это важно., из 5 опрределяем 4 на весах.
Описание всего процесса уложилось в две строчки буквенного текста.
Одним слово, что точно, - перед последним взвешиванием мы можем на весах максимально получить 5 неизвестных монет, но с известными отклонениями в весе (пропорции отклонений тяж., лёг. любые.)
Второе абсолютно точно - в стороне до последнего момента всегда могут быть 3 монеты совершенно неизвестные.
Сообщение отредактировал nebo - Пт, 16.09.16, 11:41 |
| |
| |
| Race | Дата: Пт, 16.09.16, 12:45 | Сообщение # 39 |
Просветленный Сообщений: 459
| Цитата nebo ( ) быть 3 монеты совершенно неизвестные.
Только для 2 измерений их 3, для 4 и выше 2*2... То есть мы должны иметь 2 легких и 2 тяжелых, если по 3 то не определяется. Я думаю что 3 в ожидании для N=2, это частный случай, дальше как ни крути (у меня по другому не вышло) нужно честное число монет.
Если я все правильно понял)
В самих рассуждениях я понаделал ошибок, но когда вывел общую закономерность все по исправлял (что нашел естественно).
Интересная задача. Я бы сам не додумался, не работает у меня голова в такую сторону. Так нетривиально подойти к решению как смогли вы.
Добавлено (16.09.2016, 12:45)
---------------------------------------------
Кстати, члены интересно выглядят, ща продемонстрирую:
3+8+48+248+1248+6248+31248 и так далее, только 3 выбивается. 8-48-248 и так далее) прямо магия.
Вот весело будет если мы накосячили и можно за 2 измерения 12 и 15 посчитать) вторую формулу я точно не скоро решусь вывести)
Сообщение отредактировал Race - Пт, 16.09.16, 12:47 |
| |
| |
| nebo | Дата: Пт, 16.09.16, 17:38 | Сообщение # 40 |
Высший разум Сообщений: 3636
| Я имела в виду именно для двух измерений последних, не касательно тех в сторонке, которые тяжёлые или лёгкие.
А тех, которые можно выделить из группы, не попавшей в первом измерении на весы , при необходимости, т.е., когда в первом измерении на обоих весах равновесие.
Но это , видимо, неважно.Добавлено (16.09.2016, 13:10)
---------------------------------------------
Вот как Вы упростили поиск, не смешивая монеты, вот это точно здорово. Добавлено (16.09.2016, 17:38)
---------------------------------------------
Вот я прочитала все Ваши рассуждения и пришла к некоторым выводам. Над парочкой выводов я ещё подумаю. Но кое-что изменилось в расчётах, благодаря тому, что Вы предложили не смешивать лёгкие и тяжёлые монеты.
Мы знаем точно, что в предпоследнем взвешивании должно быть не более 5 неизвестных, но с известным отклонением в весе. Тогда предположим, что в случае, где 59 монет, в 1м измерении 12,12,12,12, на обоих весах равенство.
Пусть мы не знаем, сколько монет в ожидании, т.е общая сумма не 59, а неизвестна. На двух весах можно определить группу в 5 неизвестных, но с известным отклонением в весе, имея 10 совершенно неизвестных монет,
таким образом, 5неизвестных на одной чашке, 5ранее взвешенных известных на другой чашке и так же на других весах. Тогда определится группа из 5 и останется одно измерение. А раньше я писала, что в сторонке могут стоять 3 абсолютно неизвестных монеты. Если , там, где 5,5,5,5 будет равенство, то из 3х определить легко фальшмонету.
Всё это нам даёт увеличение числа 59 до 61. Т.е получается, что максимум при 3х измерениях 61 монета. Это внесёт в Ваши уравнения незначительную коррекцию.
Я тут немного по-другому их представила, но пока ещё подумаю.
|
| |
| |
