ponom

Не сложная. Математика нужна. На решение ушла 1 минута. Никуда не смотрел, ваши решения не читал.

Обозначим все монеты как Mi, где i меняется от 0 до 63, а Mi принимает значения 0 (орел) или 1 (решка).

Вычислим сумму по модулю два (XOR) произведений позиций монет на их значения:


S - будет числом в диапазоне 0...63 и, таким образом, указывать на позицию монеты от 0 до 63.

Пусть P - номер позиции магической монеты. Вычислим сумму по модулю два S и P.

Эта сумма и будет номером монеты, которую нужно перевернуть.

     

R60

И как ты эту сумму передашь второму заключенному? Это уже выяснили, что можно только передвинуть одну фигуру, сообщать числа нельзя.

     

ponom

Зачем ее передавать? Он посмотрит на доску и вычислит в уме эту сумму. Для вычисления суммы нужно лишь видеть монеты на доске.

     

R60

Давай по другому.
Проведем 2 эксперимента. 1. надзиратель указывает клетку А4, 2. надзиратель указывает А5. Как будет изменяться твоя формула для этих экспериментов? Она же должна меняться.
Мне кажется вы не можете понять что именно надзиратель выбирает магическую монету. Если бы заключенный, то ясно что они могут договориться об одной формуле, и находить по ней число. Но для этого и формула не нужна, можно просто договориться какую клетку выбирать.
А в голову надзирателя вы не залезете, он может выбрать любой из 64 вариантов, поэтому договориться об одной формуле нереально. Переворачиванием одной монеты можно сократить область поиска, но не указать точное местоположение.

     

ponom

Формула не меняется. Меняется ответ, полученный по формуле - сумма по модулю два (оператор XOR) чисел S и P. Она четко зависит от P и после переворачивания монеты с полученным порядковым номером S начинает указывать на P.

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

Y xor X xor X = Y

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

     

R60

Хорошо, не формула меняется, а значение переменной в формуле. Поэтому и ответ меняется. Логично?
То что вы математически можете описать доску это понятно. Но в сотый раз повторю. У нас есть 3 действующих лица в задаче. Как в театре. Есть 64 варианта ответа, один из которых случайным образом выбирает надзиратель. Первый заключенный не может передать второму как изменилось значение переменной в формуле. Тоже логично? Поэтому точного ответа быть в принципе не может.

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

     

Одиссей

Только по модулю 64 все-таки.

-----------------
χαλεπὰ τὰ καλά

     

ponom

Почему? Я имею ввиду именно по модулю 2. Числа там будут 6-ти битные (0..63). И над ними должна выполняться побитная операция XOR (сложение по модулю 2).

https://ru.wikipedia.org/wiki/%D0%A...3%D0%BB%D1%8E_2

     

Одиссей

Да это я уже запутался. В таком варианте решения нужно ксорить побитно.

-----------------
χαλεπὰ τὰ καλά

     

R60

Ответ будет? Своими словами. И затем сравним с условиями задачи.

     

sineemore

"Здравый смысл" - это некоторая культурная концепция. Это выражение не во всех языках даже есть. Означать для разных людей разное может в разные эпохи.
Есть термины, им можно четкое определение дать.

Я не могу все прочитать, но....
Выражение
"Поскольку все крокодилы летают, Земля круглая" справедливо?

     

alexer

Выделенное — истинно с точки зрения формальной логики.

     

sineemore

А тогда будет справедливо, что "Земля круглая, потому что все крокодилы летают"?

     

alexer

Если Вы имеете ввиду высказывание "из того, что земля круглая следует, что все крокодилы летают", то это ложное высказывание, т.к. у него истинная посылка и ложное заключение. Это единственный случай, когда импликация ложна.
В общем, правила такие: импликация А=>B ложна, если A истинно, а B - ложно. В остальных случаях импликация истинна.

     

Димыч

Правила явно не такие. Эти правила явно нельзя применять к не относящимся друг к другу событиям. Это все равно, что пользоваться арифметическими правилами, складывая тёплое с мягким и вычитая из этой суммы громкое

     

sineemore

Нет, я имею в виду "Земля круглая, потому что все крокодилы летают". Здесь же явно круглость Земли следствие того, что летают крокодилы.

Ну "Все крокодилы летают, потому Земля круглая", если перевернуть , получится "Земля круглая, потому что все крокодилы летают"

     

Димыч

Конечно не справедливо. Разве могут быть в этом сомнения?
Земля - геоид, а не "круглая". А крокодилы тут не причем. Как и математика тоже.

     

R60

Я тюремщик, загадал монету на клетке В6, объясните каким образом её угадает второй заключенный.

     

Димыч

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

     

R60

Это что ответ? Как указала то?

     

Димыч

Это идея. Половина решения. Осталось только придумать алгоритм

     

R60

Вот ответ из гугля-
"Поначалу не мог понять — что же должен сделать второй заключённый? Про это как бы чётко не написано, хотя очевидно, с другой стороны. Но потом прояснилось: 1) посмотреть на доску 2) вычислить её чётность 3) получившееся шестизначное число в двоичной системе счисления перевести в десятеричную 4) это и есть номер «магической» клетки."
Чем это поможет угадать клетку не пойму.

     

sineemore

Не понимаю, как можно испытывать раздражение в теме, где фигурируют ложные крокодилы.

     

alexer

sineemore, Димыч не желает понимать, что напряжение, которое у него вызывает "истинность" странных утверждений выше — это парадоксы, а не ошибки. И парадоксы надо устранять, совершенствуя аксиоматику мат. логики, а уж никак не ссылаясь на "здравый смысл". Собственно, попытки это сделать были, но там свои, более глубокие парадоксы возникают и неочевидные аксиомы, до которых с позиций "здравого смысла" вообще не додуматься.

     

Димыч

Потом еще одно хочу отметить. У "так как" и "если" все-таки разный смысл.
"если" - это "предположение", а "так как" - это утверждение.
Над фразой "Если крокодилы летают, то я - королева" - уже можно подумать. Потому как тут довольно просто получается, что т.к. крокодилы не летают, то ты и не королева".
"Если" - это как раз и есть СВЯЗЬ, о которой я писал, и которой не хватало в приводимых примерах.
А когда говорят "Так как крокодилы летают, то...." - то здесь в первой части тезиса содержится УТВЕРЖДЕНИЕ, которое никакого отношения ко второй части тезиса не имеют.
Вот здесь у нас произошло основное непонимание, видимо
p.s. убегаю домой (наконец-таки)

     

alexer

Так, пока выдалась еще свободная минутка, публикую решение задачи про заключенных. Я не знаю, то ли это решение, которое Димыч нашел в сети: я его по дороге с работы придумал. Пусть Димыч напишет, совпадает ли: интересно.

Прежде всего, рассмотрим ту же задачу, когда есть всего две клетки. Я буду писать "0", когда монета повернута аверсом или "1" когда она повернута реверсом для простоты. Возможные варианты выкладывания монет следующие:
00, 01, 10, 11
Предлагается следующий код: когда обе монеты повернуты аверсом либо реверсом (т.е. выкладка 00 или 11), то "магическая" монета находится в первой клетке. В противном случае (т.е. когда выкладка была 01 или 10), то "магическая" монета лежит во второй клетке. Понятно, что перевернув любую монету, либо оставив все без изменений всегда можно закодировать правильное положение "магической" монеты.
Пример 1: выкладка 11, "магическая" монета во второй клетке. Можно попросить надзирателя перевернуть любую из монет.
Пример 2: выкладка 10, "магическая" монета в первой клетке. Снова можно попросить перевернуть любую, что приведет к выкладке 00 или 11, что является опять правильным кодом.
Важно: в предлагаемом коде принципиальным является то, что переворачивать можно любую монету или ни одну, это дает возможность масштабировать решение на бОльшие размерности.

Теперь, перейдем к размерности доски 2х2. Выпишим выкладку монет построчно, строка за строкой. Например 0111 будет означать, что в первой строке доски лежали монеты, развернутые аверсом и реверсом, а во второй обе повернуты реверсом. Я разобью строчку пополам, вот так: 01|11. В каждой из строчек посчитаю количество единиц. Если их четное число, вместо соответствующей половины нарисую 0. Если нечетное — рисую 1. Понятно, что, перевернув любую монету в любой из "половинок", я изменю четность этой "половинки". Переворачивать буду в той "половинке", в которой находится "магическая" монета если код в ней требует корректировки. В противном случае — в другой "половинке", чтобы ничего не испортить. Помимо прочего, воспользуюсь кодом, приведенным выше для двух монет, чтобы закодировать, но уже с помощью четностей, в какой именно "половинке" находится монета. Одновременно, пользуясь этим же кодом, буду кодировать где именно в этой "половинке" она находится. Например, для раскладки выше предположим, что "магическая" монета была в положении (1,2), т.е. находилась в первой строке второго столбца. Считаю четности 01|11->1|0. Это кодирует положение "магическая монета во второй строке", что неверно. Т.е. мне нужно перевернуть любую из монет в первой или во второй "половинке", чтобы прийти к правильному коду. Первая половинка содержит 01, что означает "второй столбец". Это правильно и я не хочу это портить, поэтому прошу надзирателя перевернуть любую из монет из "половинки" 11, что приведет к правильному коду.

Аналогичные рассуждения обобщаются на 8, 16, 32 и, в конечном итоге, 64 монеты.

Например, для восьми монет. Предположим, что выкладка была: 10010110. И искомая монета - четвертая. Считаем четности:
1001|0110->0|0. Это правильно, пока ничего не переворачиваем. Далее по этому коду монета находится в группе 1001.
Считаем четности: 1|1. Это неверно, надо менять четность. Четность будем менять в группе 10, т.к. группа 01 уже правильно кодирует
положение монеты и мы не хотим его портить. Т.е. просим надзирателя перевернуть любую из первых двух монет. Это ведет к правильному коду.

Если вдруг найдутся ошибки, буду признателен.

     

Димыч

Что-то очень заумно звучит. Неохота врубаться в этот способ.
Отмечу только, что там, где читал я, решение было однозначным. Там не было так, что "мы можем перевернуть эту или вон ту монету".
Там доска разбивалась на "маски" - группы клеток по 32шт. в каждой маске. Использовалось 6 масок. Также определялось - четное или нечетное количество "аверсов" в каждой из масок. 6 масок кодировали шестибитовое число (от 0 до 63). Номер монеты, которую надо было перевернуть, вычисляли путем "отксоривания" (применяли оператор XOR) этого 6-битового числа из масок и шестибитового номера "магической" монеты. После переворачивания именно этой монеты получалось, что в созданной системе масок доска давала 6-битовый номер "магической" монеты

На мой взгляд, за 45 минут придумать и полностью продумать такого рода решение практически невозможно

p.s. Собственно можно самим ознакомиться здесь, например: https://habr.com/ru/post/250585/
Там правда предлагают и другие способы решения задачи в комментариях

     

R60

Получается второй заключенный должен знать какую монету перевернул или нет первый. А тогда зачем этот балаган? Переворачивает ту которая магическая..
Вообще то несложно проверить на практике. Я надзиратель, ты с алексером будете отгадывать.

     

Димыч

Нет лучше тебя просто не выпускать из тюрьмы, пока не разберешься (потому, что я категорический противник смертной казни)

     

R60

Слабо?
Почему казнить? Математика ведь вас спасёт? Утрите нос простому инженеру пгс, я в этих нулях и единицах мало чего понимаю, унитазы в нужных местах нарисовать только могу.

     

alexer

У меня ушло 25 минут по дороге от работы до дома Но эксперимент не чистый, т.к. я про эту задачу знал раньше и даже когда-то решал, но как-то по-другому.
Если часто приходится решать головоломки, то возможно решить очень быстро.

     

Mikky

А что все таки делать для случая 1111 если монета в первой слева позиции?

     

alexer

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

     

Димыч

Скорее всего это все-таки не "решение", а "идеи" были.
Скорее всего там однозначное решение для каждой конкретной системы масок - т.е. та монета, которую нужно перевернуть однозначно определяется (она единственная)

     

alexer

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

     

Димыч

Чота думал, думал... Похоже все-таки, что события когда из 12 носков именно 6 будут красных(зеленых) равновероятно событию, когда носков этого цвета будет ноль или 12. Тогда получается, что вероятность этого события (что у каждого слепого будет по три пары красных и по три пары зеленых носков) составляет 1/13.

Но чую, блин, что здесь кроется какой-то подвох!

     

Mikky

Да подвох есть это точно. Там вероятность 100% .
Это одна из тех дурацких задач которые задают на собеседовании иногда в пижонские конторы
Просто можно кучу решений в задаче про монеты предложить за 10 мин.

     

Димыч

И почему именно 100%?
Итак вроде всеми силами старался уйти от решения

     

Mikky

Потому как в задаче про носки точно нет ни какой математики.
Просто пару носков разделяем (носки продаются соединенной парой) и один берет один носок другной второй.
Получаем что у одного 3 пары зеленых и 3 пары красных и у второго так же.


Я просто поле коммента , что нет никакой математики в задаче про монеты, подумал что там ее действительно нет,
это была моя ошибка.

     

Димыч

Носки продаются соединенной парой? Мда... Это был мой логический прокол!

p.s. А в задаче про шахматную доску математика присутствует, но не очень высокого уровня. Школьного. Однако всё равно - эта задача слишком трудная для того, чтобы с помощью неё отсеивать соискателей куда бы то ни было

     

Димыч

СТОП, мЕнуточку...
А вот и НЕТ!
Даже если носки соединенные попарно, то вероятность того, что у каждого из них окажутся 3 пары зеленых и 3 пары красных - конечно же не 100%. Потому как возможны варианты, что у одного окажутся все красные пары, а у другого - все зеленые, или у одного окажется одна пара красных носков, и 5 пар зеленых, а у другого - наоборот. И так далее.
Так, что нечего тут Димыча путать!
p.s. Хотя и вероятность события что у каждого будет по 3 пары красных и зеленых - уже будет намного больше 1/13 - это да. Вроде 1/7 получается - правильный ответ. А не единица

     

alexer

Ответ на задачу про монеты сегодня с утра пришел сразу же. Привожу ниже. А Димыч пусть уж комментирует, так
ли было у ребят с Хабра, если ему не лень, конечно.
Как и раньше буду писать "0", когда монета повернута аверсом и "1", когда она
повернута реверсом. Если обозначить развороты пары монет A, B, то под операцией "^"
буду понимать A^B=0, когда сумма чисел A+B - четная и A^B=1 - в противном случае.
Для тех, кто знает, что это, операция "^" - это XOR.
Пример: 1^0^1^1^0 = 1, т.к. 1+0+1+1+0=3 - нечетное число.

Начнем со случая, когда доска имеет размеры 2х2. Исходную выкладку монет запишем след.
образом:
A B
C D

Предлагается такой код: номер строчки с "магической" монетой определяется значением A^C: например,
первая строка когда A^C=0 и вторая строка, когда A^C=1. Номер столбца
будет определяться так же значением A^B (т.е. первый столбец, когда A^B=0 и второй когда A^B=1).
Покажем, что такой код позволит всегда указать на "магическую" монету, перевернув не более одной
монеты в исходной раскладке.
Действительно, в исходной раскладке могут быть следующие варианты:
1) В принятом коде раскладка уже указывает на "магическую" монету — ничего не переворачиваем.
2) В принятом коде раскладка указывает на правильную строку и неправильный столбец — переворачиваем монету B,
меняя тем самым A^B и сохраняя A^С
3) В принятом коде раскладка указывает на неправильную строку и правильный столбец — переворачиваем монету С,
меняя тем самым A^C и сохраняя A^B
4) И строка и столбец в исходной раскладке неправильные — переворачиваем монету A и меняем сразу и A^C и A^B.

Пример (звездочкой помечена "магическая" монета):
10
01*

раскладка кодирует положение (1,1). Ничего не переворачиваем.

Еще пример:
11*
11
Раскладка кодирует положение (1,1). У нас неправильный столбец. Переворачиваем монету в положении (1,2) (она же в этом случае "магическая").

И еще пример:
1 1
1 1*
Раскладка кодирует положение (1,1), а "магическая" монета в положении (2,2), т.е. и строка и столбец — неправильные. Переворачиваем
монету в положении (1,1).

Переходим к случаю 4x4. Пусть раскладка имеем вид:
A11 B11 A12 B12
C11 D11 C12 D12

A21 B21 A22 B22
C21 D21 C22 D22

Алгоритм следующий:
1) Посчитать:
A11^B11^C11^D11 A12^B12^C12^D12

A21^B21^C21^D21 A22^B22^C22^D22

2) Пользуясь кодировкой для случая 2х2, определить блок, в котором следует перевернуть монету.

3) Посчитать (пока ничего не переворачивали):
A11^A12^A21^A22 B11^B12^B21^B22

C11^C12^C21^C22 D11^D12^D21^D22

4) Пользуясь кодировкой для случая 2x2, определить элемент, который следует повернуть (блок уже знаем).

Пример:
1 1 0 1
0 1 1 1

1 0 1* 0
1 1 1 1

Считаем четности:
1 1
1 1
Значит переворачивать нужно монету в блоке (1,1).

Снова считаем четности:
1 0
1 0
Нужно перевернуть монету в положении (1,2) блока (1,1), т.е. монету в положении (1,2).
Приходим к раскладке:
1 0 0 1
0 1 1 1

1 0 1* 0
1 1 1 1

Чтобы угадать "магическую" монету опять считаем четности:
0 1
1 1
По нашему коду "магическая" монета находится в блоке (2,2).
И опять считаем четности:
1 1
1 0
По нашему коду, "магическая" монета находится в положении (1,1) блока (2,2), т.е. в положении (3,3), что совпадает с загаданным.

Можно проверить очень легко, что это будет работать в любом случае (следует из свойств операции "^" и того как считались четности).
Обобщение на полный случай 8x8 легко произвести, но этапов подсчета четностей будет уже 4, а не 2.
Писать еще больше мне уже лень

     

Mikky

Ваш коммент к задаче вводил в заблуждение всех

так как решение это сплошная математика и только .....

     

alexer

Какая же там математика? Четности посчитать? Эту задачку ведь не математикам на собеседовании давали, а простым SDE.

     

Mikky

Это раздел математики. Вот это точно ...
..
Если обозначить развороты пары монет A, B, то под операцией "^"
буду понимать A^B=0, когда сумма чисел A+B - четная и A^B=1 - в противном случае....
..
Просто система двоичная. Математике вообще пофиг сколькиричная система счисления

     

alexer

Мне можете не объяснять Я имел ввиду, что для решения этой задачи достаточно школьной арифметики. Хотя предупредил, что она сложная. В общем, у меня в районе часа ушло на ее решение. В Facebook не взяли бы

     

Димыч

Операция XOR никак не может давать результат "2". Тут какая-то путаница получилась, и в рассуждения кроме нулей и единиц ещё зачем-то двойки добавились. Надо что-то менять в алгоритме или его объяснении

     

Mikky

Это ж не математика. У него свой XOR определен

     

alexer

Она нигде и не давала результата "2". Если вы про номера строк и столбцов, то смотрите описание кода для случая 2х2. С ХOR это никак не связяно.

     

R60

Так об этом я уже писал, второй заключенный должен знать расположение всех монет до того как первый перевернёт или нет монету. Это принципиально меняет условия задачи. Можно просто перевернуть магическую монету и не париться.

     

alexer

Второй заключенный не знает расположения монет до того, как первый что-либо перевернет.

     

R60

Как не знает, если ты пишешь несколько раз слова - исходная раскладка. Откуда он может знать, исходная это раскладка или нет?

     

Mikky

Я предлагаю вам с alexer поиграть в эту игру.
Вы пишете код , а он отгадывает.
Если раз 10 хотя бы отгадает, то мы согласимся что его метод работает .
Хотя нет не получится. Вы же тоже не понимаете что надо перевернуть

     

R60

Я рисую раскладку и загадываю монету, Димыч с алексером угадывают. Я ещё вчера предложил. Но они магарыч требуют. И надо что бы тот кто будет первым заключенным, не передал ответ второму. В этом гарантии нет.

     

alexer

Я описываю, какую монету надо перевернуть. Тот, кто переворачивает, видит исходную раскладку. Тот, кто отгадывает, только считает четности.

Ну вот смотри. Тюремщик выложил монеты таким образом (А - аверс, Р - реверсб * - мегическая):
А Р*
Р Р

Я вижу сразу, что переворачивать нужно монету в положении (2,1). Тогда второй заключенный, зайдя в комнату видит раскладку
A Р
A Р

Он сразу говорит, что магическая - верхняя правая (что и было загадано)

     

alexer

Ох, все там нормально получается... Не надо им ничего знать "до переворачивания"
Второй заключенный, когда заходит, видит раскладку с уже перевернутой монетой :
А Р
А Р
Смотрит в первый столбец: "ага, там А,А, обе монеты повернуты одинаково, значит магическая в первой строке".
Дальше смотрит в первую строку: "ага, тут А,Р, монеты повернуты по-разному, значит магическая во втором столбце".
Т.е. магическая во втором столбце первой строки, что и было загаданно.

     

Димыч

Ещё задачи логические будут? Может "про гномов"?

     

Mikky

Задача про гномов давно уже гуляет по интернету (лет 10-15) , вот один из вариантов текста -

     

Димыч

Спасибо. Сейчас подумаю

     

R60

А вот ответ из гугля -
"Последний гном говорит цвет перед ним, а тот зная свой цвет молчит, если перед ним не тот цвет. Другой, не услышав того кто напротив, узнает, что у него другой цвет и т.д."
Очередная подстава. В условиях сказано что надо назвать цвет, иначе съест всех, а в ответе написано можно молчать.