Как сдвинуть гору Фудзи? Подходы ведущих мировых компаний к поиску талантов
Шрифт:
Эта головоломка — еще одно упражнение в рекурсивных рассуждениях. Чтобы найти решение, нужно понять, что ситуацию с n пиратов можно анализировать на основе ситуации с n — 1 пиратов и т. д., пока вы не доберетесь до «базовой ситуации», решение в которой будет абсолютно ясным.
Базовая ситуация — это один выживший пират. Очевидно, что единственный пират предложит отдать ему все монеты. Ход сделан!
А что если пиратов двое? Старшему из них придется предложить, как делить добычу. В условии головоломки говорится, что предложение принимается, если «по крайней мере половина пиратов» за него проголосует. Это значит, что достаточно одного голоса старшего пирата, чтобы предложение было принято. Следовательно, если пиратов всего двое, то старшему из них бояться нечего, и он
Может показаться, что старший пират всегда получит то, чего он хочет. Не совсем так. Представьте, что он решил воспользоваться тем же трюком, если пиратов трое. Давайте пронумеруем пиратов, начиная с самого младшего: № 1, № 2, № 3. План раздела добычи должен предложить номер 3. Если он предложит такой план: «Все достается мне, а вы, ребята, ничего не получите», то следующий пират в этой последовательности (№ 2) точно проголосует против подобного предложения. Пират № 2 знает, что он сам получит все, если останутся только два пирата после того, как № 3 будет убит. Решающим оказывается голос пирата № 1. Он ничего не получает, если проголосует за план пирата № 3, но также ничего не получит, если проголосует против, если останутся только два пирата. У него нет никаких причин, чтобы предпочесть один вариант другому.
Итак, если № 3 умен, как это предполагается в головоломках, он попытается получить поддержку пирата № 1. Нужно также учесть, что пират № 3 жадный, и он готов отдать другому пирату только необходимый минимум. Логичным предложением со стороны пирата № 3 будет дать № 1 одну золотую монету, № 2 — ничего, а ему самому — оставшиеся девяносто девять монет! Поскольку № 1 также рассуждаете логично, но поймет, что и эти жалкие гроши лучше, чем ничего, а ведь он ничего не получит, если пират № 3 будет убит. Пират № 1 проголосует за план раздела добычи (как и № 3, конечно), и это предложение будет принято двумя голосами против одного несмотря на все проклятия накачавшегося с горя ромом пирата № 2.
Теперь рассмотрим ситуацию с четырьмя пиратами. Четыре — это опять четное число. Это значит, что самому старшему пирату достаточно всего одного голоса, кроме его собственного, чтобы его предложение прошло. Ему нужно ответить на вопрос: «Какой из голосов остальных трех пиратов окажется самым дешевым?»
Вернемся к ситуации с тремя пиратами. Пират № 2 не получает в ней ничего, поэтому если пират № 4 предложит ему хотя бы что-то, то для пирата № 2 будет логично проголосовать «за».
И получив голос пирата № 2, пират № 4 может совсем не беспокоиться о том, что думают № 1 и № 3. План пирата № 4 будет таким: ни одной монеты для № 1, одна монета для № 2, ни одной монеты для № 3 и девяносто девять монет для него самого.
Теперь модель нам ясна. В каждом случае самый старший пират должен «купить» ровно столько голосов, сколько ему необходимо, и как можно дешевле. Все остальные деньги достанутся ему самому.
Теперь применим эту модель к ситуации с пятью пиратами, о которой речь и идет в задаче. Вы пират № 5. Вам нужно три голоса: ваш собственный и еще два. Таким образом, вам нужно что-то дать двум пиратам, которые больше всего проиграют, если пиратов останется только четверо. Это пираты № 1 и № 3. Оба не получат ничего, если вас убьют и останется всего четыре пирата. Обоих можно убедить проголосовать за ваш план, если он им что-нибудь сулит. Ваше предложение: ничего не давать пирату № 4, дать одну монету № 3, ничего не дать № 2 и дать одну монету № 1. Оставшиеся девяносто восемь монет вы оставите себе.
Это одно из тех абсолютно не соответствующих здравому смыслу решений, которые убеждают многих людей в абсурдности логических головоломок. Если бы пираты формировали коалиции на основе дружеских отношений (что и происходит в телешоу «Последний герой»), все эти рассуждения оказались бы бессмысленными. Но даже если не принимать в расчет возможные дружеские коалиции, решение все равно выглядит сомнительным. Вы можете
Эту головоломку использует компания Fog Creek Software из Нью-Йорка. По этому поводу в одной из интернет-конференций появилось сообщение: «Готов поклясться, что генеральный директор Fog Creek загребает 98 процентов прибылей этой компании. Реальная причина, по которой в ней задают этот вопрос, — желание найти смиренных овечек, готовых с этим мириться, если получат какое-нибудь математическое объяснение». [168]
168
168 «Готов поклясться, что генеральный директор fog creek.» jeremy singer «online posting» http://www.realrates.com.
Первая вещь, которую необходимо понять, — эта головоломка просто обязана быть проще, чем она кажется на первый взгляд. Ваши интервьюер слишком занят, чтобы сидеть и ждать, пока вы пройдете все сто шагов. Должен быть какой-то трюк, который позволит упростить решение, и ответ должен быть относительно простым. Или все 100 шкафчиков должны остаться открытыми, или ни один из них, или должна отыскаться какая-то закономерность, которая позволит легко решить, сколько будет открытых шкафчиков.
Ваш нетерпеливый интервьюер некоторое время будет сидеть спокойно, пока вы начертите таблицу с номерами с первого по десятый. Сделайте это и делайте отметку в клетке, относящейся к данному шкафчику, если положение его дверцы изменилось. Например, в первом цикле все 100 шкафчиков будут открыты. И вы поставите в таблице соответствующие отметки.
Во втором цикле вы поставите отметки в клетках с четными номерами 2,4,6,8 и 10. Продолжите это до десятого цикла (если бы вы продолжили это делать до 20, 30, 40 и т. д. — у вас получилась бы полная таблица). После десяти циклов ваша таблица будет выглядеть так:
И следующие циклы никак не повлияют на первые десять шкафчиков — ведь во время одиннадцатого цикла будет меняться положение дверец только шкафчиков номер 11, 22, 33. Таким образом, составленная вами таблица для первых десяти ящиков окончательная. Поскольку в начале шкафчики были закрыты, то все шкафчики, положение дверец которых изменилось нечетное количество раз, останутся открытыми, а если положение менялось четное количество раз, шкафчики будет закрытыми.
Это означает, что после 100 циклов шкафчики 1, 4 и 9 останутся открытыми, а все остальные закрытыми. 1,4 и 9 — это точные квадраты, то есть числа, умноженные сами на себя (1 = 1х1; 4 = 2х2; 9 = 3x3). Это очень привлекательная закономерность.
Вы понимаете, почему открытыми остались только те шкафчики, номера которых — это квадраты какого-то числа? Вы столько раз меняете положение дверцы шкафчика, сколько есть множителей в числе, соответствующем его номеру, а эти множители — парные. Например, двенадцать — это 1х12, или 2x6, или 3x4. Поскольку есть три способа разбиения этого числа на пары сомножителей, общее число сомножителей — шесть. Это значит, что положение дверцы этого шкафчика изменится шесть раз. Единственный способ, которым число может избежать четного количества сомножителей, — это такая ситуация, когда его можно представить как пару из двух идентичных сомножителей. Например, девять можно представить как 1 х 9 и также как 3x3. Это дает только три различных сомножителя (1, 3 и 9). Только те шкафчики, номер которых — это квадрат какого-то числа, будут открываться/закрываться нечетное количество раз, и только их дверцы останутся открытыми.