Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 69
Задача из разряда спортивного программирования. Хотелось бы код решения увидеть
Нет, задача совсем не на программирование, а на теоретическую математику.
(бесконечно быстро думать, бесконечно много памяти)
(бесконечно быстро думать, бесконечно много памяти)
Задачи на спортивное программирование и есть задачи на теоретическую математику.
Вот пример достаточно интересной задачи:
1. Число состоит из десяти цифр,
2. Цифра на первом месте в числе отвечает за количество единиц во всем числе, цифра на втором месте — за количество двоек во всем числе,… цифра на девятом месте — за кол-во девяток, и на десятом — за кол-во нулей.
3. Что это за число.
Вот пример достаточно интересной задачи:
1. Число состоит из десяти цифр,
2. Цифра на первом месте в числе отвечает за количество единиц во всем числе, цифра на втором месте — за количество двоек во всем числе,… цифра на девятом месте — за кол-во девяток, и на десятом — за кол-во нулей.
3. Что это за число.
Ну хорошо, задачи на спротивное программирование действительно часто связыны с теор. математикой.
Я просто хотел сказать, что эта задача чисто теоретическая, никакого кода десь быть не может.
К вашей задаче нашёл ответ без программирования: 2100010006 (хотя не знаю, единственный ли он)
Кстати, много похожих задач есть на projecteuler.net
Я просто хотел сказать, что эта задача чисто теоретическая, никакого кода десь быть не может.
К вашей задаче нашёл ответ без программирования: 2100010006 (хотя не знаю, единственный ли он)
Кстати, много похожих задач есть на projecteuler.net
> Сначала у них есть время на обсуждение алгоритма.
Каждый узник начиная со 2го и до последнего вешает себе на затылок зеркало. В итоге последний узник не видит какой у него колпак, его расстреливают. остальные живы.
Каждый узник начиная со 2го и до последнего вешает себе на затылок зеркало. В итоге последний узник не видит какой у него колпак, его расстреливают. остальные живы.
все говорят один цвет
В голову пока приходит только «отмудохать охрану» узников же бесконечно много :) всех не постреляют.
Разбить весь ряд узников пополам. Та половина, что сзади, говорит какой цвет колпаков у передней половины соответственно. i-й узник говорит цвет (length/2 + i)-го узника. Узников из задней половины расстреливают. Вторая половина узников знает свой цвет и выживает. ;)))
Тут по-моему в условии чего-то не хватает. Единственная информация, которую получает узник — это количество колпаков одного и другого цвета перед ним. Соответственно у него в голове должна работать функция, которая из этих двух параметров(а никакой другой информации у него нет) делает такой, который, так сказать минимизирует вероятность ошибки. Существование такой функции кажется чем-то невероятным — это по-моему все равно что бросать монету и определять, что выпадет следующие с более чем 50 процентной вероятностью.
Более того, на n-ом броске судя по этой задаче вы должны уже определять что выпадет со 100% вероятностью.
Единственная информация, которую получает узник — это количество колпаков одного и другого цвета перед ним.
Нет, перед каждым узником бесконечная последовательность, это намного больше, чем количество колпаков одного и другого цвета (тем более, что их в большинстве случаев бесконечно)
Нет, ну вы сами посмотрите аналогию, если представить себе, что кто-то так же бросает монетку счетное число раз, неужели он может свести количество ошибок к конечному числу?
Разница с монеткой в том, что здесь каждый узник уже видит перед собой бесконечную последовательность, а для монетки известно наоборот только конечное начало.
Хорошо, давайте представим, что у нас такая ситуация — есть та же цепочка узников. Каждый из них бросает монетку, причем бросают они в порядке убывания номеров (то есть первый бросает последним) и пытается угадать, что выпадет, при этом он объявляет, что у него выпало. Если существует решение вашей задачи, то существует способ, по которому эти узники, договорившись вначале, могут повысить вероятность угадывания того, что у них выпало до 1. (ну грубо говоря отношение мощностей конечного множества и счетному равна нулю). Согласитесь — это кажется немного абсурдным.
Конечно, с точки зрения здравого смысла, эта задача абсурдна. Не бывает бесконечно умных узников.
Но поверьте, решение у неё есть :)
Но поверьте, решение у неё есть :)
что значит с точки зрения здравого смысла? — тут математика, а не здравый смысл, и в ней могут быть бесконечно умные узники, и именно с ее точки зрения существование такого вот решения противоречит теории вероятностей:)
Применять теорию вероятности можно, только если введено вероятностное пространство. Тут же никакого вероятностного пространства нет. Требуется, чтобы ДЛЯ ЛЮБОЙ последовательности колпаков количество ошибок было конечно.
Ну а где тогда ошибка в моем рассуждении, которое на 4 поста выше этого?
Ошибки наверно нет, просто с точки зрения математики нет никакого абсурда. Действительно получается, что если каждый узник видел все выпадания монетки до него, то начиная с некоторого номера все узники будут угадывать выпадание своей монетки. Попробуйте в этом какое-то логическое противоречие найти. Теория вероятности здесь ни при чём.
Самая сдлоная задачка такого рода
«A hundred prisoners are each locked in a room with three pirates, one of whom will walk the plank in the morning. Each prisoner has 10 bottles of wine, one of which has been poisoned; and each pirate has 12 coins, one of which is counterfeit and weighs either more or less than a genuine coin. In the room is a single switch, which the prisoner may either leave as it is, or flip. Before being led into the rooms, the prisoners are all made to wear either a red hat or a blue hat; they can see all the other prisoners' hats, but not their own. Meanwhile, a six-digit prime number of monkeys multiply until their digits reverse, then all have to get across a river using a canoe that can hold at most two monkeys at a time. But half the monkeys always lie and the other half always tell the truth. Given that the Nth prisoner knows that one of the monkeys doesn't know that a pirate doesn't know the product of two numbers between 1 and 100 without knowing that the N+1th prisoner has flipped the switch in his room or not after having determined which bottle of wine was poisoned and what colour his hat is, what is the solution to this puzzle?
«A hundred prisoners are each locked in a room with three pirates, one of whom will walk the plank in the morning. Each prisoner has 10 bottles of wine, one of which has been poisoned; and each pirate has 12 coins, one of which is counterfeit and weighs either more or less than a genuine coin. In the room is a single switch, which the prisoner may either leave as it is, or flip. Before being led into the rooms, the prisoners are all made to wear either a red hat or a blue hat; they can see all the other prisoners' hats, but not their own. Meanwhile, a six-digit prime number of monkeys multiply until their digits reverse, then all have to get across a river using a canoe that can hold at most two monkeys at a time. But half the monkeys always lie and the other half always tell the truth. Given that the Nth prisoner knows that one of the monkeys doesn't know that a pirate doesn't know the product of two numbers between 1 and 100 without knowing that the N+1th prisoner has flipped the switch in his room or not after having determined which bottle of wine was poisoned and what colour his hat is, what is the solution to this puzzle?
а теперь по русски пожалуйста )
«Сто пленников заперты в комнате с тремя пиратами, один из которых утром пройдёт по доске (с борта в воду). У каждого пленника 10 бутылок вина, одна из которых отравлена; у каждого пирата 12 монет, одна из которых поддельная и весит больше или меньше, чем настоящая. В комнате есть переключатель, который пленник может оставить как есть или повернуть. Перед тем, как отвести пленников в комнаты, на них одевают красный или синий колпак; пленники видят колпаки всех остальных пленников, но не свой. Тем временем, шестизначное простое число обезьян умножают, пока их число не перевернётся, затем они все должны перебраться через реку на каное, в которую помещаются максимум две обезьяны. Но половина обезьян постоянно лжёт, а вторая половина всегда говорит правду. Зная, что N-й пленник знает, что одна из обезьян не знает, что пират не знает произведение двух чисел от 1 до 100, не зная перевернул ли N+1'ый пленик переключатель в своей комнате или не определив какая бутылка вина была отравлена и какого цвета его колпак, ответьте, какое решение у этой загадки.»
(как-то так)
(как-то так)
Как вариант, можно спасити всех, если видиш спереди синие и черные колпаки т.к. по условию использованны 2 цвета каждый должен сказать в данном случае что колпак например не зеленый.
мозговая игрушка ;)
Имея бесконечно большую выборку можно статистически оценить какой колпак на «моей» голове более вероятен. Например, если передо мной 99 узников, чёрные и белые колпаки и я вижу 50 белых и 49 чёрных — предположу, что я в чёрном.
Возможно не совсем точная формулировка с т.з. математики, но суть мне кажется такая.
При умении бесконечно быстро думать посчитать эту вероятность на бесконечном количестве элементов не такая большая проблема.
Хотя здесь может встать другая особенность бесконечных величин :)
Бесконечнобыстро думать — это значит на обдумывание примитивной мысли уходит бесконечно малая величина времени. Из математики вроде известно, что сумма бесконечного числа бесконечно малых величин — есть величина конечная :)
Не судите строго дилетанта)
Возможно не совсем точная формулировка с т.з. математики, но суть мне кажется такая.
При умении бесконечно быстро думать посчитать эту вероятность на бесконечном количестве элементов не такая большая проблема.
Хотя здесь может встать другая особенность бесконечных величин :)
Бесконечнобыстро думать — это значит на обдумывание примитивной мысли уходит бесконечно малая величина времени. Из математики вроде известно, что сумма бесконечного числа бесконечно малых величин — есть величина конечная :)
Не судите строго дилетанта)
представим себе бесконечного голубя:)
ответ-то будет? :)
Извиняюсь, пост был некоторое время скрыт (из-за нарушения правил по поводу кросс-постинга).
Вопрос: пора уже публиковать решение? Или есть ещё люди, которые хотят подумать (но не смогут не подглядывать)?
Вопрос: пора уже публиковать решение? Или есть ещё люди, которые хотят подумать (но не смогут не подглядывать)?
WARNING! ДАЛЬШЕ ИДЁТ РЕШЕНИЕ.
Разобъём все последовательности из 0 и 1 (т.е. белых и чёрных колпаков) на классы эквивалентности: две последовательности эквивалентны, если начиная с некоторого номера они совпадают. Для каждого класса эквивалентности выберем «канонического представителя» — последовательность из этого класса (здесь мы используем аксиому выбора). Все эти канонические последовательности будем хранить в бесконечной памяти каждого узника. Когда их выстроют по порядку, каждый узник будет видеть всю «настоящую» последовательность, кроме её конечного начала. По тому бесконечному куску, который он видет, он сможет определить, в каком классе эквивалентности находится настоящая последовательность (например, он может мысленно дополнить видимую им подпоследовательность нужным количеством нулей и сравнить на эквивалентность с каждой из канонических последовательностей). Тогда он должен ответить, что на нём тот вид колпака (т.е. 0 или 1), который стоит на его месте в соответствующей канонической последовательности. Т.к. каноническая последовательность и настоящая начиная с некоторого номера совпадают, то ошибок будет лишь конечное число.
Разобъём все последовательности из 0 и 1 (т.е. белых и чёрных колпаков) на классы эквивалентности: две последовательности эквивалентны, если начиная с некоторого номера они совпадают. Для каждого класса эквивалентности выберем «канонического представителя» — последовательность из этого класса (здесь мы используем аксиому выбора). Все эти канонические последовательности будем хранить в бесконечной памяти каждого узника. Когда их выстроют по порядку, каждый узник будет видеть всю «настоящую» последовательность, кроме её конечного начала. По тому бесконечному куску, который он видет, он сможет определить, в каком классе эквивалентности находится настоящая последовательность (например, он может мысленно дополнить видимую им подпоследовательность нужным количеством нулей и сравнить на эквивалентность с каждой из канонических последовательностей). Тогда он должен ответить, что на нём тот вид колпака (т.е. 0 или 1), который стоит на его месте в соответствующей канонической последовательности. Т.к. каноническая последовательность и настоящая начиная с некоторого номера совпадают, то ошибок будет лишь конечное число.
мало что я понял из этого всего )) слишком сложное и непонятное решение.
получается, что каждый узник полагается на удачу, вот и все. ))
еще задачки будут? )
получается, что каждый узник полагается на удачу, вот и все. ))
еще задачки будут? )
Очень странно, по-мойму, у вас где-то ошибка в логике. Я попробую разобраться, но, что бы и вам не сидеть без дела, приведу доказательство того, что задача не имеет решения.
Предположим противное, и пусть она имеет решение, то есть существует алгоритм, который ставит в соответствие бесконечной последовательности и порядковому числу цвет (я на пятом месте, вижу все шапки передо мной, следовательно на мне, например, белый колпак). Выбираем произвольную последовательность шапок. Для каждого человека считаем цвет, который он скажет, и ставим противоположный. Таким образом мы построили последовательность цветов, при которой каждый человек ошибается. Противоречние.
Предположим противное, и пусть она имеет решение, то есть существует алгоритм, который ставит в соответствие бесконечной последовательности и порядковому числу цвет (я на пятом месте, вижу все шапки передо мной, следовательно на мне, например, белый колпак). Выбираем произвольную последовательность шапок. Для каждого человека считаем цвет, который он скажет, и ставим противоположный. Таким образом мы построили последовательность цветов, при которой каждый человек ошибается. Противоречние.
Интересно, а есть вообще хабралюди, которые поняли решение? :)
В вашем решении же получается бесконечное количество бесконечных классов эквивалентности. Каким образом из бесконечного количества разных последовательностей в одном классе эквивалентности выбрать каноническую последовательность?
Они же заранее её выбирают. Аксиома выбора утверждает, что это можно сделать.
А если на пальцах — то в данном классе эквивалентности можно взять первую попавшуюся последовательность, объявить её канонической и записать в память.
А класс эквивалентности же не зависит от номера зэка?
Дело в том, что если н-ный зек выбрал каноническую последовательность, учитывая что н+1 зек одел белый колпак. То что мешает н+1 зеку выбрать последовательность где он оденет черный колпак?
Дело в том, что если н-ный зек выбрал каноническую последовательность, учитывая что н+1 зек одел белый колпак. То что мешает н+1 зеку выбрать последовательность где он оденет черный колпак?
Класс эквивалентности, как и каноническая последовательность этого класса, не зависят от номера узника. Они все определяют один и тот же класс и все отвечают согласно одной и той же канонической последовательности (даже если некоторые из них видят отличия с настоящей последовательностью перед собой).
Приведу пример.
Пусть настоящая последовательность такая:
0000000001010101010101010101…
Пусть узники выбрали такую каноническую последовательтность в этом классе:
0101010101010101010101010101…
4ый узник, например, видет такую подпоследовательность:
____000001010101010101010101…
Тогда, несмотря на то что он уже видит, что последовательности отличаются, всё равно отвечает согласно канонической последовательности, т.е. что на нём колпак 1. И так же поступают все другие узники.
Эти две последовательности, начиная с некоторого номера (в данном случае с 9ого) совпадают. А значит, все узники, начиная с этого номера, будут отвечать правильно.
Приведу пример.
Пусть настоящая последовательность такая:
0000000001010101010101010101…
Пусть узники выбрали такую каноническую последовательтность в этом классе:
0101010101010101010101010101…
4ый узник, например, видет такую подпоследовательность:
____000001010101010101010101…
Тогда, несмотря на то что он уже видит, что последовательности отличаются, всё равно отвечает согласно канонической последовательности, т.е. что на нём колпак 1. И так же поступают все другие узники.
Эти две последовательности, начиная с некоторого номера (в данном случае с 9ого) совпадают. А значит, все узники, начиная с этого номера, будут отвечать правильно.
здесь суть в конечном числе ошибок.
ну я суть понял)
И все-таки, условие задачи непольное. Раз используется какая-то аксиома, тем более, что эта аксиома «принимается не всеми математиками безоговорочно: некоторые относятся к ней с недоверием», то в условии нужно указать, что эту аксиому можно использовать.
Потому как решение, базирующееся на другом наборе аксиом может сильно отличаться или не существовать вовсе.
Потому как решение, базирующееся на другом наборе аксиом может сильно отличаться или не существовать вовсе.
Для большего эффекта упомянули бы, что цветов может быть не два, а много (очень много :)).
Первый раз задачу увидел задачу в жж knop-а.
Первый раз задачу увидел задачу в жж knop-а.
Все так, однако использование аксиомы выбора и требование алгоритма решения несовместимы. Своим решением Вы ответили на вопрос «можно ли», но поставленную задачу не решили. Я не конструктивист и не педант, кстати.
значит, количество памяти должно быть не просто бесконечным — оно должно быть еще и несчетным! ӕто уже невероятно=)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сложная задачка про узников