задачкa
biLLiBonS, я тут в сети порылся и вот что нарыл:
Решение для n=3 можно быстро подобрать вручную, для n>3 надо на компе генерировать (решение связано с троичной системой исчисления, т.к. у весов может быть три положения: влево, вправо и равновесие).
Так вот: для 13 монет.
Одну откладываем, остальные 12 обозначаем буквами или цифрами, например так:
1 2 3 4 5 6 7 8 9 x y z
Производим три взвешивания двух партий по 4 монеты по схеме:
левая чаша / правая чаша
1) 19yz / 567x
2) 27xz / 468y
3) 38xy / 459z
Теперь в зависимости от результатов взвешиваний (1 - весы влево, 2 - вправо, 0 - равновесие):
100 1-я монета фальшивая и она тяжелее
010 2-я
001 3-я
022 4
202 5
220 6
210 7
021 8
102 9
211 x
121 y
112 z
200 1-я монета фальшивая и она легче
020 2-я монета фальшивая и она легче
...
и т.д.
...
221 монета z фальшивая и она легче
000 13-я монета фальшивая (которую откладывали)
Я думаю, чтобы ее решить нужно изначально знать принцип. Дойти до этого своей головой - это надо быть гением.
Решение для n=3 можно быстро подобрать вручную, для n>3 надо на компе генерировать (решение связано с троичной системой исчисления, т.к. у весов может быть три положения: влево, вправо и равновесие).
Так вот: для 13 монет.
Одну откладываем, остальные 12 обозначаем буквами или цифрами, например так:
1 2 3 4 5 6 7 8 9 x y z
Производим три взвешивания двух партий по 4 монеты по схеме:
левая чаша / правая чаша
1) 19yz / 567x
2) 27xz / 468y
3) 38xy / 459z
Теперь в зависимости от результатов взвешиваний (1 - весы влево, 2 - вправо, 0 - равновесие):
100 1-я монета фальшивая и она тяжелее
010 2-я
001 3-я
022 4
202 5
220 6
210 7
021 8
102 9
211 x
121 y
112 z
200 1-я монета фальшивая и она легче
020 2-я монета фальшивая и она легче
...
и т.д.
...
221 монета z фальшивая и она легче
000 13-я монета фальшивая (которую откладывали)
Я думаю, чтобы ее решить нужно изначально знать принцип. Дойти до этого своей головой - это надо быть гением.
не претендуя на сообразительность, замечу, что надо детские книжки получше читать... нашла у себя на книжной полке:)
"Вся трудность в том, что неизвестно заранее, тяжелее или легче фальшивая монета. Поэтому, разделяя монеты на 3 группы по 4 монеты в каждой, необходимо их индивидуализировать, например перенумеровать. На одну чашку весов положим первую группу монет, имеющих, скажем, номера 1, 2, 3 и 4, а на вторую - вторую группу монет с номерами 5, 6, 7 и 8 (первое взвешивание). Возможны два случая:
Случай А: Весы в равновесии. Следовательно фальшивая монета - среди третьей группы монет с номерами 9, 10, 11 и 12. Сравним теперь вес трёх из них, например девятой, десятой и одиннадцатой, с монетами первой, второй и третьей (второе взвешивание).
Если весы останутся в равновесии, то фальшивая монета двеннадцатая, и сравнавая её, например, с первой, о которой стало известно, что она настоящая (третье взвешивание), определяем, будет ли фальшивая монета тяжелее настоящей или легче.
Если же второе взешивание не даст равновесия, то фальшивая монета или 9, или 10, или 11, причём по положению чашки весов сразу же выясняется, какая она - более тяжёлая или более лёгкая. Допустим, перетянула чашка с монетами 9, 10 и 11. Значит фальшивая - более тяжёлая. Чтобы выделить её из трёх достаточно ещё одного (третьего) взвешивания. Для этого положим на весы монеты 9 и 10. Тогда либо фальшивая перетянет, либо она под номером 11.
Случай Б: (на это месте могла бы быть схема взвешиваний, но видимо придётся обойтись...) Первое взвешивание не привело к равновесию. Перетянула, скажем, чашка с монетами 1, 2, 3 и 4. Тогда либо искомая монета среди монет 1, 2, 3, 4 (первая группа) и более тяжёлая, либо среди монет 5, 6, 7, 8 (вторая группа) и более лёгкая. Становится известным при этом, что монеты третьей группы 9, 10, 11, 12 настоящие. Вторым взвешиванием сравним монеты 1, 2 и 9 (две монеты из первой группы и одна из тертьей) с монетами 3, 4 и 5 (другие две из первой группы и одна из второй группы). Монеты 6, 7 и 8 из второй группы пока откладываем в сторону. Возможны три случая:
1) Равновесие. Фальшивая монета, следовательно, находится в более лёгкой группе, среди монет 6, 7 и 8. Третьим взвешиванием сравниваем любые две из этих трёх монет и тем самым выделяем фальшивую, устанавливая, что она наиболее лёгкая.
2) Тяжелее группа монет 3, 4 и 5. Третьим взвешиванием сравниваем монеты 3 и 4. [color=white:19xp29e4]Если весы остануться в равновесии, то фальшивая монета 5 более лёгкая, если [/color:19xp29e4]равновесия не будет, то фальшивая монета - более тяжёлая - та, которая перетянет. (выделенное белым цветом - было написано в книжке, но, видимо, по случайности, потому как такое просто невозможно! Поэтому выделяю ложную часть, делая при этом акцент на том, что всё-тки чего-то соображаю и я в этой жизни... впрочем, справедливости ради, отмечу, что на книжной схеме всё было правильно).
3) Тяжелее группа монет 1, 2 и 9. Третьим взвешиванием сравниваем, например, монеты 1 и 2. В случае равновесия фальшивая монета 5 более лёгкая; если равновесия нет, то фальшивая монета - более тяжёлая - та, которая перетянет.
Приведённое решение не является единственным, т.к. можно варьировать группы монет, предназначенных для второго взвешивания. <!-- s:D --><img src="{SMILIES_PATH}/biggrin.gif" alt=":D" title="Смех" /><!-- s:D -->
На сим позвольте откланяться и убраться восвояси...
"Вся трудность в том, что неизвестно заранее, тяжелее или легче фальшивая монета. Поэтому, разделяя монеты на 3 группы по 4 монеты в каждой, необходимо их индивидуализировать, например перенумеровать. На одну чашку весов положим первую группу монет, имеющих, скажем, номера 1, 2, 3 и 4, а на вторую - вторую группу монет с номерами 5, 6, 7 и 8 (первое взвешивание). Возможны два случая:
Случай А: Весы в равновесии. Следовательно фальшивая монета - среди третьей группы монет с номерами 9, 10, 11 и 12. Сравним теперь вес трёх из них, например девятой, десятой и одиннадцатой, с монетами первой, второй и третьей (второе взвешивание).
Если весы останутся в равновесии, то фальшивая монета двеннадцатая, и сравнавая её, например, с первой, о которой стало известно, что она настоящая (третье взвешивание), определяем, будет ли фальшивая монета тяжелее настоящей или легче.
Если же второе взешивание не даст равновесия, то фальшивая монета или 9, или 10, или 11, причём по положению чашки весов сразу же выясняется, какая она - более тяжёлая или более лёгкая. Допустим, перетянула чашка с монетами 9, 10 и 11. Значит фальшивая - более тяжёлая. Чтобы выделить её из трёх достаточно ещё одного (третьего) взвешивания. Для этого положим на весы монеты 9 и 10. Тогда либо фальшивая перетянет, либо она под номером 11.
Случай Б: (на это месте могла бы быть схема взвешиваний, но видимо придётся обойтись...) Первое взвешивание не привело к равновесию. Перетянула, скажем, чашка с монетами 1, 2, 3 и 4. Тогда либо искомая монета среди монет 1, 2, 3, 4 (первая группа) и более тяжёлая, либо среди монет 5, 6, 7, 8 (вторая группа) и более лёгкая. Становится известным при этом, что монеты третьей группы 9, 10, 11, 12 настоящие. Вторым взвешиванием сравним монеты 1, 2 и 9 (две монеты из первой группы и одна из тертьей) с монетами 3, 4 и 5 (другие две из первой группы и одна из второй группы). Монеты 6, 7 и 8 из второй группы пока откладываем в сторону. Возможны три случая:
1) Равновесие. Фальшивая монета, следовательно, находится в более лёгкой группе, среди монет 6, 7 и 8. Третьим взвешиванием сравниваем любые две из этих трёх монет и тем самым выделяем фальшивую, устанавливая, что она наиболее лёгкая.
2) Тяжелее группа монет 3, 4 и 5. Третьим взвешиванием сравниваем монеты 3 и 4. [color=white:19xp29e4]Если весы остануться в равновесии, то фальшивая монета 5 более лёгкая, если [/color:19xp29e4]равновесия не будет, то фальшивая монета - более тяжёлая - та, которая перетянет. (выделенное белым цветом - было написано в книжке, но, видимо, по случайности, потому как такое просто невозможно! Поэтому выделяю ложную часть, делая при этом акцент на том, что всё-тки чего-то соображаю и я в этой жизни... впрочем, справедливости ради, отмечу, что на книжной схеме всё было правильно).
3) Тяжелее группа монет 1, 2 и 9. Третьим взвешиванием сравниваем, например, монеты 1 и 2. В случае равновесия фальшивая монета 5 более лёгкая; если равновесия нет, то фальшивая монета - более тяжёлая - та, которая перетянет.
Приведённое решение не является единственным, т.к. можно варьировать группы монет, предназначенных для второго взвешивания. <!-- s:D --><img src="{SMILIES_PATH}/biggrin.gif" alt=":D" title="Смех" /><!-- s:D -->
На сим позвольте откланяться и убраться восвояси...
С помощью детской книжки все же, но решила. <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) --> А я уже хотел спросить у "технарей", не рано ли им еще за "силиконовую долину" браться. <!-- s:lol: --><img src="{SMILIES_PATH}/icon_lol.gif" alt=":lol:" title="Laughing" /><!-- s:lol: --> Теперь скажу просто: Вперед гуманитарии (или полу-гуманитарии, если экономисты)!Sunny, ай молодец <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) --> Такую задачу повалила <!-- s:) --><img src="{SMILIES_PATH}/icon_smile.gif" alt=":)" title="Smile" /><!-- s:) -->
Вторую задачку о фальшивых монетах предложу я. Эта совсем легкая. В помещении находятся 12 машин, штампующих монеты. Ваша задача: за одно взвешивание обнаружить ту, которая штампует фальшивые, опять неважно, если легче или тяжелее. НО! Разница в весе настоящей и фальшивой монеты известна. Как будете действовать? Удачи!
garrow, если я правильно понял условие, то достаточно взять с каждой машины раличное определенное число монет, сложить в кучу и взвесить с тем же числом монет с какой-то одной машины.
Например взять 1 монету с машины №1, 2 монеты с машины №2 и т.д. и взвесить их с 78 монетами взятыми с машины например №1.
Потом разделить полученную разницу на известную разницу в весе настоящей и фальшивой монеты.
По результату можно определить с какой машины взяты бракованные монеты. Т.е. в данном случае например если получится 7, то фальшивит 7-я машина.
Так что берегись "гуманитарий" <!-- s:twisted: --><img src="{SMILIES_PATH}/icon_twisted.gif" alt=":twisted:" title="Twisted Evil" /><!-- s:twisted: -->
Например взять 1 монету с машины №1, 2 монеты с машины №2 и т.д. и взвесить их с 78 монетами взятыми с машины например №1.
Потом разделить полученную разницу на известную разницу в весе настоящей и фальшивой монеты.
По результату можно определить с какой машины взяты бракованные монеты. Т.е. в данном случае например если получится 7, то фальшивит 7-я машина.
Так что берегись "гуманитарий" <!-- s:twisted: --><img src="{SMILIES_PATH}/icon_twisted.gif" alt=":twisted:" title="Twisted Evil" /><!-- s:twisted: -->
biLLiBonS, так тринадцатая монета во взвешиваниях не участвует.
Sunny, а без схемы сможешь воспроизвести?
А вот как решают эту задачу американские дети:
Обозначим монеты следующим образом: FAKE MIND CLOT. Взвешиваем одну четверку против другой (буквы обозначают монеты, входящие в каждую четверку): MA DO - LIKE, ME TO - FIND, FAKE - COIN. Теперь совершенно просто найти фальшивую монету: к примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "A", которая легче других.
garrow, а сколько времени тебе понадобится, чтобы найти решение для 121 монеты и 5 взвешиваний?
Sunny, а без схемы сможешь воспроизвести?
А вот как решают эту задачу американские дети:
Обозначим монеты следующим образом: FAKE MIND CLOT. Взвешиваем одну четверку против другой (буквы обозначают монеты, входящие в каждую четверку): MA DO - LIKE, ME TO - FIND, FAKE - COIN. Теперь совершенно просто найти фальшивую монету: к примеру, если результаты взвешивания были: слева легче, равно, слева легче, то фальшивой может быть только монета "A", которая легче других.
garrow, а сколько времени тебе понадобится, чтобы найти решение для 121 монеты и 5 взвешиваний?