Здравствуйте Nikto, Вы писали:
N>Здравствуйте fAX, Вы писали:
fAX>>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...
fAX>>Удачи.
N>ИМХО задачка на много проще чем если бы было 2 демона... N>Так вопрос такой: Это нужная арка? N>Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ
Вы задаёте вопрос произвольному демону!!! Т.е. в первом и третьем случае Вы можете на Ваш вопрос получить ответ и 1, и 0 , выражаясь Вашим языком.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте KonstantinA, Вы писали:
fAX>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
Здравствуйте Rumata, Вы писали:
R>Здравствуйте fAX, Вы писали:
fAX>>Здравствуйте KonstantinA, Вы писали:
fAX>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
R>Что еще за swap??? Это уже новое взвешивание!
Нет, почему? Вы согласны, что если при первом взвешивании перевесила левая чаша, можно поменять левую и правую чаши и продолжить алгоритм как если бы изначально перевесила правая?..
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Нет, почему? Вы согласны, что если при первом взвешивании перевесила левая чаша, можно поменять левую и правую чаши и продолжить алгоритм как если бы изначально перевесила правая?..
Ну да — это очевидно, я уж было испугался, что Вы собираетесь менять шарики на весах =)))
Здравствуйте KonstantinA, Вы писали:
KA>Да нет прав, извини, если обидел. Просто жаль, что нашелся человек, который знает решение. Я в свое время поломал над этим голову...
Нет, не обидел, но там такая ухмылка... Подозрительная .
А вообще-то это не слишком занимательная задача. Честно-честно.
Здравствуйте fAX, Вы писали:
fAX>Нет, почему? Вы согласны, что если при первом взвешивании перевесила левая чаша, можно поменять левую и правую чаши и продолжить алгоритм как если бы изначально перевесила правая?..
Задача в данной формулировке имеет решение только для 13 монет. И даже для такого, казалось бы много меньшего колличества, решение намного сложнее, чем для 27 монет с условием, что известно легче фальшивка или тяжелее.
Забыл решение для 27 монет? Предложи хотя бы для 14-ти. :)
Здравствуйте WeCom, Вы писали:
Что мне нравится в Вашем ответе, так это слово "однозначно". . Я должен после этого сразу согласиться?!!
WC>Задача в данной формулировке имеет решение только для 13 монет.
Аргументы??? (Заранее, не стоит предлагать решение KonstantinA, но я больше не вижу, откуда взялась эта цифра). Знаете, предложите, пожалуйста, решение для тринадцати, потом мы с Вами подискутируем.
WC>И даже для такого, казалось бы много меньшего колличества, решение намного сложнее, чем для 27 монет с условием, что известно легче фальшивка или тяжелее.
Если известно то, что Вы сказали, задача просто тривиальна.
WC>Забыл решение для 27 монет? Предложи хотя бы для 14-ти.
А кто, пардон, сказал, что для всех чисел меньше 27 оно есть (я не уверен, что это так, хотя и возможно. Тут надо подумать)???
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте KonstantinA, Вы писали:
fAX>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! :) ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
Честно говоря не очень понял, что такое swap, но это не так важно (по крайней мере не совсем понимаю что это может изменить).
Пронумеруем шарики (можно считать, что на каждом написан его номер). Теперь после каждого взвешивания ведем журнал --- какие шарики клали на какую чашу весов, какой результат был получен (то есть шарики с какими номерами перевесили, или было равенство).
Что такое алгоритм... На первом шаге у нас заранее определены (независимо от конфигурации --- мы представления не имеем какая она) те номера, которые мы положим на весы. Пусть мы должны положить шарик с номером 5 + остальные.
Теперь выберем конфигурацию = 5 шарик неправильный. Тогда в конце алгоритм скажет, что 5-й шарик фальшивый. Посмотрим записи, где будет написано, что на 1-м шаге 5-й шарик участвовал во взвешивании и посмотрим на результат этого взвешивания. Мы сразу увидим, тяжелее он или легче. Поэтому для данного алгоритма 5-й шарик будет из A1...
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте WeCom, Вы писали: fAX>Что мне нравится в Вашем ответе, так это слово "однозначно". :( . Я должен после этого сразу согласиться?!! :no:
Ok.
Доказывать, что 27 шариков — это максимум для которого существует решение, когда известно легче искомый или тяжелее (задача1) надо? Если надо, см ниже.
Итак, считаем 27 — это максимум для задачи1. Тогда, в твоей задаче если есть решение, то после двух взвешиваний должно остаться 3 шарика не побававших на весах ни разу. Если больше, то задача1 имела бы решение для более 27 шариков. Если меньше, то аналогично. Понимаешь, почему так?
Но в твоей задаче определить из трех шариков отличный за одно взвешивание вариантов нет, согласен? Поэтому твоя задача для 27 шариков решения ОДНОЗНАЧНО не имеет. Теперь можно спокойно соглашаться. :)
Осталось доказать, что в задаче1 27 шариков — это максимум для которого существует решение. Как бы мы ни раскладывали шарики на весы, как бы их не переворачивали, но каждое взвешивание позволяет отсеить не более 2/3 шариков (3 положения весов). Есть 3 взвешивания. Поэтому 27 это действительно максимум.
Вроде все доказательно.
WC>>Задача в данной формулировке имеет решение только для 13 монет. fAX>Аргументы??? (Заранее, не стоит предлагать решение KonstantinA, но я больше не вижу, откуда взялась эта цифра). Знаете, предложите, пожалуйста, решение для тринадцати, потом мы с Вами подискутируем.
Я решал по другому, с перекладываниями и выбором шариков на основании предыдуших взвешиваний. А недавно в нете нашел вот какое решение:
Один шарик в сторону. Остальные именуем буквами и проводим три вот каких взвешивания:
MA DO — LIKE; ME TO — FIND; FAKE — COIN
После чего можем однозначно определить отличающийся шарик. Как? А вот это задание на дом. :))
Здравствуйте KonstantinA, Вы писали:
fAX>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
KA>Честно говоря не очень понял, что такое swap, но это не так важно (по крайней мере не совсем понимаю что это может изменить).
KA>Пронумеруем шарики (можно считать, что на каждом написан его номер). Теперь после каждого взвешивания ведем журнал --- какие шарики клали на какую чашу весов, какой результат был получен (то есть шарики с какими номерами перевесили, или было равенство).
KA>Что такое алгоритм... На первом шаге у нас заранее определены (независимо от конфигурации --- мы представления не имеем какая она) те номера, которые мы положим на весы. Пусть мы должны положить шарик с номером 5 + остальные. KA>Теперь выберем конфигурацию = 5 шарик неправильный. Тогда в конце алгоритм скажет, что 5-й шарик фальшивый. Посмотрим записи, где будет написано, что на 1-м шаге 5-й шарик участвовал во взвешивании и посмотрим на результат этого взвешивания. Мы сразу увидим, тяжелее он или легче. Поэтому для данного алгоритма 5-й шарик будет из A1...
Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.
С уважением,
fAX
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте KonstantinA, Вы писали:
fAX>>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! :) ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
KA>>Честно говоря не очень понял, что такое swap, но это не так важно (по крайней мере не совсем понимаю что это может изменить).
KA>>Пронумеруем шарики (можно считать, что на каждом написан его номер). Теперь после каждого взвешивания ведем журнал --- какие шарики клали на какую чашу весов, какой результат был получен (то есть шарики с какими номерами перевесили, или было равенство).
KA>>Что такое алгоритм... На первом шаге у нас заранее определены (независимо от конфигурации --- мы представления не имеем какая она) те номера, которые мы положим на весы. Пусть мы должны положить шарик с номером 5 + остальные. KA>>Теперь выберем конфигурацию = 5 шарик неправильный. Тогда в конце алгоритм скажет, что 5-й шарик фальшивый. Посмотрим записи, где будет написано, что на 1-м шаге 5-й шарик участвовал во взвешивании и посмотрим на результат этого взвешивания. Мы сразу увидим, тяжелее он или легче. Поэтому для данного алгоритма 5-й шарик будет из A1...
fAX>Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.
fAX>С уважением, fAX>fAX
Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...
Здравствуйте KonstantinA, Вы писали:
KA>Здравствуйте fAX, Вы писали:
fAX>>Здравствуйте KonstantinA, Вы писали:
fAX>>>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
fAX>>Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.
KA>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...
Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...) KA> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте KonstantinA, Вы писали:
KA>>Здравствуйте fAX, Вы писали:
fAX>>>Здравствуйте KonstantinA, Вы писали:
fAX>>>>>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! :) ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
fAX>>>Я Вас прекрасно понимаю. Согласитесь, что для любого алгоритма, который получает при первом взвешивании, что левая чаша легче, существует абсолютно эквивалентный алгоритм, который, если правая чаша перевесила, меняет чаши и нумерацию (можно только логически) местами и продолжает как если бы изначально левая чаша перевесила. Но для такого алгоритма Ваша теорема 2 не соблюдается. Иными словами, для него A(n,sign) == (n,*) всегда и задача имеет решение.
KA>>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...
fAX>Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...) KA>> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
Может это разъяснит ситуацию...
A(n,sign) --- те конфигурации, для которых будут те же взвешивания, что и для (n,sign). Так всегда (n,sign) лежит в A(n,sign)
А --- решающий алгоритм, если A(n,sign)=(n,sign) или (n,*).
Это определение говорит о том, что не может быть ситуации, что для разных неправильных шариков получены одинаковые результаты взвешиваний (иначе наш алгоритм ничего не находит).
Предположим, что A(n,sign)=(n,*). Что это значит, что для конфигураций (n,+) и (n,-) результаты взвешиваний в процессе работы алгоритма совпадут.
Предположим, что A(n,sign) = (n,sign). Тогда A(n,-sign)=(n,-sign) т.к. невозможно чтобы было A(n,-sign)=(n,*) --- это означает, что для (n,+) и (n,-) результаты взвешиваний совпадают. Но это не так в силу того, что A(n,sign)=(n,sign) != (n,*).
Почему, если шарик вешали на первом шаге, то он из A1?
Потому что для (n,+) и (n,-) будут разные результаты взвешивания на первом шаге => A(n,+) != A(n,-) => ничего не остается как A(n,+)=(n,+) и A(n,-)=(n,-)
Здравствуйте KonstantinA, Вы писали:
KA>>>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...
fAX>>Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...) KA>>> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
KA>Может это разъяснит ситуацию...
KA>A(n,sign) --- те конфигурации, для которых будут те же взвешивания, что и для (n,sign). Так всегда (n,sign) лежит в A(n,sign)
Если те же взвешивания — то мой "алгоритм" (с заменой) легитимен при первом взвешиваниих (а мне больше и не надо, чтобы опровергнуть вторую теорему в её текущем виде. Если же Вы сможете доказать её дальше, т.е. опираясь на второе или третье взвешивание (если, конечно, сможете), то придётся искать другие аргументы... Про самый веский я уже писал Но я Вам скажу, решить эту задачу легче, чем доказать, что она не решаема )
Да, возможно, ещё есть путаница. Под "A(n,sign)" Вы понимаете какие взвешивания производятся или результаты этих взвешиваний??? В любом случае, проблема (на мой взгляд) Вашего доказательства в симметрии задачи на первом взвешивании.
Спасибо за дискуссию .
KA>А --- решающий алгоритм, если A(n,sign)=(n,sign) или (n,*). KA>Это определение говорит о том, что не может быть ситуации, что для разных неправильных шариков получены одинаковые результаты взвешиваний (иначе наш алгоритм ничего не находит).
KA>Предположим, что A(n,sign)=(n,*). Что это значит, что для конфигураций (n,+) и (n,-) результаты взвешиваний в процессе работы алгоритма совпадут. KA>Предположим, что A(n,sign) = (n,sign). Тогда A(n,-sign)=(n,-sign) т.к. невозможно чтобы было A(n,-sign)=(n,*) --- это означает, что для (n,+) и (n,-) результаты взвешиваний совпадают. Но это не так в силу того, что A(n,sign)=(n,sign) != (n,*).
KA>Почему, если шарик вешали на первом шаге, то он из A1? KA>Потому что для (n,+) и (n,-) будут разные результаты взвешивания на первом шаге => A(n,+) != A(n,-) => ничего не остается как A(n,+)=(n,+) и A(n,-)=(n,-)
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте fAX, Вы писали:
fAX>Ну не нравится мне Ваша теорема 2, и всё тут. Во-первых, как насчёт случая, когда никто не перевесил?!! Во-вторых, если сначала перевесила левая чаша, можно предположить, что мы делаем swap (внимание, подсказка! ) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
А как насчет моего, менее строгого и математического доказательства?
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте Nikto, Вы писали:
N>>Здравствуйте fAX, Вы писали:
fAX>>>Попадает парень на тот свет. Видит — две арки. Рядом — 3 демона. Известно, что один всегда говорит правду, а два всегда либо вместе врут, либо вместе говорят правду. За один вопрос необходимо определить, где какая арка. Задача далеко не нова, но...
fAX>>>Удачи.
N>>ИМХО задачка на много проще чем если бы было 2 демона... N>>Так вопрос такой: Это нужная арка? N>>Варианты ответов: 1,0,0 ; 1,1,1 ; 0,1,1 ; 0,0,0 . В любом случае мы сразу же выявляем правильный ответ fAX>Вы задаёте вопрос произвольному демону!!! Т.е. в первом и третьем случае Вы можете на Ваш вопрос получить ответ и 1, и 0 , выражаясь Вашим языком.
Да я понял. Я имел ввиду что знаю эту задачку и в принципе не важно сколько там демонов, решение для 2-х такое же как для 3-х. Вопрос примерно такой: "Если бы я тебя спросил правильные ли эти врата, чтобы ты ответил?"
Здравствуйте Аноним, Вы писали:
А>Здравствуйте Nikto, Вы писали:
N>>Если все время идти на северо-восток, то куда прийдешь ч/з какое-то конечное время?(в принципе не важно ч/з какое пусть будет ч/з 10 лет)
А> На мой вгляд — на Сверней полюс(или бесконечно близко к нему). А> Sam from Il.
Здравствуйте fAX, Вы писали:
fAX>Здравствуйте KonstantinA, Вы писали:
KA>>>>Да, но у нас алгоритм фиксирован, и я не утверждаю, что A1 не зависит от алгоритма --- конечно зависит. Теорема 2 утверждает, что А1 не пусто для данного фиксированного алгоритма. То, что есть другой алгоритм, для которого 5 не лежит в его множестве B1 нам не важно...
fAX>>>Тогда — ошибка вот в чём (ИМХО, ИМХО, ИМХО...) KA>>>> Определение Алгоритм A решает задачу нахождения неправильного шарика, если для любого (n,sign) либо A(n,sign) == (n,sign) либо A(n,sign) == (n,*).
KA>>Может это разъяснит ситуацию...
KA>>A(n,sign) --- те конфигурации, для которых будут те же взвешивания, что и для (n,sign). Так всегда (n,sign) лежит в A(n,sign)
fAX>Если те же взвешивания — то мой "алгоритм" (с заменой) легитимен при первом взвешиваниих (а мне больше и не надо, чтобы опровергнуть вторую теорему в её текущем виде. Если же Вы сможете доказать её дальше, т.е. опираясь на второе или третье взвешивание (если, конечно, сможете), то придётся искать другие аргументы... Про самый веский я уже писал :))) Но я Вам скажу, решить эту задачу легче, чем доказать, что она не решаема :))) )
Замена алгоритма ни при чем --- он фиксирован и все обсуждается только для него... Не понимаю при чем здесь какой-то другой алгоритм...
fAX>Да, возможно, ещё есть путаница. Под "A(n,sign)" Вы понимаете какие взвешивания производятся или результаты этих взвешиваний??? В любом случае, проблема (на мой взгляд) Вашего доказательства в симметрии задачи на первом взвешивании.
A(n,sign) --- конфигурации, дающие те же результаты взвешивания
fAX>Спасибо за дискуссию :) .
) и перевесила правая чаша. Вы не рассматриваете такой случай, а это тоже алгоритм. И в таком случае A(n,sign) == (n,*) всегда, для алгоритма, который находит решение, и, соответственно, задача решается.
.
. Я должен после этого сразу согласиться?!! 
Но я Вам скажу, решить эту задачу легче, чем доказать, что она не решаема 
