Шумерские игры

Казалось бы, как могут быть связаны математика и археология? Вы удивитесь, но порой археологические находки подкидывают математикам очень непростые задачи! И связаны они, как ни странно, с древними математическими играми.

В Древнем Шумере (насколько нам известно) не было ни мобильных телефонов, ни телевизоров, поэтому взрослые и дети развлекали себя, как могли. Например, для одной из сложных и красивых настольных игр ими использовалась двенадцатиугольная игральная доска с особым узором. К сожалению, рассказать нам об этой игре Шумеры уже не могут, поэтому о некоторых нюансах математикам приходится только догадываться. Зато игры, в которые играли дети в Шумерском государстве, доступны нам даже сейчас, ведь для них использовались только камни!

Алгоритм игры на самом деле очень прост. В первую очередь юный Шумер собирал кучу из сотни камешков, затем делил ее на две, и после каждым ходом делил таким образом какую-нибудь кучку, чтобы в конце концов получить сотню камешков, лежащих отдельно. В чем же заключался смысл игры? Будьте уверены: дети той эпохи очень хорошо умели считать и ставили перед собой непростые цели. Возможно ли раскладывать камни так, чтобы в какой-то момент в тридцати кучках было ровно 60 камешков? А в двадцати? И само главное: что делать, чтобы за всю игру ни в каких 19 кучках не оказалось бы в сумме 60 камней? Что ж, математики готовы играть!

Начнем с первого вопроса. Нам не важно, по сколько камешков в каждой из 30 кучек, главное, чтобы в сумме их было 60. Как в таком случае будут разложены оставшиеся 40 камней? Можем ли мы предположить, что все они будут лежать в кучках по одному? Давайте рассмотрим тот момент, когда кучек стало 30 + 40 = 70. Если среди них меньше 40 кучек по одному камешку, то хотя бы в 31 одной кучке не меньше 2 камней, а значит всего в сумме камней не меньше, чем 2*31 + 39 = 101 камень. Это означает, что среди 70 кучек обязательно найдется 40 кучек по 1 камню. Такой подход к решению называется Принцип Дирихле и используется во многих даже олимпиадных задачах. А нам теперь осталось только сказать, что в 30 = 70 – 40 оставшихся кучках содержится ровно 60 = 100 – 40 камней, а значит, при любой схеме действий такой момент обязательно настанет!

Рассмотрим теперь второй вопрос. Здесь все немного сложнее, и нам предстоит воспользоваться вторым замечательным инструментом, подходящим даже для олимпиад – математической индукцией. Итак, докажем по индукции, что для n = 2, 3, … 20 в некоторый момент найдется 2n + 60 камней в n + 20 кучках. Будьте внимательны: ответ на второй вопрос это доказательство может дать только при n = 0, но это значение пока не входит в наш список! Базой индукции будем считать тот факт, что при n = 20 мы имеем 100 камней в 40 кучках после любых 40 ходов. Теперь опишем Шаг индукции: считая верным утверждение для n, докажем его для n-1, тогда, «спускаясь» по такому доказательству все ниже, мы сможем доказать наше утверждения для всех n = 2, 3, … 20. Именно в таком спуске заключается смысл математической индукции. Итак, пусть n > 2 и у нас есть 2n + 60 камней в n + 20 кучках. Среди них найдется кучка из двух камней или 2 кучки по одному камню, поскольку 3*(n + 19) + 1 > 2n + 60 при n > 2 – вновь работает принцип Дирихле. Отбросим их. И еще: во втором случае, когда отбросить придется 2 кучки, разобьем одну из оставшихся кучек на две. Тогда n уменьшится на единицу: мы получим 2(n – 1) + 60 камней в (n – 1) + 20 кучках. При помощи математической индукции доказано! Так, самое время вспомнить, что мы все же не получили еще ответ на вопрос задачи: при n = 2 мы имеем 64 камня в 22 кучках. Что нужно сделать? Нужно убрать 4 камня двумя или более кучками. Возможно ли это? Вспомним вновь про принцип Дирихле: если есть кучка хоть одна кучка из одного камня и при этом нельзя убрать 4 камня двумя или более кучками, то все кучки, кроме трех, имеют не менее 4 камней, что означает, что камней не меньше, чем 1 + 1 + 1 + 4 · 19 > 64. Если же кучки из одного камня нет, и мы все еще не можем убрать 4 камня 2 и более кучками, то камней не меньше, чем 2 + 3 · 21 > 64. Мы получили противоречие: для любого случая наличия одиночной кучки камней получается слишком много, а значит, нам ничего не помешает убрать 4 лишних камня 2 или более кучками. Отбросив их, мы получим 60 камней в 20 или менее кучках. Осталось только разделить кучки до ровно 20!

Ответ на главный и третий вопрос задачи, наверное, окажется для вас самым легким: все же, использовать мы с вами будем всего лишь признаки делимости! Стратегия будет максимально проста: будем отделять от большой кучи по три камня до тех пор, пока их не останется всего 4. В большой кучке число камней все это время не будет делиться на три, а значит, в любых 19 кучках с ее участием не может быть 60 камней – кратное 3 число. При этом в любых других 19 кучках камней будет всего 57 = 19 * 3. Теперь разделим 4 камня на 2 кучки по 2. В каждой кучке с этого момента будет не больше 3 камней, а значит в любых 19-ти – не больше 57. Игра завершена!

Сегодня вместе с нами вы освоили игру Древних Шумеров, а вместе с ней – три очень важных приема решения математических задач. Спешим вас заверить: с принципом Дирихле, математической индукцией и признаками делимости вам не страшны ни последняя задача из ЕГЭ – «Числа и их свойства» – ни даже олимпиадные задачи!