Трудный вопрос на собеседовании #1

developers.org.ua решили опубликовать замечательный цикл «Трудные вопросы на собеседовании» на русском языке. Каждую неделю будет публиковаться один новый вопрос, а также добавляться в комментариях ответ на предыдущий. Учитывая, что ответы на все эти вопросы есть в открытом доступе на сайте оригинала, цель, которую мы преследуем этим циклом переводов — дать возможность потренироваться тем, кто этого хочет, плюс пополемизировать на тему качества задач и их решений. Итак!...

Задача #1

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

У магов неограниченное количество чёрных и белых шляп. Они одевают белую или черную шляпу на голову каждого гнома.

Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет).

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

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

Ответ на эту задачу и текст следующей — через неделю!

UPDATE: решение

👍НравитсяПонравилось0
В избранноеВ избранном0
Подписаться на автора
LinkedIn



Підписуйтесь: Soundcloud | Google Podcast | YouTube

142 комментария

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

ответ 75% правильные комменты № 16 и № 53сумма по модулю два тут не катит так не задано конечное число гномов и шапок.

Чего-то я с этими n — намудрил:) Где ошибка понять не могу, но вобщем ответ = 0%... 40%

Ах нет. Прошу прощения. Второй гном не знает точно из соотношения (0 * 1 = 0, 1 * 1 = 1, 1 * 0 = 0) какой у него цвет. Давайте рассмотрим варианты (первый множитель — третий гном, второй множитель — второй гном): 1) 0 * 1 = 0 — Второй гном не знает, что он 12) 1 * 0 = 0 — Второй гном знает, что он 0, если первый гном сообщит ему его цвет3) 1 * 1 = 1 — Второй гном знает, что он 0, если первый гном сообщит ему его цвет4) 0 * 0 = 0 — Второй гном знает, что он 0, если первый гном сообщит ему его цветКак видим во всех случаях кроме второго цвет третьего гнома равняется лог. умножению, которое сказал первый.Получается что в первом случае если умрёт второй, то выживет третий. И если во втором случае умрёт третий, то выживет второй. Отсуда получается, что среди вип персон есть ¼ тех кто может умереть. Отсюда предыдущий ответ 3n/ (n + 2) надо умножить на ¼ и получим 3n/2* (n + 2)

Если n = количество гномов, то макс. кол. убиенных = 3n/ (n+2). Минимальное количество убиенных = 0; Объясняю как к этому пришёл.Стратегия гнома такова. Если взять за булый цвет единичку, а за чёрный 0, то пусть первый гном смотрит на двух впереди стоящих гномов и говорит результат их логического умножения цветов (0 * 1 = 0, 1 * 1 = 1, 1 * 0 = 0). Получается, второй после него гном видит впереди себя гнома и знает результат перемножения своего цвета на след. и естесственно определяет свой цвет и его называет. Третий гном слышал от первого результат умножения и слышал цвет второго. Легко определит свой цвет и ему. Четвёртый гном повторяет действия первого и т.д. по цепочке. 1, 4, 7, 10... и.т.д гномов я назвал группой риска. Остальных — вип-персонами:) Группу риска = целое ((n-1) / 3) + 1Вип-персоны = n — Группу риска = n — (2/3) * (n — 2) = 3n/ (n + 2) . легко посчитать всё в процентном соотношении относительно n => 3n/ (n + 2) * 100 / n = 300/ (n + 2) %Вот мы и нашли макс. количество убиенных. Я не думаю, что Однако, может им всем и повезёт, если ихний цвет совпадт с произведением двух впереди стоящих гномов. И тогда никто не умрёт:) Надеюсь я нигде не ошибся:)

Рішення № 5 за умови позитивного приросту гномів за рік при кількості років, що прямують до безмежності призводить до безмежної к-сті убитих гномів.Оптимальне рішення — масовий суїцид гномів. В такому разі к-сть вбитих гномів буде рівна к-сті гномів в селещі << безмежності.

было бы неплохо увидеть еще доказательство того, что решение исходной задачи (комментарий номер 5 и аналогичные) оптимально

Гм. Вариант с xor самый простой и правильный.

Учитывая то, что нет ограничений на формат ответа гнома магу, мы воспользуемся методом карточных шулеров.Итак первый самый высокий гном называет цвет шляпы впереди стоящего гнома.Второй гном, если у него белая шляпа () он узнал ответ от самого высокого гнома), отвечает след образом: Если впереди стоящего гнома белая шляпа он произносит фразу «На мне белая шляпа».Если у впереди стоящего гнома черная шляпа он произносит «Моя шляпа белая».Смысл именно в различии фраз «На мне белая шляпа» и «Моя шляпа белая».Для магов оба будут правильными ответами, но такими вариантами фраз гномы могут завуалировано сообщать друг другу цвет шляпы.

А как вам такое решение:) Так как в задании не сказано что гномы должны называть только черный или белый цвета, предлагаю гномам создать и запомнить наизусть таблицу таблицу из 2 в степени (N-1) цветов. Например красный, сине-зеленый, серо-буро-малиновый... Каждому цвету поставить в соответствие комбинацию из (N-1) черных и белых шляп.Первый гном считывает комбинацию шляп, сверяет с таблицей и говорит соответствующий цвет. Он наверняка умрет, но другие будут спасены:)

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

Блин, фигня. Мой ответ это по факту ответm0de$t 2.06.2008 в 11: 55 Не обратил внимание на его пост. Сорри

В посте выше немного сморозил. При таком раскладе потери гномов будут до 50% в парных группах. В непарных немного больше

Допустим, что есть N групп гномов, которых построили маги. Маги надели на них шапки.Предположим, что маги будут по очереди спрашивать у гномов цвет их шляпы:) В каждой группе ессесно:) Стратегия гномов: все гномы должны знать, что «самый высокий» скажет цвет шляпы гнома, который находится перед ним. Понятно, что самый высокий гном — это «жертва». Зато все остальные выживут.Потери гномов составят N гномов, где N — количество групп гномов построенных магами:) ГЫ. Это в славянском стиле. Сорри если что не так;)

Зачем вообще такие вопросы на собеседованиях задавать?

затем чтоб ты сразу понял что там, куда ты пытаешься устроиться все шпилят в WoW!

Зачем вообще такие вопросы на собеседованиях задавать?

Павел, во-первых «БелОя» — нельзя расценивать как цвет шляпы, нет такого слова. Во-вторых, что касается второй задачи — гномы ничего не знают о предидущем и не получают от него никакой информации. Видимо это ответ-шутка.

1-й гном называет шляпу следующего, шансы выжить 50%Следующий гном, зная цвет своей шляпы, называет ее, но не просто, а коверкая цвет своей шляпы, если цвет следующей противоположен.Допустим у нашего гнома белая шляпа, а у соседнего — черная.Он произносит «БелОя» и сам остается в живих и следующий гном уже знает, что у него чёрная шляпа.Для правдоподобности можно изменять или пропускать любые буквы.В итоге: максимальное количество убитых — 1 (самый первый) гном.

Отлично, а еще такие кровожадные задачки есть? %E

Сергей: вы мне напомнили еще об одной хорошей загадке, в которой ныне ушедший из ЖЖ avva предложил идею самопожертвования.Читать тут.Только не надо устраивать очередной флейм на эту тему:)

2 Roman Cheplyaka

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

брутфорсят: -), но впустую.

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

т.к. перебирая «все» последовательности они имеют ровно 0 шансов обговорить выпавшую. бесконечности ж, ёпт!

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

Рома ответ неверный, правильный ответ белого потому, что это скорая помощь.

Parvus: зеленого. СОТОНА: вообще-то это был ответ на вопрос Restuta. А гномам во время подготовки никаких шансов не надо. Они сортируют все последовательности по классам, выбирают в каждом классе стандартную и т.д., я это все уже писал выше. Сколько времени и сил у них это займет, мы не обсуждаем.

2 Roman Cheplyaka

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

Роман, ты не понял где я нашёл шанс 0. он не у гнома, во время ответа, а у всех гномов, во время выбора классов эквивалентности. у гномов нет шансов выбрать класс (и стандартye. последовательность), которая будет похожа на ту, что выпадет.

Задача. По трассе движется бесконечная последовательность автомобилей, каждый водитель видит цвет автомобилей только впереди себя. Рома, какого цвета автомобиль едет за тобой?

Вероятность события что гном угадает с 1-го раза нужную последовательность — 1/бесконечность, т.е. равна 0 и с 99999999, тоже равна 0. А какова вероятность, что гном угадает нужную последовательность с бесконечно большой попытки? Разве не бесконечность / бесконечность?

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

2 Roman Cheplyaka

Где вы тут брут-форс увидели?

хм. чтобы выбрать классы эквивалентности и стандартные последовательности, гномам необходимо оговорить ВСЕ ВОЗМОЖНЫЕ бесконечные последовательности — это полный перебор ака брут-форс. нет?

Я вас не понимаю. Процитируйте, пожалуйста, ту часть решения, которую вы ставите под вопрос

ну его невозможно процитировать, т.к. оно явно не озвучено, но вот где-то перед этим:

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

гномы должны были сформировать классы эквивалентности — это как раз тот момент, где я утверждаю, что у них ровно 0 шансов оговорить ту последовательность, что выпадет.2 Restuta

При чем тут это? Именно начнут, это доказано при условии верности аксиомы выбора.

ты не читаешь, что я пишу:) аксиома выбора туту вообще до одного места — им можно выбрать ЛЮБУЮ последовательность в качестве стандартной и всё будет пучком, если выпадет последовательность похожая на одну из оговорёных., но шанс того, что так случится — 0. я уже писал почему.

Відповідь на задачу п. 93. У разі помилки при виборі стратегії населення планети буде знищено за 33 роки.: (Щодо задачі Романа п. 76 то у задачі нічого не говориться про зговір поміж магами та гномами, що маги будуть вибирати кольори із стандартної послідовності. А відповідно зв’язку по між значеннями у ряду немає. Тоді до чого тут взагалі аксіома вибору.

Роман: «Restuta: не совсем так. Неопределенность возникает, когда у нас сумма бесконечного числа бесконечно малых величин. А тут сумма нулей, и ничего кроме нуля получиться не может. Тут работает аксиома счетной аддитивности вероятностей.» — не совсем так =)) Вероятность события что гном угадает с 1-го раза нужную последовательность — 1/бесконечность, т.е. равна 0 и с 99999999, тоже равна 0. А какова вероятность, что гном угадает нужную последовательность с бесконечно большой попытки? Разве не бесконечность / бесконечность? СОТОНА: «читал. так вот жто неверная посылка, т.к. НЕИЗВЕСТНО (бесконечность/бесконечность = неопределённость) начнут они угадывать или нет.» — При чем тут это? Именно начнут, это доказано при условии верности аксиомы выбора.

Теория выбора и аксиома выбора — это разные вещи:) Последняя относится к теории множеств и, как выразился Родион, является «спорной и мало применимой на практике вещью».Одно из ее применений — возможность сделать из одного апельсина два:)

А что изменит написание отдельного поста?

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

Родион: скажем проще, программистам нравится флеймить:) Обсуждения по существу тут очень мало, к сожалению.Александр: грубо говоря, аксиома выбора — это то, что обосновывает осуществимость этого шага:

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

Аксиома выбора нужна в основном математикам для построения строгих доказательств. Нематиматикам она, как правило, кажется вполне очевидной: если у нас есть набор непустых множеств (в данном случае это классы последовательностей), что может мешать выбрать из каждого множества по произвольному элементу? А что изменит написание отдельного поста?

так я ж не про прямую аналогию... я про то, что трудно назвать брут-форс решение «красивым».

Где вы тут брут-форс увидели?

стоп-стоп. какая-такая ошибка? мы ещё не дошли до «начиная с некоторого гнома все будут угадывать» — они только ОГОВАРИВАЮТ последовательности и вероятность того, что они вообще оговорят выпавшую последовательность нулевая.

Я вас не понимаю. Процитируйте, пожалуйста, ту часть решения, которую вы ставите под вопрос.

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

Да уж, вышли уже на первое место по комментируемости...Роман Чепляка, я прошу вас написать пост об использовании теории выбора, ибо тема выглядит интересной, но не совсем понятной. Там и пообсуждаем;)

Этот тред ярко показывает что программистам весьма интересно обсуждать спорные и мало применимые на практике вещи, как говорится «с усердием достойным лучшего применения». Саша, развели тут словоблудие:)

2 Roman Cheplyaka

Ошибка в рассуждении Сотоны в том, что для работы этой аксиомы необходимо, чтобы события были несовместными. А в нашем случае если утверждение «начиная с некоторого гнома все будут угадывать» верна для гнома X, то оно, разумеется, будет верно и для всех последующих гномов.

стоп-стоп. какая-такая ошибка? мы ещё не дошли до «начиная с некоторого гнома все будут угадывать» — они только ОГОВАРИВАЮТ последовательности и вероятность того, что они вообще оговорят выпавшую последовательность нулевая.

2 Roman Cheplyaka

Прямой аналогией упомянутого «прикола» является утверждение, что найдется сколь угодно длинная последовательность подряд угадавших гномов.

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

2 Restuta

И ты читал конец той английской статьи, там рассмотрен случай, когда количество цветов шапки бесконечно, но гномы всё-равно обсуждают стратегию, вероятность каждого гнома угадать свой цвет равна 0, но тем не менее маги офигеют, когда большинтсво гномов ответит правильно.

читал. так вот жто неверная посылка, т.к. НЕИЗВЕСТНО (бесконечность/бесконечность = неопределённость) начнут они угадывать или нет.

Опечатка: s/начиная с некоторого гнома/начиная с данного гнома/

1. сколько должно быть рассмотрено классов для успешного применения стратегии? насколько я понимаю бесконечность.2. какой длинны «хвост» определяет класс? насколько я понимаю опять бесконечность.

Верно.

вобщем, как по мне, это «красивое» решение очень напоминает прикол про бесконечное кол-во обезьян за пишущими машинками...

Нет, тут ситуация принципиально другая. Прямой аналогией упомянутого «прикола» является утверждение, что найдется сколь угодно длинная последовательность подряд угадавших гномов. Это простой факт теории вероятностей, и никакой стратегии для этого не требуется. Мы же утверждаем, что начиная с некоторого момента все гномы будут угадывать правильно. Почувствуйте разницу. Если вы будете подкидывать монетку достаточно долго, то рано или поздно получите серию из, скажем, 100 орлов. Но вы не дождетесь того, что с некоторого момента будут выпадать одни лишь орлы.

СОТОНА: С первого раза 0, а с бесконечного нет, потому что бесконечность/бесконечность = неопределённость.

Restuta: не совсем так. Неопределенность возникает, когда у нас сумма бесконечного числа бесконечно малых величин. А тут сумма нулей, и ничего кроме нуля получиться не может. Тут работает аксиома счетной аддитивности вероятностей. Ошибка в рассуждении Сотоны в том, что для работы этой аксиомы необходимо, чтобы события были несовместными. А в нашем случае если утверждение «начиная с некоторого гнома все будут угадывать» верна для гнома X, то оно, разумеется, будет верно и для всех последующих гномов.Чтобы требование несовместности событий стало очевидным, рассмотрите пример с игральной костью. Вероятность выпадения нечетного числа равна ½, вероятность выпадения числа не кратного 3 равна 2/3, стало быть, вероятность выпадения числа не кратного 2 и 3 должна быть ½+2/3> 1?

СОТОНА: С первого раза 0, а с бесконечного нет, потому что бесконечность/бесконечность = неопределённость. И ты читал конец той английской статьи, там рассмотрен случай, когда количество цветов шапки бесконечно, но гномы всё-равно обсуждают стратегию, вероятность каждого гнома угадать свой цвет равна 0, но тем не менее маги офигеют, когда большинтсво гномов ответит правильно.

2 Roman Cheplyakaя не понял «красоты» решения. признаю:) перечитал пост Мюллера и всё равно не понимаю этой уверенности в том, что на бесконечном кол-ве гномов можно ограничится конечным числом смертоубийств.можно я тут вопросы позадаю?

Перед тем, как встретиться с магами, гномы собираются и выбирают из каждого класса по одному представителю (стандартная последовательность этого класса) — в этом нелегком деле им и поможет аксиома выбора

1. сколько должно быть рассмотрено классов для успешного применения стратегии? насколько я понимаю бесконечность.2. какой длинны «хвост» определяет класс? насколько я понимаю опять бесконечность.то есть гномы оговорили бесконечное количество бесконечных последовательностей. я так понял злые волшебники умерли от старости пока гномы готовились...

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

1. как можно определить, что «хвост» принадлежит какой-то оговорённой последовательности, ведь он же бесконечный? 2. чтобы гномы могли «угадывать», каждый гном должен перед ответом сравнить бесконечность оговорённых бесконечных последовательностей с бесконечным хвостом, который он видит.

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

вобщем, как по мне, это «красивое» решение очень напоминает прикол про бесконечное кол-во обезьян за пишущими машинками...кстати — какова вероятность того, что гномы оговорят выпавшую последовательность с 1го раза? 1/бесконечность=0. будем складывать нули до бесконечности, чтобы определить вероятность того, что гномы таки оговорят выпавший вариант?: -)

Restuta: совершенно верно — гномы называют свои цвета из предположения, что они находятся в стандартной последовательности того класса, котороый они вычислили (проверить предположение они не могут, т.к. не видят начала последовательности). Если им повезло и это действительно стандартная последовательность, то угадывать будут с самого начала. Но даже если нет, поскольку реальная последовательность находится в одном классе с данной стандартной (т.е. с последовательностью ответов), то они похожи —, а это, согласно нашему определению похожести, как раз и означает, что с какого-то момента (после конечного числа убийств) они будут совпадать.

А все понял, они находят класс эквивалентности, а не последовательность и предполагают, что они в выбранное одной стандартной последовательности из этого класса. Как говорится в первоисточнике" How well does this work? Well, the sequence they are actually in and the representative element they picked with the axiom of choice must be equivalent, so they are the same after a finite number of entries." — почему «finite number of entries»? Почему не на бесконечном удалении встретится заветная последовательность?

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

Менторский тон в посте 95 вызывает смех

+1

Restuta: Стратегия гномов заключается в том, чтобы по тому хвосту который они видят определить класс эквивалентности, и затем называть цвета из выбранной (стандартной) последовательности для этого класса. По приведенному аргументу, любые два гнома видят один и тот же хвост, значит они выберут один и тот же класс эквивалентности и будут называть цвета из стандартной последовательности для этого класса. Поскольку любые два выберут одну и ту же последовательность, то все гномы выберут одну и ту же последовательность (ту, которую выбрал первый гном).Вадим: Менторский тон в посте 95 вызывает смех. Вы или провокатор, или действительно не понимаете о чем говорите. Комментировать ваши реплики довольно сложно, поскольку они в основном представляют собой бессмысленное нагромождение слов. Если вам действительно интересно, то задайте продуманные вопросы — на них ответят.

Вадим, Роман взял известную аксиому и не применял её не к месту. Он просто перевел участок статьи из ссылки в посте 83. Решение задачи в любом случае будет противоречить здравому смыслу, потому что наличие бесконечного числа гномов уже противоречит здравому смыслу =) Роман, есть вопрос по последнему абзацу в вашем решении"Но очевидно, что любые два гнома видят похожие хвосты (один получается издругого отбрасыванием отрезка между этими двумя гномами), так чтопоследовательность догадок всех гномов является той самой стандартной." — это почему? Почему последовательность догадок всех гномов является стандартной?

Роман, Вы взяли редкую аксиому, применили её не к месту и с ошибками, и это привело к результату, который противоречит здравому смыслу. Но в целом хочу отметить, что у вас не плохие знания с математики, как для студента второго курса. Хотя вы уже должны были закончить изучение курса теории вероятности, и ошибок таких не допускать. На этом мы заканчиваем обсуждение этого вопроса. Хочу сказать, что ошибки допускать это хорошо, значительно хуже ничего не делать. :) Успехов, Вам Роман.

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

Ответ на 91. Бесконечность мы можем и не разбивать на группы и классы, а описать и одной бесконечной последовательностью, беда в том, Роман, что мы будем иметь бесконечное количество точек входа в эту последовательность. И в результате всё равно получим бесконечное количество вариантов, и по-другому быть не может. В таких случаях, Роман, пользуются теорией вероятностей, а она, как не крутитесь, даёт однозначный ответ — 50% жертв.Предлагаю всем решить задачу, за сколько лет, маги уничтожат всех гномов, если гномы будут пользоваться стратегией гадания, а количество гномов равно современному населению планеты (шесть миллиардов).

вариант — забыть про то что цвета только два, вернемся к стеганографии,... первый так тоже умирает з вероятнстью 50%, но остальным не обязательно видеть всех перед собой дстаточно одного.а вариантов разделить цвета на два очень много, например руский белый — перед тобой тот же цвет, падонковский (или с неправильным ударением, или очень близкий оттенок) — цвет другой... и так шеренга неограниченой длинны выживает вся кроме «половины» первого гнома

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

Мое доказательство (87) верно, как в случае конечного, так и бесконечного числа элементов.Что касается доказательства (83) Романа, то Роман предлагает разбить бесконечную последовательность на классы. Введем классы, например: 00, 01, 10, 11. В результате мы просто перешли к другой системе исчисления. Совершенно очевидно что, разбиение бесконечной последовательности на классы ничего не даёт, так как последовательность классов будет всё равно бесконечной, и, следовательно, количество жертв будет бесконечно. :) «Для 6 миллиардов вообще никаких проблем нет — даже если они все будут убиты, их лишь конечное количество» (89) — представляю Роман, что бы с Вами сделала мировая общественность, ведь это всё современное население планеты.

mickolka: ну, насчет аксиомы выбора я сразу предупредил:) По поводу алгоритма. Как только вы принимаете аксиому выбора, в вашей «стандартной библиотеке» появляется новая процедура — «применить аксиому выбора». Если рассматривать ее как данную и не требовать исходники, то вот вам и алгоритм.Понятно, что раз речь идет о бесконечном количестве гномов, то алгоритма в традиционном понимании не будет — они все работают с конечными сущностями. Вадим Романько: в задаче речь идет о бесконечном количестве гномов. Прочтите, пожалуйста, условие (комментарий 76).Для 6 миллиардов вообще никаких проблем нет — даже если они все будут убиты, их лишь конечное количество, что по условию нам подходит.

Неограниченная память... они не увидят столько шапок... вероятность... скорость вычисления...Эй, это гномы и маги. Ребята, ГНОМЫ. ГНОМЫ.

Роман, для какого количества гномов работает Ваша теория для 6 миллиардов? Вы говорите «стратегия будет работать для любой последовательности и наличие периода не играют роли». Вот, последовательность без периода: Х01010100000101001010110100101010101010Ответьте на вопрос, чему равно Х? Отвечу, я могу поставить сюда любое значение наоборот сказанному Вами, потому что нет условий ограничивающих это. Нет условий, которые запрещают методом индукции размножить это решение для всех гномов. Ваше заявление о возможности решении без дополнительного условия: «наличие повторяющейся последовательности с периодом меньше длины выборки» — опровергнуто.

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

Вадим: стратегия будет работать для абсолютно любой последовательности, и наличие периода и его длина не играют никакой роли. Что именно в моем решении вы не поняли?

Описанная Романом стратегия будет работать, только, если маги будут пользоваться очень плохим генератором псевдослучайных чисел с очень короткой длиной последовательности, буквально в десятки. Для срабатывания алгоритма период генератора должен быть, как минимум, на ключ меньше количества гномов. В таком случае, решение можно получить путём поиска подстроки. Алгоритм: i = ИскатьПодстроку К в S СоВторогоВхожденияC = S [i-1] гдеS — полная последовательность, которую видит гном впереди себя; К — ключ из 20 (например) элементов, которые видит перед собой гном; i — индекс начала найденной повторяющейся последовательности; С — цвет гнома.Пример: S = 11011100101001001000010010010010001011101110010100100100001001001001000101К = 1101110010100100100Результат С = 1Данная задача, не смотря на кучу математических терминов, используемых Романом в описании на самом деле очень простая с точки зрения программирования, и сводится к простому поиску подстроки. Но так, как маги вряд ли смогут (без сговора с гномами конечно) найти такой генератор псевдослучайных чисел, то половина гномов при такой стратегии погибнет.Что касается большого количества гномов в деревне, то гномам надо разбиться на группы, например по 10. В таком случае рискует только, каждый десятый. И в случае сбоя погибнет только половина группы, в которой произошел сбой, а не половина всех гномов. Частный случай этого решения предложен в m0de$t в ответе 1, для группы из двух гномов.

Решение моего варианта задачи.

(Прелюдия) Вполне естественным желанием гнома является по «хвосту» последовательностикаким-то образом угадать его «начало» (в частности, цвет его собственной шляпы).При этом, как верно заметили многие комментаторы, если между магами и гномаминет сговора, то вероятность угадать цвет шляпы равна 50%.Поэтому, если гномы будут угадывать независимо, то сработает законбольших чисел, и половина гномов (т.е. бесконечное количество) будет убито.Отсюда делаем очевидный вывод — гномы должны действовать согласованно.В данном случае согласованность означает то, что на вопрос «я вижу впереди себяхвост некоторой последовательности; как такая последовательность можетвыглядеть? » все гномы будут отвечать одинаково. (Решение) А именно, назовем две последовательности похожими, если у них есть одинаковыехвосты. Иными словами, если выкинуть несколько начальных членов из однойпоследовательности и несколько из другой, то получим идентичныепоследовательности.Несложно проверить, что так определенная нами похожесть является отношениемэквивалентности. Поэтому все возможные последовательности разбиваются на классыэквивалентности, в каждом из которых все последовательности попарно похожи.Перед тем, как встретиться с магами, гномы собираются и выбирают из каждогокласса по одному представителю (стандартная последовательность этогокласса) — в этом нелегком деле им и поможет аксиома выбора.Таким образом, любая последовательность похожа на некоторую (и только одну) стандартную последовательность. Теперь стратегия каждого гнома такова: оннаходит стандартную последовательность, которая похожа на наблюдаемыйим хвост, и делает свою догадку, основываясь на предположении, что он стоит какраз в той самой стандартной последовательности. Разумеется, предположение этововсе не обязательно верно, и гном рискует умереть.Но очевидно, что любые два гнома видят похожие хвосты (один получается издругого отбрасыванием отрезка между этими двумя гномами), так чтопоследовательность догадок всех гномов является той самой стандартной. Посколькустандартная последовательность выбиралась похожей на ту, которую составили маги, то их хвосты совпадают, а значит, начиная с некоторого момента все гномы будутназывать правильные цвета.

Я узнал об этой задачке от Грега Мюллера.

это ужас, а не правильное решение. я бы такого программиста не взял на работу.решение строго заточено под то, что гномиков будет немного. ещё раз повторюсь — нигде не написано что гном видит всех и может посчитать шляпы впереди стоящих, а это значит, что вероятность обратного очевидна и правильно решение превращается в абсолютно неприемлимое.может неверный перевод? и «...так что каждый гном может видеть только тех, кто ниже его самого.» должно звучать так: «...так что каждый гном видит всех кто ниже его самого и не видит тех кто выше» — тогда правильный ответ принимается.а вообще рубрика интересная, молодцы!

Апелляция: И что это за алгоритм такой «может легко вычислить»? Я с таким же успехом мог сказать, что эта задача «может легко решается» не решая ее. «Индуктивное доказательство» решения в принципе легко получить. А решение где? Половина задачи не решена. Алгоритма нет. Как на основании этого решения составить программу? Вы на работу программистов набираете?:)

Итак, ответ, данный автором задачи (далее — «Правильный ответ»):

У гномов есть стратегия, которая будет стоить жизни максимум одному из них.Пусть черные шляпы обозначают единицы, а белые — нули. Каждый гном вычисляет сумму по модулю 2 шляп перед ним. Первый (самый высокий гном) объявляет цвет, согласно сумме, им посчитанной. Он может быть убит либо нет (зависит от его удачливости... конечно, маги всегда могут подстроить так, что он умрет в любом случае, т.к. они знают, что используется оптимальная стратегия). Следующий гном сравнивает сумму, посчитанную им, с суммой, сказанной самым высоким гномом. Если суммы совпадают, сие означает, что его шляпа белая, иначе — черная. Он объявляет свой цвет и выживает.Каждый последующий гном, вооруженный первоначальной суммой всех гномов кроме первого и цветами шляп всех предыдущих гномьих шляп (опять же, кроме первого), может легко вычислить цвет своей собственной шляпы. Индуктивное доказательство достаточно просто.Итак, только самый первый (и самый высокий) гном погибает... что, на мой взгляд, объясняет, почему гномы такие низенькие.

Небольшая интрига:) По единодушному мнению некоторых членов нашей редколлегии, мы хотим подарить новую футболку сайта developers.org.ua автору коммента № 17 Роману Чепляке. Ура, товарищи!

1.Гномы вооружены алгоритмом — деревня спасена. 2.Маги, узнав об алгоритме гномов, могут убивать каждый год самого большого гнома, и уничтожить деревню за N лет.3.Гномы, узнав о том, что маги знают их алгоритм, могут изменить свой алгоритм: заменить на противоположное значение цвет самого большого гнома, сведя свои потери к нулю.4...

Алгоритм: c [i] = sum (c [j]; j =1...N; j! = i) & 1 (0 — черный; 1 — белый; «&» — бинарное «И») i-тий гном вычисляет свой цвет c [i] по формуле, цвета меньших гномов c [j] он видит, цвета больших слышит.Проверяйте: 0 1 0 0 1, 1 0 0 0 1 1 1 0.Рискует с вероятность 50% только самый высокий гном.

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

Пожалуйста.

Маги выстроили гномов в бесконечную последовательность и надели на головукаждого гнома белую или черную шляпу.Затем маги обходят гномов и у каждого из них спрашивают, какого цвета шляпа ненём надета. Если гном ошибается, маги убивают его.Каждый гном видит шляпы всех гномов, которые стоят в последовательности посленего, но не видит свою шляпу и шляпы гномов до него. Гномы не могут слышать то, что говорят остальные.У гномов есть возможность заранее обсудить стратегию поведения с магами.Как гномам добиться того, чтобы лишь конечное число гномов было убито?

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

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

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

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

Роман, я наверное слишком давно учил математику, но скажите мне как знание хвоста бесконечной последовательности НЕЗАВИСИМЫХ случайных величин может дать информацию о началеРазумеется, никак:) Но в «начале» лишь конечное число шапок. мне кажется что если маги будут одевать шапки независимо и равновероятно то шансы каждого гнома выжить равны 50% независимо от положения в шеренге..Какими соображениями пользуются маги, абсолютно не важно. «Шансы» гнома выжить определяются исключительно ответами гномов, а они отнюдь не должны быть случайными (и тем более — независимыми, т.к. у гномов есть общая информация — «хвосты» последовательности).

Roman Cheplyaka

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

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

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

Несложно, но это не имеет никакого отношения к задаче. Если маги выбирут такую стратегию, тогда стратегия гномов очевидна.Дмитрий

P.S.: Кеос, это ты чтоли? о_О))

Нет

Роман

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

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

Потому «не черный» — это не «белый», а любой цвет кроме черного, это может быть «зеленый». А в условии задачи явно сказанно что гном должен назвать цвет шляпы на своей голове, а это или «черный» или «белый».

В принципе да, но один момент — о конкретности ответа в условии как раз не оговаривается: тут уже вопрос лексики — вопрос сформулирован не настолько чётко!) Потому этот вариант возможен, так как цветов всего два, и никаких зелёных, красных или серо-буро-малиновых шляп не имеется) Чтобы исключить этот вариант, надо немного перефразировать вопрос задачи, например так: "Маги просят гнома назвать цвет шляпы"P.S.: Кеос, это ты чтоли? о_О))

Спасибо ДОУ за премодерацию моих комментариев, да здравствует цензура и долой живое общение.Где Веб 2.0 ребята?

martin, а еще гномы могут поднять восстание против магов и выжить все! Какие мы все тупые что об этом не догадались сразу.Ответ 0. Я победил в конкурсе?

63, гномы могут перед приходом магов встать в такую же шеренгу и узнать свой порядковый номер.считаю, что идеальным был бы ответ — выбор оптимальной стратегии самими гномами из описаной в п.5 или п.45 исходя из дополнительных условий. Чем больше гномов, тем больше вероятность того, что стратегию 5 можно будет заменить на стратегию 45 и будут бОльше потери.А могу ещё один вариант предложить: если предположить, что гномам можно дотронутся до впереди стоящего рукой или ногой, то первый как всегда камикадзе, а следущие называют цвет своей шляпы и дотрагиваются рукой впереди стоящего гнома если шляпа у него белая или ногой если шляпа черная.ПЫ СЫ. правильный ответ не смотрел и не собираюсь, так обсуждать интереснее)

Не буду ругаться против (любителей) вольных трактовок условия, однако сделаю некоторые пояснения.В этих задачах (как в исходной, так и в моей модификации) речь идет не о вероятностной модели (матожидание выживших), но о количестве гарантированно выживших гномов (см. принцип максимина).Кроме того, статистические методы здесь не применимы по той простой причине, что нет никаких оснований считать последовательность цветов случайной. Исходить надо из худшего случая — маги знают стратегию гномов и могут исходя из этого подбирать цвета.Так как колличество гномов бессконечно, а шапок конечно — данная последовательность шапок псевдослучайна и имеет определенный период.Это просто неверно. Несложно доказать, что, например, последовательность результатов подбрасывания монетки с вероятностью 1 не является периодической.

Роман, я наверное слишком давно учил математику, но скажите мне как знание хвоста бесконечной последовательности НЕЗАВИСИМЫХ случайных величин может дать информацию о начале, мне кажется что если маги будут одевать шапки независимо и равновероятно то шансы каждого гнома выжить равны 50% независимо от положения в шеренге.В чем здесь прокол?

Эдинственно верное решение для поставленной задачи (с конечным числом гномов) передача информации следующему гному о четности/нечетности белых/черых шляп.Например 45-й вариант с деление на тройки будет работает только при условии что каждый гном будет считать колличество ответов и определять свою позицию в тройке (остаток от деления колличества ответов на 3) — это необходимое условие при выборе такой стратегии. А такие вещи не стоит забывать указывать явно на собеседовании.Вариант 58 вообще в корне неверен. Потому «не черный» — это не «белый», а любой цвет кроме черного, это может быть «зеленый». А в условии задачи явно сказанно что гном должен назвать цвет шляпы на своей голове, а это или «черный» или «белый».Усложненный вариант задачи, номер 17-ть имеет не одно решение. Если суть исходной задачи в передачи информации, то в модифицированной в выборе эффективной стратегии анализа исходных данных, и принятии решения.Неверная стратегия анализа данных приведет к тому что вероятность выжить первого будет 50% и будет уменьшаться по мере уменьшения колличества данных. Причем у последнего будет такая же 50% вероятность выжитьЭффективная стратегия же приведет к тому что вероятность выжить первого будет 99.9%, а у последнего только 50%.Например: 1. Так как колличество гномов бессконечно, а шапок конечно — данная последовательность шапок псевдослучайна и имеет определенный период.2. Использование статистических методов анализа распределения: Например: дихотомия (до пока не надоест) и счет белых/черных шапок в группах с последующей нормализацией результатов вычисления вероятностей. Тоесть есть последовательность 1...N, (посчитали вероятности), поделили 1...N/2 N/2...N (посчитали вероятности) и так до того момента когда вероятность определить свой цвет не будет например выше 95%.

mickolka: прокол в том, что у гномов все же есть информация — цвета шляп впереди них, так что они вовсе не должны играть в орлянку.Более того, каждый из них видит бесконечное количество шляп впереди стоящих — и этого оказывается достаточно для существования нужной стратегии.

Скакунов Александр, если внимательно прочитать 17-й коммент, то становится ясно, что там решения не существует, человек наверняка ошибся — ГНОМЫ НЕ СЛЫШАТ ОТВЕТОВ ДРУГИХ ГНОМОВ — это значит, что каждый ответ индивидуальный и это является рядом независимых испытаний в теории вероятностей, ГНОМОВ БЕСКОНЕЧНО МНОГО — это значит, что для того, чтобы число убитых было конечным, то в 1 прекрасный момент убийства должны прекратиться, чего быть не может (из предыдущего вывода).Для того, чтобы это понимать не надо быть математиком, а математики ошибаются, потому что они тоже люди.Дальше обсуждать задачу нет смысла, решение было озвучено в 9 комменте и аналогичном 5-м.

Нет слов, цикл задач наверное не стоит продолжать в будущем так как с этой аудиторией это неминуемо превратится в конкурс «Найди самое оригинальное неправильное решение»

Не, так, а в чем обида? Как написано в самом начале поста,

ответы на все эти вопросы есть в открытом доступе на сайте оригинала

так что, зная правильный ответ, постить его сюда не имеет смысла. А вот дойти до него самому, в дискуссии, начав от вырезанной магами деревни и постепенно уменьшая процент жертв — это уже интересно, согласны? Я к тому, что дискуссия в этой ветке (даже с приколами) имхо ценее правильного ответа: например, в комменте № 17 дан усложенный вариант задачи.

Нет слов, цикл задач наверное не стоит продолжать в будущем так как с этой аудиторией это неминуемо превратится в конкурс «Найди самое оригинальное неправильное решение», либо прийдется привлекать юристов к доработке условий перед публикацией.ЗЫ, еще напомнило древнюю тему «взлетит или не взлетит» http://forum.ixbt.com/topic.cg...

По-любому, могут выжить все, если первый гном удачливый) Из условия задачи не следует, что нужно говорить чётко «чёрный» или «белый», значит, можно говорить как «не белый» (чёрный), так и «не чёрный» (белый) — варианты сгодятся, так как цветов всего два (простая унарная операция отрицания...)). Таким образом, первый должен глянуть на гнома, стоящего после него и решить, что он скажет...Допустим, у второго гнома белая шляпа, тогда первый должен ответить либо «белый», либо «не белый» (полагаясь на свою удачу, угадать свой цвет), при этом второй поймёт, какого цвета у него шляпа (он ведь услышит слово «белый» и поймёт, какого цвета шляпа у него — об этом гномы могут договориться ещё до всего этого). Если ему повезёт, то выживут абсолютно все, так как второй и последующие за ним гномы будут придерживаться этой же стратегии, называя свой цвет с подсказкой впередистоящему о цвете его шляпы. Ну, а если не повезёт... тогда умрёт только один, зато он спасёт второго и всю колонну в целом) В общем, всё элементарно)

Чмтати ці коментарі після того як прозвучала правельна відповідь...Пропоную інше питання для співбесіди — задача про гномів і 2 відповіді на неї правельна і будь-яка неправельна. Причому правельна відповідь починається зі слів «Увага! Правельна відповідь».Кандидату пропонується вибрати з двох відповідей одну правельну.Думаю такий тест відсіє багато кандидатів (якщо вибірка буде по дописувачах до цього форума)

много камментовбольшинство читают только последниена самом деле ответы 51 и 5 одинаковыдискуссию можно закрывать

к 49 jzk.при чем тут ваш подход? подходите как угодно. а ответ будьте добры дать в виде «цвет шляпы текущего гнома».

Нечетные номера говорят четным их цвет, четные называют услышанный цвет.Выживают все четные гномы (50%) плюс случайно угадавшие нечетные, чей цвет был рядом с соседом (25%) Итог: 75% выжило.

to FOVСупер! Мегареспект!

На мою думку треба привязуватися до парна/непарна кількість гномів з чорними шапками.Перший гном рахує чи парна кількість гномів з чорнимим шапаками стоїть перед ним. Якщо парна, каже чорна, в іншому разі каже біла. Тепер наступний гном рахує кількість чорних шапок перед собою. Якщо парність чорних шапок не помінялася, значить на ньому біла і він каже біла. Якщо помінялася то каже чорна, і всі гноми чують його відповідь і знають що при слові чорна міняється парність на протилежну. І так далі...Мінімальні втрати 1 гном.

Непонимаю, откуда берется цифра 50% в постах 9 и 27. В условии не сказано, что количество белых и черных шапок равно. Ч то мешает магам надеть их на гномов в пропорции 1/5? Я думаю, более правильный ответ с xor описаный в посте 45. При таком раскладе, выживших гномов 66%-100%.

В відповідь на 41.Якщо в людини комплекс неповноцінності і багато нереалізованих функцій по поверненню цілого числа це ще не причина флудити і переходити на образи. Чи я неправий? Ау адміни? По суті я сказав вже в 33 пості, що я лише хочу показати не тільки математичний підхід.Скільки людей — стільки і думок.Я вважаю, що для розвязку задачі з максимальними втратами в 1 гнома, можна розширити відповідь до 2 бітів.Не завжди щлях запропонований замовником є найкращим. Дивіться ширше. "Відрий очі"© ictv.:)

47, кто флудит не понял? где два решения исходной задачи? что-то я не заметил. вариант считать шляпы впереди стоящих — не подходит

господа еще раз призываю к порядку и давайте не будем флудить по поводу задачи дважды решенной в этой ветке.Давайте решать все еще нерешенную здесь задачу про бесконечность гномов, мне кажется она не решается и вот почему.так как гном не слышит то что говорили до него и не знает про то убивали или нет кажного конкрентого гнома то не существует передачи информации, следовательно N-й гном не получает никаких данных от N-1 гнома которых тестировали до него.Теперь в случае если при одевании шляп маги пользовались монеткой (так что получилась независимая и равновероятная последовательность) то N-й гном умрет с вероятностью 50% так как он ничего не знает про свою шляпу ибо не получил никакой информации от предыдущих.В итоге помрет 50% гномов в среднемВот такая вот ситуация, либо у меня где-то прокол либо задача некорректна

мой вариант проходит, если посчитать все шляпы на четность первому и остальным физически невозможно:) (ну много ещё гномов — 10 000 штук)

Предлагаю свой вариант решения построенный на логике: 1. Для простоты пусть белый цвет — 0, черный — 1.2. Гномы условно делятся на тройки. Самый первый и потом каждый четвертый гномы спасают других. Они называют результат логического исключения (XOR) от операции со шляпами двух передних гномов. 3. Каждый второй гном в тройке слыша ответ первого и видя шляпу впереди себя, точно знает какая у него шляпа.4. Каждый третий в тройке слышит ответы первого и второго и безошибочно определяет цвет своей шляпы.5. Потом цикл повторяется. Гномы хотят жить поэтому не ошибаются и безупречно решают простейшие логические уравнения.Таким образом гарантировано спасены две трети гномов. Шансы остальных 50 на 50.Максимальные потери — треть гномов.

  1. Почитал подумал, считаю, что самая продвинутая идея была по-поводу договоренности о типе четности и цвете.2. В тоже время это не правильно, так как и вправду — рост последующих нескольких гномов может быть одинаковым и их количество может быть очень велико.3. Делаю вывод — задачу надо реализовать для того случая, когда гном видит либо одного гнома спереди либо двух, иначе номер не пройдет.Пытался это сделать, но когда вопрос касается самопожертвования в момент, когда стоит сменить стратегию, и думать дальше...:) то тут проблема, так как появляется человеский фактор у гнома:) гному то не хочеться умирать:). Да и логика сильно усложняется, запутаються гномы, появляется вероятность того, что кто-то ошибется, а ведь там еще и гномы-дети и пожилые гномы:) одними можно жертвовать, другими нельзя:) Короче парил мозг 2 часа, в итоге — надо либо конкретизировать задачу, либо склониться к решению о договоренности о типе четности и цвете. Когда утрясется постановка задачи — будем включать теорию вероятности, не стал сам этого делать, т.к. то что очевидно для меня, не очевидно для других и т.д. Мы же не американцы!

mars ответь мне, зачем ты убил двух лишних гномов:) вообще-то поражает, математика — она ведь точная блина наука, я думал то же самое и про программирование, так почему программисты всегда ищут свой единственный и уникальный путь к неправильному познанию истины в то время как правильный путь лежит у их ног? Или программированием у нас в стране стали заниматься люди которые не прошли по конкурсу на философию?

:) Еще вариант. Для начала пусть их будет десять. Три первых почетно умирают, но сообщают число белых шляп на остальных семи (2^3 — 1 = 7). Зная это, все семь успешно отгадывают цвет своей шляпы. Таким образом макс потери — 3.В общем случае для N гномов кол-во смертников — минимальное n, такое, что n + 2^n — 1 > = N.Т. е. порядка двоичного логарифма.

2jzk. в таком случае предлагаю рассказать сказку магам, спеть колыбельную. глядишь уснут, и убивать перестанут.ну сами же выделили что его спрашивают? и что он должен ответить? интересно, как вы из функции целое число возвращаете:)?

Ой, протупил. Типа первый говорит число, двоичное представление которого он видит, и умирает., но это чуть гуманитарно, если учесть что говорить можно одно из двух.

2 andy78 — А чё я?:) Я только задание перевел.

Правильный ответ — Шифратор! Скакунов Александр, Правильно?

Таки неправильно. Сорри за глупость. Был неправ.:)

Гном называет цвет впереди стоящего. Макс потери — 1 человек. Или я неправильно понял условие?

Если самый высокий гном видит остальных то визуально определяет преобладающее количество черного или белого цвета и говорит цвет преобладающий. Таки образом сохранится преобладающее количество гномов возможно +1, если цвет его шляпы совпадет с преобладающим, слышащие его должны поддерживать туже логику.

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

serge lorich, в умові сказано наступне: "Затем, начиная с самого высокого гнома (в конце шеренги), они спрашивают его, какого цвета шляпа не нём надета. Если гном ошибается, маги убивают его (другие гномы слышат его ответ, но не могут определить, был ли он убит или нет)."Гном видає колір шапки в зручному йому форматі. Принаймі на формат відповідей в умові обмежень немає.З.І. Правильну відповідь завжди можна знайти на сайті з запитаннями.Я просто пропоную інший підхід.

jzk, не перекручивайте условие. гном называет цвет своей шапки.

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

нечётные говорят цвет чётных рядом стоящих, чётные говорят уже названый чётным цвет...т. о. уже N/2, ну, и + вероятность повторения шляп ето N/2 то есть N-N/2-N/2/2 = вероятных смертников.

Niraxoid, без суттєвої різниці. Тоді зправа/зліва заміняєм на поередній/наступний відповідно.

Jzk, постойте, а как это «сосед слева», я понял из постановки задачи, что они все стоят в одну колону по росту, начиная от высоких и заканчивая низкими, лицом в сторону уменьшения роста...разве не так?

Все дуже просто: 1. Перший гном при запиті мага видає відповідь наступного формату «колір_шапки_сосіда_зліва; випадковий_колір» а) як наслідок перший гном загине з ймовірністю 50% б) наступний гном знає колір своєї шапки2. Всі наступні видають відповіді такого формату «колір_шапки_сосіда_зліва; власний_колір_почутий_від_сосіда_зправа» а) ніхто з них не загине3. Останній гном видає «власний_колір_почутий_від_сосіда_зправа» Отже загине лише один гном з ймовірністю 50%

mickolka: про аксиому выбора можно почитать в википедии, есть еще целая неделя чтоб подумать:)

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

Что-то наблюдается много гуманитариев, придирающихся к формулировкам, а не ищущим решения.Господа, решайте задачи, а не торгуйтесь, в математике ведь даже непрерывность есть, вещь с бытовой точки зрения совсем бредовая.Еще было бы интересно послушать решение в случае бесконечности, мне на первый взгляд кажется что это невозможно, но бесконечность она штука странная, и к стыду моему я совсем не помню что такое аксиома выбора: (. Мистер http://ro-che.info/ — пожалуйста, решение в студию! А вообще задачки тема очень интересная. Спасибо что затронули.

так что ихний, «канонический», ответ должен включать в себя ещё такой пункт: «перед приходом магов, все гномы одного роста должны самоубиться так, чтобы в итоге у них у всех был разный рост и чтобы при построении их по росту каждому гному было видно всех следующих»:)) А если рост гномов не слишком разнообразен, это будет не совсем оптимальная стратегия))

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

Да не, все правильно, для четности неважно. Это я погорячился.

Sniff, ну так поделитесь соображениями тогда:)

Sniff, зачем им знать убит он или нет? Если гномы заранее договорились, что первый гном выдаст полезную инфо для других гномов. И не важно погибнет 1-й или нет — он надеется на случай.А другим гномам важна инфо, которую передаст первый устно, а не факт его смерти.Например, самый просто вариант: Чтобы спасти друг друга, каждый гном называет цвет впередистоящего гнома. Тогда впередистоящий гном 100% останеться жив, потому что ему помогли «сзади». Только у первого есть вероятность погибнуть и величина этой вероятности зависит от количества гномов и шляп каждого из цветов.

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

Ха, все похвастались глубоким знанием? Теперь ВНИМАТЕЛЬНО читаем условие: > другие гномы слышат его ответ, но не могут определить, был ли он убит или нет

Дмитрий Кузнецов, по поводу сообщения № 9. Согласен, но: Самый первый гном должен иметь хорошее зрение, и проходить тренировку в подсчете количества шляп определенного цвета в экстремальных условиях (угроза жизни) на время. Ведь если количество гномов больше 1000, то вряд ли он успеет досчитать до конца все шляпы. Я так понял у гнома есть время на ответ о цвете шляпы? Если приходит timeout, то его убивают? А если гномов достаточно много, что разрешающая способность зрения самого высокого гнома не даёт приемлемый результат, и ему кажеться что там далеко это не две шляпы, а одна? Тогда его ошибка может привести к гибели многих гномов!:) Плюс процедуру подсчета контрольной суммы приходиться выполнять каждому гному кроме последнего, за один день при большом количестве гномов магам не управиться:)

2Скакунов Александр: всегда найдутся люди типа миколки или Дмитрия Кузнецова, которые переведут конец фильма с точностью до названия переменных:)

2IgorТак вы наверное к магам на работу устраивались? Этот вопрос задают только на собеседованиях у гномов...

за 8 лет работы ниразу не спрашивали этот вопрос на собеседованиях. Может есть другие кандидаты на № 1;)

2 Дмитрий Кузнецов: смысл тот же, что публиковать здесь текст задачи — 1) не все знают инглиш, 2) прочитать ответ всегда проще, чем сесть и подумать — к последнему мы и призываем, 3) дать возможность обсудить задачу и её решения, 4) опубликованный где бы то ни было ответ — не всегда единственный, верно?

Кстати, посмотрел тут... на странице цикла есть решения. Смысл здесь публиковать ответ если он есть там?

Один гном который называет цвет шляпы первым умрет с вероятностью 50%, остальные выживут, если будут придерживаться правильной стратегии. Первому нужно посчитать четность одного из видов шляп (договориться изначально какого и какой цвет сказанный первым что будет означать — четное количество или нечетное). Все слышат ответ. Первого гнома убивают (или не убивают, если случайно цвет означающий четность оказался цветом его шляпы). Теперь остальные гномы знают четное количество шляп, допустим, белого цвета или нет. Допустим количество четное. Следующий гном смотрит вперед, если количество все еще четное — он говорит что на нем черная шляпа. На следующем гноме шляпа белая. Он видит что впереди нечетное количество белых шляп и поэтому знает что на нем именно белая шляпа. Все последующие гномы теперь знают что количество белых шляп стало нечетным. Ну и так далее. Короче, при этой стратегии выживают в лучшем случае все, в худшем — одного первого гнома убивают.

2vanoasв твоем случае количество жертв будет ДАФИГА, ибо только последний гном назоветцвет СВОЕЙ шляпы:)

Каждый третий гном, начиная с первого, говорит БЕЛАЯ, если шляпы рядом стоящих гномовсовпадают, и ЧЕРНАЯ, если нет.В результате имеем 66% точно выживших (ну и 50% от оставшихся 33%)

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

Готовимся к приходу гугла? Ответ — пол гнома.Решение — пусть 0 — белый 1 — черныйСамый высокий камикадзе говорит 0 если сумма перед ним черных четна и 1 если нечетна, его убивают с вероятностью ½ (ну или 1 если маги просекут этот алгоритм и специально его подставят) Далее второй знает какая у него шляпа, ее и называет. остальным нужно только внимательно считать, так как они видят конец и знают что говорили до них.

> Какой стратегии должны придерживаться гномы, чтобы минимизировать количество убиенных гномов? Убить всех магов на подходе к деревне.Каково максимальное количество гномов, которые будут убиты при использовании оптимальной стратегии? 0.

Т.е. каждый нечетный гном предупреждает чётного, какой цвет шляпы у этого чётного? Я когда кумекал над задачей тоже что-то похожее придумал, только ответ оказался во много раз оптимальнее (в смысле минимизации потерь)...

Как на меня, то гномам нужно за год придумать план, и когда маги придут, напасть первыми и всех их убить:)

Стратегия: 1.Первый, самый высокий гном, говорит цвет шляпы того, кто стоит перед ним.2.Второй произносит ответ первого.3.Третий говорит цвет шляпы следующего, т.е. четвертого.4.Четвертый произносит ответ третьго.И т.д.Максимальные потери = (N/2 + 1) гномов (N — общее кол-во гномов).

Подписаться на комментарии