86236 (Целочисленные функции)
Описание файла
Документ из архива "Целочисленные функции", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "остальное", в предмете "математика" в общих файлах.
Онлайн просмотр документа "86236"
Текст из документа "86236"
Федеральное агентство по образованию
Государственное общеобразовательное учреждение высшего профессионального образования
Вятский государственный гуманитарный университет
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
«Целочисленные функции»
Выполнила: студентка
V курса математического факультета Мошкина Т.Л.
Научный руководитель: старший преподаватель Семёнов А.Н.
Рецензент:
Допущена к защите в ГАК
Зав. кафедрой Вечтомов Е.М.
« »
Д екан факультета Варанкина В.И.
« »
Киров
2005
Содержание
Введение 3
Глава 1. Целочисленные функции (теоретические факты) 4
I. Определения 4
II. Связь с непрерывными функциями 5
III. Количество целых чисел в интервалах: [, ], [, ), (,), (, ] 7
IV. Спектры. 8
V. ‘Mod’: бинарная операция 9
Глава 2. Целочисленные функции (применение к решению задач) 11
Литература 28
Введение
Целые числа составляют костяк дискретной математики, и на практике часто приходится округлять дробные или произвольные вещественные числа до целых.
До недавнего времени для обозначения целой части вещественного числа использовалась запись . Но в начале 60-х годов Кеннет Э.Айверсон предложил в этом случае писать и дал удачное название этому обозначению: «пол». Для обозначения верхнего целого он предложил запись и назвал её «потолком», а для квадратных скобок нашёл новое применение. Предложенная Айверсоном нотация оказалась настолько удачной, что за рубежом старое обозначение уже практически не встречается. С появлением русского издания книги Р.Грэхем, Д.Кнут, О.Паташник «Конкретная математика» эта нотация становится популярной и в России.
Цель данной работы — получить представление и навыки в обращении с «полом» и «потолком».
Задачи работы:
-
Осветить теоретические аспекты данной темы:
-
Дать определение функций «пол», «потолок»;
-
Рассмотреть некоторые свойства этих функций;
-
Установить связь с непрерывными функциями;
-
Подсчитать количество целых чисел в заданных интервалах;
-
Рассмотреть определение спектра и его свойства;
-
Дать определение бинарной операции «mod» и рассмотреть приложение этой операции;
-
Рассмотреть на примере, как можно вычислить сумму, содержащую «полы».
-
-
Показать, как теория применяется на практике при решении задач.
Глава 1. Целочисленные функции (теоретические факты)
-
Определения.
Договоримся через обозначать множество всех натуральных чисел, т.е. множество всех целых положительных чисел. Определим для любого вещественного числа x функции наибольшего и наименьшего целого:
x — наибольшее целое, меньше или равное x;
x — наименьшее целое, больше или равное x.
Из определения ясно, что , . Отсюда следует, что
(1)
В целых точках неубывающие функции и совпадают, т.е. — целое . А если они не совпадают, то они отличаются на 1, т.е.
[ не целое] (2)
Эта формула связывает все три обозначения Айверсона. Здесь и далее квадратные скобки используются для произвольного высказывания P в таком смысле:
Функции и являются отображениями друг друга относительно координатных осей, т.е.
, (3)
Из определений «пола» и «потолка» легко следуют свойства этих функций: и
(4)
Разность между и называется дробной частью x и обозначается
Иногда называется целой частью , поскольку .
Докажем следующее свойство рассматриваемых функций:
(5)
Так как равно либо 0, либо 1, то равно либо , либо .
-
Связь с непрерывными функциями.
Пусть — некоторая непрерывная монотонно возрастающая функция, обладающая тем свойством, что — целое число — целое число. Тогда
(6)
и
(7)
всякий раз, когда определены функции , , .
Докажем, что
Случай 1: если , тогда .
Случай 2: если , тогда (в силу того, что функция монотонно возрастающая), а так как функция «пол» — не убывающая, то . Предположим, что , тогда существует такое число , что и (в силу непрерывности функции ). Из условия следует, что — целое число. Это противоречит тому, что между и нет целых чисел. Значит, .
Докажем, что
Случай 1: если , то .
Случай 2: если , то (в силу того, что функция монотонно возрастающая), а так как функция «потолок» — не убывающая, то . Предположим, что , тогда существует такое число , что и (в силу непрерывности функции ). Из условия следует, что — целое число. Это противоречит тому, что между и нет целых чисел. Значит, .
Рассмотрев , получаем полезное свойство:
и (8)
Например, при и получаем , т.е. троекратное деление на 10 с последовательным отбрасыванием цифр остатка — это то же самое, что и непосредственное деление на 1000 с последующим отбрасыванием всего остатка.
-
Количество целых чисел в интервалах: [, ], [, ), (,), (, ].
Будем рассматривать указанные интервалы при условии .
Если и — целые числа, тогда интервал [, ) содержит ровно целых чисел: , +1, …, , аналогично интервал (, ] содержит целых чисел, но и — произвольные вещественные числа. Из (4) следует
, когда — целое число
Поэтому интервал [, ) содержит ровно целых чисел, а интервал (, ] содержит ровно целых чисел.
Рассмотрим промежуток [, . Имеем (на основании свойств (4)). Отсюда следует, что рассматриваемый промежуток содержит ровно целых чисел: , , …, , .
Рассмотрим (, ), причём . Имеем
. Отсюда следует, что рассматриваемый интервал содержит ровно целых чисел: , , …, , . Если не вводить дополнительное ограничение то получим, что пустой интервал (, ) содержит ровно
целых чисел.
Подытожим установленные факты:
Интервал | Количество целых чисел | Ограничение |
[, | + 1 |
|
[, ) |
| |
(, ] |
| |
(, ) | 1 | < |
(9)
-
Спектры.
Спектр некоторого вещественного числа определяется как бесконечное мультимножество целых чисел:
Spec () = { , , ,…} (10)
Если , то Spec ()Spec (), т.е. нет двух одинаковых спектров.
Действительно, если предположить, что , то найдётся некоторое положительное целое число , такое, что . Следовательно, и . Таким образом, Spec() содержит менее чем m элементов не больших , тогда как Spec(α) содержит по меньшей мере m.
Пусть . Число элементов в Spec( ), которые не превосходят , равно
(11)
Говорят, что спектры образуют разбиение всех целых положительных чисел, если любое число, отсутствующее в одном спектре, присутствует в другом; но никакое число не содержится одновременно в обоих. Пусть и — вещественные положительные числа, тогда Spec( ) и Spec( ) образуют разбиение натуральных чисел тогда и только тогда, когда . Интересное свойство спектров будет доказано в задаче 10. В задаче 17 будет показана связь между мультимножествами Spec( ) и Spec , где — некоторое положительное число.
-
‘Mod’: бинарная операция.
Если m и n — целые положительные числа, то неполное частное от деления n на m равно . Для того, чтобы было удобно работать с остатками, введём определение остатка:
.
Это определение можно распространить на произвольные вещественные числа:
(12)
при . Положим .
Дробную часть числа x можно представить как .
Самым важным алгебраическим свойством операции ‘mod’ является распределительный закон:
(13)
Доказательство следует из (11):
.
Приложение операции ‘mod’: разложение n предметов на m групп как можно более равномерных. Решение этого вопроса даёт тождества, справедливые при целых и натуральных .
— выражает разбиение n на m как можно более равных частей в невозрастающем порядке. (14)
— выражает разбиение n на m как можно более равных частей в неубывающем порядке. (15)
Доказательство этих фактов можно найти в книге Р.Грэхем, Д.Кнут, О.Паташник «Конкретная математика» на с.106-108. Если в (15) заменить n на mx и применить правило (8), то получим тождество, которое справедливо при любом вещественном x и натуральном :
(16)
Глава 2. Целочисленные функции (применение к решению задач)
Задача 1.
Всякое натуральное число представимо в виде: , где . Приведите явные формулы для l и m как функций от n.
Решение:
Тогда
Ответ: , .
Задача 2.
Как выглядит формула для ближайшего целого к заданному вещественному числу x? В случае «равновесия» — когда x лежит ровно посередине между целыми числами — приведите выражение, округляющее результат:
-
в сторону увеличения, т.е. до x;
-
в сторону уменьшения, т.е. до x.
Решение:
Пусть вещественное число округляется до .
-
В этом случае до округляются числа , удовлетворяющие неравенству:
(по свойству (4)).
-
В этом случае до округляются числа , удовлетворяющие неравенству:
(по свойству (4)).
Ответ: a) ; b)
Задача 3.
Вычислите , если m и n — натуральные числа, а — иррациональное число, большее n.
Решение:
= = = = = (так как и ).
Ответ: .
Задача 4.
Докажите, что .
Доказательство:
.
Отсюда , так как n — натуральное число.
Итак, . Что и требовалось доказать.
Задача 5.
Доказать, что если f(x) — непрерывная, монотонно убывающая функция и f(x) — целое x — целое, тогда .
Доказательство:
1 случай: если , то .
2 случай: если , то , так как f – убывающая функция; (в силу того, что функция «пол» — неубывающая).
Если , то существует такое число , что и (так как f непрерывна). Поскольку f(y) целое, то по условию целое. А это противоречит тому, что между x и x не может быть никакого целого числа. Следовательно, .
Что и требовалось доказать.
Задача 6.
Решите рекуррентность при целом
при ,
при .
Решение:
Покажем, что методом математической индукции по .
База: : из того, что , следует, что , тогда и , поэтому для выполняется .
Переход: пусть для некоторого номера и для меньших номеров утверждение верно: .
Докажем, что .
= .
Что и требовалось доказать.
Задача 7.
Докажите принцип ящиков Дирихле: если n предметов размещены по m ящикам, то некоторый ящик должен содержать не меньше чем n/m предметов, а некоторый ящик должен содержать не более чем n/m.
Решение:
Предположим, что каждый ящик содержит меньше, чем n/m предметов. Тогда наибольшее количество предметов в каждом ящике — это предметов. Следовательно, наибольшее количество предметов, размещённых по ящикам — это . Это противоречит тому, что .
Значит, существует ящик, который содержит не менее чем n/m предметов.
Предположим, что нет ящика, в котором не более, чем n/m предметов, т.е. каждый ящик содержит более чем n/m предметов. Тогда наименьшее количество предметов в каждом ящике — . Следовательно, наименьшее количество предметов, размещённых по ящикам — это . Это противоречит тому, что .
Значит, существует ящик, который содержит не более чем n/m предметов.
Что и требовалось доказать.
Задача 8.
Покажите, что выражение всегда равно либо x, либо x. При каких условиях получается тот или иной случай?
Решение:
1 случай: x = (4k1)/2, kZ
Тогда , так как целое число.
Получим = = = =
2 случай: x (4k-1)/2, k Z, тогда .
Получим = =
Итак, данное выражение округляет числа до ближайшего целого; в случае «равновесия» — когда x лежит ровно посередине между целыми числами — данное выражение округляет число в сторону чётного.
Задача 9.
Докажите, что при любом целом n и любом целом положительном m.
Доказательство:
Пусть .
Покажем, что .
Имеем
(по свойствам (4))
Что и требовалось доказать.
Задача 10.
Пусть α и β — вещественные положительные числа. Докажите, что Spec(α) и Spec(β) образуют разбиение всех целых положительных чисел тогда и только тогда, когда α и β иррациональны и .
Решение:
Пусть α и β — вещественные положительные числа.
Докажем, что если Spec(α) и Spec(β) образуют разбиение всех целых положительных чисел, то α и β — иррациональные числа и .
Spec(α) и Spec(β) образуют разбиение всех целых положительных чисел, тогда .
Рассмотрим
.
Докажем, что α и β иррациональны. Так как , то числа α и β либо оба рациональны, либо оба иррациональны.
Если α и β оба рациональны, т.е. существует такое целое число m, что и , где и — натуральные числа, тогда Spec(α) и Spec(β).
Но никакое число не содержится одновременно в двух спектрах, образующих разбиение всех целых положительных чисел. Следовательно, α и β — иррациональны.
Докажем обратное: если α и β иррациональны и , то Spec(α) и Spec(β) образуют разбиение всех целых положительных чисел.
Так как и — иррациональны, то и — не целые числа, то
и
Отсюда получаем:
(так как и и — иррациональны, то ).
Получаем, что . Отсюда Spec(α) и Spec(β) образуют разбиение всех натуральных чисел.
Что и требовалось доказать.
Задача 11.
Докажите, что при целом n.
Доказательство:
-
если ( или ), то ,
тогда .
Получаем верное равенство .
-
если , тогда .
Правая часть имеет вид: .
Преобразуем левую часть:
.
Получили, что при любом целом . Что и требовалось доказать.
Задача 12.
Имеется ли аналогичное (16) тождество, в котором вместо «полов» используются «потолки»?
Решение:
Тождество (16) получается из тождества (15) заменой n на mx.
Аналогичное тождество для потолков получается из тождества (14) заменой n на mx:
mx = =
= =
Итак, получили тождество аналогичное данному:
mx = .
Задача 13.
Докажите, что . Найдите и докажите аналогичное выражение для вида , где ω – комплексное число .
Доказательство:
При делении числа на 2 возможны только два различных остатка: либо 0, либо 1.
-
если , то и .
-
если , и .
Следовательно, равенство верно для любого натурального n. Что и требовалось доказать.
Найдём аналогичное выражение для , т.е. найдём коэффициенты a, b, c.
Поскольку — есть корень третьей степени из 1, то и .
Так как , то .
При делении числа на 3 возможны только три различных остатка: либо 0, либо 1, либо 2.
Если , то .
Если , то .
Если , то .
Решая систему , находим a, b, c.
, , .
Итак, получаем следующую формулу:
.
Задача 14.
Какому необходимому и достаточному условию должно удовлетворять вещественное число , чтобы равенство выполнялось при любом вещественном ?
Решение:
При любом вещественном и равенство выполняется b — целое число.
Если b — целое число, то функция непрерывная, возрастающая функция (так как ). Пусть — целое число, т.е. . Тогда , так как и . Выражая через , получим — целое, как натуральное число в неотрицательной целой степени. Поэтому можно применить формулу (6) и получить равенство .
Если b — не целое число, то при равенство не будет выполняться, так как
Итак, если , то равенство выполняется при любом вещественном тогда и только тогда, когда b — целое число.
Ответ: b — целое число.
Задача 15.
Найдите сумму всех чисел, кратных x, в замкнутом интервале [, , при .
Решение:
Числа, кратные имеют вид , где . Нужно просуммировать те из чисел , для которых . Учитывая, что и (4), имеем
.
Нам нужно вычислить следующую сумму:
.
В этой сумме можно вынести за скобки, а в скобке останется сумма всех чисел от до включительно. Применяя формулу арифметической прогрессии получаем:
.
Задача 16.
Покажите, что n-й член последовательности 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,… равен . (Каждое число m входит в данную последовательность m раз.)
Решение:
В этой последовательности чисел меньших будет , а чисел не превосходящих будет . Поэтому, если xn=m, то
Оценим n:
.
Следовательно, .
Задача 17.
Найдите и докажите связь между мультимножествами Spec(α) и Spec(α/(α+1)), где α — некоторое положительное вещественное число.
Решение:
Число элементов в Spec(α), которые не превосходят n:
.
Число элементов в Spec(α/(α+1)), которые не превосходят n:
.
Итак, получили, что .
Покажем на основе этого, что чисел равных в Spec будет на 1 больше, чем в Spec( ).
При если , тогда .
Пусть в Spec( ) элементов не превосходящих будет , тогда число элементов в Spec( ) равных будет . Подсчитаем количество элементов в Spec равных :
Что и требовалось доказать.
Ответ: чисел равных в Spec будет на 1 больше, чем в Spec( ).
Задача 18.
На шахматной доске клеток симметрично начерчена окружность с диаметром единиц. Через сколько клеток доски проходит данная окружность?
Решение:
Радиус окружности равен .
Горизонтальных прямых, не являющихся сторонами квадрата — ( ).
Вертикальных прямых, не являющихся сторонами квадрата — ( ).
Окружность каждую из указанных прямых пересекает в двух точках. Она не проходит через углы клеток. Действительно, если предположить, что данная окружность проходит через какой-нибудь угол клетки, то существуют такие целые числа и , для которых выполняется теорема Пифагора: , но — целое число, а — не целое. Получили противоречие. Следовательно, окружность не проходит через углы клеток.
Каждую клетку окружность пересекает в двух точках, а каждая точка пересечения принадлежит двум клеткам. Следовательно, окружность проходит через столько клеток доски, сколько имеется точек пересечения её с прямыми: .
Ответ: клеток.
Задача 19.
Говорят, что f(x) является репликативной функцией, если
f( ) = f( ) + f + … + f
при каждом целом положительном m. Укажите, какому необходимому и достаточному условию должно удовлетворять вещественное число c, чтобы функция f(x) = x+c являлась репликативной.
Решение:
f(x) = x+c — репликативна
= 0 .
Ответ: .
Литература
Р.Грэхем, Д.Кнут, О.Паташник. Конкретная математика. М.: «Мир» 1998. С 88 124.