Найти умного. Как проверить логическое мышление и творческие способности кандидата (Паундстоун) - страница 166

Эту головоломку использует компания Fog Creek Software из Нью-Йорка. По этому поводу в одной из интернет-конференций появилось сообщение: «Готов поклясться, что генеральный директор Fog Creek загребает 98 процентов прибылей этой компании. Реальная причина, по которой в ней задают этот вопрос, – желание найти смиренных овечек, готовых с этим мириться, если получат какое-нибудь математическое объяснение»».

Первая вещь, которую необходимо понять, – эта головоломка просто обязана быть проще, чем она кажется на первый взгляд. Ваш интервьюер слишком занят, чтобы сидеть и ждать, пока вы пройдете все сто шагов. Должен быть какой-то трюк, который позволит упростить решение, и ответ должен быть относительно простым. Или все 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 = 3 × 3). Это очень привлекательная закономерность.

Вы понимаете, почему открытыми остались только те шкафчики, номера которых – это квадраты какого-то числа? Вы столько раз меняете положение дверцы шкафчика, сколько есть множителей в числе, соответствующем его номеру, а эти множители – парные. Например, двенадцать – это 1 × 12, или 2 × 6, или 3 × 4. Поскольку есть три способа разбиения этого числа на пары сомножителей, общее число сомножителей – шесть. Это значит, что положение дверцы этого шкафчика изменится шесть раз. Единственный способ, которым число может избежать четного количества сомножителей, – это такая ситуация, когда его можно представить как пару из двух идентичных сомножителей. Например, девять можно представить как 1 × 9 и также как 3 × 3. Это дает только три различных сомножителя (1, 3 и 9). Только те шкафчики, номер которых – это квадрат какого-то числа, будут открываться/закрываться нечетное количество раз, и только их дверцы останутся открытыми.