В математике доказывают не только абсолютную истинность, но и невозможность. Часто приходится слышать: «Нельзя доказать невозможное». Полагаю, здесь имеется в виду, что никому не под силу доказать существование розовых коров – по крайней мере, до тех пор, пока мы не увидим их в один прекрасный день. Но в математике невозможное вполне себе доказуемо. Например, сколько ни пытайтесь, вы ни за что не найдете два четных числа, которые в сумме давали бы нечетное. Или простое число, которое было бы больше всех остальных простых чисел. Сложность таких доказательств поначалу пугает, к ним нужно привыкнуть, и не ждите, что это произойдет с первого (а то и со второго или с третьего) раза. Но стоит войти во вкус – и удержаться уже невозможно: настолько они удивительны и притягательны. Стройное доказательство подобно хорошему анекдоту или уместной шутке – удовлетворение от него испытываешь ничуть не меньшее.
С вашего позволения, расскажу о первом своем опыте на этой стезе. В детстве двумя главными предметами моего обожания были настольные игры и загадки. Как-то раз мой друг предложил мне загадку, связанную с настольными играми, и, конечно, я был заинтригован. Он положил передо мной пустую шахматную доску размером 8 на 8 клеточек и 32 костяшки домино и спросил:
– Можешь выложить домино так, чтобы они закрыли всю доску?
– Конечно, – уверенно ответил я. – Просто по четыре костяшки на ряд. Вот так:
– Молодец, – сказал он. – А если я уберу две клетки – правую нижнюю и левую верхнюю, и их останется 62 – сможешь закрыть оставшиеся 31 костяшкой? – и он положил на крайние квадратики две монетки.
– Хм… Наверное, – ответил я.
Но как я ни пытался, какие комбинации ни пробовал, у меня ничего не получалось. Наконец я сдался, заявив, что это в принципе невозможно.
– А если невозможно, – сказал мой друг, – можешь доказать это?
Я не мог. Ведь для этого потребовалось бы проверить бесконечное множество вариантов (если хотите, можете посчитать, сколько именно) и удостовериться в том, что каждый из них невозможен.
– Посмотри на цвета, – посоветовал друг, видя мое замешательство.
«На цвета? Причем тут цвета?» – подумал я. А потом понял. Обе закрытые клеточки были белыми, а значит, из 62 оставшихся свободными, 32 были черными и всего лишь 30 – белыми. А поскольку костяшка домино, как ее ни положи, закрывает пару разноцветных клеточек, выложить ими всю доску не получилось бы ни за что на свете. Здо́рово!
Отступление
Если вам понравилось последнее доказательство, понравится и это. Играя в известный всем «Тетрис», нужно заполнять «стакан» из 10 клеток падающими фигурами. Всего их 7, и соответственно их форме их иногда обозначают латинскими буквами: I, J, L, O, Z, T и S.
Каждая фигура состоит из 4 квадратиков, поэтому вполне естественно задаться вопросом, можно ли сложить их как-нибудь так, чтобы получился прямоугольник размером 4 на 7? При этом фигурки можно переворачивать как угодно.
Оказывается, нельзя. Как это доказать? Давайте раскрасим квадратики в прямоугольнике в шахматном порядке – так, чтобы получилось 14 серых и 14 белых.
Обратите внимание: любая фигура, кроме «Т», должна закрывать 2 белых и 2 серых квадратика независимо от своего положения. Сама же «Т» состоит из 3 квадратиков одного цвета и 1 квадратика – другого. Следовательно, как бы ни располагались остальные 6 фигур, они закроют 12 белых и 12 серых квадратиков, а это значит, что для «Т» останется только по 2 квадратика каждого цвета, в которые она «не впишется».
Как же убедить окружающих в истинности математического утверждения, которое кажется нам верным? Обычно начинают с описания математических объектов, которые мы используем, например целых чисел
множества, которое включает положительные и отрицательные числа и ноль.
Определив объекты, мы делаем допущение, которое считаем самоочевидным – например, «сумма или произведение двух целых чисел всегда будет целым числом» (в следующей главе, посвященной геометрии, мы будем исходить из того, что между двумя точками можно провести только одну прямую). Такие самоочевидные, не требующие доказательств утверждения называются аксиомами. С их помощью, плюс немного логики и алгебры, мы можем доказывать другие положения, не столь очевидные – теоремы. В этой главе вы познакомитесь с основным инструментарием математических доказательств.
Начнем, пожалуй, с доказательства простых теорем, которые вызывают минимум сомнений. Когда мы слышим «два четных числа при сложении дают третье четное число» или «два нечетных числа при умножении дают третье нечетное число», наш разум обычно пытается проверить такие утверждения рядом примеров и из них сделать вывод, что это, скорее всего, верно. Ну или хотя бы не полная чушь. Вы даже можете решить, что это настолько очевидно, что может быть принято как аксиома. Делать этого не стоит – по крайней мере, до тех пор, пока вы можете построить цепочку доказательств, используя уже известные вам аксиомы. Так, чтобы доказать утверждения о четных и нечетных числах, начать стоит с понимания того, что вообще такое «четное» и «нечетное».
Четным называется число, которое делится на 2 без остатка. Если выразить это алгебраически, то число n является четным, если n = 2k (где k есть целая величина). Будет ли четным числом 0? Да, потому что 0 = 2 × 0. Теперь у нас есть все необходимое, чтобы доказать, что два четных числа в сумме дают третье четное.
Теорема: Если m и n – четные, то сумма m + n – тоже четное.
Это прекрасный пример теоремы по принципу «если…, то…». Чтобы ее доказать, нам надо сделать допущение в части, начинающейся с «если…», и, смешав логику с алгеброй, показать, что часть, начинающаяся с «то…», является следствием этого допущения. В нашем примере мы предполагаем, что m и n – четные, и поэтому m + n тоже будет четным.
Доказательство: Предположим, что m и n – четные числа. Значит, m = 2j, а n = 2k, где j и k суть целые величины. Тогда
