sineemore

А что конкретно Вас в результатах не устраивает?

     

Mikky

Условия внимательно читаем Они слепые! А мешок один, а людей двое.

     

alexer

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

     

Димыч

Так, вот это уже интересный поворот. В рассуждения до этого я рассматривал именно ВЫВОД, и понятие "ложный" он или нет, обоснованный он или нет, применял именно к нему. Рассматривать "всё в целом" это как? Это значит надо рассмотреть летающего крокодила с королевой вместе? Три кило персиков и 4 метра кабеля? Скрещивать ужа с ежами - это насилие над здоровой психикой. Наверняка - с очень тяжелыми последствиями для "исследователя"

    кто голосовал?  

R60

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

     

Димыч

Прочел еще раз:
"

"
В чём задача не понял. Т.к. если они приносят этот пакет домой, то в нем будет равное количество зеленых и красных пар - по условию задачи.

     

Димыч

Это краткое описание алгоритма. Подробнее - надо почитать чуть больше

     

Димыч

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

     

alexer

Знаете, я устал тут писать, не обижайтесь ЗахотИте разобраться - разберетесь. А если не захотИте, так мои послания здесь точно не помогут, как бы я ни старался.

     

Mikky

А блин, слова - у каждого одинаковое количество пар - я не написал , сорри хоккей смотрю .
Хотя как то все грустно
Короче каждый из двух должен иметь у себя одинаковое количество пар зеленых и красных

     

sineemore

Вот мою психику, напротив, расслабляет и отвлекает от рутины. Тут уже столько смешного было. Опошление математики, ложные крокодилы.... пустые множества, внутри которых возможно все. Фантазии только и гулять.

Вы думаете, от длинны кабеля зависит, сколько электричества выработают персики?

     

Mikky

Идея в том , как я понял что можно с помощью остатка от деления на 2 получить любое число то 0 до 64 переворачивая
только одну монету. Возможно , надо как то доказать

     

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 уже правильно кодирует
положение монеты и мы не хотим его портить. Т.е. просим надзирателя перевернуть любую из первых двух монет. Это ведет к правильному коду.

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

     

Димыч

Остаток от деления на 2 может быть только 1 или 0

     

Mikky

И это правда !
Там еще все в двоичной системе . Так что только единицы и нули.
Пока не готов обсуждать так как в голове логика не улеглась еще


Вот пытаюсь понять предыдущего оратора для случая 1111 если монета в первой слева позиции,
что нужно переворачивать .

     

Димыч

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

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

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

     

Димыч

Зависит конечно. Чем длиннее кабель - тем больше будут потери!

     

R60

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

     

Димыч

Опять не понимаю в чём вопрос. Допустим у одного 5 зеленых и 7 красных носков. Ну и что? Все равно ведь это 6 пар носков будет как ни крути. Из них можно сложить 5 пар одноцветных и одну пару разноцветную. Поэтому если они возьмут одинаковое количество носков, то у них будет одинаковое количество пар носков. Всегда (т.е. вероятность равна единице). И то, что они "слепые" - рояля никакого не играет. В вопросе ведь ничего не говорится про то, что пары должны быть одноцветные

     

Димыч

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

     

Mikky

У каждого должно быть 3 пары зеленых и 3 пары красных носков.

     

alexer

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

     

Mikky

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

     

R60

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

     

alexer

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

     

Димыч

Не утрём. Т.к. мы унитазами не занимаемся и в них плохо разбираемся

     

Димыч

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

     

alexer

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

     

Димыч

Чота не гуглится...

Пока я думаю, вот попроще задача из той же серии:

"В ящике комода лежит 15 пар носков, из них одна пара красная, остальные черные. В темноте эти носки делят на 2 равные кучки по 15 носков. Какова вероятность того, что оба красных носка будут в одной кучке?"

     

Димыч

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

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

     

Mikky

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

     

sineemore

Эта тема посто кладезь идей.

Вы в нужных можете, а могу в ненужных! Попробую этим заняться как-нибудь, тихонечно нарисую где-нибудь в неожиданном месте унитаз.

     

sineemore

Интересно, сколько в персике электричества...?
Или там, может, неиссякаемый источник, пока персик не сгниет?

     

Димыч

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

     

Димыч

Если по Эйнштейну, то очень и очень много
p.s. А если не по нему, то скорее всего - ещё больше

     

R60

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

Ну что, ответа на задачу мы не дождёмся?? Тем более абсолютно не сложно проверить его опытным путем. Ау, математики!

     

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.
Писать еще больше мне уже лень

     

R60

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

     

alexer

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

     

Димыч

Математики народ ленивый и заставить их повторно решать решённые задачи очень трудно.
(нужно приплатить немного)

     

alexer

Ну да, особенно если в качестве решалки гугл.

     

Mikky

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

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

     

alexer

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

     

Mikky

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


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

     

Mikky

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

     

alexer

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

     

R60

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

     

Mikky

Арифметика - раздел математики. просто для общего развития

     

Mikky

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

     

Димыч

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

     

alexer

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

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

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

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

     

Mikky

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

     

Димыч

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

     

alexer

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

     

R60

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

     

alexer

К тому же я не уверен, что алгоритм, который Димыч нашел в гуглах — такой же. Поэтому может не сработать.

     

Димыч

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

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

     

alexer

Для Facebook годится. Мне более сложную давали на порядок. Правда на размышления — час.

     

Mikky

Проблема еще в алгоритме шифрования.
Его должны оба очень хорошо понимать.
Походу пока таких нет.

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