22 сент. 2011 г.

Вспоминаем логарифмы

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

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

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

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

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

Наличие унарных функций существенно меняет смысл игры. Если раньше надо было искать такие наборы действий, которые приводят к новому натуральному числу, то теперь достаточно взять самый большой результат конкурентов, после чего просто «наехать» на него факториалом. Получится натуральное число, которое ранее заведомо никто не получал.

Тут, правда, проявляется забавное ограничение: в правилах чётко сказано, что надо предъявить полученное натуральное число, если хочется сделать ход. Поэтому, например, ход (222)! невозможен (так как в его записи почти 26 миллионов цифр, а такие длинные комментарии недопустимы на этом блоге). Но если говорить о строгой математической постановке, то, конечно, подход, например, с факториалами, полностью уничтожает аукцион.

Остаётся искусственно усложнить игру — научиться получать любое натуральное число (или понять, какие натуральные числа невозможно получить из трёх двоек). Ранее мы уже поняли, что если пользоваться только функциями от двух аргументов, то удастся получить натуральные числа из очень ограниченного набора. Это значит, что для получения произвольного натурального числа придётся применять произвольное число раз функции одного аргумента. А какие такие функции знает школьник? Перечислим их:

  • Факториал,
  • Квадратный корень,
  • sin, cos, tg, ctg,
  • arcsin, arccos, arctg, arcctg.
Давайте попробуем что-нибудь сконструировать из них. С факториалом ничего хорошего в голову не приходит (уж больно неудобная функция для точных действий), поэтому давайте разберёмся с квадратным корнем. Вот если мы N раз «наехали» квадратным корнем на 2, то какое число получится?
sqrt(sqrt(...(sqrt(2)...)) = 2^(1/(2^N)) (т.е. корень из двойки 2N степени).

Что можно сделать с таким числом? Сразу чешутся руки применить к нему функцию log. Только как это лучше сделать? Можно взять логарифм по этому дикому основанию от двойки. Напомню, что логарифм числа b по основанию a определяется как показатель степени, в которую надо возвести основание a, чтобы получить число b.

Логарифм по основанию корень из корня из корня...Другими словами, из двух двоек, логарифма и N операций корня мы можем накрутить уже достаточно интересную конструкцию. Сколько корней мы поместим в основание логарифма, такую степень двойки и получим. Удобно? Не то слово! Из двух двоек мы научились получать 2N (для произвольного натурального N).

Это уже очень хорошо. Но можно попробовать продвинуться дальше — попробовать вытащить из 2N само число N. У нас же ещё осталась одна двойка, а логарифмом мы пользоваться не разучились, верно? Поэтому давайте «наедем» на это число 2N функцией логарифм по основанию 2. Она как раз и вернёт нам N. Получается, что мы можем из трёх двоек, двух логарифмов и N квадратных корней получить произвольное натуральное число N.

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

Можно ли решить эту же задачу без использования квадратных корней? Да, можно! И мы рассмотрим это решение в следующей заметке.

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

  1. Анонимный23.09.2011, 19:36

    Здравствуйте, Илья. Очень интересная статья (как, впрочем, и все Ваши статьи). Мне приятно, что я все понял :). Что бывает не всегда. Илья, не знаю, удобно ли это... При подготовке к ЗНО (зовнишне незалежне оцинювання :))я столкнулся с заданием, которое вызвало затруднение. Если Вам не сложно, помогите мне, пожалуйста. В задании требуется установить соответствие. 1. y=(1/3)в степени x; 2. y=ctgx; 3. y=4; 4. y=cosx c a) периодическая функция, которая не имеет наименьшего положительного T; b)D(f)=(0; + бесконечность); с) функция убывает на (- бесконечность, + бесконечность); d)нечетная функция;e)E(f)=-1включительно;+1включительно. Если я правильно понимаю, то
    1.- с); 3.- а); 4.- е). А вот к чему подходит 2.? (Может в задание вкралась ошибка...)

    ОтветитьУдалить
  2. Анонимный23.09.2011, 19:44

    И вторая часть этого же задания.
    1. 13; 2. корень квадратный из 8; 3. 10/2; 4. 3,4 с а) множество составных чисел; b)множество дробных чисел; с) множество иррациональных чисел; d) множество натуральных чисел; е) множество целых чисел, которые не являются натуральными. Я сопоставил 1.-d); 2.-с); 4.-b. А вот к чему отнести 3.? (Может, к а)?)
    Спасибо, Влад

    ОтветитьУдалить
  3. Анонимный24.09.2011, 06:15

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

    А вообще ctg(-x)=-ctg(x). Значит, это нечётная функция, если мне не изменяет память.

    Ну а с числом 10/2 вроде вообще сомнений быть не может, так как это натуральное число (и не подходит под остальные варианты). В этом тесте же можно сопоставлять один ответ нескольким вопросам?

    ОтветитьУдалить
  4. Анонимный24.09.2011, 20:33

    Спасибо анонимному комментатору! Функция у=сtgx действительно нечетная (мне почему-то вчера график этой функции не показался симметричен относительно начала координат :)), сегодня мне просто стыдно... А вот относительно

    В этом тесте же можно сопоставлять один ответ нескольким вопросам?

    Не знаю. Это меня и смущает. Раньше нигде с этим не встречался.

    Еще раз спасибо, это замечательный блог!

    Влад

    ОтветитьУдалить
  5. Анонимный25.09.2011, 01:51

    Влад, в обоих задачах ваша проблема в непонимании термина "соответствие". Пройдите по этой ссылке и, даже не читая статью, по иллюстрации вы поймёте, где вы заблуждаетесь. http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D1%81%D1%82%D0%B2%D0%B8%D0%B5
    С заданиями всё в порядке. Ошибки нет. Просто будте несного внимательнее и уделите этому заданию чуть больше времени, если оно вас действительно интересует.

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

    Что касается темы, тут всё-таки не всё так чисто. Знает ли школьник о таких простых функциях как декримент или инкримент, используя которые даже трёх двоек не нужно? (Но так совсем не интересно.)

    Уже определились, что на бинарных ф-циях далеко не уедешь, но что знает школьник из унарных кроме модуля, отрицания, факториала и тригонометрических? Округление до N-го знака? Может, имеется ввиду, что помимо ф-ций можно использовать функционалы?

    ОтветитьУдалить
  6. Влад, спасибо за тёплые слова.
    На Ваши вопросы уже ответили, тут мне добавить нечего.

    Уважаемый первый аноним, считать ctg(x) убывающей функцией на множестве всех вещественных чисел неправильно, так как эта функция не убывает в тех точках, где не является определённой.

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

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

    ОтветитьУдалить
  7. Анонимный06.10.2011, 17:32

    Народ как из 13 двоек сделать число 2011?Плиз помогите!!

    ОтветитьУдалить
  8. Анонимный08.10.2011, 09:22

    Вообще-то и трёх двоек хватает :) Зачем 13?
    Но можно как-то так сделать: 2011=2^11-33.
    11=22/2
    37=2*2*2*2*2+2*2+2/2
    Соответственно, 2011 = 2^(22/2) - (2*2*2*2*2+2*2+2/2). Это как раз 13 двоек.

    ОтветитьУдалить
  9. В самом деле, зачем использовать 13 двоек, если достаточно даже не трёх, а одной?
    Но спасибо, что показали и эту задачку.

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

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

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



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

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