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

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

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

    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 } $



    Эту программу можно запустить в online ide ideone.com и codepad.org.




    Далее, перейдём к основной теме статьи и рассмотрим ещё один пример из задачника.
    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} $ на $ a_{n+1} $, получим уравнение $ \frac{a_{n+2}}{a_{n+1}} = 1 + \frac{a_{n}}{a_{n+1}} $.
    Произведя замену $\frac{a_{n+2}}{a_{n+1}}=x , \frac{a_{n}}{a_{n+1}} = \frac{1}{x} $, получим квадратное уравнение.

    Если в программе geogebra соединить дугами окружности точки 2 и $ \frac{3}{2}$, $ \frac{3}{2}$ и $ \frac{5}{3}$, $ \frac{5}{3}$ и $ \frac{8}{5}$ и т.д. — получим самоподобную фигуру





    Следующий пример из задачника
    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:
    ( Ideone.com и codepad.org)
    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]

    Геометрическая интерпретация


    Попробуем использовать метод касательных для приближенного вычисления обратного числа.
    Касательные $ y=f'(x_{0})(x-x_{0})+ f(x_{0})$ к графику функции $ y=\frac{1}{x} $ выражаются формулой $ y = \frac{2}{x_{0}} - \frac{x}{x_{0}^{2}} $

    Подставляя числа $1,2,3,4, ...$ вместо $ x_{0} $ получим уравнения касательных

    $ y=2-x $


    $ y=1-\frac{x}{4} $


    $ y=\frac{2}{3}-\frac{x}{9} $


    $ y=\frac{1}{2}-\frac{x}{16} $


    Построим эти графики


    Если сдвинуть гиперболу вниз на $ \alpha $, то она пересечёт ось абсцисс в точке $ \frac{1}{\alpha} $.
    Уравнение касательных преобразуется в $ y = \frac{2}{x_{0}} - \frac{x}{x_{0}^{2}} - \alpha $
    Далее, приравняв уравнение касательной к нулю и выразив $ x $, получим уравнение $ x= x_{0} - \frac{f(x_{0})}{f'(x_{0})}$

    Вместо $ f(x_{0}) $ подставим $ \frac{1}{x_{0}} - \alpha$
    Вместо $ f'(x_{0}) $ подставим $ -\frac{1}{x_{0}^{2}} $

    Получим выражение $ x= x_{0} + (\frac{1}{x_{0}}-\alpha) x_{0}^{2} $
    Раскрыв скобки, получим $ x= x_{0} + x_{0}-\alpha x_{0}^{2} $

    Подставим $ 0.1 $ в уравнение $ x=x_{0}(2-\alpha x_{0}) $ и посмотрим, какие значения будет «пробегать» $ x $ при $ \alpha=2 $, получим $ 0.1, 0.18, 0.29, 0.42, 0.49, 0.5 $

    Подставив эти значение в уравнение $y=\frac{2}{x_{0}}-\frac{x}{x_{0}^{2}}-2 $, получим прямые

    $ y= 0.111 - \frac{x}{0.897} $


    $ y= 0.222 - \frac{x}{0.81} $


    $ y= 0.816 - \frac{x}{0.504} $


    $ y= 0.857 - \frac{x}{0.49} $


    $ y= 1.5 - \frac{x}{0.326} $


    $ y= 2 - \frac{x}{0.25} $







    P.S. Решите задачу ( «Задачи для детей от 5 до 15 лет»)
    27. Доказать, что остаток от деления числа $ 2^{p-1} $ на простое нечетное число
    $ p $ равен $ 1 $
    (примеры: $ 2^{2} = 3a+1, 2^{4}=5b+1, 2^{6}=7c+1, 2^{10} -1 = 1023 = 10 \cdot 93) $.
    Эта задача рассматривается в статье Удивительные приключения цепных дробей журнала «Квант».

    Книги:
    «Задачи для детей от 5 до 15 лет», В. И. Арнольд.
    «Курс дифференциального и интегрального исчисления», Г. М. Фихтенгольц.
    «Теория чисел», А. А. Бухштаб.
    «За страницами учебника математики», Н. Я. Виленкин, Л. П. Шибасов, З. Ф. Шибасова.
    «Digital Arithmetic» Ercegovac Milos D., Lang Tomas.
    Поделиться публикацией
    Комментарии 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)

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

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