Любопытная задачка для математиков

Vano

Сорри, если было...
Итак. Троих мудрецов сажают в тюрьму (начало оптимистичное, правда? . Каждого в изолированную одиночную камеру. Никакими способами они общаться ни с кем не могут. В каждой камере имеется лампочка. Про эту лампочку известно, что она либо горит весь день, либо весь день не горит.
Имеются два типа тюрем:
1 тип.
В тюрьмах первого типа каждый день лампочка горит только в одной камере. В остальных двух камерах лампочки не горят. Закон выбора камеры, в которой в данный день зажгут лампочку, мудрецам не известен.
2 тип.
В тюрьмах второго типа в течение первых N дней лампочки зажигают по тому же принципу, как и в тюрьмах первого типа (т.е. лампочка каждый день горит только в одной камере а начиная с N+1-го дня лампочки каждый день зажигают в двух камерах, а в третьей не зажигают. Закон выбора камер, в которых в заданный день зажгут лампочки мудрецам не известен. Число N мудрецам неизвестно.
Теперь самое любимое моё место в постановке задачи:
После того, как мудрецы отсидят счётное число дней... их поведут на Страшный-Престрашный Суд, где каждому независимо зададут один и тот же вопрос: "В тюрьме какого типа они сидели?". Если большинство (т.е. хотя бы 2 из 3-х) мудрецов ответят правильно, то они все... э-э... выйдут на свободу и вообще молодцЫ, а если большинство ответит неправильно, то э-э... ну их снова посадят, но уже на континуум дней и вообще они проиграли...
До попадания в тюрьму мудрецы могут обменяться произвольной информацией (выбрать стратегию поведения). Подчёркиваю еще раз, что всё время отсидки и после нее мудрецы обмениваться информацией не могут. Задача математическая, никаких подвохов нет.
Внимание вопрос: как должны действовать мудрецы?
P.S. Если кто-то уже решал эту задачу, то просьба не беспокоиться - дайте и другим попробовать.

sfmike

А известно хотя бы распределение вероятности? Иначе задача ИМХО бессмысленна.

Vano

По-моему, я нигде не употреблял слово вероятность...
Насчет бессмысленности задачи... Давай не будем об этом?
А вот решение она имеет.

sfmike

Ну лампочки зажигаются в каждой комнате с определенной вероятностью. Ее распределение нужно знать. Например знать что это равномерное распределение. Иначе ничего сказать нельзя.

Vano

Можешь считать, что тюремщики играют против мудрецов. Т.е. тюремщики знают, какой именно информацией обменялись мудрецы и какую стратегию поведения они выбрали. И эти самые тюремщики сами решают каждый день, в какой(-их) камере(-ах) зажечь свет так, чтобы мудрецы в итоге облажались. А уж кидают они кости или имеется у них детерминированный алгоритм - сиё мудрецам неизвестно.

sfmike

Ты не ответил на мой вопрос. Можем ли мы быть уверены что вероятности P( {0,1,0} ) == P( {1,0,0} ) == P( {0,0,1} где {} - исходы(0 - лампочка не горит, 1 - горит). Мы хоть что-нибудь об этом знаем?

Vano

Коротко - НЕТ.
Намекаю еще раз, что процедура выбора камеры может быть, например, детерминированной, а не случайной.
Но если тебе удобнее мыслить в терминах теорвера, то можешь себе представить, что, скажем, каждый день распределение новое, т.е. существует счётное семейство вероятностных мер P_n(. обладающее свойством
P_n( {1,0,0} ) + P_n( {0,1,0} ) + P_n( {0,0,1} ) = 1
Всё. Мудрецы не знают P_n ни для какого n.

sasha_m

где каждому независимо зададут один и
Когда задавать вопрос будут, мудрецы слышат ответы друг друга? Вроде да.А очередность ответов задают охраники или мудрецы сами выбирают кто отвечает из них? И ещё: Они сидеть будут Меньше или больше N дней? Это оговаривается или нет?

Vano

Когда задавать вопрос будут, мудрецы слышат ответы друг друга? Вроде да
Нет, не будут. Это я подразумевал под словом независимо, сорри, если непонятно выразился. Ну а даже если будут, то это упрощает жизнь?
А очередность ответов задают охраники или мудрецы сами выбирают кто отвечает из них?
Поскольку мудрецы не слышат ответов друг друга, то это не важно. Но даже если слышат и сами выбирают порядок ответа, то это упрощает жизнь?
Они сидеть будут Меньше или больше N дней? Это оговаривается или нет?
Разъясняю: мудрецы сидят счётное число дней. Именно счётное - ровно столько дней, сколько есть натуральных чисел (1,2,3... и т.д.).
В частности, они сидят больше любого наперед заданного числа N. Говорю же - для математиков задача :-

natunchik

А ты умеешь доказывать, что для решения необходима аксима выбора?
Или ты знаешь решение без неё?

stm25972421

а я вроде зарюхал... если опять не отошьет...

olga58

каждый мудрец говорит если у него горела лампа больше чем M/3 дней лампа варинт 2. если меньше, то вариант 1. M>N.

stm25972421

это даже я скажу что нет.

olga58

а почему?

sasha_m

В данной задаче М = бесконечности

olga58

они ж когда нибудь из тюрьмы выдут =)

sasha_m

Говорю же - для математиков задача :-

olga58

где палех?
пусть он скажет, прав ли я или нет.

Vano

нет

Vano

тоже неправильно или я не понял предлагаемого решения
напиши поподробнее в приват

stm25972421

я те скажу, что не прав. потому что
1: треть бесконечности - это сурово
2: в тюрьме 1 лампа попеременно тольеко у 1 и 2. оба говорят 2
3: подобный вариант был. Палех ответил нет

Thanhsoa

Иначе говоря, для каждого мудреца ты пытаешься оценить предел последовательности дробей A_n/n, где A_n - количество дней, в течение которых в его камере лампочка горела в течение первых n дней. Так вот, прежде чем сравнивать этот предел с чем-либо, нужно сначала убедиться, что он существует. А существует он не всегда.

Vano

Куда ж без аксимы выбора?
В известном мне решении она в явном виде не участвует (рассуждение "и из множеств этого семейства выберем по одному элементу" отсутствует но без нее решение будет неверным.
Поправка: а может быть и верным, кстати, не задумывался.

zuzaka

я, пожалуй, не буду анализировать свое решение, т.к. иду спать - даже если неправильное, будет хотя бы для затравки.
Итак. Если с какого-то момента чувак увидел, что частота зажигания у него превысила половину и таковой и осталась до конца (вот тут и нужна счетность) - значит, он говорит, что тип 2. Иначе - тип 1.

olga58

нафиг им между собой догавариваться если они потом не могут даже ответ друг друга услышать.

Thanhsoa

Для камер обоих типов можно придумать такие правила зажигания лампочек, что верхний предел частот зажиганий для каждого из мудрецов будет равен 1, а нижний 0.

Vano

выше уже сказал, почему это неправильно.

zuzaka

Не понял. Где? Если про пределы 0 и 1, то это неправда: для счетной суммы единичек и нулей нельзя придумать последовательность с разными суп и инф.

stm25972421

зачем это единичек и 0. кто говорит про 1 и 0. ? ;-)

Vano

я правильно понял, что ты предложил
a_n = {0,1}
0 - не горит
1 - горит
S_n = \sum_{k=1}^{n} a_k / n
и утверждаешь, что последовательность S_n сходится для любой последовательности a_n? Или что?

zuzaka

да, правильно. Если я не прав, привежи пример

Vano

ok, завтра приведу, на сегодня я всё...

Thanhsoa

Рассмотрим в качестве частного случая тюрьму первого типа (идея построения для тюрьмы второго типа такая же). Первые 10^1 дней лампа горит в 1-й камере. Следующие 10^4 лампа горит во 2-й камере. Следующие 10^9 дней лампа горит в 3-й камере. Следующие 10^16 дней лампа горит в 1-й камере. Так далее. Длина промежутка растет как 10^(k^2 k=1,2,3,....,бесконечность. Легко видеть, что для каждой камеры последовательность частот не является сходящейся и в ней будут встречаться члены со сколь угодно большим номером, сколь угодно близкие к 0 или к 1.

natunchik

Пример: у мудреца №1 лампочка горит всё время. Последовательность расходится.

Thanhsoa

Скорее сходится и состоит из одних единиц. Там деление на n.

vitamin8808

моё решение :
Воспользуемся следующим фактом :
Теорема Банаха. Существует такой линейный функционал F на множестве всех ограниченных последовательностей, что
1. F(a_n) \in closure(range(a_n
То есть для последовательности из нулей и единиц это нуль или единица.
2. Если a_n сходится, то F(a_n) равно пределу этой последовательности.
Ну там ещё свойства, но они мне не пригодятся(линейность я уже упомянул !)
Ну так вот, мудрецы фиксируют этот функционал, договариваются, что горит - 1, не горит -- 0 и
запоминают последовательности.
Потом вычисляют F(...) от своих последовательностей, и у кого получилось > 1/2 говорит что
второй тип, остальные первый.

vitamin8808

Тупняк. Бери последовательность, в которой то очень много нулей, то очень много единиц.
Не сойдётся.
Блин, это я -e отвечал.

Thanhsoa

Ну, во-первых, у тебя хотя бы число, с которым сравнивать нужно, неверно подобрано.
Контрпример:
1-я комната: a_i=1;
2-я комната: a_i=i(mod 2);
3-я комната: a_i=i+1(mod 2);
(здесь я под a_i понимаю индикатор того, горит ли лампочка на i-й день)
Тогда предел частот в 1-й комнате равен 1, во 2-й и 3-й равен 0.5
По твоему алгоритму два мудреца скажут "1-й тип", хотя тюрьма, очевидно, 2-го типа.

natunchik

> Если a_n сходится, то F(a_n) равно пределу этой последовательности.
Сам же сказал, что a_n не обязана сходиться =)

vitamin8808

исправил, просто не >=2/3, а >1/2. Остальное также. Всегда в арифметике ошибаюсь

PS Блин, 2/3 тож подходит. Ж

vitamin8808

И чего ? не вижу противоречия...

vitamin8808

кстати, неверно, что F(обобщённый предел) a_i=i mod 2 равен 1/2.

Thanhsoa

Так, теперь разбираемся дальше.
Рассматриваем уже приведенный пример, где в 2-х комнатах частоты равны 0.5
Если ты выбираешь порог >0.5 (строгое неравенство то будем считать, что в третей комнате постоянно горела лампочка, то есть тюрьма была 2-го типа. Видим, однако, что двое мудрецов утверждают обратное.
Если же выбрать порог >=0.5 (нестрогое неравенство то можно предположить, что в третей комнате лампочка, наоборот, была всегда выключена, то есть тюрьма была 1-го типа, и снова получаем, что мудрецы ошиблись.

vitamin8808

Ничего не понял... Откуда ты берёшь свои 0.5 к каким-то __несходящимся__ последовательностям ?
И какие последовательности ты рассматриваешь тоже не понятно.

Thanhsoa

Все-таки уточни, что ты понимаешь под a_i и предел чего ты считаешь.
Я под a_i понимаю индикатор того, горит ли лампочка в камере на i-й день, а считаю предел частот. То есть я предполагал, что ты все-таки применяешь теорему не к последовательности индикаторов, а к последовательности частот...

natunchik

Имеется в виду следующий вопрос: если мудрец видит последовательность вида a_i = i mod 2, он что говорит? И, соответственно, может ли он сказать что-нибудь другое на последовательность a_i = (i + 1) mod 2.
Если на обе последовательности мудрец вынужден говорить одно и то же, то задача решения не имеет.

plugotarenko

Смотрите, вот здесь
есть метод, который позволяет функционал определить как надо. Решение после этого доводится не очень сложно:)

Thanhsoa

Не мог бы ты написать нечто более содержательное? Какой именно метод? Что значит "как надо"?

natunchik

Вот тут дяденька ругается словом "Ультрафильтр" и заморачивается на тему аксиомы выбора.
Поскольку я не очень представляю себе, что такое ультрафильтр, то не могу точно сказать, дохнет ли оно на нашем примере.
Я щаз пытаюсь сформулировать, что нужно доказать, чтобы показать, что нет решения.

vitamin8808

Объясняю подробнее -- получили три последовательности a_n, b_n, c_n.
a_n+b_n+c_n=1 or 2 \forall n>=N => F(a_n+b_n+c_n)="prison type".
F(a_n F(b_n F(c_n) это число нуль или единица.

Thanhsoa

F(a_n F(b_n F(c_n) это число нуля или единица.
Здесь следует читать "от нуля до единицы" или "ноль или единица"?

vitamin8808

как написано.
F(a_n) is in the closure of the range of a_n

Nefertyty

> Ну так вот, мудрецы фиксируют этот функционал
Они успеют это сделать до того, как отправятся по камерам.
Хватит ли для этого конечного времени?

zuzaka

Короче, я сам придумал тот пример, где посл-ть расходится (напр, 1001110000001...)

denis85

УГАРНАЯ ЗАДАЧКА! Вот решение:
Мудрецы просидели М дней (М>N). На вопрос каждый мудрец должен ответить следующее: Если в последний день отсидки у него горела лампочка, то 2 тип тюрьмы, если не горела - то 1 тип!

denis85

Т.к. счетное число дней, то М будет больше N!
Первый нах!

dimkaL

нет последнего дня..они отсидели счетное число дней, да и возможности найти M>N нет никакой

denis85

Если нет последнего дня, то как им будут вопрос задавать?

plugotarenko

Бог с них спросит на Страшном суде.

dimkaL

Представь себе например что iый день в тюрьме длится в 2^ i раз меньше обычного

natunchik

Ок. Про функционал я почти понял.
А можно теперь доказательство того, что если они так делают, то в результате выигрывают?
Ты как бы упомянул два свойства - линейность и то, что F({0}) = 0, F({1}) = 1. Больше про этот функционал ты вообще ничего не сказал.
Да, по поводу линейности - как ты складываешь наши последовательности (из 0 и 1 и умножаешь их на число? Ты же каждый раз будешь вываливаться в более широкий класс последовательностей вообще. Или я не понимаю, что имеется в виду под словами "линейный функционал"?

plugotarenko

Этот линейный функционал определен на пространстве ограниченных последовательностей и равен пределу данной последовательности, если он существует. А если не существует, то равен одной из предельных точек. Последовательности складываются почленно и умножаются на число тоже почленно.
Соответственно сумма трех последовательностей в первой тюрьме - {1,1,1....}, а во второй - {2,2,2....}. Значения функционала на каждой последовательности либо 0, либо 1.
Таким образом в первой тюрьме у мудрецов будет набор значений функционалов 1,0,0
А во второй тюрьме - 1,1,0.

vitamin8808

Ты как бы упомянул два свойства - линейность и то, что F({0}) = 0, F({1}) = 1. Больше про этот функционал ты вообще ничего не сказал.
Как бы ? Что значит "больше ничего не сказал" ? Свойство номер один перечитай...

natunchik

Вот теперь верю.
А где можно в электронном виде про неё почитать? А то что-то гугль мне не помог и яндекс тоже.
И вопрос о конструктивном построении интересен. То есть как эти математики будут фиксировать функционал интересно.

Thanhsoa

Сомневаюсь, что это конструктивно делается...
Но, с другой стороны, если уж этим мудрецам под силу отсидеть в тюрьме счетное число дней, то может и такой функционал не будет для них проблемой..

Vano

Ну, смотрю, общими усилиями зарюхали похоже...

Thanhsoa

Скорее так: несмотря на общие усилия 'у запутать не удалось

plugotarenko

Конструктивно не строится. При доказательстве теоремы о существовании такого функционала используется лемма Цорна (или эквивалентные ей утверждения).
Кроме того, такой функционал не единственный.
Можно прочитать в КФ, искать теорему Хана-Банаха.
Идея для доказательства, использовнного Авовой факта, таже самая.
Сам факт в КФ обнаружен не был. Может плохо искал.

olga58

народ, а чем yellow неправ?

dumber

Да прав он, конечно!

natunchik

Задача - для _математиков_.

Sander

решил.

dumber

Мне вот непонятно, как в голове у математиков совмещается счетное (в математическом, а не обывательском смысле слова) число отсиженных дней и следующий за этим страшный суд?!
З.Ы. И вообще, можно для не математиков рассказать алгоритм по которому мудрецы должны выбрать вариант ответа (а не просто сказать, что такой существует).
З.З.Ы. ИМХО, если рассматривать "счетное" в общепринятом смысле, т.е. конечное число, то Йеллоу прав.

natunchik

> "счетное" в общепринятом смысле, т.е. конечное число.
Гы гы гы гы гы. Гы гы. Спасибо, повеселил.

sirp

специально для тех, у кого слабо развито математическое воображение, переформулирую задачу:
задано три бесконечных последовательности нулей и единиц (Ai, Bi и Сi)
Известно, что либо a) Ai+Bi+Ci=1 для всех i,
либо б) cуществует такое N, что Ai+Bi+Ci=1 для всех i<N, и Ai+Bi+Ci=2 для остальных i.
Задача: построить функции(функционалы) f(A g(B h(C) принимающие значения 0 или 1 такие, чтобы в случае a) хотя бы две из трех функций дали 0, в случае б) хотя бы две из трех функций дали 1.
Кстати, как я понял, в решении Avov'ы нужный результат дают ровно две из трех функций.

plugotarenko

построить функции(функционалы)
Тут ты немного загнул. Существуют ли такие функционалы, что.....? так лучше.

dumber

Интересно, а какое же еще общеупотребительное значение имеет слово "счетное" ?
З.Ы. Я ж написал, что если мы будем понимать "счетное" не как бесконечное нумеруемое натуральным рядом, а как это понимают 95% населения нашей планеты, т.е. "конечное" (в противовес "несчетному", "бесчетному" то Йеллоу будет несомненно прав.
З.З.Ы. Мне просто сложно представить как после счетного (в математическом значении) количества дней может быть этот хренов ссудный день. И каким таким образом при этом невозможно сказать ничего о дне предшествующем?!
З.З.З.Ы. Это я к тому что, если ты такой умный, то мог бы повнимательнее вчитываться в мой пост и объяснить как возможно "З.З.Ы."

dumber

Я, наверно, невнимательно читал, но где ж такие функционалы были указаны в решении? Или вы просто утверждаете, что они есть? Можно поподробнее для людей не разбирающихся в математике, т.е. для меня!

plugotarenko

Счетное - это математический термин. И как термин это слово имеет только одно значение - мощность натурального ряда. Важно, что все математики понимают его одиноково. Как это слово понимают остальные мне все равно.
Если в данном случае место счетное понимать конечное задача из интересной превращается в бессмысленную. Есть математический факт про существование обобщенного предела. Его завернули в прикольную оболочку и все. Математики развлекаются.
Ты легко сможешь ответить на свой З.Ы.Ы, если ответишь на вопрос какой момент времени был сразу перед 20:20:18 10 апреля 2005 года от Р.Х. в третьем часов поясе от Гринвича?

dumber

Ты легко сможешь ответить на свой З.Ы.Ы, если ответишь на вопрос какой момент времени был сразу перед 20:20:18 10 апреля 2005 года от Р.Х. в третьем часов поясе от Гринвича?
Вот только не надо от темы уходить. Чтобы мудрец мог четко ставить единички и нолики сидя в тюрьме, он должен точно различать день текущий, предшествующий и следующий. И не знать ничего о "последнем" дне предварительного заключения находясь в ссудном дне он не может! Вообщем, видимо у математиков плохо с физической интерпретацией, плохая получилась обертка для математической задачи.

plugotarenko

У тебя плохо с воображением. Время не дискретно. Он различает текущий, предшествующий и следующий, а последнего нет. В чем противоречие?

olga58

а где последний день? его че нет?
блин, чесслово, сферический конь в вакууме.

sfmike

Ясным языком сказали, что задачка - для математиков. Судя по твоим постам ты не математик. Так чего ты хочешь? Ну нет последнего дня, и что? Тебя например не смущает тот факт что нет последнего рационального числа перед 1? А если ты будешь с постоянной скоростью двигаться вдоль оси ох, то ты проедешь 1. А значит и все рац.числа до 1. Ты при этом проедешь последнее рац. число? Нет. Ты их все проедешь? Да.

dumber

Время не дискретно.

А что поэтому поводу скажут физики?!

dumber

Ну вообщем, из всего этого топика я извлек то, что вы можете только доказать, что решение существует, но найти его вы не в состоянии. А также то, что обертка этой математической задачи крайне некорректна (ну не получилось у математиков соотнести свой "научный флуд" с реальностью. Как говориться Бог интегрирует эмпирически).
Спасибо за разъяснения!
Тебя например не смущает тот факт что нет последнего рационального числа перед 1? А если ты будешь с постоянной скоростью двигаться вдоль оси ох, то ты проедешь 1. А значит и все рац.числа до 1. Ты при этом проедешь последнее рац. число? Нет. Ты их все проедешь? Да.
Меня не смущает, так как все эти числа - это объективно несуществующие вещи, навыдумывать и смоделировать можно все что угодно.

sfmike

В состоянии. За бесконечно большое время. Блин. Сказано же, что задача для математиков. Физикам как обычно не понять/принять.

natunchik

Меня не смущает, так как все эти числа - это объективно несуществующие вещи, навыдумывать и смоделировать можно все что угодно.
Ахиллес бежит за черепахой. Ахиллес бегает в два раза быстрее черепахи (шустрая попалась). Изначально он находится в двух метрах от черепахи. Когда он пробегает два метра, черепаха успевает уползти на метр. За то время, пока он пробегает этот метр, черепаха успевает уползти ещё на полметра. И так далее.
Как ты думаешь, он её догонит?

olga58

конешна.

natunchik

Но ведь тогда получится, что эти моменты - когда он добегал до того места, где в предыдущий раз находилась черепаха - случались счётное число раз! Ах! Как же так!

Thanhsoa

Ну вообщем, из всего этого топика я извлек то, что вы можете только доказать, что решение существует, но найти его вы не в состоянии. А также то, что обертка этой математической задачи крайне некорректна (ну не получилось у математиков соотнести свой "научный флуд" с реальностью. Как говориться Бог интегрирует эмпирически).
Спасибо за разъяснения!
А потом такие вот люди выходят на улицы и: web page

AlexInes

Но ведь тогда получится, что эти моменты - когда он добегал до того места, где в предыдущий раз находилась черепаха - случались счётное число раз!
просто глупый подход!
берём фиксированные дискретные интервалы любой длины - решение = перегонит
тоже самое и с этой задачей ...
существование последнего дня есть факт наличия дня Страшнага_Сюда
при переходе к счётному числу дней => потеря детерминированности дня С_С
решение элементарно, если не думать слишком много и долго = оно приходит в голову само ...

AlexInes

и не пытайтесь придумывать последовательности - их не требуется ...
нельзя привязывать фиксированную величину дня как единицы измерения к зависимости от номера дня
Оставить комментарий
Имя или ник:
Комментарий: