Целочисленные функции Федеральное агентство по образованию Государственное общеобразовательное учреждение высшего профессионального образования Вятский государственный гуманитарный университет Математический факультет Кафедра алгебры и геометрии Выпускная квалификационная работа «Целочисленные функции» Выполнила: студентка V курса математического факультета Мошкина Т.Л. Научный руководитель: старший преподаватель Семёнов А.Н. Рецензент: Допущена к защите в ГАК Зав. кафедрой Вечтомов Е.М. « » Декан факультета Варанкина В.И. « » Киров 2005 Содержание Введение. 3 Глава 1. Целочисленные функции (теоретические факты) 4 I.Определения. 4 II.Связь с непрерывными функциями. 5 III.Количество целых чисел в интервалах: [a , b ], [a , b ), (a ,b ), (a , b ] 7 IV.Спектры. 8 V.‘Mod’: бинарная операция. 9 Глава 2. Целочисленные функции (применение к решению задач) 11 Литература. 28 Введение Целые числа составляют костяк дискретной математики, и на практике часто приходится округлять дробные или произвольные вещественные числа до целых. До недавнего времени для обозначения целой части вещественного числа использовалась запись . Но в начале 60-х годов Кеннет Э.Айверсон предложил в этом случае писать и дал удачное название этому обозначению: «пол». Для обозначения верхнего целого он предложил запись и назвал её «потолком», а для квадратных скобок нашёл новое применение. Предложенная Айверсоном нотация оказалась настолько удачной, что за рубежом старое обозначение уже практически не встречается. С появлением русского издания книги Р.Грэхем, Д.Кнут, О.Паташник «Конкретная математика» эта нотация становится популярной и в России. Цель данной работы — получить представление и навыки в обращении с «полом» и «потолком». Задачи работы: 1. Осветить теоретические аспекты данной темы: · Дать определение функций «пол», «потолок»; · Рассмотреть некоторые свойства этих функций; · Установить связь с непрерывными функциями; · Подсчитать количество целых чисел в заданных интервалах; · Рассмотреть определение спектра и его свойства; · Дать определение бинарной операции «mod» и рассмотреть приложение этой операции; · Рассмотреть на примере, как можно вычислить сумму, содержащую «полы». 2. Показать, как теория применяется на практике при решении задач. Глава 1. Целочисленные функции (теоретические факты) I. Определения. Договоримся через обозначать множество всех натуральных чисел, т.е. множество всех целых положительных чисел. Определим для любого вещественного числа x функции наибольшего и наименьшего целого: ëx û — наибольшее целое, меньше или равное x ; éx ù — наименьшее целое, больше или равное x . Из определения ясно, что , . Отсюда следует, что (1) В целых точках неубывающие функции и совпадают, т.е. Û — целое Û . А если они не совпадают, то они отличаются на 1, т.е. [ - не целое] (2) Эта формула связывает все три обозначения Айверсона. Здесь и далее квадратные скобки используются для произвольного высказывания P в таком смысле: Функции и являются отображениями друг друга относительно координатных осей, т.е. , (3) Из определений «пола» и «потолка» легко следуют свойства этих функций: и (4) Разность между и называется дробной частью x и обозначается Иногда называется целой частью , поскольку . Докажем следующее свойство рассматриваемых функций: (5) Так как равно либо 0, либо 1, то равно либо , либо . II. Связь с непрерывными функциями. Пусть — некоторая непрерывная монотонно возрастающая функция, обладающая тем свойством, что — целое число Þ — целое число. Тогда (6) и (7) всякий раз, когда определены функции , , . Докажем, что Случай 1: если , тогда . Случай 2: если , тогда (в силу того, что функция монотонно возрастающая), а так как функция «пол» — не убывающая, то . Предположим, что , тогда существует такое число , что и (в силу непрерывности функции ). Из условия следует, что — целое число. Это противоречит тому, что между и нет целых чисел. Значит, . Докажем, что Случай 1: если , то . Случай 2: если , то (в силу того, что функция монотонно возрастающая), а так как функция «потолок» — не убывающая, то . Предположим, что , тогда существует такое число , что и (в силу непрерывности функции ). Из условия следует, что — целое число. Это противоречит тому, что между и нет целых чисел. Значит, . Рассмотрев , получаем полезное свойство: и (8) Например, при и получаем , т.е. троекратное деление на 10 с последовательным отбрасыванием цифр остатка — это то же самое, что и непосредственное деление на 1000 с последующим отбрасыванием всего остатка. III. Количество целых чисел в интервалах: [a, b], [a, b), (a,b), (a, b]. Будем рассматривать указанные интервалы при условии . Если a и b — целые числа, тогда интервал [a , b ) содержит ровно целых чисел: a , a +1, …, , аналогично интервал (a , b ] содержит целых чисел, но a и b — произвольные вещественные числа. Из (4) следует , когда — целое число Поэтому интервал [a , b ) содержит ровно целых чисел, а интервал (a , b ] содержит ровно целых чисел. Рассмотрим промежуток [a , b ]. Имеем (на основании свойств (4)). Отсюда следует, что рассматриваемый промежуток содержит ровно целых чисел: , , …, , . Рассмотрим (a , b ), причём . Имеем . Отсюда следует, что рассматриваемый интервал содержит ровно целых чисел: , , …, , . Если не вводить дополнительное ограничение то получим, что пустой интервал (a , a ) содержит ровно целых чисел. Подытожим установленные факты: Интервал Количество целых чисел Ограничение [a , b ] ëb û-éa ù + 1 a £ b [a , b ) éb ù-éa ù a £ b (a , b ] ëb û-ëa û a £ b (a , b ) éb ù-ëa û-1 a < b (9) IV. Спектры. Спектр некоторого вещественного числа a определяется как бесконечное мультимножество целых чисел: Spec (a ) = { , , ,…} (10) Если , то Spec (a )¹Spec (b ), т.е. нет двух одинаковых спектров. Действительно, если предположить, что , то найдётся некоторое положительное целое число , такое, что . Следовательно, и . Таким образом, Spec(b ) содержит менее чем m элементов не больших , тогда как Spec(α ) содержит по меньшей мере m . Пусть . Число элементов в Spec( ), которые не превосходят , равно (11) Говорят, что спектры образуют разбиение всех целых положительных чисел, если любое число, отсутствующее в одном спектре, присутствует в другом; но никакое число не содержится одновременно в обоих. Пусть и — вещественные положительные числа, тогда Spec( ) и Spec( ) образуют разбиение натуральных чисел тогда и только тогда, когда . Интересное свойство спектров будет доказано в задаче 10. В задаче 17 будет показана связь между мультимножествами Spec( ) и Spec , где — некоторое положительное число. V. ‘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 лежит ровно посередине между целыми числами — приведите выражение, округляющее результат: a) в сторону увеличения, т.е. до éx ù; b) в сторону уменьшения, т.е. до ëx û. Решение: Пусть вещественное число округляется до . a) В этом случае до округляются числа , удовлетворяющие неравенству: Û (по свойству (4)). b) В этом случае до округляются числа , удовлетворяющие неравенству: Û (по свойству (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 = (4k - 1)/2, k ÎZ Тогда , так как - целое число. Получим = = = = 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 , в замкнутом интервале [a , b ], при . Решение: Числа, кратные имеют вид , где . Нужно просуммировать те из чисел , для которых . Учитывая, что и (4), имеем Û Û. Нам нужно вычислить следующую сумму: . В этой сумме можно вынести за скобки, а в скобке останется сумма всех чисел от до включительно. Применяя формулу арифметической прогрессии получаем: . Задача 16. Покажите, что n -й член последовательности 1,2,2,3,3,3,4,4,4,4,5,5,5,5,5,… равен . (Каждое число m входит в данную последовательность m раз.) Решение: В этой последовательности чисел меньших будет , а чисел не превосходящих будет . Поэтому, если xn = m , то Оценим n : Û Û Û Û Û Û Û Û Û Û Û Û Þ Þ . Следовательно, . Задача 1 7 . Найдите и докажите связь между мультимножествами 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.