Упражнения

Разминочные упражнения

1 Когда в гл. 1 мы разбирали задачу Иосифа, то представляли произвольное целое положительное число в виде , где Приведите явные формулы для I и как функций используя скобки пола и/или потолка.

2 Как выглядит формула для ближайшего целого к заданному вещественному числу ? В случае „равновесия" — когда х лежит ровно посредине между целыми числами — приведите выражение, округляющее результат: (а) в сторону увеличения, т. е. до в сторону уменьшения, т. е. до

3 Вычислите если - целые положительные числа, а иррациональное число, большее

4 В тексте охарактеризованы задачи с уровня по 5-й. А что представляет собой задача уровня 0? (Это, между прочим, вопрос не уровня 0.)

5 Укажите необходимое и достаточное условие того, что если — целое положительное число. (Ваше условие должно включать в себя

6 Что примечательного можно сказать про если — непрерывная, монотонно убывающая функция, которая принимает целые значения, только когда само х — целое число?

7 Решите рекуррентность

т.

8 Докажите принцип ящиков Дирихле: если предметов размещены по ящикам, то некоторый ящик должен содержать предметов, а некоторый ящик должен содержать

9 В 1800-м году до н. Э. египетские математики представляли рациональные числа между 0 и 1 в виде сумм „основных" дробей где суть различные целые положительные числа. Например, вместо они писали Докажите, что всегда есть возможность делать это систематически: если то

(Это алгоритм Фибоначчи, предложенный Леонардо Фибоначчи в 1202 г. н. э.)

Обязательные упражнения

10 Покажите, что выражение

всегда равно либо либо При каких условиях получается тот или иной случай?

11 Приведите детали отмеченного в тексте доказательства того, что открытый интервал содержит ровно целых чисел при Почему для корректности доказательства нужно исключить случай

12 Докажите, что

при любом целом и любом целом положительном т. [Это тождество дает другой способ обращения потолков в полы и обратно вместо применения рефлексивного закона (3.4).]

13 Пусть и Р — вещественные положительные числа. Докажите, что образуют разбиение всех целых положительных чисел тогда и только тогда, когда иррациональны и

14 Подтвердите или опровергните, что

15 Имеется ли аналогичное (3.26) тождество, в котором вместо полов используются потолки?

16 Докажите, что Найдите и докажите аналогичное выражение для вида а где — комплексное число Указание:

17 Вычислите сумму в случае, когда подставляя вместо и суммируя сперва по к. Согласуется ли ваш ответ с

18 Докажите, что остаточный член в (3.30) не превосходит Указание: покажите, что малые значения не существенны.

Домашние задания

19 Какому необходимому и достаточному условию должно удовлетворять вещественное число чтобы

при любом вещественном

20 Найдите сумму всех чисел, кратных х, в замкнутом интервале при

21 Сколько чисел вида , начинаются с 1 в десятичной записи?

22 Вычислите суммы

23 Покажите, что элемент последовательности

равен (Каждое число входит в данную последовательность раз.)

24 Упражнение 13 устанавливает замечательную связь между двумя мультимножествами когда некоторое иррациональное число поскольку Найдите (и докажите) другую примечательную связь между мультимножествами когда а — некоторое положительное вещественное число.

25 Подтвердите или опровергните, что числа Кнута, определенные соотношением (3.16), удовлетворяют условию при любом неотрицательном

26 Покажите, что вспомогательные числа Иосифа (3.20) удовлетворяют неравенству

27 Докажите, что среди определенных посредством (3.20) чисел бесконечно много четных и бесконечно много нечетных.

28 Решите рекуррентность

29 Покажите в дополнение к (3.31), что

30 Покажите, что рекуррентность

имеет решение если — целое число, большее 2, где . К примеру, если то решением является

31 Подтвердите или опровергните, что

32 Обозначим через расстояние от x до ближайшего целого. Какова величина суммы

(Заметьте, что эта сумма может быть бесконечной в обе стороны. Так, если то ее члены отличны от нуля как при к так и при к

Контрольные работы

33 На шахматной доске размером клеток симметрично начерчена окружность с диаметром единиц; вот как это выглядит при

а Через сколько клеток доски проходит данная окружность?

b Укажите функцию такую, что внутри данной окружности полностью умещается ровно клеток доски.

34 Пусть

а Найдите выражение для при 1 в замкнутой форме.

b Докажите, что при любом .

35 Упростите формулу

36 Считая, что — целое неотрицательное число, найдите выражение для суммы

в замкнутой форме.

37 Докажите справедливость тождества

при любых целых положительных титг.

38 Пусть — вещественные числа, такие, что тождество

справедливо при любом целом положительном т. Выясните что-нибудь характерное для чисел

39 Докажите, что двойная сумма

равна при каждом вещественном 1 и каждом целом

40 Спиральная функция схематически показанная внизу, отображает целое неотрицательное число в упорядоченную пару целых чисел Например, она отображает в упорядоченную пару (1,2).

а Докажите, что если то

и укажите аналогичную формулу для Указание: разбейте спираль на сегменты в зависимости от значения b И наоборот, докажите, что можно установить из по формуле вида

Приведите правило, определяющее, когда знак есть , а когда

Конкурсные задачи

41 Пусть — возрастающие функции, такие, что множества образуют разбиение всех целых положительных чисел. Предположим, что связаны условием при любом Докажите, что , где

42 Существуют ли вещественные числа такие, что вместе взятые образуют разбиение множества целых положительных чисел?

43 Дайте другую интересную интерпретацию числам Кнута, развернув рекуррентность (3.16).

44 Покажите, что существуют целые числа и такие, что

где является решением рекуррентности (3.20). Воспользуйтесь этим фактом для получения решения обобщенной задачи Иосифа в другой форме:

45 Примените прием из упр. 30 для нахождения решения рекуррентности

в замкнутой форме, если — целое положительное число.

46 Докажите, что если где и I — целые неотрицательные числа, то Воспользуйтесь этим замечательным свойством для нахождения решения рекуррентности

в замкнутой форме. Указание:

47 Говорят, что является репликативной функцией, если

при каждом целом положительном т. Укажите, каким необходимым и достаточным условиям должно удовлетворять вещественное число с, чтобы следующие функции являлись репликативными:

48 Докажите тождество

и покажите, как можно получить аналогичные формулы для при

49 Укажите, какому необходимому и достаточному условию должны удовлетворять вещественные числа чтобы можно было установить и (3 из бесконечного мультимножества величин

Исследовательские проблемы

50 Укажите, какому необходимому достаточному условию должны удовлетворять вещественные неотрицательные числа и (3, чтобы можно было установить из бесконечного мультимножества величин

51 Обозначим через х вещественное число Тогда решение рекуррентности

может быть записано в виде если х — целое число, где

так как Какими еще интересными свойствами обладает функция

52 При заданных вещественных неотрицательных числах положим

— мультимножество, обобщающее мультимножество Докажите или опровергните, что если мультимножеств образуют разбиение всех целых положительных чисел и при этом параметры ост рациональны, то

53 Алгоритм Фибоначчи (из упр. 9) является „жадным" в том смысле, что на каждом шаге он выбирает как можно более малое Известен более сложный алгоритм, с помощью которого любая дробь с нечетным может быть представлена в виде суммы различных основных дробей с нечетными знаменателями. Всегда ли заканчивается жадный алгоритм при поиске такого представления?