Главная > Математика > Конкретная математика. Основание информатики
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

А. Ответы к упражнениям

КАЖДОЕ УПРАЖНЕНИЕ сопровождается (по крайней мере, кратким) ответом, а некоторые из этих ответов выходят за рамки того, что спрашивалось. Читатели извлекут наибольшую пользу, если предпримут серьезную попытку найти свои собственные ответы, прежде чем заглянуть в данное приложение.

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

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

1.2 Если — требуемое число перекладываний, то при Отсюда следует (если, например, прибавить 1 к обеим частям), что (После перекладываний оказывается, что башня целиком будет находиться на среднем колышке — перевалочный пункт!)

1.3 Всего существует возможных размещений, ибо каждый диск может оказаться на любом колышке. Мы обязательно столкнемся с каждым из них, поскольку самое короткое решение требует перекладываний. (Подобная конструкция эквивалентна „троичному коду Грея! который пробегает все числа от до изменяя каждый раз только одну цифру.)

1.4 Нет. Если самый большой диск не перекладывать, то будет достаточно перекладываний (доказывается по индукции); в противном случае будет достаточно ) перекладываний (также по индукции).

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

овалов:

Венн [51] утверждал, что случай пяти множеств невозможно проиллюстрировать эллипсами, однако такое построение было найдено Грюнбаумом [92].

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

1.7 Мы не доказали базу индукции; и в самом деле, так что данная последовательность периодична!

1.9 (а) Утверждение мы получаем из неравенства

(b) в силу произведения внутри в силу . К примеру, следует из — из — из

1.10 Вначале покажите, что при Между прочим, методы гл. 7 позволяют показать, что

1.11 (а) Мы не можем сделать ничего лучшего, чем переместить вначале двойную -башню, затем переложить (с изменением порядка) два самых больших диска, а на них снова поместить двойную -башню; следовательно, Это решение меняет местами два самых больших диска, но сохраняет исходный порядок других дисков.

(Ь) Обозначим через минимальное число перекладываний. Тогда и можно показать, что нет лучшей стратегии, чем когда Следовательно, для всех Как ни странно, но это просто , и мы также имеем

1.12 Бели все то Это уравнение является уравнением „обобщенного иосифова“ типа с решением

К тому же соответствующее обобщение упр. приводит к рекуррентности

1.13 Зная, что прямых разбивают плоскость на областей, мы можем заменить их исключительно узкими зигзагами с настолько длинными отрезками, что каждая пара зигзагов имеет девять пересечений. Это показывает, что при всех следовательно,

1.14 Число новых трехмерных областей, образованных новым - это число двумерных областей, образованных на новой плоскости линиями ее пересечений с прежними плоскостями. Следовательно, откуда выясняется, что (С помощью шести разрезов кубической головки сыра можно получить 27 кубиков сыра или же до 42 кусков сыра неправильной формы.)

Между прочим, решение этого рекуррентного соотношения приобретает привлекательный вид, если выразить его через биномиальные коэффициенты (см. гл. 5):

Здесь — наибольшее число одномерных областей, на которые прямая делится точками.

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

Если , где то решением является при всех

Другой способ записи решения в случае, когда таков:

1.16 Пусть Из (1.18) известно, что при это определяет Подстановка в наше рекуррентное соотношение означает, что так что на все известно. [Подстановка дает дополнительное равенство которое может быть использовано для определения через более простые функции

1.17 В общем случае при 0 к . (Данное соотношение соответствует перемещению верхних — к дисков с последующим использованием только трех колышков для перекладывания к дисков и завершающим перекладыванием верхних — к дисков.) Установленное соотношение оказывается основанным на единственном значении к, которое минимизирует правую часть данного общего неравенства при (Однако мы не можем утверждать, что имеет место равенство, поскольку для перемещения подобной башни приемлемы многие другие способы.) Если мы положим то обнаружим, что следовательно,

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

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

1.19 Не могут, когда Ломаная линия, полупрямые которой образуют при вершине углы 0 и , может пересечься четыре раза с другой ломаной, полупрямые которой образуют углы , только если 30° . Невозможно выбрать более 5 углов, удаленных друг от друга на требуемое расстояние. (5 углов выбрать можно.)

1.20 Пусть Из (1.18) известно, что при это определяет Подставляя нашу рекуррентность, имеем а подставляя имеем

. Итак,

1.21 Можно положить равным наименьшему (или любому другому) общему кратному чисел [Нестрогое рассуждение наводит на мысль, что „случайное" значение подойдет с вероятностью

поэтому можно было бы ожидать, что удастся найти меньшее

1.22 Возьмите правильный многоугольник с сторонами и пометьте каждую из сторон элементами „цикла де Брейна" длины (Это циклическая последовательность нулей и единиц, в которой все наборы из смежных элементов различны; см. [139, упр. 2.3.4.2-23] и [140, упр. 3.2.2-17].) Затем добавьте к каждой стороне, которая помечена единицей, очень тонкий „довесок" Требуемые множества представляют собой таких многоугольников, повернутых длину" к сторон при

1.23 Да. (Нам потребуются основные понятия элементарной теории чисел из гл. 4.) Пусть Можно предположить, что тогда, согласно постулату Бертрана, между имеется простое число р. Можно также предположить, что поскольку оставляет в живых тогда и только тогда, когда оставляет в живых Выберите так, что Тогда люди выбывают в порядке

1.24 Единственно известные примеры: где — рациональное число, (при изменении все периоды имеют длину 2); рекуррентность Гаусса с периодом 5 из упр. 8; еще более замечательная рекуррентность Тодда [196] периодом 8; а также рекуррентности, полученные из них путем замены на умноженное на константу. Мы можем считать, что первый ненулевой коэффициент в знаменателе равен единице и что первый ненулевой коэффициент в числителе (если таковой имеется) имеет неотрицательную вещественную часть. Как легко показать при помощи компьютерной алгебры, при нет никаких других решений с периодом 5. Частичная теория была разработана Линессом [196, 197] и Куршаном и Гопинатом [172].

Интересным примером иного сорта, когда начальные значения вещественны, служит рекуррентность с периодом 9, обнаруженная Мортоном Брауном [34]. Получение нелинейных рекуррентностей с любым желаемым периодом 5 может быть основано на „континуантах" [164].

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление