Трудный вопрос на собеседовании #8
Скакунов АлександрОпубликовано 21.07.2008 в Учеба
Продолжаем разбираться с циклом задач “Трудные вопросы на собеседовании“.
Какое предложение лучше и почему:
- Вы делаете утверждение. Если оно истинно, Вы получаете ровно $10. Если же утверждение ложно, Вы получаете либо больше, либо меньше чем $10, но точно не $10.
- Вы делаете утверждение. Вне зависимости, ложно оно или истинно, Вы получаете больше чем $10.
UPDATE: ответ.
Загрузка ...Понравилась статья? Подпишись на обновления по RSS/E-mail
Возможно в качестве утверждения надо сказать что-то типа такого : “я получу > 10$”,
тогда 10 дать не могут т.к. это уже не истина
и меньше 10 тоже т.к. это это будет истиной
т.е. ответ - 1
P.S. если конечно имелось ввиду что лучше если $$ больше )
Вспомнилось это: http://davydov.blogspot.com/2008/02/blog-post_09.html
Задача, схоже, статистична, або швидше навіть на границі функцій.
2 варіант вигідніший, тому що незалежно від кількості тверджень за кожне з них буде нараховано >10 $, тобто середня кількість грошей за одне твердження при кількості тверджень, що прямує до безмежності, буде 10+епсилон. При першому ж варіанті середня кількість прямуватиме до 10 (принаймі якщо припустити, що може бути нараховано і від’ємну кількість грошей, а розподіл грошей симетричний відносно 10)
Ежу понятно первый вариант лучше, ибо можно сделать утверждение “я получу меньше 100 000 000 $, но не 10$”
Правильным оно не может быть, ибо тогда я получил бы 10$ что противоречит утверждению… ну а чтобы оно было неправильным, придётся давать 100 лимонов или больше
Оба предложения асимптотически эквивалентны
Після того, як прочитано кілька коментарів (в яких, думаю, вже є “вірна” на думку автора відповідь), виникає кілька питань:
А що трапляється якщо істинність твердження встановити неможливо? (Як відомо завдяки Гьоделю, таке твердження завжди існує
В який момент відбувається встановлення істинності твердження? Що, якщо твердження стає істинним (чи припиняє бути істинним) в деякий момент часу?
Olexiy, а какое это имеет значения для ответа на задачу? Я полагаю, если правильность вопроса нельзя определить, то и получаемую сумму тогда нельзя определить тоже. И?.. Обратите внимание, что истинность утверждения имеет значение только если мы выбрали первый вариант, от чего ваш вопрос выглядит ещё более академическим. Вы бы ещё спросили кто бреет брадобрея
>> Я полагаю, если правильность вопроса нельзя определить, то и получаемую сумму тогда нельзя определить тоже.
І, до речі, вміння знайти двозначності - також ціниться 
Ну от це ви так думаєте. Можливо, що автор задачі думає інакше. Просто умова - неповна. Крім того, якщо на співбесіді ви продемонструєте знання теореми Гьоделя - вам буде плюс
>> Обратите внимание, что истинность утверждения имеет значение только если мы выбрали первый вариант, от чего ваш вопрос выглядит ещё более академическим.
В корені невірно.
По-перше, хто сказав, що обидві суми в другому варіанті - однакові? Може за істинне дають 20 баксів, за неістинне - 30, а інакше - 40?
По-друге, в другому варіанті так само нічого не сказано про такі твердження. Там сказано, що дають більше десяти баксів і за істинне, і за неістинне - але існують твердження, які не є ані першим, ані другим.
І, нарешті, по-третє - вибрати варіант можна тільки знаючи відповідь на моє питання - якщо, наприклад, у відповідь на невиводиме твердження ми отримаємо мільйон - то я беру перший варіант!
очень очень сильно сомневаюсь
ну, там чёрным по белому пишет — Вне зависимости, ложно оно или истинно. Вам как ещё сказать?
Скажите, а, скажем, в задаче про ханойские башни вы тоже начинаете нудить — а гибкие ли блины, а можно ли их разобрать, а снимаются ли стержни?.. Я бы это не назвал практичным подходом, вы программер или матанщик какой-то?
И, наконец, если вы посмотрите на предложенное мной решение, вы увидите что можно обойтись без невыводимых решений и получить любую сумму что вы назовёте. Так зачем усложнять? Чмоки. То есть я хотел сказать KISS
По поводу того, что постановка задачи обязательно должна быть предельно, математически, нечеловечески чёткой — сдаётся мне, такую глупость может сказать человек, никогда в жизни не видевний ни одного ТЗ. И никогда не получавшего вообще никаких задач. Всё ж таки надо постараться угадать что в задаче подразумевается
>> якщо на співбесіді ви продемонструєте знання теореми Гьоделя
>> очень очень сильно сомневаюсь
Можливо, ми з вами проходимо співбесіди в різні компанії
>> ну, там чёрным по белому пишет — Вне зависимости, ложно оно или истинно. Вам как ещё сказать?
Ви не виривайте половину твердження. Ви витягнули з твердження “Якщо Вова важить 100 кіло, то він важчий від мене” фразу “Вова важить 100 кіло”. Що, хіба мій варіант “за істину 20, за неістину 30″ не задовільняє умові задачі? Істинне твердження чи ні, ви отримаєте більше 10. Ніби збіглось.
Про ханойські вежі - якби мені сказали, що є чотири вежі, а розповіли тільки про три, то я б поцікавився про четверту
Я бачив ваш розв’язок, і чому і поставив своє останнє запитання:
Коли визначається істинність твердження? А якщо цього зробити не можна?
Ви сказали: “я получу меньше 100 000 000 $, но не 10$”. Ну добре. З одного боку, спочатку треба вирішити чи твердження істинне, а потім дати грошей. З іншого, допоки грошей не дадуть, істинність встановити неможливо. Замкнуте коло
>> Всё ж таки надо постараться угадать что в задаче подразумевается
Так, у нас в проекті деякі так робили. Просто є ризик не вгадати.
видимо да, и притом в очень разные компании. Я, например, хожу в программерские. Хотя безусловно, всё зависит от интервьюера, если у него в детстве было увлечение математикой, то знание трудов Гегеля безусловно поможет. Ой, то есть Гёделя
ну, это просто напросто не известно. По условию задачи. Так в и жизни иногда бывает
Вы что же, не можете представить что вам в жизни поставили такие условия, и предложили выбрать? Не можете представить, что в ответ на все ваши попытки уточнить вам не отвечают, а только таинственно улыбаются, и вам всё равно надо выбрать один из вариантов?
сэр, вот здесь вы точно не правы. Вы говорите о всяких теоремах-штеоремах, но не знаете как доказывают от противного?… “Предположем, что это утверждение истинно……приходим к противоречию……. что и требовалось доказать.” Пробелы заполните?
Конечно, всему надо знать меру. Просто ваш подход мне кажется другой крайностью — уточняя детали, которые не являются частью постановки задачи, вы просто напросто либо за*бёте кустомера, либо шаг за шагом заставите его сформулировать решение
Первый исход, конечно, вероятнее 
Кстати, даже если, допустим, получаемая сумма зависит от правильности ответа, что для вас, как для решающего задачу, изменилось бы, если бы там было написано (или если бы мы так трактовали эту фразу)
Вы считаете, это как то повлияло бы на ответ, то есть могло бы сделать этот вариант более предпочтительным? Каким образом?
>> “Предположим, что это утверждение истинно……приходим к противоречию……. что и требовалось доказать.” Пробелы заполните?
Так, я заповню деякі пробіли. Ваші знання матлогіки зупинились у 19-му сторіччі (== на рівні того, що вчать в школі). Доведення від супротивного в своїй основі містить припущення, що твердження або істинне, або неістинне, і третього не дано. Те, що це невірно, довели в двадцятому столітті, а зараз вчать на другому курсі університету, на парах з матлогіки.
А краще давайте підемо спати - саме час
хе-хе, подловил
Спасает то, что обычно (не всегда, ага) в таких случаях у нас либо в обоих случаях противоречие, либо в обоих случаях его нету — этого более-менее хватает для обыденных ситуаций, тем более что подобные прадоксы обходятся, насколько я помню, формальной логикой, с позиций которой мы запаримся эту задачу решать 
Кстати, можете привести пример парадокса, не выводящего к взаимному противоречию или подтверждению противоположных гипотез, а однозначно наталкивающего на (неверный) вывод?
что вы, самое время когда совы летают
Если количество моих НЕ ПРАВИЛЬНЫХ утверждений -> 0, то для первого варианта количество заработаных денег Х*10$,
для второго вариата - X*(10+a), где Х - количество попыток, а > 0. Т.е второй вариант однозначно выгоднее.
Если количество моих ПРАВИЛЬНЫХ утверждений -> 0, то учитывая то что в первом варианте оплата за каждый ответ может колебатся от 0 до
бесконечности исключая 10, а во втором варианте от 10 до бесконечности - варианты при количестве проб стремящемся к бесконечности будут одинаковы.
–
Исходя из вышесказаного очевидно, помоему, что выгоднее выбрать 2й вариант, поскольку от отлично себя показывает в любых ситуациях, при любом
количестве попыток в независимотсти от правильности утверждения.
Лучший вариант 1. (Учитывая что на собеседовании). Он окажет что ты уверенный в себе человек (будеш получать 10 за правильней ответ).
Вариант 1, 100%
ну вы даете! Никто не смотрел мульт, как чувак всех облапошивал: рассажи мне мне небылицу, если я с ней не соглашусь, то я дам тебе денег, …
Соответственно мужик соглашался со всеми небылицами, и только бравый лодарь сыграл на человеческой жадности его…
я забыл название мультика, но очень поучительный… ДЕТКИ, ДАВАЙТЕ БЫТЬ ЛОДАРЯМИ И ДУРИТЬ ЖАДИН!
Короче, если предположить, что истина где-то там, как говорил Малдер, то второй выгоден, т.к. его мат. ожидание больше… Если же человек судящий об истине и ведающий казной идиот, то развод “умного” лодаря про <100 000 000 $ может и сработать, если этот человек опытный, то он скажет, что утверждение ложь - т.к. ты получишь в глаз а не бабло, а раз ложь - то на свой бакс моральной компенсации…
Согласен с Орехом, задача не до конца сформулирована…
Ну если поставить границу в N баксов, чтобы было наглядней, то выходит так:
P - вероятность
М - мат. ожидание (среднее арифметическое)
для первого:
P(10)=0,5, M(10) = 10
P(<10)=0,25, M(10)=0,25, M(>10) = (N - 10)/2 = 45
M(общ.) = P(10)*M(10)+P(<10)*M(10)*M(>10) = 0.5 * 10 + 0.25*5 + 0.25*(N/2-5) = 5 + N/8
для второго:
P(10)=0, M(10) = 0
P(<10)=0, M(10)=1, M(>10) = N/2
M(общ.) = P(10)*M(10)+P(<10)*M(10)*M(>10) =N/2 * 1 = N/2
Теперь считаем при каком верхнем значение варианты будут равны.
N/2 = N/8 + 5
3N/8 = 5
N = 13,(3)
Выходит что при N > 13,(3) лучше 2й вариант, а при 10 < N < 13,(3) лучше 1й
тогда по аналогии к некоторым предложениям вначале темы говорим, что я получу сумму которая меньше 13,(3) исключая 10, тоесть [0;10)И(10;13,(3)] из этого выходит что при таком ответе в 1м варианте я получаю сумму от 13,3 до бесконечности, а во 2м от 10 до бесконечности )))..
Выходит варинат предложения зависит от того что скажет человек..
З.Ы. Пора завязывать пить во выходным
капец…сайт нагло порезал формулы …БАГА!!!
Ну если поставить границу в N баксов, чтобы было наглядней, то выходит так:
P - вероятность
М - мат. ожидание (среднее арифметическое)
для первого:
P(10)=0,5, M(10) = 10
P(<10)=0,25, M(10)=0,25, M(>10) = (N - 10)/2 = 45
M(общ.) = P(10)*M(10)+P(<10)*M(10)*M(>10) = 0.5 * 10 + 0.25*5 + 0.25*(N/2-5) = 5 + N/8
для второго:
P(10)=0, M(10) = 0
P(<10)=0, M(10)=1, M(>10) = N/2
M(общ.) = P(10)*M(10)+P(<10)*M(10)*M(>10) =N/2 * 1 = N/2
Теперь считаем при каком верхнем значение варианты будут равны.
N/2 = N/8 + 5
3N/8 = 5
N = 13,(3)
Выходит что при N > 13,(3) лучше 2й вариант, а при 10 < N < 13,(3) лучше 1й
тогда по аналогии к некоторым предложениям вначале темы говорим, что я получу сумму которая меньше 13,(3) исключая 10, тоесть [0;10)И(10;13,(3)] из этого выходит что при таком ответе в 1м варианте я получаю сумму от 13,3 до бесконечности, а во 2м от 10 до бесконечности )))..
Выходит варинат предложения зависит от того что скажет человек..
З.Ы. Пора завязывать пить во выходным
to aRt:
У вас в обгрунтуванні є багато неточностей
1) Звідки ви взяли що ймовірність того скільки вам дадуть грошей має рівномірний розподіл, якщо ви вже припускаєте що N обмежене то беріть нормальний розподіл, він більше підходить для реальності.
2) Ніяких обмежень на N не накладається
3) Звідки ви взяли що твердження має бути про те скільки вам дадуть грошей?
Як на мене то вирішувати задачу потрібно з умови.
1) Ми досить точно можемо припустити що в нас як у гравця є 2 можливості “сказати і помилитися” та “сказати і не помилитися”.
2) Ми не можемо з впевненістю сказати що ми будемо праві чи помилимось. Тому я би сказав що обидва варіанти рівноймовірні. Хоча як показує практика якщо двоє льюдей говорять про якусь область то ймовірність помилитися менша в тої котра має більше довсіду, тому розподіл не буде рівномірним, але для академічної задачі можна припустити що він є рівномірним.
3) Оскільки в нас є 2 варіанти відповіді (помилитися або сказати правильно) і є 2 стратегії, то можна скласти таблицю
| сказав правильно | помилився
стратегія 1 | 10 | 10
стратегія 2 | >10 | >10
Звідси дуже добре видно що друга стратегія абсолютно краща за першу.
Возможно автор забыл указать какие утверждения разрешены? Потому что я бы выбрал второй вариант и утверждение: я существую(готов пожертвовать потенциальным миллионом в обмен на ответ на этот вопрос
) ну или там земля вертится!
Подсчеты с нормальным распределением оставляю вам сделать на досуге. мне как то не очень хочется это делать :)..
да это и не меняет сути решения задачи.. во как..
Никаких ограничений и нету. Где вы их увидели? Число N - любой произвольное, хоть бесконечность. Оно использовалось только для нахождения варианта предположения который будет делать человек.
А кто-то ставил ограничения на утверждения?:) в условии есть только слово “утверждение”, а какое оно должно быть - нету. Так же как и у вас на слово “утверждение” и его истинности использовано достаточно фантазии явно не с условия задачи
И вобще, наверное, все думают что 2й варинт лучше, но возникает чувство что здесь подвох и начинаем спасать первый вариант
aRt: Не волнуйтесь про порезанные формулы, в ваших записях столько ошибок, что никто ничего не потерял. Кроме того поставленная вами для самого себя задача имеет такое же отношение к исходной, как бузина к дядьке в Киеве.
Disturbed: Орех же в совершенно простых и понятных терминах описал почему данной формулировки задачи недостаточно. Чтобы проверить ваше утверждение надо знать количество выдаваемых денег, а чтобы знать это количество надо проверить истинность утверждения. Это, наверное, не имеет отношения к тому что хотели проверить этой задачей, но все-таки это правда. И кстати: да, я “матанщик какой-то”.
Вообще мне это напомнило парадокс Ньюкома, кто не знает и кому интересно может над ним подумать:
Представим себе игру, в которой участвуете вы и предсказатель. Предсказатель - это субъект, про которого в задаче известно, что он никогда не ошибается. Вам показывают две коробки - в первой или миллион долларов или пусто, во второй точно тысяча долларов. Вам можно открыть или только первую коробку, или две сразу. Однако за день до того как вы говорите свое решение предсказатель предсказывает ваши действия. То есть на момент когда надо принимать решение, предсказатель уже высказался, но вы разумеется не знаете что он сказал. Если он предполагал что вы откроете две коробки - первую оставляют пустой. Если он предполагал что вы откроете только первую - в нее кладут миллион. Какое решение следует принять?
2 Merlin
А ти не Паша з мехмата і Матеріалайза?
2 Вірт
Ми знайомі?
2Merlin, я думаю парадоксальность задачи Ньюкомба в том, что существование Предсказателя надуманно и нереально и парадоксально само по себе. Следовательно, сам парадокс не более занимателен чем боянчег “А может ли всемогущий субьект создать камень, который он не может поднять?”
В то же время, представленная задача вполне практична. Представьте: я делаю упомянутое мною утверждение. Задача ведущего — сказать, прав я или нет. Предположим, он говорит что я прав…. *skip*
Вы же не видите парадокса в самопротиворечивой фразе по типу “Я большой и маленький”? Она просто неверна. Так же само и предлагаемое мною утверждение самопротиворечиво при заданных условиях игры. Следовательно, оно неверно…. *skip*
ЗЫ. про матанство: вы-то ладно, но с предыдущих ораторов по типу aRt’а я прифигел :). Пожалуй, знание трудов Герринга следует таки считать минусом на программерском интервью
я имею ввиду — ясное ж дело задача на логику, а не на знание матана… (или это только мне так кажется что это ясно?) Во всяком случае, в контексте “Трудный вопрос на [программерском] собеседовании”
так какого ж …. вы тут выводите какие то последовательности как будто сказано что сумма определяется произвольно или как будто вы не можете придумать утверждение которое всегда верно или всегда неверно?
Ведь любому ж понятно, что нужно объяснить оптимальность вашей стратегии независимо от того, по какому принципу даётся приз. То есть стратегия должна быть оптимальна даже если в (2) вам всегда дают 10.01$. Из этого *уже* ясно что (2) не может быть оптимальной стратегией. Дальше надо лишь подумать какое такое утверждение сделать чтобы на нём сорвать куш, то есть любую названную сумму
имхо условий в задаче недостаточно, чтобы делать обоснованные выводы.
2 Merlin
Жаль не видел ваших записей с формулами кроме согласия с тем что задача не полностью поставлена
2 Disturbed
Геррингом не увлекаюсь, а матан для матанов..
Да если уж задача не до конца сформулирована, то и давать оценку правильное решение или нет тоже как-то не корректно. В этом может и есть смысл этой задачи - посмотреть на то как человек может выкрутиться. Все таки программирование дело творческое и в тоже время с области точных наук. Да и на собеседованиях задачки извращенней иногда задают чем эта.
ИМХО, любая задача базируется на некоторых неявно принимаемых утверждениях. И любую дискуссию можно свести к спору об определениях.
На интервью эти предположения можно уточнить явно, демонстрируя “ход своих мыслей”.
Если не хватает данных более продуктивно спрашивать “правильно я понимаю, что “, чем просто требовать “уточните условия, иначе всё это не имеет смысла”.
Между уточняющими вопросами и упоминанием теоремы Гёделя я бы выбрал первое при собеседовании в контору, которая разрабатывает продукт для денег, и второе - при собеседовании на исследовательский проект в институт математики.
В этой задаче (имхо) разумно предположить следующие неявные условия:
1. Наша задача получить как можно больше денег.
2. “Дающая” сторона стремится отдать как можно меньше денег.
3. Дающая сторона имеет три варианта: дать 10$ (вариант “дать в морду” не рассматриваем).
4. Истинность утверждения проверить можно.
В этом случае “лучше” первый вариант, так как позволяет нам явно влиять на получаемую сумму денег (как описано в комментарии #4).
задачка мабуть з “битви екстрасенсов” на тему: “прочитай думки автора”
Автор мабуть вважає себе великим психологом аки Зігмунд Фрейд, або обчитався Джоеля Спольскі
Написал простенькую программку и проверил, что при утверждении 2 денег будет больше..
Это в смысле, в программке подставил в уравнение “почти все числа”?
В какое уравнение? Где в условии сказано про уравнение и что такое “почти все числа”?
Программка на вход получает 10000 псевдослучайных boolean и в зависимости от истинности добавляет (или вычитает) к сумме псевдослучайное количество денег (как описано в условии). Естественно всё это происходит в некоторой дельта эпсилон нуля, дабы небыло переполнения разрядной сетки..
Неопределенность и случайность не одно и тоже.
Товарищи.
наприклад про
Суть не в грошах, а в фішка тому, що ви можете
“афігітєльно” круті питання ставити
холодний термояд, теорію струн і доведення NP-повноти,
і нафіга вам тоді якесь бабло коли при такому джерелі
інформації ви легко досягнете технологічної сингулярності у розвитку …
Думаю суть в тому, що в першому випадку хоча кількість бабла менша,
однак ви отримуєте інформацію, причому на будь-які питання які
вас цікавлять, і тому цей варіант набагато крутіший.
Отак.
http://en.wikipedia.org/wiki/Technological_singularity
Подивився розв’язок
Не вгадав. Зате мій варіант оригінальніший
Ответ:
Ответ ‘используя следующее утверждение: “Я не получу ни $10, ни $10000“’ не подходит к условиям задачи, поскольку приведенная фраза является двумя утверждениями, а не одним.
Господа, а можете ткнуть пальцем - чем второй вариант может быть хуже? Почем вообще могут возникнуть сомнения, что правильный ответ не “второе”?
Кстати, о приведенной в комментах фразе “А может ли всемогущий субьект создать камень, который он не может поднять?” - конечно же может, ибо во власти всемогущего должно находиться и право ограничить свою всемогущесть, и тот факт, что он после этого перестанет быть всемогущим, не противоречит условию.
Вы бы еще про “раньше появилось яйцо или курица” вспомнили - тоже однозначно яйцо, поскольку их еще динозавры несли.
@44.
Во шиза. А если сказать “я не получу вообще ничего” вселенная перестанет существовать потому что это противоречит данному условию?
2 LastHand про всемогущего субьекта: твое обьяснение это лишь придирка к точности формулировки задачи и она не меняет смысла проблемы. Проблему можно переформулировать: сможеть ли субьект создать камень который никто не сможет поднять и остаться при этом всемогущим, или попросту утрируя можно ли присвоить некоторому обьекту одновременно свойства P и ~P.
Поправка, противоречие будет если сказать “я не получу $10″.
2 Щетинин Сергей ну тогда ты с больштой вероятностью вообще ничего не получишь
2 LastHand я не совсем понял где в условии задачи нельзя делать утверждения вида А и Б? А второй вариант очевидно хуже первого потому что в первом ты гарантировано получаешь любую сумму которую пожелаешь.
2 Автор: Решение красивое, но помоему задача не для собеседования. А кто нибудь ее вообще решил без посторонних усилий?
crypto5, на самом деле просто условия задачи несовместимые с реальностью. Любого кто задаст такое на собеседовании надо отстранять от найма людей, а лучше от людей вообще.
Присутствующие здесь технари в большинстве своем хотят вместо простого чтения ТЗ либо проигнорировать часть условий, либо додумать что-то свое.
@47
Это не придирка к точности формулировки условия, это вполне корректный ответ в рамках условия. В условии ничего не было сказано про “остаться после этого всемогущим”.
@49
В условиях задачи сказано “сделать утверждение”, не сказано “сделать несколько утверждений плюс условие об обязательности каждого”. Смотри массу историй про джинов и прочих золотых рыбок - нельзя загадать “хочу быть всегда здоровым, никогда не стариться, не быть убитым, не прибить себя, не погибнуть в катаклизме или несчастном случае, при этом богатым и счастливым - это все мое первое желание”. Потому что после такого собеседования джин скорее всего передумает делать для тебя добро.
Кстати, мой ответ на задачу - лучше второе предложение, поскольку оно гарантирует создание простого кода, который нельзя будет подвесить хитрыми входными данными типа “я не получу 10$”.
LastHand, “присутствующие здесь технари” ещё со школьных лет знают что условие может в себя включать логичекие операции как то И, ИЛИ, и от этого оно не становится двумя условиями.