Еще одна задачка.

[qaz]

  Цитата

  Цитата

link=topic=160873.msg2023675493#msg2023675493 date=1288464967]

  Цитата

  Цитата

link=topic=160873.msg2023675399#msg2023675399 date=1288464341]

1 взвешивание - максимум 3 монеты. не очень сложно посмотреть на 4 монеты и понять, что ничего не выйдет. а потом индукция (как то так это называется)

как происходит переход индукции? как ты от 3х монет к большему числу перейдешь? тоже аргументами типа ну "очевидно что 82 мы не сможем взвесить"?

зачем так копаться то. просто в следующем шаге в роли монеты будет куча из 27 монет. и мы снова вернемся к ситуации с 3-мя монетами.

а может можно как нибудь сделать кучи по 28-27-27. почему нельзя. есть более изысканное доказательство.

ну так взвесь эти три кучи, допустим при взвешивании 27 и 27 они получились равны, значит монета в куче из 28, а теперь за 3 взвешивания определи-ка какая там фальшвая монета умник

[_Koto]

  Цитата

  Цитата

Старо наверно, но выложу всетаки:

 

Есть три бога: A, B и C, которые являются богами истины, лжи и случая в произвольном порядке. Бог истины всегда говорит правду, бог лжи — всегда обманывает, бог случая может говорить и правду, и ложь в произвольном порядке. Требуется определить богов, задав 3 вопроса, на которые можно ответить «да» или «нет». Каждый вопрос задаётся только одному богу. Боги понимают язык, но отвечают на своём языке, в котором есть 2 слова «da» и «ja», причём неизвестно, какое слово обозначает «да», а какое «нет».

уточнения:

Можно задавать одному богу более чем один вопрос (поэтому другим богам может быть не задано ни одного вопроса вообще).

Каков будет следующий вопрос и кому он будет задан, может зависеть от ответа на предыдущий вопрос.

Бог случая отвечает случайным образом, зависящим от подбрасываний монетки, спрятанной в его голове: если выпадет орел, то отвечает правдиво, если решка — то врёт.

Бог случая отвечает «da» или «ja» на любой вопрос, на который можно ответить «да» либо «нет».

И еще: Нельзя задавать вопросы - "парадоксы", на которые можно ответить и "da" и "ja", или никак нельзя ответить. К примеру, "Ты сейчас ответишь "da"?

 

из разряда  

 

Спросим бога B: Если я спрошу у тебя Бог А — бог случая?, ты ответишь „ja“?.

Если бог B отвечает «ja», значит, либо он бог случая , либо он не бог случая, а на самом деле бог A — бог случая. В любом варианте, бог C — это не бог случая. Если же B отвечает «da», то либо он бог случая , либо B не бог случая, что означает, что бог А — тоже не бог случая. В любом варианте, бог A — это не бог случая.

Спросим у бога, который не является богом случая :

Если я спрошу у тебя: ты бог правды?, ты ответишь „ja“?.

Поскольку он не бог случая, ответ  «ja» обозначает, что он бог правды, а ответ «da» обозначает, что он бог лжи.

Спросим у этого же бога

Если я у тебя спрошу: „Бог B — бог случая?“, ответишь ли ты „ja“?.

Если ответ «ja» — бог B является богом случая, если ответ «da», то бог, с которым ещё не говорили, является богом случая.

 

Решали на логике

Показать больше  

мы же незнаем pro ja i da

[Rise[Lich]]

  Цитата

  Цитата

link=topic=160873.msg2023675493#msg2023675493 date=1288464967]

  Цитата

  Цитата

link=topic=160873.msg2023675399#msg2023675399 date=1288464341]

1 взвешивание - максимум 3 монеты. не очень сложно посмотреть на 4 монеты и понять, что ничего не выйдет. а потом индукция (как то так это называется)

как происходит переход индукции? как ты от 3х монет к большему числу перейдешь? тоже аргументами типа ну "очевидно что 82 мы не сможем взвесить"?

зачем так копаться то. просто в следующем шаге в роли монеты будет куча из 27 монет. и мы снова вернемся к ситуации с 3-мя монетами.

а может можно как нибудь сделать кучи по 28-27-27. почему нельзя. есть более изысканное доказательство.

мде. будем доказывать по индукции утверждение "за n взвешиваний максимум можно узнать фальшивую из 3ⁿ гребаных монет". база ясна. суть перехода заключается в том, чтобы рассматривать с последнего взвешивания. в последнем взвешивании должно быть 3 гребаных монеты. иначе можно больше, исходя из базы. Итак, значит на последнем ходу ты взвешивал 3 гребаных монеты. Сколько же ты взвешивал на предпоследнем. Ясно понятно, что 9, иначе, если больше, то это противоречит базе. а если меньше то можно добавить еще одну монету. Что тут неясного. Итого если взвешивания 4, то ответ 81

[Vanys]

если не знаем про ja i da, тогда она не решается

[_Koto]

там написали решение,но я признаться нифига про первый вопрос непонял..

P.S. когда бог B оказывается богом случая,и ему выпадает первый вопрос,то я вообще невижу ответа О_О  с учётом незнания про Ja i DA

[Hunter]

да и бтв вспомнил, что раньше как раз верно решал эту задачу :(

а формула у меня всё равно косячная

[Гость kax]

  Цитата

там с определённого номера начинают слагаемые равняться 0

но у меня не совсем верно

нашёл на хабре ответ

хотя формула почти верная

Не сдержался, хотя был близок  :._.:

[adskii_troglotit]

  Цитата

  Цитата

  Цитата

link=topic=160873.msg2023675493#msg2023675493 date=1288464967]

  Цитата

  Цитата

link=topic=160873.msg2023675399#msg2023675399 date=1288464341]

1 взвешивание - максимум 3 монеты. не очень сложно посмотреть на 4 монеты и понять, что ничего не выйдет. а потом индукция (как то так это называется)

как происходит переход индукции? как ты от 3х монет к большему числу перейдешь? тоже аргументами типа ну "очевидно что 82 мы не сможем взвесить"?

зачем так копаться то. просто в следующем шаге в роли монеты будет куча из 27 монет. и мы снова вернемся к ситуации с 3-мя монетами.

а может можно как нибудь сделать кучи по 28-27-27. почему нельзя. есть более изысканное доказательство.

ну так взвесь эти три кучи, допустим при взвешивании 27 и 27 они получились равны, значит монета в куче из 28, а теперь за 3 взвешивания определи-ка какая там фальшвая монета умник

так это вы должны доказать почему нельзя 28 за 3 взвешивания. а если бы в задаче взвешиваний было 142981857123075230852375 взвешиваний, вы бы тоже ссылались на очевидность?

[qaz]

  Цитата

  Цитата

  Цитата

  Цитата

link=topic=160873.msg2023675493#msg2023675493 date=1288464967]

  Цитата

  Цитата

link=topic=160873.msg2023675399#msg2023675399 date=1288464341]

1 взвешивание - максимум 3 монеты. не очень сложно посмотреть на 4 монеты и понять, что ничего не выйдет. а потом индукция (как то так это называется)

как происходит переход индукции? как ты от 3х монет к большему числу перейдешь? тоже аргументами типа ну "очевидно что 82 мы не сможем взвесить"?

зачем так копаться то. просто в следующем шаге в роли монеты будет куча из 27 монет. и мы снова вернемся к ситуации с 3-мя монетами.

а может можно как нибудь сделать кучи по 28-27-27. почему нельзя. есть более изысканное доказательство.

ну так взвесь эти три кучи, допустим при взвешивании 27 и 27 они получились равны, значит монета в куче из 28, а теперь за 3 взвешивания определи-ка какая там фальшвая монета умник

так это вы должны доказать почему нельзя 28 за 3 взвешивания. а если бы в задаче взвешиваний было 142981857123075230852375 взвешиваний, вы бы тоже ссылались на очевидность?

лич пару постов выше, даже специально на один пост ниже отписал тебе в обшем виде для любого количества взвешиваний, а я тебе конкретно пояснил на данном примере, чтобы ты понял и переключился на другую задачу :._.:

[Rise[Lich]]

  Цитата

  Цитата

  Цитата

  Цитата

link=topic=160873.msg2023675493#msg2023675493 date=1288464967]

  Цитата

  Цитата

link=topic=160873.msg2023675399#msg2023675399 date=1288464341]

1 взвешивание - максимум 3 монеты. не очень сложно посмотреть на 4 монеты и понять, что ничего не выйдет. а потом индукция (как то так это называется)

как происходит переход индукции? как ты от 3х монет к большему числу перейдешь? тоже аргументами типа ну "очевидно что 82 мы не сможем взвесить"?

зачем так копаться то. просто в следующем шаге в роли монеты будет куча из 27 монет. и мы снова вернемся к ситуации с 3-мя монетами.

а может можно как нибудь сделать кучи по 28-27-27. почему нельзя. есть более изысканное доказательство.

ну так взвесь эти три кучи, допустим при взвешивании 27 и 27 они получились равны, значит монета в куче из 28, а теперь за 3 взвешивания определи-ка какая там фальшвая монета умник

так это вы должны доказать почему нельзя 28 за 3 взвешивания. а если бы в задаче взвешиваний было 142981857123075230852375 взвешиваний, вы бы тоже ссылались на очевидность?

Ты такой умный. Я тебе так завидую.

 

  Показать содержимое

мде. будем доказывать по индукции утверждение "за n взвешиваний максимум можно узнать фальшивую из 3n гребаных монет". база ясна. суть перехода заключается в том, чтобы рассматривать с последнего взвешивания. в последнем взвешивании должно быть 3 гребаных монеты. иначе можно больше, исходя из базы. Итак, значит на последнем ходу ты взвешивал 3 гребаных монеты. Сколько же ты взвешивал на предпоследнем. Ясно понятно, что 9, иначе, если больше, то это противоречит базе. а если меньше то можно добавить еще одну монету. Что тут неясного. Итого если взвешивания 4, то ответ 81

 

[adskii_troglotit]

  Цитата

link=topic=160873.msg2023675597#msg2023675597 date=1288465696]

мде. будем доказывать по индукции утверждение "за n взвешиваний максимум можно узнать фальшивую из 3ⁿ гребаных монет". база ясна. суть перехода заключается в том, чтобы рассматривать с последнего взвешивания. в последнем взвешивании должно быть 3 гребаных монеты. иначе можно больше, исходя из базы. Итак, значит на последнем ходу ты взвешивал 3 гребаных монеты. Сколько же ты взвешивал на предпоследнем. Ясно понятно, что 9, иначе, если больше, то это противоречит базе. а если меньше то можно добавить еще одну монету. Что тут неясного. Итого если взвешивания 4, то ответ 81

проще можно просто потому что за 1 взвешивание мы получаем 1 трит информации. за n взвешиваний n тритов информации. значит мы можем определить фальшивую только из 3^n.

 

 

[YahooOMG]

Из 3х элементов за одну взвешивание можно определить фальшивый. Если элементов больше 3х - взвешиваний придется делать больше. Поэтому для подсчета максимального кол-ва монет и берем степень 3ки.

[adskii_troglotit]

  Цитата

link=topic=160873.msg2023675639#msg2023675639 date=1288466108]

  Цитата

  Цитата

  Цитата

  Цитата

link=topic=160873.msg2023675493#msg2023675493 date=1288464967]

  Цитата

  Цитата

link=topic=160873.msg2023675399#msg2023675399 date=1288464341]

1 взвешивание - максимум 3 монеты. не очень сложно посмотреть на 4 монеты и понять, что ничего не выйдет. а потом индукция (как то так это называется)

как происходит переход индукции? как ты от 3х монет к большему числу перейдешь? тоже аргументами типа ну "очевидно что 82 мы не сможем взвесить"?

зачем так копаться то. просто в следующем шаге в роли монеты будет куча из 27 монет. и мы снова вернемся к ситуации с 3-мя монетами.

а может можно как нибудь сделать кучи по 28-27-27. почему нельзя. есть более изысканное доказательство.

ну так взвесь эти три кучи, допустим при взвешивании 27 и 27 они получились равны, значит монета в куче из 28, а теперь за 3 взвешивания определи-ка какая там фальшвая монета умник

так это вы должны доказать почему нельзя 28 за 3 взвешивания. а если бы в задаче взвешиваний было 142981857123075230852375 взвешиваний, вы бы тоже ссылались на очевидность?

Ты такой умный. Я тебе так завидую.

 

  Показать содержимое

мде. будем доказывать по индукции утверждение "за n взвешиваний максимум можно узнать фальшивую из 3n гребаных монет". база ясна. суть перехода заключается в том, чтобы рассматривать с последнего взвешивания. в последнем взвешивании должно быть 3 гребаных монеты. иначе можно больше, исходя из базы. Итак, значит на последнем ходу ты взвешивал 3 гребаных монеты. Сколько же ты взвешивал на предпоследнем. Ясно понятно, что 9, иначе, если больше, то это противоречит базе. а если меньше то можно добавить еще одну монету. Что тут неясного. Итого если взвешивания 4, то ответ 81

 

я медленно печатаю. просто взгляд на типовые задачи с точки зрения информации, они кажутся уже НАМНОГО ПРОЩЕ. хотел чтобы ты догадался =) no offence. вот только qaz тупенький

[Vanys]

задача

 

  Показать содержимое

11заключеных.

им завязывают глаза, ставят в круг и одевают каждому шапку. Потом развязывают глаза, каждый должен сказать да или нет(каждый говорит только 1 раз). Потом каждого отводят в свою камеру и спрашивают какого цвета его шапка, если он угадывает - свободен. у шапок 1000 цветов. заключенные заранее обсуждают план действий. Как сделать, чтобы все вышли?

 

[Гость }Doodlez{]

эх мне бы олимпиаду физтеха осилить

[_Koto]

ээ,куда делся автор задачи с богами,тот ответ от goanal правильный? просто вроде он отгадывал зная ja и da,но если незнать то это же эпик,у меня вышло за 3 вопроса узнать только тот бог с которым  я говорю бог случая или нет,и ja и da что значит,т.е. за 5 вопросов смог бы узнать а за 3 сложно О_О

[iT_Chemist]

rise[lich], ссаненькая какая-то индукция у тебя

 

  Цитата

задача

 

  Показать содержимое

11заключеных.

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

 

ояебу

[_Koto]

чемист ты пробовал отгадать про богов ? :)

[iT_Chemist]

  Цитата

чемист ты пробовал отгадать про богов ? :)

да вроде я ее решил даже. мне просто не ответили на мой вопрос или я профтыкал. если боги знаю не только себя но и кто есть кто среди оставшихся, то вроде не сложно

[Гость kax]

  Цитата

задача

 

  Показать содержимое

11заключеных.

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

 

Каждый должен угадать свой цвет? Или хотя бы один?