Федеральное агентство по образованию
Государственное общеобразовательное учреждение высшегопрофессионального образования
Вятский государственный гуманитарный университет
Математический факультет
Кафедра алгебры и геометрии
Выпускная квалификационная работа
«Целочисленные функции»
Выполнила: студентка
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
ab
(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:
/> Û
Û /> Û
Û /> Û
Û /> Û
Û />Û
Û /> Û
Û /> Þ
Þ />.
Следовательно, />.
Задача 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.