30 апр. 2011 г.

Как решать алгебраическую задачку?

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

Первым делом надо понять, что всё это значит. Что такое натуральное число? Непрерывщикам удобно считать, что это целые неотрицательные числа (0, 1, 2, ...), а дискретчики (как и большинство школьников) работают с натуральными числами, не включающими ноль. Вообще говоря, решая эту задачку, можно продемонстрировать понимание этого вопроса: «Если бы речь шла о множестве натуральных чисел, включающих ноль, то правильным ответом был бы 0, потому что это наименьшее n, такое, что n-я степень всех чисел не бывает шестизначным числом (так как нулевая степень любого числа равна единице). Но это слишком просто, поэтому я решу задачу и для более классического определения множества натуральных чисел».

Второй момент - понять, что значит выражение «n-я степень натурального числа не бывает шестизначным числом». О каком натуральном числе идёт речь? Надо понимать, что обо всех. Да, именно так принято выражаться: вместо «никто из кандидатов не решил эту задачку» говорят «кандидаты не решили эту задачку».

Теперь давайте переформулируем задачу, сузив круг поиска. Например, может ли искомое n равняться единице? Не может, потому что шестизначное число в первой степени является шестизначным.

Другими словами, наша задача теперь звучит так: найти целое число n > 1, чтобы никакое натуральное x в n-ой степени не могло быть шестизначным.

Теперь давайте как-нибудь ограничим n сверху. Чем больше x, тем больше xn, поэтому давайте возьмём наименьшее x, которое имеет смысл возводить в степень. Так как единица в любое степени равна единице, мы возьмём двойку.

Программисты, в какую степень надо возвести 2, чтобы получить семизначное число? Чему равно 220? Да, это чуть больше миллиона (1048576) - как раз семизначное. Если мы возьмём число x большее двух, то получим x20 > 220, т.е. заведомо не шестизначное.

Задача стала ещё проще: надо найти наименьшее 1 < n < 20, чтобы для любого натурально x было ложным следующее утверждение 100000 <= xn < 1000000.

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

Дальше можно решить эту задачку, показав свои способности быстро считать и хорошо помнить. Например, можно сказать так:

«Пусть n=2. Так как 10002 = 1000000, то 9992 как раз будет шестизначным числом (если надо, можем явно посчитать его по формуле сокращённого умножения: 9992 = (1000-1)2 = 1000000 - 2000 + 1). Поэтому квадрат точно отметаем.

Пусть n=3. Так как 1003 = 1000000, то 993 как раз будет шестизначным числом. Куб отметаем.

Пусть n=4. Вспоминаем случай n=2 - нам достаточно оценить корень из 999 - это примерно 30. Значит, 304 будет шестизначным (304 = 9002 = 810000), так что и четвёртая степень не подходит.

Пусть n=5. Это легко - 105 = 100000. Поэтому и пятая степень не может быть ответом.

Пусть n=6. Вспоминаем случай n=3. Надо оценить корень из 99. Это примерно 9. Давайте посчитаем 96. Это легко: 96 = 813 ~= 803 = 83 * 1000 = 29 * 1000 = 512000. Как и ожидалось, получили шестизначное число, поэтому n=6 не подходит.

Пусть n=7. Мы помним, что 96 уже около полумиллиона, поэтому в седьмую степень имеет смысл возводить что-то меньшее девяти. Давайте оценим 87. Со степенями двойки всё очень быстро: 87 = 221 (уже больше миллиона). Поэтому пробуем семёрку возвести в седьмую степень: 77 = 493 * 7 < 503 * 7 = 125000 * 7 (чуть меньше миллиона). Так мы разобрались с седьмой степенью.

Пусть n=8. Вспоминаем n=4: 304 является шестизначным, поэтому осмысленно смотреть на корень из 30, округляя вниз. Чему равна восьмая степень пятёрки? 58 = 254 = 6252 ~= чуть меньше полумиллиона.

Пусть n=9. Сейчас уже имеют смысл только очень маленькие x (меньшие 5, потому что 59 ~= 5*полмиллиона уже будет семизначным). Давайте попробуем четвёрку: 49 = 218 ~= чуть больше четверти миллиона. И девятка не подходит.

Пусть n=10. Как мы помним, 410 = 220 больше миллиона, а 210 = 1024. Поэтому остаётся проверить только тройку в десятой степени: 310 = 95. Но мы же помним, что 105=100000 является наименьшим шестизначным числом. А так как 95 < 105, то 95 заведомо не шестизначное. Выходит, мы нашли границу: 310 меньше шестизначного, а 410 уже больше шестизначного. А поскольку мы для всех степеней меньших десяти уже нашли такое x, что xn является шестизначным, то мы решили задачку
».

Я несколько раз слышал примерно такое рассуждение (устно эту задачку рассказывают за 3-4 минуты). Интересно, что рассказывающий решение может не знать ответ (потому что ещё до него не дошёл), но он уверен, что идёт по верному пути (так как уже ограничил n маленьким интервалом, а на каждой из 18 итерации задерживается на считанные секунды). Конечно, двигаясь к ответу, можно было и срезать некоторые углы. Но даже такое переборное решение является вполне неплохим: человек показывает свою способность быстро и адекватно проводить оценки, использовать ранее сделанные вычисления, сосредоточенно и целенаправленно двигаться к цели, не опускать руки на середине пути, не путаться в логике происходящего. Не скрывайте эти свои качества, когда проходите собеседование!

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

Хороших праздничных выходных!

25 комментариев:

  1. Не понял рассуждений для случая n=7. Как знание того, что 8^6 ≈ 250000 помогает понять, что 6^7 и 7^7 — шестизначные?

    ОтветитьУдалить
  2. > Пусть n=8. Вспоминаем n=4: 334 является шестизначным
    Точно вспоминаем? Мы ведь никаких пометок по условию задачи делать не можем.
    Да и оценки не все такие уж очевидные.
    И такое длинное решение перебором в устной задаче скорее всего приведёт к тому, что человек решит, что пошёл не тем путём, бросит и будет искать что же простое он упустил.
    В общем не спорю что так решить эту задачу можно, но на устное решение это не похоже.

    ОтветитьУдалить
  3. Анонимный30.04.2011, 22:32

    Прикинув, что 2^20 - около миллиона, сходу получаем, что 2^18 - шестизнак, а значит, случаи
    n=2, n=3, n=6, n=9 можно не проверять

    ОтветитьУдалить
  4. evle, никак не помогает. Но нам это и не надо. Нам ведь просто надо убедиться, что есть хотя бы одно натуральное число, седьмая степень которого будет шестизначным числом. Восьмёрку проверили - подошло. Если бы не подошло, то пришлось бы, конечно, смотреть на семёрку и шестёрку.

    LisandreL, да, у нас хорошая память, поэтому вспоминаем (или делаем быструю оценку вновь). Важно просто чувствовать, что что-то такое уже только что было, поэтому надо не изобретать новые рассуждения, а вспомнить/придумать похожие.

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

    ОтветитьУдалить
  5. Анонимный30.04.2011, 22:50

    a^n < 10^5 < 10^6 <= (a+1)^n
    lg a < 5/n < 6/n <= lg (a+1)
    Вспоминая, что √10 ~ π, а 2^10 чуть больше 10^3, получаем, что lg 3 < 0.5, а lg 4 > 0.6, т.е. n=10 и a=3 подходит.
    Проверяем n = 9. 10^(6/9) = 10^(2/3) = кубический корень из 100 - между 4 и 5
    4^9 = 2^18 ~ 1000000/4 - шестизначное, при желании можно написать точное значение.

    ОтветитьУдалить
  6. Илья, калькулятор настойчиво уверяет, что 8⁷=2097152, то есть семизначное. А в тексте заметки вы зачем-то проверяете 8⁶

    ОтветитьУдалить
  7. evle, спасибо! Вы не только нашли у меня ошибку, но и настояли на этом (когда с первого раза я её не увидел). Заметку поправил. Ещё раз благодарю.

    ОтветитьУдалить
  8. Мы ищем наименьшее натуральное число n, такое, что при некотором натуральном m происходит перепрыгивание через все шестизначные числа:

    m^n < 100.000
    (m+1)^n >= 1.000.000

    Теперь давайте облегчим нашу задачу и спросим: чему равняется n, если мы зафиксируем m=1? Ответ очевиден: n=20. Поэтому n=20 уже становится кандидатом на решение исходной задачи. Также очевидно, что 2^20=4^10 и, кроме того, нетрудно прикинуть в уме, что 3^10 < 100.000, т.е. мы практически ответили на вопрос: чему равняется n, если мы зафиксируем m=3? Обратите внимание, что мы не стали утруждать себя лишним вопросом: чему равняется n, если мы зафиксируем m=2? Таким образом мы имеем n=10 как лучший, пока что, кандидат на решение исходной задачи.

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

    [(m+1)/m]^n >= 10

    Но это неравенство никак нельзя удовлетворить при n<10 и m > 3 поскольку максимум выражения в левой части, при таких ограничениях на n и m, достигается при n=9 и m=4, и этот максимум меньше чем 10.

    Следовательно результат n=10 нельзя улучшить, т. е. он представляет собой решение исходной задачи.

    ОтветитьУдалить
  9. Анонимный01.05.2011, 19:54

    Интересно, на какую работу, специальность, должность проводят такое собеседование?

    ОтветитьУдалить
  10. Анонимный02.05.2011, 01:20

    Оффтоп
    Здравствуйте, Илья.
    Это опять я :).
    Написал новый пост. Он вполне отвечает первичной задаче Вашего блога. Если Вам он понравится, прорекламируйте, если не трудно. А то полное молчание гнетет. А если не понравится, напишите, пожалуйста, чем именно.
    С уважением, Юрий.

    ОтветитьУдалить
  11. Анонимный02.05.2011, 11:46

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

    ОтветитьУдалить
  12. Xaositect и Arthur Baraov, спасибо за идеи. Если честно, то мне ни разу не доводилось слышать подобные решения на устном собеседовании. Но я допускаю, что есть люди, которые способны их произнести :)

    Юрий, ответил в Вашем ЖЖ.

    Уважаемые анонимы:

    > Интересно, на какую работу, специальность, должность проводят такое собеседование?
    В заметке об устных собеседованиях я старался пояснить, о какого рода деятельности идёт речь: обучение или интеллектуальная работа в команде (в обоих случаях надо адекватно взаимодействовать с людьми). Ну а математическая направленность последних двух разобранных задачек указывает на математический же профиль.

    > Я не очень-то понял, каким образом во время таких рассуждений можно выполнить требование - не пользоваться ручкой и бумагой.
    Если даже такая задачка вызывает сложности, то как решать настоящие проблемы? Невозможно построить дом, если забивание гвоздя требует большого напряжения. И невозможно обдумывать настоящую задачу, если приходится распылять внимание на мелочи (т.е. мелочи должны уже казаться смехотворно простыми).

    ОтветитьУдалить
  13. Анонимный07.05.2011, 02:30

    (сайт съел мой прошлый комментарий, это сокращенная версия ибо полностью повторять лень)

    Быстрые мелкие заметки могут помочь включить дополнительные виды памяти и освободить голову для решения самой задачи (по принципу "узелка на память"). К тому же в реальной жизни обсуждение задач в команде редко обходится без whiteboard. Поэтому считаю что условие "без бумажки" многим помешает показать свой потенциал в полной мере.

    ОтветитьУдалить
  14. > Если даже такая задачка вызывает сложности, то как решать настоящие проблемы? Невозможно построить дом, если забивание гвоздя требует большого напряжения. И невозможно обдумывать настоящую задачу, если приходится распылять внимание на мелочи (т.е. мелочи должны уже казаться смехотворно простыми).

    In my humble opinion, как раз на решение такого рода задачек в голове вы потратите больше и сил и сильнее отвлечёте внимание.
    Да, оценить, <20 (<10) можно. Но дальше идёт в общем-то перебор вариантов, и с записями он будет делаться быстрей и с меньшим шансом на ошибку (банально обсчитаться может любой).

    И да, электронная таблица позволит построить таблицу m^n и решить задачу секунд за 10, вернувшись к действительно сложным вопросам, но это, конечно, не наш метод.

    ОтветитьУдалить
  15. Пока Илья, пользуясь хорошей майской погодой, отдыхает и сажает лучок и картошку на даче, совмещая приятное с полезным, предлагаю вниманию достопочтенных читателей "устную задачку" почти 400-летней выдержки, над которой до сих пор спорят учёные мужи.

    На заре науки, Галилей, изучая свободное падение тел, выдвинул очень простую и, как вначале казалось ему, очень естесственную гипотезу: Скорость тела, свободно падающего из состояния покоя, растёт пропорционально пройденному пути. Впоследствии он отвёрг свою гипотезу и объяснил почему она не может быть верна следующим логическим аргументом.

    Когда скорости имеют такую же пропорцию что и пройденные расстояния, эти рассстояния будут пройдены за одинаковый промежуток времени; следовательно, если скорости с которыми падающее тело прошло расстояние в 4 локтя были бы в два раза больше скоростей с которыми оно прошло первые 2 локтя, также как первое расстояние в 2 раза больше второго расстояния, тогда промежутки времён на прохождение этих расстояний будут равны между собой; но пройти 4 локтя и 2 локтя за одно и то же время одному и тому же телу невозможно за исключением мгновенного движения. Но мы наблюдаем, что падающее тело совершает своё движение не мгновенно, и проходит 2 локтя за меньшее время чем 4 локтя; следовательно это неверно, что скорость свободно падающего тела растёт пропорционально пройденному пути.

    Во времена Галилея его противники сразу отвергли этот аргумент как логический несостоятельный. Сторонники Галилея также были озадачены его аргументом. Даже осторожный Пьер Ферма высказался по поводу этого аргумента и признался, что он находит логическую демонстрацию Галилея довольно туманным. Позднее Австрийский физик и философ Эрнст Мах возобновил интерес к знаменитому аргументу Галилея, но рассматривал его как наглядный пример ложной цепочки рассуждений. В частности, Мах думал, что результат Галилея противоречит современной (1919) классической механике, полагая что закон, который Галилей якобы сумел опровергнуть, не является логически абсурдным, а просто не согласуется с опытом.

    С другой стороны, очень компетентный и очень вдумчивый математик George Polya считал, что недостаточная развёрнутость и краткость доводов Галилея возможно стали причиной того, что даже такой авторитет как Мах не сумел по достоинству оценить знаменитый аргумент.

    А как вы считаете?

    ОтветитьУдалить
  16. Анонимный10.05.2011, 14:15

    --- Пппиривиди.
    --------------------------
    (c) Москва слезам не верит

    ОтветитьУдалить
  17. --- Пппиривиди.

    Спасибо за меткий, и очень уместный кстати, комментарий, уважаемый аноним. Полагаю речь идёт о переводе с русского на русский, тем не менее даю перевод оригинального текста Галилея на английский, чтобы добрые читатели, знакомые с английским, не заподозрили меня в клевете на человека, которого можно назвать первым в мире учёным в современном понимании этого термина. Галилей дал свой аргумент в знаменитых Диалогах (Discorsi e Dimostrazioni). Английский перевод аргумента, взятый из Dialogues Concerning Two New Sciences, выглядит так:

    When speeds have the same ratio as the spaces passed or to be passed, those spaces come to be passed in equal times; if therefore the speeds with which the falling body passed the space of four braccia were the doubles of the speeds with which it passed the first two braccia, as one space is double the other space, then the times of those passages are equal; but for the same moveable to pass the four braccia and the two in the same time cannot take place except in instantaneous motion. But we see that the falling heavy body makes its motion in time, and passes the two braccia in less [time] than the four; therefore it is false that its speed increases as the space.

    Перевод с русского на русский , т.е. моё понимание аргумента Галилея, дам в следующий раз, как только представится такая возможность.

    ОтветитьУдалить
  18. vayun, всему своё время. Бывают устные собеседования, бывают письменные, бывают домашние задания и так далее. Сейчас мы говорим о устном мероприятии. И, если честно, оно много интересного показывает. И Вы правы, кому-то в самом деле хватит клочка бумаги, чтобы ответить гораздо лучше, чем без него. Но эти люди себя прекрасно проявят на других собеседованиях.

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

    А вот на собеседовании могут быть задания сколь угодно отдалённые от будущей работы/учёбы (тут всё зависит от целей и методики).

    > И да, электронная таблица позволит построить таблицу m^n и решить задачу секунд за 10, вернувшись к действительно сложным вопросам, но это, конечно, не наш метод.
    Вы же видели детей, которые с первого класса считают на калькуляторах? Бывают исключения, наверное, но попадавшиеся мне не могут сложить два однозначных числа в уме, они не могут удержать в голове коротенькое определение, у них почти не развита способность делать выводы и так далее. Поэтому мне больно слышать призывы делать простые вещи "электронной таблицей, чтобы разгрузить голову". Голову сначала тренировать надо, а потом разгружать. И если человека просят решить задачку на собеседовании (в тепличных условиях, когда от его неправильного решения ничего не поломается), то можно это сделать, если пришёл на собеседование осознанно (по собственному желанию).

    Arthur Baraov, спасибо за формулировку и перевод. Надеюсь, Вы продолжите эту тему :)

    ОтветитьУдалить
  19. Что-же имел ввиду Галилей когда он заявил: Когда скорости имеют такую же пропорцию, что и пройденные расстояния, эти рассстояния будут пройдены за одинаковый промежуток времени.

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

    Допустим, что тело начинает своё движение с точки x=0 и продолжает двигаться вдоль положительной оси x>0 таким образом, что в любой момент времени его скорость пропорциональна пройденному расстоянию: v(x)=kx. Давайте вычислим время t1, которое потребуется телу для прохождения от точки x=a до x=b, а также время t2, которое потребуется для прохождения от точки x=na до x=nb (где n - любое положительное число):

    t1 = ∫dx/(kx)=(1/k)ln(b/a) (где интеграл берётся от a до b)

    t2 = ∫dx/(kx)=(1/k)ln(nb/na) (где интеграл берётся от na до nb)

    Следовательно, t1=t2 при любых b>a>0 и n>0, что и утверждает Галилей.

    Далее Галилей заявляет: следовательно, если скорости с которыми падающее тело прошло расстояние в 4 локтя были бы в два раза больше скоростей с которыми оно прошло первые 2 локтя, поскольку первое расстояние в 2 раза больше второго расстояния, тогда промежутки времён на прохождение этих расстояний будут равны между собой.

    На нашем математическом языке это утверждение, очевидно, равносильно тому, чтобы положить n=2, зафиксировать b=(2 локтя), и наконец перейти к пределу: a → 0. Как видите, Галилей уже понимал на интуитивном уровне всю сущность не изобретённого ещё аппарата дифференциального и интегрального исчислений, и, по-видимому, неплохо считал в уме.

    Галилей продолжает: но пройти 4 локтя и 2 локтя за одно и то же время одному и тому же телу невозможно за исключением мгновенного движения

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

    И наконец, Галилей завершает цепочку своих гениальных умозаключений следующим опытным наблюдением: Но мы наблюдаем, что падающее тело совершает своё движение не мгновенно, и проходит 2 локтя за меньшее время чем 4 локтя; следовательно невозможно чтобы скорость свободно падающего тела росла пропорционально пройденному пути.

    Теперь я спрашиваю вас, кто же всё-таки был прав, а кто нет:

    (1) Galileo Galilei
    (2) Ernst Mach
    (3) George Polya
    (4) Все (каждый по-своему )
    (5) Никто (тогда предложите своё понимание)

    Я льщу себе надеждой, что знаю разгадку этой тайны, которой 405 лет.

    ОтветитьУдалить
  20. Анонимный17.05.2011, 14:05

    Я полагаю, что в рассуждениях не хватает слова: СЛЕДУЮЩИЕ 4 локтя ... Потому что тело пройдя 2 локтя следующие 2 локтя должно пройти в 2 раза быстрее, и тогда 4 локтя ( от начала отсчета) оно пройдет за время в полтора раза большее чем время, требуемое для прохождения первых 2-х локтей. А еще есть тут интересный момент в самом начале движения, так называемый пограничный случай, когда расстояние и скорость равны нулю. Поскольку скорость равна нулю, то расстояние пройденное телом с такой скоростью также равно нулю, а следовательно исходя из пропорциональности движения в следующий момент скорость тела тоже может быть только нулевой (поскольку скорость пропорциональна пройденному расстоянию). А значит тело зависло в воздухе без опоры... Чего мы не наблюдаем. :-)

    ОтветитьУдалить
  21. Поскольку скорость равна нулю, то расстояние пройденное телом с такой скоростью также равно нулю, а следовательно исходя из пропорциональности движения в следующий момент скорость тела тоже может быть только нулевой (поскольку скорость пропорциональна пройденному расстоянию). А значит тело зависло в воздухе без опоры... Чего мы не наблюдаем. :-)

    Уважаемый аноним,

    Вы обладаете великолепной физической и математической интуицией, и вдобавок к этому, вы продемонстрировали завидную способность чётко и красиво мыслить.

    Поздравляю вас - теперь и вы знаете разгадку 405-летней загадки!

    Продолжение следует.

    ОтветитьУдалить
  22. Привожу перевод изъящного аргумента анонима на математический язык для тех, кто считает что решение не может считаться вполне строгим пока оно не представлено в математической форме.

    Исходная гипотеза Галилея v(x)=kx равносильна следующему дифференциальному уравнению dx(t)/dt = kx(t) с начальным условием x(0)=0, откуда очевидно следует v(0)=0, т. е. тело в исходной позиции имеет нулевую скорость.

    Но решением вышеприведённого дифференциального уравнения с таким начальным условием является постоянная функция x(t)=0, т. е. как аноним выразился: тело зависло в воздухе без опоры... Чего мы не наблюдаем.

    Действительно, общее решение дифференциального уравнения dx(t)/dt = kx(t), которое очевидно имеет вид x(t)=Cexp(kt), может удовлетворит начальному условию x(0)=0 только при C=0, т. е. x(t)=0.

    ОтветитьУдалить
  23. Анонимный27.06.2011, 09:49

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

    Алексей.

    ОтветитьУдалить
  24. Анонимный11.07.2011, 22:00

    Пусть n=8. Вспоминаем n=4: 33^4 является шестизначным

    33^4 > 32^4 = 1024^2 > 10^6

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

    ОтветитьУдалить
  25. Уважаемый аноним, спасибо за обнаруженную опечатку!
    Не знаю, почему я написал 33 вместо 30. Сейчас текст исправлен благодаря Вам. Успехов!

    ОтветитьУдалить

Понравилась заметка? Подпишитесь на RSS-feed или email-рассылку.

Хотите поделиться ссылкой с другими? Добавьте в закладки:



Есть вопросы или предложения? Пишите письма на адрес mytribune АТ yandex.ru.

С уважением,
      Илья Весенний