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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть n=6. Вспоминаем случай n=3. Надо оценить корень из 99. Это примерно 9. Давайте посчитаем 9⁶. Это легко: 9⁶ = 81³ ~= 80³ = 8³ * 1000 = 2⁹ * 1000 = 512000. Как и ожидалось, получили шестизначное число, поэтому n=6 не подходит.

Пусть n=7. Мы помним, что 9⁶ уже около полумиллиона, поэтому в седьмую степень имеет смысл возводить что-то меньшее девяти. Давайте оценим 8⁷. Со степенями двойки всё очень быстро: 8⁷ = 2²¹ (уже больше миллиона). Поэтому пробуем семёрку возвести в седьмую степень: 7⁷ = 49³ * 7 < 50³ * 7 = 125000 * 7 (чуть меньше миллиона). Так мы разобрались с седьмой степенью.

Пусть n=8. Вспоминаем n=4: 30⁴ является шестизначным, поэтому осмысленно смотреть на корень из 30, округляя вниз. Чему равна восьмая степень пятёрки? 5⁸ = 25⁴ = 625² ~= чуть меньше полумиллиона.

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

Пусть n=10. Как мы помним, 4¹⁰ = 2²⁰ больше миллиона, а 2¹⁰ = 1024. Поэтому остаётся проверить только тройку в десятой степени: 3¹⁰ = 9⁵. Но мы же помним, что 10⁵=100000 является наименьшим шестизначным числом. А так как 9⁵ < 10⁵, то 9⁵ заведомо не шестизначное. Выходит, мы нашли границу: 3¹⁰ меньше шестизначного, а 4¹⁰ уже больше шестизначного. А поскольку мы для всех степеней меньших десяти уже нашли такое x, что xⁿ является шестизначным, то мы решили задачку».

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

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

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

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

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

Метод 1 («универсальный», «метод кувалды», «лишь бы не думать»).
Пусть длина стороны этого куба равна 2. Тогда векторы, соответствующие красным отрезкам, можно записать как v1=(1, 1, 0) и v2=(1, 0, 1). Угол между ними легко найти из определения скалярного произведения (<v1,v2> = |v1|*|v2|*cos(a)). Получается cos(a) = <v1,v2>/2 = 1/2. По косинусу угла находим сам угол - 60 градусов.

Некоторые люди, идущие по этому пути, сразу себя поправляют, получив такой ответ: «Но искомый угол очевидно тупой, а мы получили острый, потому что... а-а, потому что мы посчитали угол не между векторами, исходящими из общей точки двух отрезков... Один из векторов надо развернуть в противоположную сторону, поэтому правильный ответ 180-60=120 градусов.

Более аккуратные, применяя метод координат, хорошо понимают, что он позволяет легко делать серьёзные ошибки, которые иногда очень трудно отловить (в этой простой задачке нам просто повезло, что сразу было видно неправильность ответа 60). Такие люди сразу корректно записывают вектора (один из них с противоположным направлением), поэтому получают cos(a) = -1/2, из чего сразу следует верный ответ.

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

Метод 2 («метод пристального взгляда», «красивый», «лишь бы не считать»).
Давайте построим сечение куба плоскостью, проходящей через два красных отрезка. Легко показать, что получится правильный шестиугольник, у которого, естественно, все углы равны 120 градусам.

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

Метод 3 («красивый, но и думать надо», «компромисс»).
Воспользуемся тем, что угол между отрезками не поменяется, если мы будем их параллельно переносить:
- верхний отрезок передвинем на диагональ верхней грани, а потом сбросим на такую же диагональ нижней грани,
- ближний к нам отрезок передвинем на диагональ ближней к нам квадратной грани.

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

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

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

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

Хорошего дня! (кстати, завтра вечером пройдёт турнир по «Банальностям», рекомендую - подробности)

Как отвечать на собеседовании?

Речь идёт исключительно об отборе для интеллектуальной деятельности (обучение или работа), а не о проверках «кто будет возмущаться, что HR-менеджер опаздывает уже больше чем на час» или имитации всяких стрессовых ситуаций.

Пусть известно, что цель беседы – выявление следующих свойств:
- способность логически мыслить (делать только правильные выводы из имеющихся данных),
- умение чётко и кратко излагать свою идею,
- наличие хорошей быстрой памяти (легко ориентироваться в сказанном за последние 10 минут),
- широкий кругозор (оперативно вспоминать, что когда давно читал про решение похожей проблемы, то вроде бы рассматривался такой-то приём),
- обучаемость (например, способность применить ранее неизвестную теорему, если экзаменатор предложил считать, что на неё можно опираться),
- настойчивость и аккуратность (если видно три способа решить проблему, а уже проверенные первый и второй не показались эффективными, то пробовать третий, а не опускать руки),
- адекватность (например, если для устной задачи с собеседования найдено решение, предполагающее многочасовой перебор, то надо искать другое, а если экзаменатор задаёт наводящий вопрос, то надо постараться на него ответить, а не продолжать двигаться своим безнадёжным путём),
- критичность к сделанным выводам (постоянная автоматическая их проверка на простых/граничных примерах, чтобы убедиться, что не сделано хотя бы легко обнаруживаемой ошибки),
- умение отвечать на вопрос, а не просто произносить набор слов, имеющих какое-то отношение к словам из вопроса (очень досадно, когда кандидат произносит какую-то глупость, а мои попытки позволить ему исправиться упираются в стену игнорирования сути наводящего вопроса).

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

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

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

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

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

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

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

В моей шкале (а надо понимать, что шкалы бывают разными) совершение ошибки имеет наименьший вес, потому что ошибки ещё можно найти и исправить, если есть что-то кроме них. Более того, на собеседовании я всегда стараюсь «загнать» человека в такую ситуацию, чтобы он ошибся, потому что его слова/действия при ошибке очень показательны (да и «уровень устойчивости» надо знать, ведь кто-то ошибается в элементарной арифметике или простейших алгебраических преобразованиях, а кто-то в применении теоремы Рамсея или Менелая, например). Обычно я предлагаю задачи, для которых знаю несколько типичных ошибок (и умею быстро показать соответствующий контрпример, чтобы собеседуемый успел себя поправить) и несколько подходов, приводящих к хорошему решению. Иногда случается праздник - обнаруживается ранее неизвестное красивое решение (что указывает на оригинальность мышления, кстати).

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

Хорошего завершения выходного дня!

Устные задачки

Добрый день.

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

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

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

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

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

1. Через середины трёх рёбер куба провели два отрезка (как на рисунке). Найдите угол между этими отрезками.

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

3. Два автомобиля массы m едут со скоростью v по дороге в одну сторону. В системе отсчёта дороги их кинетическая энергия равна mv²/2. А относительно друг друга их скорость равна нулю, поэтому и кинетическая энергия рава нулю. Теперь один из автомобилей потратил литр бензина, чтобы разогнаться до скорости 2v. Его кинетическая энергия в лабораторной системе отсчёта стала равной m(2v)²/2 = 2mv². А в системе отсчёта второго автомобиля его кинетическая энергия стала mv²/2 (так как их скорости отличаются на v). Возникает вопрос: почему сжигание одинакового количества топлива в разных системах отсчёта привело к отличающемуся в три раза приросту энергии объектов? Закон сохранения энергии ведь никто не отменял.

Кстати, год назад мы рассматривали одну задачку о сохранении энергии - и вот её разбор.

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

Хорошего дня!

В ожидании шутки

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

Это тоже можно использовать в своих целях. Например, если известно, что слушатели ожидают лжи, то можно сказать им правду - тогда они неправильно воспримут верную информацию, что приведёт к нужным для говорящего действиям. Ровно один раз в году наступает такой день, когда можно говорить чистую правду, заранее зная, что в неё не поверят.

С 2008-го года каждое первое апреля я рассылаю 10 смс-сообщений на почти случайные номера: «Поздравляю! Вы выиграли в моей персональной лотерее. Позвоните мне, чтобы получить свой приз - 1000 рублей» (раньше приз был меньше). Легко догадаться, что люди не верят в такие сообщения 1 апреля, хоть я и готов честно переслать обещанную сумму на их счёт. Ни разу мне не перезвонили :)

А как вы пользуетесь тем, что 1 апреля мало кто готов к правдивым сообщениям? Какие вы знаете удачные розыгрыши, построенные на этом эффекте?

P.S.
С днём математика!