SavePearlHarbor

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

—

от автора

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

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

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 лет», В. И. Арнольд.
«Курс дифференциального и интегрального исчисления», Г. М. Фихтенгольц.
«Теория чисел», А. А. Бухштаб.
«За страницами учебника математики», Н. Я. Виленкин, Л. П. Шибасов, З. Ф. Шибасова.


ссылка на оригинал статьи https://habr.com/post/419237/

Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *