Целочисленные функции
‘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 = (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.
Доказательство:
если
(
или
),
то