Некоторые задачи школьной математики

    По мотивам статьи «Об одной задаче, которую больше не предлагают на собеседовании».

    Для начала рассмотрим задачу, которую всё-таки могут предложить на собеседовании.

    38. Вычислить сумму ( «Задачи для детей от 5 до 15 лет»)

    $\frac{ 1 }{ 1\cdot2 } + \frac{ 1 }{ 2\cdot3 } + \frac{ 1 }{ 3\cdot4 } + ... + \frac{ 1 }{ 99\cdot100 }$


    (с ошибкой не более 1% от ответа)

    Алгоритм для вычисления частичных сумм этого ряда на языке Scheme (Lisp) в среде drRacket (drRacket позволяет производить вычисления в обыкновенных дробях):

    #lang racket
    (define series_sum
     ( lambda (n)
      (if (= n 0) 0 
        (+ (/ 1 (* n (+ n 1))) (series_sum(- n 1)))
      ) ) )
    (series_sum 10)
    (series_sum 100)
    (series_sum 1000)
    (series_sum 10000)
    (series_sum 100000)
    (series_sum 1000000)
    
    (define series_sum_1
     ( lambda (n)
      (if (= n 0) 0 
        (+ (/ 1.0 (* n (+ n 1.0))) (series_sum_1(- n 1.0)))
      ) ) )
    (series_sum_1 10)
    (series_sum_1 100)
    (series_sum_1 1000)
    (series_sum_1 10000)
    (series_sum_1 100000)
    (series_sum_1 1000000)
    


    Два последних примера drRacket вычислил с ошибкой



    Если рассмотреть частичные суммы в обыкновенных дробях, то можно заметить, что сумма ряда равна

    $ \frac{ n }{ n + 1 } $



    Напомню, что $\lim \frac{ n }{ n+1 } = \frac{ 1 }{ 1+ \frac{1}{n} } = \frac{1}{1}=1 $ при $ n \to \infty $

    Во втором томе «Курса дифференциального и интегрального исчисления» (363) рассматривается общий случай

    $ \sum \frac{ 1 }{ ( \alpha + n)( \alpha + n +1) } = \frac{ 1 }{ \alpha + 1 } $



    Далее, перейдём к основной теме статьи и рассмотрим ещё один пример из задачника.
    43. Числа кроликов («Фибоначчи»), образуют последовательность $(a_{1}=1), 1, 3, 5, 8, 13, 21, 34, ..., $ в которой $ a_{n+2} = a_{n+1} + a_{n} $ для всякого $ n = 1, 2, ... $. Найти наибольший общий делитель чисел $ a_{100} $ и $ a_{99} $.

    Ответ: Два соседних числа Фибоначчи взаимно просты, т.е. $ \gcd(u_{n+1},u_{n}) = 1 $
    (gcd — это greatest common divisor, т.е. НОД).

    Доказательство из книги «За страницами учебника математики» [10-11]:
    Из равенства $ u_{n+2} = u_{n+1} + u_{n} $ следует, что $ \gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},u_{n})$. Пятясь таким образом назад, придём к $ \gcd(u_{2},u_{1}) = \gcd(1,1) = 1 $, а потому два соседних числа Фибоначчи взаимно просты.

    Доказательство того, что $\gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},u_{n})$ в книге не приводится, но по алгоритму Евклида
    $\gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},r)$
    где $ r $ — остаток от деления $u_{n+2} $ на $ u_{n+1}$

    а поскольку для чисел Фибоначчи $ r = u_{n}$
    то
    $\gcd(u_{n+2},u_{n+1}) = \gcd(u_{n+1},u_{n})$

    Еще один пример из задачника
    53. Для последовательности чисел Фибоначчи $a_{n}$ задачи 43 найти предел отношения $ \frac { a_{n+1} }{ a_{n} } $ при стремлении $ n $ к бесконечности:

    $ \frac { a_{n+1} }{ a_{n} } = 2, \frac {3}{2}, \frac {5}{3}, \frac {8}{5}, \frac {13}{8},\frac {21}{13}, \frac {34}{21}. $


    Ответ: «золотое сечение», $ \frac {\sqrt{5} + 1}{2} \approx 1,618 $.

    Рассмотрим отрезки, представляющие собой разности двух соседних членов ряда $ \frac { a_{n+1} }{ a_{n} } $.

    Четные члены ряда $ \frac { a_{n+1} }{ a_{n} } $ представляют растущую последовательность $ x_{n} $

    $\frac{ 3 }{ 2 }, \frac{ 8 }{ 5 }, \frac{ 21 }{ 13 }, ..., $



    Нечетные члены ряда $ \frac { a_{n+1} }{ a_{n} } $ представляют убывающую последовательность $ y_{n} $

    $2 , \frac{ 5 }{ 3 }, \frac{ 13 }{ 8 }, ..., $



    По лемме о вложенных промежутках (Курс дифференциального и интегрального исчисления, 38)

    $ c = \lim x_{n} = \lim y_{n} $


    Для нашего ряда в точке $ c $ справедливо равенство $ \frac { a_{n+2} }{ a_{n+1} } = \frac { a_{n+1} }{ a_{n} } $

    Произведя замену $ a_{n+2} = a_{n+1} + a_{n} $, получим искомое решение.

    Визуализация сделана в программе geogebra







    Следующий пример из задачника
    54. Вычислить бесконечную цепную дробь

    $1+ \frac{1}{2 + \frac{1}{1+ \frac{1}{2+ \frac{1}{1+ \frac{1}{2+...}}}}}$



    Рассмотрим уравнение

    $ \alpha = 1+ \frac{1}{2 + \frac{1}{ \alpha}}$


    Согласно теоремам 236 и 235 из книги «Теория чисел»:

    $ \alpha = \frac{ P_{1}\alpha+ P_{0}}{Q_{1}\alpha+ Q_{0} } $


    Составляем таблицу значений $ P_{n} $ и $ Q_{n} $ при $ n=0,1:$

    1 2
    P 1 3
    Q 1 2


    так что $\alpha = \frac{ 3\alpha + 1 }{ 2\alpha + 1}, 2\alpha^{2} - 2\alpha -1 = 0$

    и поскольку $ \alpha > 0 ,$ то

    $ \alpha = \frac{ 1 + \sqrt{3} }{ 2 } $


    Рассмотрим задачу из книги «За страницами учебника математики» [10-11]
    4. Покажите, что число $\sqrt{1+ \sqrt{1 +\sqrt{1 + ...} } }$ равно числу $\varphi $, задающему золотое сечение.

    Варианта $ x_{n} = \sqrt{c+ \sqrt{c +... + \sqrt{c } } } $
    Курс дифференциального и интегрального исчисления, 35 (2):
    Таким образом $ x_{n+1}$ получается из $ x_{n}$ по формуле

    $ x_{n+1} = \sqrt{c + x_{n} } $


    … По основной теореме, варианта $ x_{n}$ имеет некий конечный предел $ a $. Для определения его перейдём к пределу в равенстве

    $ x_{n+1}^{2} = c + x_{n}; $


    Мы получим, таким образом, что $ a $ удовлетворяет квадратному уравнению

    $ a^{2} = c + a $


    Уравнение это имеет корни разных знаков; но интересующий нас предел $ a $ не может быть отрицательным, следовательно, равен именно положительному корню:

    $ a = \frac{ \sqrt{4c + 1} + 1}{2} $



    Из чего можно сделать вывод, что «золотое сечение» является решением уравнения $ a^{2} = c + a $
    при $ c = 1 $.

    Далее, рассмотрим варианту $ x_{n+1} = x_{n}(2 - x_{n}) $
    Курс дифференциального и интегрального исчисления, 35 (3):
    Пусть $ c $ — любое положительное число, и положим $ x_{n} = cy_{n} $. Написанное выше рекуррентное соотношение заменится таким:

    $ y_{n+1} = y_{n}(2 - cy_{n}) $


    Взяв начальное значение $ y_{0} $ под условием: $ 0< y_{0}<\frac{1}{c} $, получим, что $ y_{n} $, монотонно возрастая, будет стремиться к $ \frac{1}{c} $. По этой схеме на счётных машинах и вычисляется число, обратное $ c $.


    Алгоритм вычисления числа, обратного $ c $ на языке Python:
    def reciprocal(c,y0,n):
    	arr=[]
    	for i in range(n):
    		arr.append(y0)
    		y0=y0*(2-c*y0)
    return arr
    

    Функция reciprocal принимает на вход число $ c $, начальное значение $ y_{0} $, количество итераций $ n $ и возвращает массив «приближений» к числу $ \frac{1}{c} $.
    $ y_{0} = 0.1 $ при $ c<10 $
    $ y_{0} = 0.01 $ при $ 10<c<100 $
    $ y_{0} = 0.001 $ при $ 100<c<1000 $
    и т.д.
    Примеры работы функции reciprocal при различных $ c $

    >>> reciprocal(3,0.1,10)
    

    [0.1, 0.17, 0.2533, 0.31411733000000003, 0.3322255689810133, 0.3333296519077525,
    0.3333333332926746, 0.33333333333333337, 0.33333333333333337, 0.33333333333333337]

    >>> reciprocal(8,0.1,10)
    

    [0.1, 0.12, 0.1248, 0.12499968, 0.1249999999991808, 0.125, 0.125, 0.125, 0.125, 0.125]

    >>> reciprocal(5,0.1,10)
    

    [0.1, 0.15000000000000002, 0.18750000000000003, 0.19921875000000003, 0.19999694824218753, 0.1999999999534339, 0.20000000000000004, 0.19999999999999998,
    0.19999999999999998, 0.19999999999999998]
    (Т.о. применение этого алгоритма требует ограничений)

    В завершение: хотелось бы напомнить всем о задаче Много битов из ничего из журнала «Квант». Задача предполагает решение методом перебора и уже упоминалась на Хабре — вот, вот, вот, вот и вот.

    Книги:
    «Задачи для детей от 5 до 15 лет», В. И. Арнольд.
    «Курс дифференциального и интегрального исчисления», Г. М. Фихтенгольц.
    «Теория чисел», А. А. Бухштаб.
    «За страницами учебника математики», Н. Я. Виленкин, Л. П. Шибасов, З. Ф. Шибасова.
    Поделиться публикацией
    Похожие публикации
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 22
      +4
      Слово «варианта» — устаревшее, понятное только в контексте самого Фихтенгольца, все же кто изучал теорию предела по другим учебникам знают слово «последовательность», неплохо было бы заменить везде в тексте. Точно также, к слову, Фихтенгольц дальше называет «выпуклую» функцию «вогнутой» и, наоборот, т.е. современное понимание этого термина оказывается обратно противоположным.

      Далее, при перепечатке и сокращении примера 35.2 стало непонятно какая «основная теорема» имеется в виду в тексте. А имеется ввиду теорема о гарантированном существовании предела монотонной и возрастающей последовательности – это важно, т.к. не удостоверившись в существовании предела, предельный переход к числу a делать нельзя – можно получить бессмысленный ответ (примеры есть в том же Фихтенгольце).
        0
        Да, с корнями тоже непонятный огород.
        Пишем просто x = sqrt(1 + sqrt(1 + ..)) и возводим в квадрат.
        Получается: x2 = 1 + x.
        Решаем.
        Основная часть задачи (опущенная в статье) как раз в том, чтобы удостовериться в существовании предела последовательности, то есть возможности написать «x =».
          0
          Спасибо (кстати, слово «варианта» встречается не только у Фихтенгольца)
            +1
            Ну может где-то ещё и встречается в текстах времён Фихтенгольца или их переизданий, но сейчас полностью устарело за ненадобностью (о чём пишут, например, в примечаниях от редактора в новых изданиях того же Фихтенгольца).
          +2
          Что-то с 38-й задачей не понял.
          1 / [ n * (n+1) ] = 1/n − 1/(n+1)
          Если так расписать каждый член суммы, то будет 1/1 − 1/2 +1/2 − 1/3 + 1/3 − 1/4 +… + 1/99 − 1/100 = 1 − 1/100 = 0.99
          А… понял: у Вас в условии n от 1 до 99, а в программе — 99, 999, 9999… Но всё равно, надо просто из единицы вычитать 1 / (n + 1).
            0
            Т. о. можно доказать (по индукции), что сумма ряда равна 1-1/(n+1)=n/(n+1)
            0
            Для начала рассмотрим задачу, которую всё-таки могут предложить на собеседовании


            А расчёт обменного интеграла ещё пока не могут предложить на собеседовании? :)
              0
              Задача не требует каких-то особых знаний из области дифференциального и интегрального исчисления.
                0
                А много ли народу решило эту «не требующую особых знаний» задачу? :)
                  0
                  Нам на первом курсе похожую задачу задавали на ИТ-курсе.
                    0
                    И что же, все решили? :)
              0
              по поводу примера 54. это нормально, что получается 2 ответа: (1 +- sqrt(3))/2? или я ошибся? если коротко, то решал так: x = 1 + 1/(2 + 1/x)
                0
                извиняюсь за глупый вопрос. мое решение строится на предположении о том, что эта дробь равна конечному числу. из полученного противоречия ясно, что это не так.
                  0
                  Полученный вами ответ говорит о том, что иррациональное число (1+sqrt(3))/2 можно представить в виде приближений данной цепной дроби.
                    0
                    а как же (1 — sqrt(3))/2?
                  +7

                  Решать 38 программой на лиспе вместо 1-2 строчек на листе бумаги? Экий вы, сударь, простофиля.
                  (1/1-1/2) + (1/2-1/3) +… + (1/99-1/100), раскрываем скобки, видим ответ. А не лезем в "Курс дифференциального и интегрального исчисления"

                    +2
                    Вы фактически разрушили всю идеологическую ценность статьи. :)
                      +1
                      :))
                        0
                        На самом деле, это удивительно. :) Вы столько усилий потратили, но… решение было в другой плоскости. Так в общем-то получилось потому, что здесь задача изначально сделана под конкретное решение. И если не догадаться, то решать можно разными способами.
                      0
                      А как у вас получилось, что 1/(2*3) = (1/2-1/3)? Ведь 1/5 <> 1/6.
                      (простите, конечно, мою безграмотность, если глупость сказал: математика уже порядком подзабылась)
                        +1
                        Приводим к общему знаменателю:
                        1/2 — 1/3 = 3/(2*3) — 2/(2*3) = (3-2)/(2*3) = 1/(2*3)
                        Ну, на самом деле я просто примерно помнил, что такие дроби (типа 1/(2*3)) раскладываются в разность соседних. Может быть, даже и задачку подобную решал лет 30 назад, что-то в памяти задержалось — во всяком случае, идея привести произведение дробей к их разности пришла сразу, а дальше уже сразу видно, что задача решилась.

                        P.S. А насчёт 1/5 — это, думаю, не математика подзабылась, а внимание рассеялось, не удивлюсь, если, пока я писал ответ, вы и сами сообразили (или вспомнили, что знаменатели складывать не надо)
                          +1
                          И правда.
                          Видимо почаще высыпаться надо (пишу 2*3 а считаю как 2+3)

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

                    Самое читаемое