VIII Всероссийский студенческий турнир математических боёв
2 тур, 7 апреля 2013 г.
1. В n клетках, расположенных в строку, записаны числа 1, … , n в некотором порядке. Разрешается выбрать любую клетку и заменить числа в этой и соседних по стороне клетках на их среднее арифметическое. Всегда ли существует такая начальная расстановка чисел, для которой найдется способ с помощью нескольких таких операций сделать все числа равными?
2. В таблице 3´3 записаны числа 1, … , 9, так что модуль разности между числами в любых двух соседних по стороне клетках не меньше данного числа а. При каком наибольшем значении а это возможно?
3. Вычислите определитель n-го порядка 
.
4. p – простое число, большее 3. Докажите, что 7p – 6p – 1 делится на 43.
5. n школьников сидят вокруг учителя, который раздает леденцы. Учитель выбрал первого попавшегося ребенка и дал ему леденец, следующий леденец он дал ребенку сидящему через одного от первого по часовой стрелке, затем он пропустил еще двух школьников, и дал леденец следующему ребенку, затем он пропустил трех, и так далее…Найдите все значения n, при которых рано или поздно каждый ребенок получит хотя бы по одному леденцу.
6. Четыре куба расположены в пространстве так, что каждые три из них имеют общую вершину. Верно ли, что все четыре обязаны иметь общую вершину? (кубы могут пересекаться).
7. Решите уравнение 
.
8. На доске 3n×3n уложены плитки 1×3, покрывающие всю доску. Докажите, что на доске найдется квадрат 3×3, покрытый тремя плитками. Какое наибольшее число таких квадратов гарантированно может найтись для данного n?
9. Капитан Кук попал на остров, каждый из ста жителей которого либо лжец, который всегда врет, либо рыцарь, который всегда говорит правду. Среди туземцев есть хотя бы один лжец. Лжецы сговорились лгать таким образом, что каких бы 50 жителей Кук ни собрал вместе, имеющиеся среди них лжецы отвечали на вопрос «Сколько среди собранных здесь туземцев рыцарей?» так, что Кук всегда получал один и тот же набор из 50 ответов. Какое наибольшее число рыцарей могло быть на острове?
2 тур, 7 апреля 2013 г.
Решения задач
1. () Всегда. При указанных операциях сумма всех чисел не меняется. Значит, если они станут одинаковыми, то будут равны среднему арифметическому всех чисел, то есть (n+1)/2. Построим искомую расстановку. Разобьем все числа на пары чисел, дающих в сумме n + 1 (при нечетных n среднее число останется без пары, оно уже равно (n+1)/2). Располагаем числа в строку этими парами произвольно, начиная с левой клетки. Сначала выбираем левую клетку, у нее есть только одна соседняя. Среднее арифметическое чисел в этих клетках равно (n+1)/2. Далее действуем по общему правилу: выбираем первую слева клетку, которая еще не участвовала в преобразованиях. Одно из трех чисел, для которых ищем среднее арифметическое, будет равно (n+1)/2, два других в сумме дают (n+1). Значит, среднее арифметическое опять будет равно (n+1)/2. Пройдя строку до конца, сделаем все числа равными.
2. () При а = 3 это можно сделать, например, как показано на рисунке. При а = 4 это невозможно. У числа 5 есть только два числа, отличающихся от него на 4: это 1 и 9. Значит, число 5 должно стоять в углу таблицы, а 1 и 9 быть его соседями. Но тогда у 1 и 9 есть еще одна общая соседняя клетка, в которую записать нечего.
3. (из задачников) Обозначим этот определитель через Dn. Умножим первый столбец на n и вычтем из него второй, затем умножим второй столбец на n и вычтем из него третий, и т. д. до предпоследнего столбца. В результате определитель умножится на nn–1 и преобразуется к виду
nn–1Dn =
=
=nn
=
= nn(n – 1)! Dn –1.
Отсюда получаем рекуррентное соотношение Dn = n! Dn –1. А так как D1 = 1, то Dn = 1! 2! … n!
4. (Иранская олимпиада 1994 г) Простое число, большее 3, имеет вид 6k + 1 или 6k + 5. Замечаем, что
76 º 1(mod 43) и 66 º 1(mod 43). Поэтому 76k +1 – 66k +1– 1 º 7 – 6 – 1 º 0(mod 43);
76k + 5 – 66k + 5– 1 º 75 – 65 – 1 º 0(mod 43).
5. (Азиатско-Тихоокеанская МО, 1991) Пронумеруем школьников по часовой стрелке. Нулевой номер присвоим тому, кто получил первый леденец. Пусть am – номер школьника, получившего леденец на m-ом шагу. Тогда am+1 = am + (m + 1), сложение выполняется по mod n. Значит, am = 1 + … + m = 
.
Чтобы все школьники получили по леденцу, требуется, чтобы в списке получающихся номеров встретились все номера. Пусть n = 2kl, где l – нечетное, l > 2. Чтобы встретились все номера, требуется, чтобы встретились все номера по mod l. Но al – 1 º al º 0(mod l), и при дальнейших шагах будет циклическое повторение номеров по mod l, полученных до l-го шага. А так как среди номеров a0, a1, … , a l – 1 есть одинаковые (a0 = a l – 1), то какой-то номер не встретится. Значит, для рассматриваемых значений n не все школьники получат леденец.
Пусть теперь n = 2k. Покажем индукцией по k, что в этом случае все школьники получат по леденцу. При k=1 на первых двух шагах имеем номера 0 и 1. Делаем индуктивное предположение, что для n = 2k все номера a0, a1, … , a n – 1 различны, и рассмотрим n = 2k + 1. По индуктивному предположению номера a0, a1, … , различны по mod 2k, а значит, и по mod 2k + 1. Далее, = + 2k, значит, º (mod 2k), но ¹ (mod 2k + 1). Пусть º (mod 2k), но ¹ (mod 2k + 1). Это значит, что º + 2k(mod 2k + 1). Отсюда
= + 2k + m º + 2k + 2k + m º + (2k – m)+ 2k + 2k + m º + 2k(mod 2k + 1).
Значит, номера , , … , совпадают с соответствующими номерами a0, a1, … , , расположенными в обратном порядке, по mod 2k, но не совпадают по mod 2k + 1. Таким образом, первые 2k + 1 номеров включают все номера школьников, и каждый получит по леденцу.
6. () Не обязательно. Для построения примера возьмем вспомогательный куб и впишем в него вспомогательный правильный тетраэдр с вершинами в вершинах куба. Отразим вспомогательный куб относительно каждой грани тетраэдра. Получившиеся четыре куба и образуют требуемую конструкцию: каждая вершина тетраэдра является общей вершиной для трех кубов, а все четыре общей вершины не имеют.
7. () Уравнение преобразуется к виду 
. Производим замену cos x = t. Уравнение 2t = t + 1 имеет два корня 0 и 1. Других корней нет, так как график левой части уравнения – экспонента, выпуклая вниз, а график правой части – прямая, и они могут иметь не более двух точек пересечения. Значит, приходим к уравнению cos x = 0 или cos x = 1, и решения исходного уравнения 2pn; p/2 + pn, n Î Z.
8. () Предположим, что такой квадрат не найдется. Рассмотрим клетку, находящуюся в левом нижнем углу. Пусть она покрыта плиткой, расположенной вертикально. Рядом с этой плиткой справа можно расположить еще не более одной вертикально расположенной плитки, а следующая клетка, расположенная в образовавшемся углу, должна быть расположена горизонтально. Выше этой горизонтальной плитки можно расположить еще не более одной горизонтальной плитки, а следующая угловая клетка обязательно должна быть покрыта горизонтальной плиткой. Продолжая далее, получаем покрытие «ёлочкой». В какой-то момент ёлочка дойдет до правого или верхнего края доски, когда располагать плитки горизонтально или вертикально станет невозможно. Здесь и возникнет квадрат 3×3, покрытый тремя плитками.
В любом случае можно предложить покрытие с одним единственным таким квадратом. Сначала выложим три ряда из вертикальных плиток вдоль правого и левого краев доски: два ряда возле одного края, один ряд возле другого. Затем выложим три горизонтальных ряда возле верхнего и нижнего краев доски. В результате останется непокрытым квадрат 3(n – 1)×3(n – 1). С ним поступаем таким же образом. В конце придем к единственному квадрату 3×3, покрытому тремя плитками.
9. (Д. Калинин, турнир им. ) Если рыцарей не менее 50, то возможна ситуация, когда вместе соберутся 50 рыцарей, тогда будет 50 ответов «50». Могут собраться 49 рыцарей и один лжец, тогда гарантированно будет 49 ответов «49». Совместить эти наборы ответов невозможно. Значит, рыцарей меньше 50. Пусть число рыцарей k. Тогда возможны ситуации, когда в собранной группе из 50 туземцев будет 1, 2, … , k рыцарей. Значит, возможен 1 ответ «1», 2 ответа «2», … , k ответов «k». Все это необходимо учесть в том наборе ответов, который хотят обеспечить лжецы. Следовательно, этот набор должен включать k(k + 1)/2 упомянутых ответов. При k ≥ 10 это невозможно, так как k(k + 1)/2 ≥ 55. При k £ 9 имеем k(k + 1)/2 £ 45, и составить нужный набор ответов возможно. В любой собранной группе из 50 человек имеющиеся рыцари дадут необходимое количество правильных ответов, а все остальные ответы из заданного списка будут неправильными и могут быть даны лжецами. Оставшиеся из 50 ответов должны быть неправильными в любом случае; это могут быть, например, ответы «10» (но не «0»).
