Яков Перельман - Веселые задачи. Две сотни головоломок
160. «Скромная награда» не могла быть выдана потому, что не только в Индии, но и во всем мире нет такого количества зерен, какое она предполагает. Само вычисление затребованной суммы зерен представляет собой нелегкую задачу. В самом деле: требуется сложить ряд чисел
1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + и т. д.
Здесь выписаны только первые 8 чисел. Но остается еще 56. Чтобы узнать последнее 64-е число, нужно умножить число 2 само на себя 62 раза. В то время индусы не знали логарифмов, сокращающих подобные вычисления, поэтому они должны были выполнить умножение обычными приемами арифметики. Однако стоит лишь приступить к подсчетам, чтобы ощутить, насколько они утомительны. Правда, можно облегчить себе работу и сэкономить много времени, разбив наши 63 множителя на группы, по 7 двоек, тогда придется перемножить «только» 9 множителей, каждый из которых равен 128 (или же, если хотите, «всего» три множителя, каждый из которых равен произведению 128 х 128 х 128). Но слова «только» и «всего» недаром взяты здесь в кавычки, потому что работы все равно останется предостаточно. Ведь это лишь одно, последнее, 64-е слагаемое; а еще нужно вычислить все предыдущие 63 слагаемых, да кроме того эти числа сложить…
Для тех, кто изучал алгебру и знаком с логарифмами и прогрессиями, выполнение этого расчета – правда, приближенное, с точностью до 100 000-й доли результата – не составило бы никакого труда. Так как я не могу предполагать у читателей таких познаний из алгебры, а с другой стороны, не собираюсь засадить их за многочасовые выкладки, то укажу простой способ хотя бы грубо оценить истинные размеры «скромной награды» индусского мудреца.
Продолжив ряд2, 4, 8,16, 32, 64 и т. д.
до его 10-го члена, получим 1024. Так как мы стремимся определить, как велико последнее слагаемое лишь приблизительно, то откинем в числе 1024 24 единицы, чтобы округлить результат до 1000. Если первые десять двоек при перемножении дали около 1000, то столько же дает и умножение следующих двоек, а также дальнейших групп из 10 двоек. Всех множителей-двоек у нас 63, т. е. шесть групп по 10 и еще седьмая группа из трех двоек. Значит, число зерен, причитающееся изобретателю за последнее, 64-е поле шахматной доски должно приблизительно равняться
1000 × 1000 × 1000 × 1000 × 1000 × 1000 × (2 × 2 × 2) = 8 000 000 000 000 000 000
Восемь квинтиллионов зерен – вот примерная величина последнего слагаемого! Чтобы вычислить (приблизительно) всю сумму, обратим внимание на поучительную особенность ряда
1,2, 4, 8,16, 32, 64, 128 и т. д.
Легко заметить, что каждое число в нем равно сумме всех предыдущих, увеличенной на 1. Например:
8 = (1 + 2 + 4) + 1; 16 = (1 + 2 + 4 + 8) + 1;
32 = (1 + 2 + 4 + 8 +16) +1.
Понятно, что и последнее, 64-е число этого ряда равно сумме 63 предыдущих плюс 1. Но мы уже знаем, что это последнее число приблизительно равно 8 квинтиллионам. Следовательно, сумма всех предыдущих чисел приблизительно равна 8 квинтиллионам, а общее число всех зерен, причитающихся изобретателю, приблизительно равно
16 000 000 000 000 000 000.
Рис. 157.
Этот результат, однако, заведомо меньше истинного – вспомните, что в каждом из 6 множителей мы откидывали 24 единицы (брали ровно 1000 вместо 1024). Точное вычисление дало бы результат
18 446 744 073 709 551 515.
Чтобы помочь вам ощутить «огромность» этого числа, замечу, что в кубическом метре (80-ведерной бочке) помещается 15 миллионов пшеничных зерен. «Скромная награда» должна была занять объем около 12 000 000 000 000 кубических метров, или 12 000 кубических километров! Далее. Поверхность земного шара – всех его материков и океанов – равна 500 миллиардам квадратных метров. Поэтому, если рассыпать наше число зерен ровным слоем по всему миру, он имел бы толщину 12: 500 = 0,024 м, или примерно 1/4 см. Будь земной шар целиком превращен в сплошное пшеничное поле (для чего потребовалось бы осушить океаны, растопить полярные льды и оросить все пустыни), то урожай с него целиком пошел бы в награду изобретателю шахматной игры. В заключение предлагаю читателю самому вычислить, цепочка какой длины получилась бы, если все эти зерна выложить в один ряд. На всякий случай сообщаю, что от Земли до Солнца 150 000 000 км, хотя не думаю, что с такой цепью зерен вы останетесь в пределах Солнечной системы.
Путешествия по кристаллу и непрерывное черчение (161–170)
– Чем вас так заинтересовала эта муха на кристалле?
– Своим странным поведением: она ходит по кристаллу, право, не без системы. Посмотрите, она путешествует только по ребрам и не ступает по граням. Что за охота ей ходить по острым ребрам, когда рядом сколько угодно плоских мест?
– Мне кажется, дело довольно просто. Чем склеены у вас грани кристалла?
– Вы подозреваете, что в клее есть что-то сладкое, привлекающее муху? Кажется, вы правы; она действительно вылизывает хоботком ребра кристалла. Так вот почему она медленно и систематически переходит с одного ребра на другое!
Рис. 158. Муха на кристалле.
– И при этом на практике решает интересную задачу: обойти многогранник по его ребрам, не посещая дважды ни одного ребра.
– Разве это возможно?
– В данном случае вполне: ведь этот кристалл – восьмигранник.
– Да, октаэдр. И что же?
– У него на каждой вершине сходятся 4 ребра.
– Разумеется. Но какое отношение это имеет к нашей задаче?
– Самое непосредственное. Задача обойти все ребра многогранника, и притом не более чем по одному разу, разрешима только для тех многогранников, у которых в каждой вершине сходится четное число ребер.
– Вот как! Я об этом не знал. Почему же?
– Почему в каждой вершине должно сходиться именно четное число ребер? Очень просто. Ведь в каждую вершину надо попасть и надо из нее уйти, причем прийти по одной дороге, а уйти по другой, значит, нужно, чтобы в ней сходилась пара ребер. Если же, путешествуя по кристаллу, вы попадете на вершину вторично, если к ней ведет еще и третье ребро, то должно иметься непременно и четвертое, чтобы вы могли уйти с этой вершины, а не очутиться в тупике. Другими словами, число ребер, сходящихся в каждой вершине, должно быть парное, т. е. четное. Если хотя бы одна вершина многогранника имеет нечетное число сходящихся в ней ребер, то на такую вершину вы, конечно, можете, исчерпав все ведущие к ней парные ребра, попасть по последнему неиспользованному ребру, но покинуть эту вершину вам уже не удастся: путешествие здесь поневоле оборвется.
– Но ведь я могу просто не воспользоваться этим ребром, раз оно заведомо ведет в тупик!
– Тогда вы не выполните другого условия нашего путешествия: пройти по всем ребрам без исключения.
– Позвольте, но может же случиться, что это ребро как раз последнее и единственное, еще не пройденное. Тогда нет вовсе надобности покидать его: оно и будет конечной целью путешествия.
– Совершенно правильно. И если бы в фигуре была только одна «нечетная» вершина, то вам нужно было бы избрать такой маршрут, чтобы вершина эта оказалась последним этапом – тогда вы разрешили бы задачу успешно. Или же начать движение с этой вершины – тогда вам не пришлось бы в нее возвращаться. Однако, фигур с одной «нечетной» вершиной не существует: таких вершин должно быть четное число – две, четыре, шесть и т. д.
– Это почему же?
– Вспомним о том, что каждое ребро соединяет две вершины. И если какая-нибудь вершина имеет ребро без пары, то оно должно упираться в какую-нибудь соседнюю вершину и там тоже быть непарным ребром.
– А если соседняя вершина и без этого ребра «нечетная»? Тогда новое ребро делает ее «четной», и наша «нечетная» вершина остается одинокой.
– Этого не может быть. Если без нашего ребра у соседней вершины сходится нечетное число ребер, то, значит, одно из ее непарных ребер соединено с какой-то другой вершиной, и следовательно, «нечетная» вершина еще будет найдена. Иначе говоря, если в фигуре имеется одна «нечетная» вершина, то непременно должна существовать и вторая. Число «нечетных» вершин не может быть нечетным. Поясню это еще и иным путем, пожалуй, более простым. Представьте, что вам нужно сосчитать число ребер в какой-то фигуре. Вы считаете ребра, сходящиеся в одной вершине, прибавляете ребра, сходящиеся во второй, потом – в третьей и т. д. Когда вы все это сложите, что у вас получится?
– Двойное число ребер фигуры, потому что каждое ребро считалось дважды: ведь каждое ребро соединяет две вершины.
– Именно. Вы получите удвоенное число ребер. И если допустить, что в одной из вершин сходится нечетное число ребер, а во всех прочих – четное, то результатом сложения будет, конечно, число нечетное. Но может ли удвоенное целое число быть нечетным?
– Не может, конечно. Теперь мне совершенно ясно, что «нечетных» вершин во всякой фигуре должно быть две, четыре, т. е. обязательно четное число. Все же я думаю, что и кристалл с двумя «нечетными» вершинами возможно обойти. Пусть у нас имеется фигура с двумя «нечетными» вершинами. Что мешает начать путешествие именно в одной из этих точек и закончить в другой? Тогда не понадобится ни возвращаться в первую, ни уходить из последней. Путешествие будет выполнено с соблюдением всех требуемых условий.
