3.2 ПОЛ/ПОТОЛОК: ПРИМЕНЕНИЯ

Итак, мы подобрали основные инструменты для работы с полами и потолками. Опробуем их на деле, начав с простой задачки: что такое (Следуя предложению Эдварда М. Рейнгольда, мы используем для обозначения логарифма по основанию 2.) Ну, поскольку можно взять логарифмы, получая -таким образом, правило утверждает, что

Заметим, что будучи записанным в системе счисления с основанием 2, число 35 тоже состоит из шести битов: верно ли, что — это всегда длина записанного в двоичной форме? Не всегда. Для записи тоже необходимо шесть битов, так что — неверный ответ на этот вопрос. (Он неверен только в случае, когда является степенью 2, но это означает, что он неверен в бесконечном числе случаев.) Правильный же ответ можно получить, заметив, что для записи каждого числа такого, что требуется битов. А поскольку по правилу То есть, для того чтобы выразить любое в двоичной форме, необходимо битов. Исходя из правила аналогичный вывод дает ответ — эта формула справедлива даже при если нам хочется считать, что для записи в двоичной форме требуется нуль битов.

Обратимся далее к конструкциям с несколькими полами и потолками. Что такое ? Ответ прост: поскольку — целое число, то — это просто . Этому же равно любое другое выражение, в котором самый внутренний окружен каким угодно числом полов и потолков.

А вот орешек покрепче: разгрызитека такую задачку — верно или неверно утверждение, что

Очевидно, это равенство справедливо, когда х — целое число, ибо тогда Но это является равенством и для и для и для ибо во всех этих частных случаях мы получаем Наша безуспешная попытка найти какой-либо опровергающий пример наводит на мысль, что равенство справедливо и в общем случае, так что давайте попробуем его доказать.

Между прочим, когда мы сталкиваемся с выбором между „доказать или опровергнуть", то обычно предпочитаем вначале опровергнуть с помощью какого-нибудь контрпримера по двум причинам: опровержение существенно проще (нужен всего лишь один опровергающий пример), а „придирки по мелочам" вызывают прилив творческих сил. Даже если данное утверждение оказывается верным, поиск контрпримера зачастую приводит к его доказательству, как только скептик осознает, почему контрпример невозможен. Помимо всего прочего, скептицизм полезен для здоровья.

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

Гораздо практичнее воспользоваться уже подготовленными нами инструментами. Предлагается такой план: каким-либо образом разобрать наружный пол и квадратный корень после чего убрать внутренний пол, а затем вновь собрать разобранное, чтобы получить Годится. Положим и воспользуемся правилом получая Тем самым мы избавляемся от скобок наружного пола, ничего не теряя при этом. Поскольку все три части этой конструкции неотрицательны, возводим их в квадрат, получая Тем самым мы отделываемся от квадратного корня. Затем разбираем оставшийся пол, пользуясь правилом для левого неравенства и правилом для правого: . А теперь не составляет труда восстановить проделанное: извлечь квадратные корни, получая и воспользоваться правилом получая Таким образом, — наше утверждение оказалось верным. Тем же способом можно доказать, что

Предложенное доказательство не столь уж существенно опирается на свойства квадратных корней. Более внимательное рассмотрение

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

(Символ означает „влечет за собой") Тогда

всякий раз, когда определены функции Давайте докажем это общее свойство для потолков, поскольку до этого мы уже занимались полами, тем более, что доказательство для полов почти такое же. Если то доказывать нечего. В противном случае поскольку — возрастающая функция. Тогда так как — неубывающая функция. Если бы было то должно найтись число у, такое, что поскольку функция непрерывна. Это у должно быть целым в силу специального свойства Но непосредственно между не может быть никакого целого числа. Это противоречие означает, что должно быть

Явного упоминания заслуживает важный частный случай этой теоремы:

если тип — целые числа, а знаменатель положителен. К примеру, пусть тогда Троекратное деление на 10 с последовательным отбрасыванием цифр остатка — это то же самое, что и непосредственное деление на с последующим отбрасыванием всего остатка.

Попробуем теперь подтвердить или опровергнуть другое предположение:

Оно проходит при но не проходит при — тем самым выясняется, что в общем случае оно неверно.

Прежде чем двинуться дальше, сделаем минутное отступление для того, чтобы обсудить различные „уровни" задач, которые могут рассматриваться в книгах по математике.

Уровень 1. Для определенного объекта х и определенного соотношения доказать, что выполняется Например, „доказать, что Здесь суть дела заключается в нахождении доказательства некоторого предполагаемого факта.

Уровень 2. Для определенного множества X и определенного соотношения доказать, что выполняется при любом . Например, „доказать, что при любом вещественном

Суть дела опять заключается в нахождении доказательства, но на этот раз — общего доказательства. Мы имеем дело уже не с арифметикой, а с алгеброй.

Уровень 3. Для определенного множества X и определенного соотношения подтвердить или опровергнуть, что выполняется при любом . Например, „подтвердить или опровергнуть, что любом вещественном Здесь мы имеем дело с дополнительным уровнем неопределенности — результат может оказаться либо тем, либо другим. Это ближе к той реальной ситуации, с которой постоянно сталкивается математик: утверждения, попадающие на страницы книг, имеют обыкновение быть правильными, но к новому следует относиться предвзято. Если данное утверждение ошибочно — наше дело найти контрпример. Если данное утверждение правильно — мы обязаны найти доказательство (как на уровне 2).

Уровень 4. Для определенного множества X и определенного соотношения найти необходимое и достаточное условие того, что выполняется Например, „найти необходимое и достаточное условие того, что Суть дела заключается в нахождении условия такого, что Безусловно, всегда наготове тривиальный ответ: просто взять Нет, имеется в виду, что нужно найти условие, которое настолько просто, насколько это возможно. А для нахождения удовлетворяющего этому требованию простого условия нужна сообразительность. (Так, в нашем случае Этот самый элемент сообразительности, который необходим для нахождения существенно усложняет решение подобных задач, но как нельзя лучше характеризует то, с чем приходится сталкиваться математику в „реальной действительности! И, наконец, должно быть, естественно, доказано, что выполняется тогда и только тогда, когда выполняется

Уровень 5. Для определенного множества X найти некоторое интересное общее свойство его элементов. Тем самым мы вторгаемся в жуткие дебри чистой науки, где, как полагают студенты, царит всеобщий хаос. Но это уже настоящая математика. Авторы учебников редко осмеливаются задавать вопросы уровня 5. Конец отступления.

Но давайте переведем наш последний вопрос с уровня 3 на уровень 4: каково необходимое и достаточное условие того, что ? Мы уже выяснили, что при это равенство выполняется, а при — не выполняется. Дальнейшие проверки показывают, что к тому же оно не выполняется при х между 9 и 10. Ого-го. Более того, случаи невыполнения возникают всякий раз, когда так как в этих случаях в левой части получается а в правой — Во всех других случаях, когда определен, а именно при или при получается равенство. Поэтому для выполнения

равенства необходимо и достаточно следующее условие: либо х - целое число, либо целое число.

Для формулировки нашей следующей задачи воспользуемся удобным обозначением для интервалов вещественной прямой, предложенным К. А. Р. Хоаром и Лайлом Рэмшоу. Интервал обозначает множество вещественных чисел х, таких, что Это множество называется замкнутым интервалом, поскольку он включает как одну, так и другую концевую точку и (3. Интервал не включающий ни одной, ни другой концевой точки, состоит из всех х, таких, что он называется открытым интервалом. А интервалы включающие либо одну, либо другую концевую точку, определяются аналогично и называются полуоткрытыми.

Сколько целых чисел содержится в подобных интервалах? Нам удобнее начать с полуоткрытых интервалов. И вообще, почти всегда удобнее иметь дело с полуоткрытыми, чем с открытыми или замкнутыми интервалами. К примеру, они аддитивны — при объединении полуоткрытых интервалов получается полуоткрытый интервал Для открытых интервалов этого не произошло бы, ибо точка (3 оказалась бы исключенной, а для замкнутых интервалов возникли бы проблемы, ибо точка (3 оказалась бы включенной дважды.

Но вернемся к нашей задаче. Если и — целые числа, то ответ простой: тогда интервал содержит ровно целых чисел при условии, что Точно так же интервал содержит целых чисел при том же условии. Но наша задача потруднее, ибо по условию и — произвольные вещественные числа. Тем не менее, ее можно свести к более легкой задаче, поскольку согласно (3.7)

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

Кстати, существует мнемонический прием для запоминания того, в каком случае употребляются полы, а в каком — потолки: полуоткрытые интервалы, которые включают не правую, а левую концевую точку (такие, как несколько более употребительны, чем те, которые включают не левую, а правую концевую - так же как полы несколько более употребительны, чем потолки. Но по закону Мерфи действительное прямо противоположно ожидаемому — потолки соответствуют интервалам а полы соответствуют интервалам .

Аналогичный разбор показывает, что замкнутый интервал содержит целых чисел и что открытый интервал содержит целых чисел, хотя в последнем случае мы налагаем дополнительное ограничение с тем, чтобы эта формула не приводила нас в замешательство откровением, что пустой интервал содержит ровно — 1 целых чисел. Подытожим установленные факты:

А вот задача, которая не может нас не заинтриговать. В Клубе любителей конкретной математики находится казино (доступное только обладателям этой книги), в котором колесо рулетки имеет тысячу гнезд с номерами от 1 до 1000. Если выпадающий при вращении рулетки номер делится на пол своего кубического корня, т. е. если

то это выигрышный номер и казино выплачивает нам 5 долларов; в противном случае это проигрышный номер и уже мы обязаны уплатить 1 доллар. (Обозначение которое читается как делит означает, что в точности кратно - это соотношение обстоятельно исследуется в гл. 4.) Можно ли рассчитывать „сделать деньги" на такой игре?

Средний выигрыш — т. е. сумму, которую мы выиграем (или проиграем) за одну игру, — можно вычислить, подсчитав сперва число выигрышных номеров и число проигрышных номеров. Если каждый номер выпадает по одному разу в 1000 играх, то мы выигрываем долларов и проигрываем долларов, так что средняя сумма выигрыша составит

долларов. Если выигрышных номеров 167 и более, то мы извлекаем прибыль; в противном случае выигрывает казино.

Но как подсчитать число выигрышных номеров среди тысячи? Не так уж и трудно уловить их закономерность. Все номера от 1 до — выигрышные, ибо для каждого из них Среди номеров от до выигрышными являются только четные номера. А среди номеров от до — только те, которые делятся на 3; и т. д.

Общее число благоприятных исходов игры можно выразить аналитически, если воспользоваться техникой суммирования из

предыдущей главы с привлечением нотации Айверсона для логических выражений, доставляющей 0 или 1:

Этот вывод заслуживает внимательного изучения. Обратите внимание, что в строке используется формула (3.12) для количества целых чисел в полуоткрытом интервале. Единственно „трудный" момент — это решение при переходе от 3-й к 4-й строке выделить в качестве отдельного случая. (Неравенство не так просто объединить с неравенством при Вообще-то, граничные условия, похоже, самое скользкое место при - манипуляциях.

В нижней строке сообщается, что следовательно, наша формула для средней суммы выигрыша за одну игру сводится к долларам, что составляет 3.2 цента. Можно рассчитывать стать богаче примерно на 3.20 доллара, сделав 100 ставок по 1 доллару. (Если, конечно, владельцы казино не сделают так, что номера будут выпадать с равной вероятностью, но некоторые — равнее других.)

Задача о казино, которую мы только что решили, представляет собой приукрашенную версию более прозаического вопроса: Сколько целых чисел при удовлетворяют соотношению . С математической точки зрения эти два вопроса одинаковы. Но иногда неплохо приукрасить задачу: мы обогащаем свой словарь („выигрышными номерами" и „проигрышными номерами"), что помогает нам разобраться в существе дела.

Попробуем обобщить задачу. Предположим, что 1000 заменяется на 1 000000 или на еще большее число (Мы допускаем, что у владельцев казино есть связи и они могут достать колесо побольше.) Насколько тогда увеличится число выигрышных номеров?

Для ответа на этот вопрос достаточно тех же самых рассуждений, но необходимо осторожнее обращаться с самым большим значением к, которое для удобства обозначим через К:

(Раньше К равнялось 10.) Для произвольного общее число выигрышных номеров становится равным

Нам известно, что оставшаяся сумма есть следовательно, формула

дает общий ответ для колеса с гнездами.

Первые два члена этой формулы приближенно равны а при большом остальные члены по сравнению с ними много меньше. В гл. 9 мы узнаем, как получать выражения, подобные выражению

где означает величину, которая не превосходит константы, умноженной на Какой бы ни была константа — она не зависит от так что при большом вклад О-члена в величину будет весьма незначительным по сравнению с . Так, следующая таблица показывает, насколько близки значения к величине

Вполне приличное приближение.

Приближенные формулы полезны постольку, поскольку они проще, чем формулы с полами и потолками. Однако зачастую

важна „абсолютная точность", особенно при малых значениях с которыми обычно имеют дело на практике. Скажем, владелец казино может ошибочно предполагать, что при имеется лишь выигрышных номеров (в таком случае доход казино составил бы 10 центов).

И в завершение этого раздела обратимся к так называемым спектрам. Спектр некоторого вещественного числа определяется как бесконечное мультимножество целых чисел:

(Мультимножество — это то же самое, что и множество, но в нем могут содержаться повторяющиеся элементы.) К примеру, спектр числа начинается так:

Легко показать, что нет двух одинаковых спектров — т. е. влечет за собой Действительно, если предположить, не умаляя общности, что то найдется некоторое положительное целое число такое, что (На самом деле, любое будет таковым, но мы не видим необходимости каждый раз бравировать своими познаниями в области полов и потолков.) Следовательно, Таким образом, содержит менее чем элементов тогда как содержит по меньшей мере .

Спектры обладают многими замечательными свойствами. Рассмотрим, например, два мультимножества

Элементы легко вычисляются на калькуляторе, а согласно элемент ровно на больше элемента Более внимательное рассмотрение показывает, что два этих спектра связаны друг с другом гораздо более удивительным образом: получается так, что любое число, отсутствующее в одном спектре, присутствует в другом, но никакое число не содержится одновременно в обоих! И это действительно так — все целые положительные числа представляют собой объединение непересекающихся множеств Говорят, что эти спектры образуют разбиение всех целых положительных чисел.

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

Пусть положительно. Число элементов в , которые равно

Этот вывод интересен двумя моментами. Во-первых, здесь используется правило

для замены тем, чтобы в соответствии с (3.7) можно было убрать скобки пола. Во-вторых и это более тонкий момент — суммирование проводится по а не по так как величина могла бы оказаться меньшей 1 при некоторых и а. Если бы мы попытались применить (3.12) для определения количества целых чисел в интервале в отличие от определения количества целых чисел в интервале то получили бы правильный ответ, однако наш вывод был бы неправильным, поскольку не были бы соблюдены условия его применимости.

В любом случае у нас есть формула для . Теперь можно проверить, образуют или нет множества разбиение всех целых положительных чисел, проверив, выполняется или нет равенство при любом целом используя для этого (3.14):

Все упрощается благодаря изящному равенству 1 1

так что наше условие сводится к проверке, правильно или нет, что

при любом . А это правильно, потому что это дробные части нецелых чисел, которые в сумме дают целое число Действительно, разбиение.