открытая тема

[avva]

Комменты о чем угодно.

Хотите об этом поговорить?

Comments

[butbka.livejournal.com]

Просто делюсь интересной задачей, которая съела у меня много времени.

В магазине имеется три компьютера: американский, русский и китайский. Все могут ответить на ЛЮБОЙ yes-no question (обладают абсолютным знанием).

Американский отвечает на такие вопросы всегда истину. Китайский всегда врёт. Русский отвечает случайно: (кидает монетку и по результатам - да или нет).

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

Перед покупкой можно задать ОДИН yes-no question, любому, но ТОЛЬКО ОДНОМУ компьютеру.

Какой вопрос необходимо задать?
Ну и, естественно, какой компьютер по результатам ответа выбрать?

[(Anonymous)]

Ты лжешь? Для компьютера с детерминированными ответами результат - нет. Для русского компьютера - ответ может быть да.

[(Anonymous)]

Ну или какой-нибудь парадокс. Детерминированный компьютер зависнет?

[butbka.livejournal.com]

Никаких подвохов и парадоксов. Точное строгое решение.

[(Anonymous)]

Но на любой вопрос русский компьютер может ответить так-же как и детерминированный.

[(Anonymous)]

Хотя парадокс уже не будет yes-no question.

[butbka.livejournal.com]

Не катит.
Компьютер ответил: "нет" (может быть русским). Кого покупать будем?

[timur0.livejournal.com]

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

[(Anonymous)]

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

[timur0.livejournal.com]

блин, я дурак! если два американских и один русский, то решается элементарно: спрашиваем у первого компа "второй комп американский?". если ответил "да", то берем второй, если ответил "нет", берем третий.

с китайским компом тоже что-то придумается

[drw.livejournal.com]

Нужно спросить так: «Верно ли, что если ты сделан в америке, то на этот вопрос ты ответишь "нет", а если ты сделан в китае, то на этот вопрос ты ответишь "да"». Все детерминированные компьютеры зависнут без пизды.

[(Anonymous)]

только это не yes-no question

[drw.livejournal.com]

Вопрос, начинающийся со слов "верно ли, что", предполагает ответы "да, верно" и "нет, неверно".

[isk.livejournal.com]

- ты китайский компьютер?
если ответ нет, брать его.
если да, то любой из двух других.
вероятность ошибиться 1/6

[(Anonymous)]

а потом русский компьютер воьзмет и посчитает ваши налоги так, что вы сядете на десять лет. зато с вероятностью всего 1/6.

[isk.livejournal.com]

дело в том, что при заданных условиях лучшей вероятности получить нельзя.
да и замучаетесь вы считать налоги с помощью yes-no question %)

[n0-spam.livejournal.com]

Думаю, копать нужно в двух направлениях:

1) Как всегда в подобных задачах, интересоваться у данного компьютера что на тот или иной счет думает другой комп ("Что бы на этот вопрос ответил китайский компьютер?" или "Что вот этот вот соседний компьютер ответил бы на такой вопрос...").

2) Нужно спрашивать о возможности однозначного ответа. Типа "Может ли вот этот комп дать однозначный ответ на такой вопрос..."

[markvs.livejournal.com]

Берете ОЧЕНЬ большое простое число (10000 цифр), и спрашиваете любой компьютер: верно ли, что это число простое. Если компьютер задумывается больше, чем на 10 секунд, вы его берете. Если отвечает сразу, берете один из двух других. Для более интеллигентных компьютеров подходит вопрос: верна ли гипотеза Римана, с тем же результатом.

[isk.livejournal.com]

во первых, компьютеры обладают абсолютным знанием
во вторых, в компьютер может быть встроена задержка (особенно в русский)

[markvs.livejournal.com]

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

[butbka.livejournal.com]

Пока верных ответов нет.
Задача решается.
Вопрос, естественно, можно задавать только корректный - имеющий однозначный ответ.

[avva.livejournal.com]

Я знаю ответ, просто не хочу вмешиваться. Это не самая сложная задача такого вида - есть сильно муторнее, напр. http://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever.

[kum-tykva.livejournal.com]

Да она вовсе не сильно муторнее, просто все эти "da/ja"-неизвестности надо вводить сразу на первых задачках этой серии, когда встретил кого-то и надо выбрать правильную дорогу -- и тогда вывести главное правило, про одинаковый/разный сигнал на входе и выходе.
На самом деле даже по ссылке ее недостаточно "замуторнили", можно было бы добавить, что для разных богов пара "da/ja" может быть еще и в разных ролях у разных божков, а там они все-таки на одном языке говорят. Хотя, как я уже сказал, "муторности" оно все равно не добавляет.

[timur0.livejournal.com]

Спрашиваем первый комп: "Второй - китаец ИЛИ третий - американец?"
Если ответ "Да", берем второй комп, если "Нет" - третий.

[butbka.livejournal.com]

Можно обойтись простым вопросом без И и ИЛИ