Здравствуйте fAX,
Почему то не вижу возражений на свое доказательство. Возможно, в некоторых местах, не все понятно, попробую уточнить.
Итак, считаем 27 — это максимум для задачи1. Предположим у тебя есть алгоритм решения твоей задачи. Тогда, при применении твоего алгоритма, после двух взвешиваний с результатом обоих взвешиваний "равно" должно остаться ровно 3 шарика не побававших на весах ни разу.
Потому что:
Если больше, то задача1 имела бы решение для более чем 27 шариков. Потому что, существовал бы вот такой алгоритм решения задачи1, начинаем с оригинального алгоритма для задачи1 и если на хотя бы одном из двухпервых взвешиваний результат "не равно", то этим алгоритмом и завершием решение на третьем шаге. Если же оба результата "равно", то для третьего взвешивания переходим к твоему алгоритму. итого 9+9+6+(больше 3-х) > 27.
Если меньше, то аналогично. Начинаем решение с твоего алгоритма. Если хотя бы одно из двух первых взвешиваний "не равно", то им же и завершаем решение задачи. Если же оба взвешивания "равно", то для третьего взвешивания переходим к оригинальному алгоритму решения задачи1. Т.е. решаем для оставшихся шариков (меньше трех) плюс дополнение до трех. Итого получаем (больше 24 (т.к. осталось<3)) + 3 > 27.
Но в твоей задаче определить из трех шариков отличный за одно взвешивание вариантов нет, согласен? Т.е. с одной стотоны в твоем алгоритме (если он есть и решает задачу) после двух взвешиваний с результатами "равно" должно остаться ровно 3 шарика, а с другой стороны за одно взвешивание из трех шариков неправильный найти невозможно. Из этого противоречия следует, что алгоритма решения твоей задачи НЕ СУЩЕСТВУЕТ.
WC>Осталось доказать, что в задаче1 27 шариков — это максимум для которого существует решение. Как бы мы ни раскладывали шарики на весы, как бы их не переворачивали, но каждое взвешивание позволяет отсеить не более 2/3 шариков (3 положения весов). Есть 3 взвешивания. Поэтому 27 это действительно максимум.
Слудует отметить, что задача поиска фальшивой монеты (неправильного шарика) из K монет за N взвешиваний на чашечных весах когда неизвестно легче фальшивая или тяжелее и среди всех K монет фальшивая только одна, может иметь решение только когда K <= (3^N-1)/2 + 1.
Обьяснение:
Ясно, что фальшивка однозначно определяется N показаниями весов, соответственно в 1-м, 2-м ... N-м взвешивании. Число всевозможных комбинаций для N взвешиваний — 3^N. Когда же неизвестно легче фальшивка или тяжелее, то 2 комбинации в которых каждый результат взвешивания заменен на противоположный, т.е. "слева легче" на "слева тяжелее", "слева тяжелее" на "слева легче", а "равны" остается без изменений должны указывать на одну и ту же монету. У нас один случай для которого нет пары — "равны", "равны", "равны". Поэтому пар у нас 3^N-1. Максимальное число монет, которое может определять это кол-во пар — (3^N-1)/2. И соответственно еще одна монета может определяться случаем с тремя равенствами. Поэтому и получаем K <= (3^N-1)/2 + 1.
Для N=3, K<=14. Для 13 решение известно. Уверен, для 14 решения нет. Но интересно, может быть есть решение для 14-ти, когда в условии задачи есть неограниченное колличество эталонных монет (в отдельной куче). Для N=2, например, K<=5. Для 5 без эталонов, решения нет, а с эталонами есть. Верно ли аналогичное для любого N. Т.е. то, что есть решение для K = (3^N-1)/2 + 1 при условии с эталонами? Как получить точное значение K для общего случая (любого N) и без эталонов?
---
Возможно можно доказать, что если есть хоть какой-то алгоритм решения — то есть и алгоритм, когда последующие взвешивания не зависят от предыдущих.
Здравствуйте AlexKu, Вы писали:
AK>Еще одна бородатая задачка.
AK>Какой следующий член последовательности: AK>11, 21, 1112, ...
AK>Всяких предположений может быть достаточно много, но если догадаться до правильного решения, то становится очевидным, что это ОНО.
Здравствуйте AlexKu, Вы писали:
AK>Еще одна бородатая задачка.
Тоже старая (кто знает, молчать!).
Приходит мужик в скобяную лавку и видит некий предмет. Он спрашивает:
- Сколько будет стоить 1?
- 6 ,- отвечают.
- А сколько будет стоить 12?
- 12 ,- был ответ
- А сколько будет стоить 237?
- 18 ,- сказали ему
Вопрос - чего покупал мужик? Задача на логику.
Здравствуйте Flamer, Вы писали:
F>Здравствуйте AlexKu, Вы писали:
AK>>Еще одна бородатая задачка.
F>Тоже старая (кто знает, молчать!).
F>
F>Приходит мужик в скобяную лавку и видит некий предмет. Он спрашивает:
F>- Сколько будет стоить 1?
F>- 6 ,- отвечают.
F>- А сколько будет стоить 12?
F>- 12 ,- был ответ
F>- А сколько будет стоить 237?
F>- 18 ,- сказали ему
F>Вопрос - чего покупал мужик? Задача на логику.
F>
Здравствуйте AlexKu, Вы писали:
AK>Еще одна бородатая задачка.
AK>Какой следующий член последовательности: AK>11, 21, 1112, ...
AK>Всяких предположений может быть достаточно много, но если догадаться до правильного решения, то становится очевидным, что это ОНО.
Здравствуйте AlexKu, Вы писали:
AK>Еще одна бородатая задачка.
AK>Какой следующий член последовательности: AK>11, 21, 1112, ...
AK>Всяких предположений может быть достаточно много, но если догадаться до правильного решения, то становится очевидным, что это ОНО.
Есть замечательный сайт ... ловите: cool site
Соответственно следующий член либо 1231 — "одна двойка, три единицы", либо 3112 — "три единицы, одна двойка". Классная последовательность!
Здравствуйте Rumata, Вы писали:
R>Есть замечательный сайт ... ловите: cool site
R>Соответственно следующий член либо 1231 — "одна двойка, три единицы", либо 3112 — "три единицы, одна двойка". Классная последовательность!
Вариант 1231 не проходит. Иначе третий член исходной последовательности был бы 1211.
А вот 3112 — правильнный ответ.
Надо подумать...
