Сектор с квадратиком имеет размер 2k на 2k, что значит, что его можно полностью выложить тримино (исходя из того, что наше утверждение истинно при n = k). Затем положим одну костяшку тримино в центр доски так, чтобы она находилась одновременно в трех оставшихся секторах, каждый из которых также равен 2k на 2k и в каждом из которых у нас теперь есть по одному квадратику, что делает их абсолютно похожими на первый. Ну а если можно полностью выложить неперекрывающимися тримино каждую часть (размером 2k на 2k) доски, то ими можно выложить и всю доску размером 2k+1 на 2k+1.☺
Последнее тождество имеет много полезных применений. Давайте докажем его по индукции, добавив парочку других способов. Какова сумма первых n чисел, которые получаются при возведении 2 в последовательные степени, начиная с 20 = 1?
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…
Приступим к сложению:
Видите закономерность? Каждая сумма на 1 меньше следующего числа, получаемого от возведения 2 в степень. Все это сводится вот к чему.
Теорема: Для n ≥ 1
1 + 2 + 4 + 8 +… + 2n–1 = 2n – 1
Доказательство по индукции: Как мы уже отмечали, утверждение является верным при n = 1 (а также 2, 3, 4 и 5). При n = k мы можем утверждать, что
1 + 2 + 4 + 8 +… + 2k–1 = 2k – 1
Добавив к обеим частям следующее число, получаемое при возведении 2 в степень (то есть 2k), приходим к
1 + 2 + 4 + 8 +… + 2k–1 + 2k = (2k – 1) + 2k = 2 × 2k – 1 = 2k+1 – 1 ☺
В 4 и 5 главах мы подтвердили множество закономерностей, находя ответ двумя разными способами. Возможно, комбинаторный подход покажется вам наиболее ценным.
Вопрос: В хоккейной команде n игроков (соответственно, их свитера пронумерованы от 1 до n). Созывается пресс-конференция, на которую должен прийти хотя бы один игрок. Чему равно количество возможных «составов» команды на этой пресс-конференции?
Ответ 1: У каждого игрока два варианта: идти или не идти. Значит, у команды в целом есть 2n вариантов. Но из этого числа нам нужно вычесть единицу, чтобы исключить вероятность того, что на конференцию не придет никто. В итоге получается 2n – 1.
Ответ 2: За основу «состава» положим хоккеиста с наибольшим номером на свитере. «Состав» с единицей в качестве наибольшего числа всего 1, с двойкой их 2 (потому что хоккеист № 2 может пойти либо в одиночестве, либо в компании хоккеиста № 1), с тройкой – 4 (потому что хоккеист № 3 может пойти либо один, либо в компании хоккеиста № 2, который точно так же может позвать, а может и не позвать с собой хоккеиста № 1). Следуя этой логике и дальше, мы увидим, что всего возможных «составов» будет 2n–1, ведь хоккеист № n будет обязан пойти на конференцию, а у каждого из его товарищей (начиная с № 1 и заканчивая № n – 1), которых он может позвать с собой, будет по 2 варианта выбора. То есть 1 + 2 + 4 +… + 2n–1.
Оба результата верны, а значит, равны. Таким образом, получается, что 1 + 2 + 4 +… + 2n–1 = 2n – 1.☺
При всех достоинствах комбинаторного метода наиболее простым здесь будет алгебраический – схожий с тем, который мы использовали для преобразования периодической десятичной дроби в простую.
Алгебраическое доказательство:
Пусть S = 1 + 2 + 4 + 8 +… + 2n–1.
Удвоив обе части, получим
2S = 2 + 4 + 8 +… + 2n–1 + 2n
Вычтем первое уравнение из второго, что позволит нам избавиться от всего лишнего и оставить только S из первого и 2S из второго, то есть
Теорема эта – ключ к двоичной системе, имеющей огромное практическое значение: именно на ее основе проводят числовые операции все компьютеры. Смысл ее заключается в том, чтобы представить любое число как уникальную сумму различных степеней основания числа 2. Например,
Запишем это двоичным кодом, заменяя каждое возведенное в степень число 2 единицей, а каждое пропущенное значение 2 в степени – нолем. В нашем примере это 83 = (1 × 64) + (0 × 32) + (1 × 16) + (0 × 8) + (0 × 4) + (1 × 2) + (1 × 1). Следовательно, в двоичной системе число 83 выглядит так:
Как удостовериться, что в таком виде можно представить любое положительное число? Предположим, что каждое число от 1 до 99 есть уникальная сумма степеней основания 2. Сможем ли мы представить в столь же уникальном виде число 100? Начнем с наибольшей степени основания 2, которая меньше 100, то есть с 64. (Почему именно 64? Да потому что меньшие значения – 1, 2, 4, 8, 16 и 32 – дадут в сумме лишь 63, а значит, 100 нам никак не получить.) Остается добрать 36 – точно так же, с помощью чисел, которые получаются от возведения 2 в разные степени. Как это сделать? Проще всего – следуя той же логике, что и с сотней, то есть начать с самого большого подходящего нам числа. Так как 36 = 32 + 4, значит 100 = 64 + 32 + 4, в двоичной системе – (1100100)2. Обобщив это (с помощью так называемого убедительного индуктивного подтверждения), приходим к выводу, что любое положительное число имеет уникальное двоичное представление.
Простые числа
Как мы только что убедились, любое положительное целое число может быть представлено в виде уникальной суммы различных степеней числа 2. В принципе, можно говорить, что числа, получаемые при возведении 2 в последовательные степени – это строительные блоки, из которых складываются положительные целые числа.
