МАЛЫЙ МЕХМАТ МГУ

Кружок 7 класса

Занятие 1.

Новые встречи со старыми знакомыми (07.10.2006)

1.

Можно ли выписать в ряд числа от 1 до 2006 так, чтобы любые два соседних числа, а также любые два числа, расположенные через одно, были взаимно просты?

Решение

Решение. Нельзя.

По определению, два числа взаимно просты, если их наибольший общий делитель равен 1. Следовательно, никакие два чётных числа не могут быть соседними и не могут стоять через одно в указанной расстановке, так как их НОД заведомо не менее двух (и то, и другое число делятся на 2). Теперь предположим, что расстановка чисел, указанная в условии, существует. Из рассуждений, проведённых выше следует, что и слева, и справа от каждого чётного числа должно стоять не менее двух нечётных: …, н, н, ч, н, н, … . Разобьём все расставленные числа на группы следующим образом: группу будут образовывать чётное число и все нечётные числа, стоящие справа от него до следующего чётного. В каждой такой группе будет одно чётное число и не менее двух нечётных. Таким образом, по кругу должно быть расставлено нечётных чисел минимум в два раза больше, чем чётных. Но расставлялись числа от 1 до 2006, среди которых чётных и нечётных поровну. Получаем противоречие. Значит, наше предположение неверно, и такая расстановка не существует.

2.

а)

Найдите значение суммы: 1 + 2 + ... + 500;

б)

Найдите значение суммы: 1 + 2 + ... + 1001;

в)

Докажите, что 1 + 2 + ... + = n(n+1)/2.

Ответ Решение Комментарий

Ответ. а) 250·501=125250; б) 500·1001=500500

Решение. Приведём решение сразу пункта в).

Обозначим сумму чисел от 1 до n за s: s = 1 + 2 + … + (n-1) + n.

Перепишем эту сумму по-другому:

s = 1 + 2 + … + (n-1) + n.

s = n + (n-1) + … + 2 + 1.

Сложим эти два равенства. Сумма левых частей равна 2s. В правых частях всего написано 2n чисел: n пар чисел, написанных друг под другом, - причём в каждой паре сумма равна n+1 (1 и n, 2 и n-1, 3 и n-2 и т.д.). Тогда сумма правых частей равна (n+1)n. Приравниваем полученные суммы, получаем: 2s=n(n+1). Тогда s=n(n+1)/2. А так как s – это и есть сумма чисел от 1 до n, то получаем требуемое равенство.

Комментарий. Формулу из пункта в) можно также доказать, например, методом математической индукции. Многие участники кружка должны были уже его знать к этому моменту.

3.

Сколько рёбер в полном графе с n вершинами?

Решение 1 Решение 2 Ответ Комментарий

Решение 1. (через комбинаторику)

Каждое ребро в графе задаётся парой вершин. В полном графе любые две вершины соединены ребром. Следовательно, задача о нахождении количества рёбер эквивалентна задаче о нахождении количества всевозможных пар вершин. Это количество равно n(n-1)/2. (В качестве первой вершины можно выбрать любую из n, в качестве второй – любую из (n-1)-ой оставшейся, при этом каждая пара посчитана дважды, так как нам не важно, какая вершина в паре первая, а какая – вторая.)

Решение 2. (через формулу суммирования из задачи 2в)

В полном графе с n вершинами из каждой выходит по (n-1) ребру. Из первой вершины выходит n-1 ребро, из второй вершины также выходит n-1 ребро, но одно из них, соединяющее эту вершину с первой, мы уже посчитали, то есть, новых рёбер появилось n-2. Из третьей вершины выходит n-1 ребро, из которых новых – n-3. И т. д., аналогично из (n-2)-ой вершины выходит 2 новых ребра, из (n-1)-ой – 1 новое ребро, из n-ой – 0. Таким образом, количество рёбер в этом графе равно: 1+2+…+(n-1). Воспользовавшись формулой суммирования, получим, что это равно (n-1)n/2.

Ответ. n(n-1)/2

Комментарий. Что такое граф, вершина графа и его ребро можно посмотреть в архиве занятий 6 класса за 2005/06 уч.г., занятие №13 «При чём здесь граф?»

4.

Найдите все n, для которых сумма всех натуральных чисел от 1 до n - простое число.

Решение Ответ

Решение. Сумма чисел от 1 до n равна n(n+1)/2. Так как n и (n+1) – последовательные числа, то одно из них делится на 2.

Если n>2 и n – чётное, то после сокращения n на 2 получится число, большее одного. Тогда данная сумма будет равна произведению двух чисел, больших 1 и меньших её самой (одно из них – это (n+1), другое то, что получилось после сокращения n на 2). Значит, эта сумма не может быть простым числом, так как имеет делители, отличные от 1 и самой себя.

Аналогично рассматривается случай, когда n>2 и n – нечётное. (В этом случае, (n+1) – чётное и большее 2.

Остались два возможных случая: n=1 и n=2. Если n=1, то сумма будет состоять из одного слагаемого, равного единицы, то есть, сама будет единицей. Но 1 не является простым числом. Если n=2, то сумма равна 1+2=3. 3 – простое число: такое n удовлетворяет условию задачи.

Ответ. n=2

5.

Можно ли расположить по кругу числа 1, 2, …, 8 так, чтобы сумма любых трёх рядом стоящих чисел была а) больше 11; б) больше 13?

Решение

Решение. а) Можно. Например, так: 1, 8, 3, 7, 4, 2, 6, 5.

б) Нельзя.

Предположим, что такая расстановка возможна. Рассмотрим все возможные тройки подряд стоящих чисел. Каждое число войдёт ровно в три такие тройки, и в каждой тройке сумма чисел должна быть больше 13, а значит, не меньше 14. Всего троек будет 8, тогда общая сумма чисел в них будет не меньше, чем 14·8=112. В эту сумму каждое из выписанных чисел входит по три раза. Тогда получается, что сумма чисел от 1 до 8 равна числу, которое не меньше, чем 112/3>37. Но 1+2+…+8=8·9/2=36. Противоречие, значит указанной в условии расстановки не существует.

6.

Существует ли десятизначное число, делящееся на 11, в записи которого каждая цифра встречается по одному разу?

Решение Комментарий

Решение. Существует, например, 1526384970.

Комментарий. Пример такого числа легко построить, воспользовавшись признаком делимости на 11.

7.

Циферблат часов (круг с числами 1, 2, …, 12) насажен в центре на ось, укреплённую на классной доске. Циферблат может поворачиваться вокруг оси на любой угол, кратный 30°. В начале на доске около каждого числа циферблата написали нуль. Затем циферблат несколько раз повернули, причём после каждого поворота к каждому из написанных на доске чисел прибавляли то, число, которое оказалось около него. Могли ли в итоге все числа на доске оказаться равными 2006?

Решение

Решение. Не могут.

Будем рассматривать в каждый момент времени сумму всех чисел, написанных на доске. После каждого поворота циферблата эта сумма увеличивается на 1+2+…+12=12·13/2=78. Так как в самом начале сумма была равна нулю, то в любой момент времени она должна делиться на 78. Если все числа на доске станут равны 2006, то их сумма, равная 2006·12, должна делиться на 78. Но нетрудно проверить, что это не так, значит, указанная ситуация невозможна.

8.

Двенадцать чисел 1, 2, …, 12 каким-то образом записаны по окружности. Одним ходом можно поменять местами два соседних числа, если модуль их разности больше 1. Докажите, что можно за несколько ходов расставить числа в естественном порядке.

Решение

Решение. В самом начале поставим 1 рядом с 2. Если между 2 и 3 нет 4 (с той стороны, где нет 1), то ставим 3 рядом с 2: …, 1, 2, …, 3, … - числа от 1 до 3 будут идти по порядку. Если между 2 и 3 стоит 4: …, 1, 2, …, 4, …, 3, …, то сначала передвигаем все числа между 2 и 4 за 1: …, 1, 2, 4, …, 3, потом задвигаем 4 за 2: 4, 1, 2, …, 3, а потом перемещаем 3 к 2. Аналогичным образом перемещаем 4 к 3, затем 5 к 4 и т. д. до тех пор, пока все числа не будут стоять по порядку.

9.

В шахматном турнире приняло участие n человек. Каждый сыграл с каждым ровно одну партию. Оказалось, что все, кроме Гоши, набрали одинаковое количество очков. Докажите, что Гоша либо у всех выиграл, либо всем проиграл. (В шахматном турнире за победу даётся 1 очко, за ничью 1/2 очка, за поражению 0 очков.)

Решение 1 Решение 2

Решение 1. ( С помощью естественных, но длинных алгебраических рассуждений.)

Всего в турнире было проведено n(n-1)/2 игр (это утверждение эквивалентно задаче о количестве рёбер в полном графе). Суммарно оба участника за игру получают 1 очко: 1+0 в случае победы одного из них и 1/2+1/2 – в случае ничьи. Значит, количество очков, суммарно набранное всеми участниками, равно n(n-1)/2. Обозначим количество очков, набранное Гошей через G, а каждым из остальных – через l. Тогда

n(n-1)/2 = l(n-1) + G или

n(n-1) = 2l(n-1) + 2G.

Из этого равенства следует, что 2G делится на (n-1). Если n – чётное, то (n-1) – нечётное, а значит 2 и (n-1) – взаимно просты, следовательно, G делится на (n-1). 0≤G≤n-1 (так как в турнире нельзя набрать меньше 0 очков и больше (n-1). Значит, либо G=0, либо G=n-1. В первом случае, Гоша все партии проиграл, во втором, все партии выиграл.

Если n – нечётное, то его можно представить в виде n=2k+1, где k – некоторое целое число. (В этом случае 0≤G≤2k.) Тогда равенство n(n-1)=2l(n-1)+2G можно переписать в виде

2k(2k+1)=2l·2k+2G или k(2k+1)=2kl+G. (*)

Из этого следует, что G делится на k. Значит, G равно 0, k или 2k. Если G=0, то Гоша всем проиграл, если G=2k=n-1, то Гоша у всех выиграл. Осталось рассмотреть случай, когда G=k. Равенство (*) можно переписать в виде k(2k+1)=2kl+k. Сокращаем на k≠0 (так как иначе n=1, а количество участников больше 1):

2k+1=2l+1. Отсюда следует, что k=l. Но l – это количество очков, которое набрали все участники, кроме Гоши. Но Гоша тоже набрал k очков, что противоречит условию задачи. Таким образом, этот случай невозможен.

Утверждение доказано.

Решение 2. (Предложенное одним из школьников)

Всего участники турнира набрали n(n-1)/2 очков. Если все, кроме Гоши, набрали по n/2 очков, то Гоша набрал n(n-1)/2-(n-1)n/2=0. Значит, в этом случае, он всем проиграл. Кроме того, остальные участники не могли набрать больше, чем по n/2 очков, так как иначе, у Гоши должно быть отрицательное число очков.

Если все, кроме Гоши, набрали по (n-1)/2 очков, то Гоша набрал n(n-1)/2-(n-1)(n-1)/2=(n-1)/2 – столько же, сколько и все остальные, а такого быть не может.

Если все, кроме Гоши, набрали по (n-2)/2 очков, то Гоша набрал n(n-1)/2-(n-1)(n-2)/2=2(n-1)/2=n-1. В этом случае, Гоша у всех выиграл.Понятно, что меньше, чем по (n-2)/2 очков остальные набрать не могли, так как иначе у Гоши будет больше, чем (n-1) очко, что больше, чем количество игр, которое он сыграл.

10.

Можно ли в клетках таблицы 6×6 записать натуральные числа от 1 до 36 так, чтобы сумма чисел, записанных в клетках каждой из фигур, изображённых на рисунке, была чётной?

Решение

Решение. Нельзя.

Предположим, что требуемым образом числа записать можно. Рассмотрим фигуру в виде «креста», составленную из клеток нашей таблицы. По условию задачи сумма чисел в клетках с номерами 1, 2 , 3 и 4, а также с номерами 1, 3, 4, 5 чётные. Следовательно, числа в клетках с номерами 2 и 5 либо оба чётные, либо оба нечётные. То же самое можно сказать и про числа в клетках 1 и 2, 4 и 5. Значит, все числа в клетках «креста», кроме, может быть, числа стоящего в центре, имеют одинаковую чётность. Из того, что «крест» может быть выбран произвольно, следует, что все числа в таблице, кроме тех, которые стоят в углах, должны иметь одинаковую чётность. Но это невозможно, так как среди чисел от 1 до 36 ровно 18 чётных и 18 нечётных. Получаем противоречие, значит, числа указанным образом расставить нельзя.