Курсовая работа по математике

Нестандартные задачи по математике

Студент: Игнатьева Ольга Михайловна

физико – математический факультет 4 курс

Научный руководитель: Емельченков Евгений Петрович

СГПУ

2001

1. Инварианты

Инвариантом некоторого преобразования или системы действий называется величина (или свойство), остающаяся постоянной при этом преобразовании.

Нередко встречаются задачи, в которых спрашивается, можно ли в результате некоторых действий получить тот или иной результат. Основным методом решения подобных задач является нахождение свойства исходного объекта, которое не меняется после выполнения таких действий, - это и есть инвариант. Если конечный объект задачи не обладает найденным свойством, то он, очевидно, не может быть получен в результате этих действий из исходного объекта.

Полуинвариант - величина, изменяющаяся только в одну сторону (т.е. которая может только увеличиваться или только уменьшаться). Понятие полуинварианта часто используется при доказательствах остановки процессов.

1. Имеется квадратная таблица 10х10, в клетки которой в последовательном порядке вписаны натуральные числа от 1 до 100: в первую строку - числа от 1 до 10, во вторую - от 11 до 20 и т. д. Докажите, что сумма S любых 10 чисел таблицы, из которых никакие два не стоят в одной строке и никакие два не стоят в одном столбце, постоянна. Найдите эту сумму.

Решение.

Обозначим слагаемое исходной суммы S из первой строки через а1 , из второй - через 10 + а2, из третьей – через 20 + а3 и т. д., наконец, из десятой – через 90 + а10.

Здесь каждое из натуральных чисел а1, а2, …,а10 заключено в пределах от 1 до 10 , причем эти числа попарно различны, так как, если бы, например, а1 = а2 , то числа а1 и 10 + а2 стояли бы в одном столбце таблицы. Получаем:

S = а1 + ( 10 + а2 ) +( 20 + а3 ) + …+ ( 90 +а10 ) =

= ( 10 + 20 +…+ 90 ) + ( а1 + а2 +…+ а10 ) =

= 450 + (а1 + а2 +…+ а10 ).

Поскольку числа а1, а2,…, а10 попарно различны и принимают все целые значения от 1 до 10 , то каждое из натуральных чисел от 1 до 10 входит в сумму а1 + а2 +…+ а10 в качестве слагаемого ровно один раз. Следовательно,

а1 + а2 +…+ а10 = 1 + 2 +3 +… + 10 = 55,

S = 450 + 55 = 505.

Сумма S и является инвариантом : если в ней одни слагаемые заменить другими, но так, чтобы все слагаемые новой суммы стояли в таблице в разных строках и в разных столбцах, сумма примет, тоже самое значение.

Ответ : 505.

2. На каждой клетке шахматной доски 8х8 написали произ-ведение номера строки, в которой расположена клетка, на номер ее столбца. Выбрали 8 клеток, из которых никакие две не стоят в одной строке и никакие две не стоят в одном столбце. Докажите, что произведение чисел, написанных в этих клетках, постоянно, и вычислите его .

3. Лист бумаги разорвали на 5 кусков, некоторые из этих кусков разорвали на 5 частей, а некоторые из этих новых частей разорвали еще на 5 частей и т. д. Можно ли таким путем получить 1994 куска бумаги ? А 1997 ?

Решение.

При каждом разрывании листа или одного куска бумаги на 5 частей общее число кусков увеличивается на 4 . Поэтому число кусков бумаги на каждом шаге может иметь только вид 4k + 1 (k-

натуральное число ). Это выражение и является инвариантом.

Так как 1994 нельзя представить в виде 4k + 1 , то число кусков, равное 1994 , получиться не может, а 1997 = 4k + 1 при k = = 499 ,следовательно, 1997 кусков получиться могут.

4. Имеется два листа картона. Каждый из них разрезали на 4 куска, некоторые из этих кусков разрезали еще на 4 куска и т. д. Можно ли таким путем получить 50 кусков картона? А 60 ?

5. Каждое натуральное число от 1 до 50000 заменяют числом равным сумме его цифр. С получившимися цифрами проделывают ту же операцию, и так поступают до тех пор, пока все числа не станут однозначными. Сколько раз среди этих однозначных чисел встретится каждое из целых чисел от 0 до 8?

Решение.

Указанные однозначные числа в последовательном порядке таковы : 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2,3, 4, 5, 6, 7, 8, 0,… .

Эта закономерность сохраняется и дальше. В самом деле, при замене натурального числа суммой его цифр остаток от деления числа на 9 остается неизменным, поэтому при переходе от каждого натурального числа к следующему остаток от деления числа на 9 увеличивается на 1 или перескакивает от 8 к 0. Для того чтобы узнать, сколько таких групп цифр по 9 цифр в каждой, разделим 50000 на 9 с остатком : 50000 = 9 5555 + 5.

Следовательно, таких групп 5555 . Еще одну, неполную группу образуют последние 5 цифр : 1, 2, 3, 4, 5.

Ответ : 1, 2, 3, 4, 5 – по 5556 раз , 6, 7, 8, 0 – 5555 раз .

6.На доске написаны числа 1, 2, 3, …, 125 . Разрешается стереть любые два числа и написать вместо них остаток от деления суммы этих чисел на 11 . После 124 таких операций на доске осталось одно число. Какое это число?

7.Первый член последовательности равен 1 , а каждый следующий, начиная со второго, получается прибавлением к предыдущему члену суммы его цифр. Может ли в этой последовательности встретиться число 765432?

8.Круг разбит на 6 равных секторов, в каждом из которых стоит по одной шашке. Одним ходом разрешается любые две шашки передвинуть в соседние секторы , причем так, чтобы одна шашка двигалась по часовой стрелке, а другая – против. Можно ли за несколько таких ходов собрать все шашки в одном секторе.

9.Круг разбит на 6 равных секторов, в которых расставлены цифры 0, 1, 2, 0, 2, 1 ( в указанном порядке ). Разрешается за один ход одновременно прибавлять одно и то же число к двум стоящим рядом числам. Можно ли за несколько таких ходов добиться того, чтобы все 6 чисел, стоящие в секторах были равны?

Решение.

Пусть на некотором шага в секторах оказались в последовательном порядке числа а1, а2, а3, а4, а5, а6. Составим такую сумму : S = а1 – а2 + а3 – а4 + а5 – а6 .

После каждого хода она не меняется, так как каждая из разновидностей а1 – а2 , а3 – а4 , а5 – а6 при увеличении уменьшаемого и вычитаемого на одно и то же число сохраняет свое значение; следовательно, она является инвариантом . Но в начальном положении S = 0 – 1 + 2 – 0 + 2 – 1 = 2 , а в конечном , когда каждое из шести чисел равно одному и тому же числу , S = 0. Поэтому сделать равными все шесть чисел нельзя.

Ответ : нельзя.

10.В вершинах выпуклого шестиугольника записаны числа 8, 3, 12, 1, 10, 6 (в указанном порядке). За один ход разрешается к4 любым двум числам в соседних вершинах прибавить одно и то же число. Можно ли за несколько таких ходов получить в последовательном порядке шестёрку чисел 5, 2, 14, 6, 13, 4?

11.Даны четыре числа 3, 4, 5, 6. За один ход разрешается написать четыре новых числа, заменив каждое из исходных чисел средним арифметическим трех других. Докажите, что за несколько таких ходов нельзя получить набор 1, 3, 5, 8.

12.В каждой клетке доски 5 х 5 сидит жук. В некоторый момент все жуки переползают на соседние (по горизонтали или вертикали) клетки . Докажите , что после этого останется по крайней мере одна пустая клетка .

13. На чудо-яблоне растут бананы и ананасы. За один раз разрешается сорвать с нее два плода. Если сорвать два банана или два ананаса, то вырастет еще один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Какой это плод, если известно, сколько бананов и ананасов росло вначале?

Решение.

Четность числа бананов не меняется, если число бананов было четным, то оставшийся плод ананас, если число бананов было нечетным, то – банан.

14. На прямой стоят две фишки: слева красная, справа синяя. Разрешается производить любую из двух операций: вставку двух фишек одного цвета подряд (между фишками или с краю) и удаление пары соседних одноцветных фишек (между которыми нет других фишек). Можно ли с помощью таких операций оставить на прямой ровно две фишки: слева синюю, а справа красную?

Решение.

Рассмотрим число разноцветных пар (не только соседних), где левая фишка красная, и заметим, что четность этого показателя не меняется. Но в исходной ситуации наш показатель равен 1, а в желаемой ситуации - нулю. Поэтому перейти к желаемой ситуации невозможно.

15. На острове Серобуромалин живут хамелеоны: 13 серых, 15 бурых и 17 малиновых. Если 2 хамелеона разных цветов встречаются, то они оба меняют свой цвет на третий. Может ли случиться, что в некоторый момент все хамелеоны на острове станут одного цвета?

Указание.

Рассмотрите остатки от деления чисел Б бурых, С серых и М малиновых хамелеонов на 3 и проверьте, что попарные разности у этих остатков не меняются.

16. Докажите, что в игре «15» нельзя поменять местами фишки «15» и «14», оставив остальные на месте.

Идея решения.

Рассмотрим «пустое поле» как отдельную фишку. Мы можем только менять «пустую фишку» с соседними. Поскольку пустая фишка должна попасть на исходное поле, число наших операций должно быть четным. Поэтому мы можем получить конфигурации, отличающиеся от начальной только четным числом перестановок.

17. На 44 деревьях, расположенных по кругу, сидели по веселому чижу. Время от времени какие-то два чижа перелетают на соседнее дерево - один по часовой стрелке, а другой - против. Могут ли все чижи собраться на одном дереве?

Решение.

Пронумеруем деревья по кругу с 1-го по 44-е. Сумма номеров деревьев, на которых сидят чижи либо не меняется, либо уменьшается на 44, либо увеличивается на 44. Тем самым, остаток от деления этой суммы номеров на 44 не меняется. Изначально этот остаток равен 22, а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому чижи не смогут собраться на одном дереве.

18. Можно ли разрезать выпуклый 17-угольник на 14 треугольников?

Общая постановка задачи.

При помощи инвариантов решаются задачи следующего типа: даны мно­жество М (элементы его мы будем называть «позициями») и правило, по которому разрешается переходить от одной позиции к другой; можно ли из данной позиции а перейти за не­сколько шагов в другую данную пози­цию p? Более общая задача: как. для произвольной пары позиций а, p уста­новить, можно ли из а за несколько шагов перейти в р?

Очевидно, описанные ситуации об­ладают следующим свойством: если из позиции a можно перейти в пози­цию р и из p можно перейти в пози­цию h, то из a можно перейти в h. Это свойство называется транзитив­ностью.

Рассмотрим конкретную задачу.

Задача 1. Круг разделен на n секторов, в которых как-то расстав­лены n фишек. Разрешается одно­временно передвинуть любые две фиш­ки: одну — на один сектор по часовой стрелке, другую — на один сектор в противоположном направлении. Мож­но ли из позиции M, в которой в каж­дом секторе стоит' по одной фишке, перейти к позиции V, в которой все фишки собраны в каком-нибудь од­ном секторе?

В данной задаче, кроме свойства транзитивности, имеет место также следующее важное свойство: если из позиции a можно перейти в пози­цию р, то и из р можно перейти в a. Это свойство называется симмет­ричностью.

Свойство симметричности соблю­дается не во всех задачах рассмат­риваемого типа; например, в шах­матах пешки назад не ходят. В этой статье мы ограничимся задачами, для которых условие симметричности выполнено.

Условимся считать, что из любой позиции a можно «перейти» в нее же. Это свойство называется рефлексив­ностью.

Назовем позиции a и p эквива­лентными, если по заданным прави­лам из a можно перейти в p (ввиду предположенной симметричности это равносильно тому, что из p можно пе­рейти в a). Эквивалентность позиций a и p мы будем обозначать так: a~ p; неэквивалентность — так: a ~/ p.

Поскольку эквивалентность позиций рефлексивна, симметрична и транзитивна, исходное множество М разбивается на непустые непересекающиеся подмножества (рис. 1): М = M1UM2UM3U... В каждом из подмножеств Mi, все позиции экви­валентны: если a из Мi, и p из Mi, то a~ p. Если же позиции a и p принадлежат разным подмножест­вам: a из Mi p из Mj ( i отлично от j ), то a и p не эквивалентны ). Подмножества Мi мы будем называть орбитами. Повторим еще раз: если мы находимся в позиции a, принадлежащей какой-нибудь орбите Mi, то мы можем, перемещаясь по этой орбите, пере­браться из позиции a в любую другую позицию, принадлежащую орбите. С другой стороны, сойти с этой орбиты, т. е. перебраться с по­зиции a на позицию p, принадлежа­щую любой другой орбите, мы не можем. Орбит может быть как конечное, так и бесконечное число. Впрочем, если множество М конечно, то, ра­зумеется, и число орбит конечно. Инвариант. Числовая функция f, определенная на множестве «позиций» M, назы­вается инвариантной функцией, или инвариантом, если на эквивалент­ных позициях она принимает одина­ковые значения: если a~ р, то f(а) = f(р). (1)

Задача 1 (продолжение). Пусть п = 2т. Раскрасим секторы через один в серый и белый цвет. Тогда при каждом перемещении число фишек в белых секторах либо не меняется (рис. 2), либо увеличи­вается на 2 (рис. 3), либо умень­шается на 2 (рис. 4). Для произвольной расстановки a фишек по секторам обозначим через б (а) число фишек в белых секторах. Рассмотрим теперь такую функцию g.

0, если б (a) четно,

g(a) =

1, если б (a) нечетно.

Из сказанного выше вытекает, что эта функция g (четность числа фишек в белых секторах) является инвариан­том. Поскольку п = 2т, для конеч­ной позиции v имеем g(v) = 0. Если т = 2k+ 1, то n/2 нечетно. Значит, для начальной позиции w имеем g(w) =1. Из того, что g(w) отлично от g(v) вытекает, что позиции w и v не эквивалентны. Таким образом, в этом случае

(п = 2 т, т = 2 k + 1) из позиции w нельзя перейти в пози­цию v. Ну, а если т =2 k? Тогда n/2 четно и g(w) = g(v) = 0. В этом случае инвариант g не дает возможности установить эквивалентны позиции w и v или нет.

Дело в том, что если f - инвариант, то из f(a.) = f(p), вообще говоря, ничего не вытекает. Если f(a) отлично от f(p) то позиции а и p не эквивалентны (это следует из (1)). Если же f(a) = f(p), то позиции а и р могут быть как эквивалентными, так и не эквива­лентными: инварианту не запрещается на разных орбитах принимать одинаковые зна­чения. (Например, постоянная функция, т. е. функция, которая на всех элементах из М принимает одно и то же значение, тоже инвариантна.)

Как же быть? Попробуйте для какого-нибудь п вида 4k перейти от позиции w, к позиции v... Почему-то не удается. Попробуем Найти другой , более тонкий инвариант.

Занумеруем секторы (скажем, по часовой стрелке) от 1 до n. Для про­извольной расстановки а.фишек по секторам обозначим через xk (а) количество фишек в k-м секторе при расстановке a.

Рассмотрим теперь такую функцию q:

q (a)= 1 x1 (a) + 2 x2 (a) +3x3(a) +

+ ... + n xn(a). (2)

Является ли функция q инвариантом?

Произвольное допустимое переме­щение (рис. 5) затрагивает 4 слагае­мых суммы (2):

... + i xi (a) + (i + 1) xi+1 (a) + ...+ (j - 1) xj -1(a) + j x j(a)+ … (3)

При перемещении , изображенном

... + i [xi(a) - 1] + (i + 1) [xi+1(a) + 1]+

+…+(j – 1) [xj-1(a) + 1] + j [x j (a) - 1] +…

Легко проверяется, что обе суммы равны. Итак, q - инвариант! Нет,

мы забыли, что n-й сектор граничит с первым. Значит, есть еще 3 возмож­ности. Подсчет, аналогич­ный только что сделанному, показы­вает, что в случае, изображенном на рис. 6, q (a) уменьшится на п, а в случае увеличится на п. В третьем случае q (а), конечно, не изменится. Итак, за одно переме­щение значение функции q может измениться, но только на п. Следовательно, функция r, значение которой на расстановке a равно остатку. от деления числа q (a) на п, есть ин­вариант.

Для позиции v (если все п фишек собраны в 1-м секторе)

x1(v) = x2(v) =…= xl -1(v) = xl+1(v) = …=xn (v) = 0,

xl(v) = n.

Значит, q (v) = l n и r (v) = 0 (каковы бы ни были п и l ). С другой стороны,

x1(w) = x2(w) =…= xn(w) = 1. Значит, q(w) = 1 + 2 + 3 +…+ n = (n(n+1))/2

Если n = 2m, то q(w) = nm + m и r(w) = т =/0 . Сле­довательно, при четном п получаем r(w) =/ r(v). Итак, при четном п по­зиции w и v не эквивалентны.

Если же п = 2т + 1, то q(w) = n(m + 1) и r(w) = 0. Таким образом, при нечетном п мы опять имеем: r (и) — r (v). Получается, что при нечетном п вопрос об эквива­лентности позиций w и v снова остается открытым.

Универсальный инвариант

Назовем инвариант f универсальным, если на неэквивалентных позициях он принимает различные значения: если a ~/ p, то f(a) №f(p) . Таким образом, для универсаль­ного инварианта f: если f(a) = f (р), то a ~ р.

Универсальный инвариант на каждой орбите принимает свое значение. По­скольку для универсального инва­рианта a~p Ы f(a) = f(p), универсальный инвариант для любой пары позиций позволяет установить, эквивалентны ояи или нет.

Как проверить, что некоторый ин­вариант f универсален? Общего мето­да не существует. Иногда может по­мочь следующая простая

Теорема. Если а) существуют такие l позиций б1, б2, ..., бl, что каждая позиция a из М эквивалентна одной из них и b) инвариант f при­нимает, по крайней мере, l различ­ных- значений, то f—универсальный инвариант и позиции бi, бj (i=/j) noпарно не эквивалентны.

Из а) вытекает, что существует не более l орбит. Из b) вытекает, что существует не менее l орбит. Следо­вательно, существует ровно l орбит. Снова из b) вытекает теперь, что ин­вариант f принимает ровно l значе­ний и, значит, f универсален. Нако­нец, из а) вытекает, что позиции б1, б2, ..., бl принадлежат разным ор­битам и, таким образом, попарно не эквивалентны.

Задача 1 (окончание). Дока­жем, что инвариант r универсален. Обозначим через бi, такую расстанов­ку фишек: одна фишка — в i-м сек­торе, все остальные — в п-м секторе. Под бn мы будем, разумеется, пони­мать расстановку, при которой все n фишек — в n-м секторе.

Легко сообразить, что любая рас­становка эквивалентна одной из по­зиций б1, б2, ... , бn. В самом деле, пусть a — произвольная расстановка фишек. Попытаемся собрать все п фишек в n-м секторе. Для этого бу­дем передвигать первую фишку, пока не загоним ее в п-ый сектор; од­новременно, в соответствии с прави­лами, мы будем перемещать вторую фишку в противоположную сторону. Затем загоним в n-й сектор вторую фишку, двигая в противоположную сторону третью фишку, и так далее — вплоть до (п— 1)-й фишки. Когда мы загоним п — 1 фишек в n-й сек­тор, п-я фишка будет в каком-то i-м секторе (i = 1, 2, ... , п). Это и озна­чает, что a~ бi.

Посчитаем r(бi). При i не равном п:

x1(бi) == x2(бi) = …= x i - 1(бi) = x i+1 (бi) =...= xn-1(бi)=0,

xi(бi)=1,

xn(бi)-=n - 1.

Следовательно, q (бi) -= i l + п (п— 1) и r (бi) = i. Кроме того, q(бn) = nn и r(бn) = 0. Итак, инвариант r принимает по крайней мере п значений.

По теореме инвариант r универ­сален и позиции б1, б2, ... , бn попарно не эквивалентны.

Поскольку r — универсальный инвариант, a ~ р Ы r(а) = r(р).

В предыдущем параграфе мы посчи­тали, что r(w) = r(v) Ы n-нечетное. Следовательно, w ~ v ,тогда и толь­ко тогда, когда п — нечетное. Зада­ча, наконец, решена полностью.

Задачи

1.19. Докажите, не используя понятия инварианта, что при не­четном п позиции w и v эквиваленты.

1.20. Проверьте, что любая функция от инварианта снова является инвариантом: если f — инвариант и g — произвольная числовая функция, то и функ­ция h : h(a) = g(f(a)) (4) тоже инвариантна.

1.21.Докажите, что любой инвариант можно представить в виде функции от любого универсального инвариан­та: если h — инвариант, a f — универсаль­ный инвариант, то существует такая число­вая функция g, что выполняется (4).

1.22.Определим через универсальный инвариант r из задачи 1 два новых инварианта: f(a) = [r(a)]2; g(a) = [r(а) - 2]2. Докажите, что инвариант f универсален, а инвариант g не универсален.

1.23. Пусть f - уни­версальный инвариант. Каким условиям должна удовлетворять числовая функция g, чтобы инвариант h, определенный равенст­вом (4), был универсальным?

Задача 2. Даны 20 карточек. На двух карточках написана цифра 0, на двух — цифра 1, ... , на двух последних — цифра 9. Можно ли расположить эти карточки в ряд так, чтобы карточки с 0 лежали ря­дом, между карточками с 1 лежала ровно одна карточка, ... , между кар­точками с 9 лежало ровно 9 карточек?

Эту задачу можно решить без вся­ких инвариантов. Однако для нас она интересна тем, что у нее есть два принципиально разных решения, ис­пользующих инварианты.

Представим себе 20 ящиков, рас­положенных в ряд. Переформули­руем теперь нашу задачу следующим образом: можно ли расположить карточки по ящикам так, чтобы вы­полнялись два условия:

a) карточки с 0 лежат в соседних ящиках, карточки с 1 — через один ящик, ... , карточки с 9— через де­вять ящиков;

b) в каждом ящике лежит по од­ной карточке?

Очевидно, порознь выполнить каж­дое из условий очень легко. Это и приводит к двум решениям.

Первое решение. Поло­жим в первый ящик 10 карточек:

Одну - с 0, одну - с 1, ... , одну - с 9. Затем вторую карточку с 0 по­ложим во второй ящик, вторую кар­точку с 1 - в третий ящик, .... вто­рую карточку с 9 — в одинадцатый ящик. Условие а) выполняется. Мы хотим попытаться, не нарушая его, так переложить карточки, чтобы ус­ловие b) тоже выполнялось. Разре­шим перекладывать любые две «одно­именные» (с одной и той же цифрой) карточки через одинаковое число ящиков. Нетрудно заметить, что при произвольном разрешенном пере­мещении сдвиг в сумме происходит на четное число ящиков. Это подска­зывает идею взять в качестве инва­рианта остаток от деления на 2 суммы номеров ящиков, в которых лежат карточки.

Задачи

1.24. Закончить наме­ченное решение.

Второе решение. Поло­жим в первый и второй ящики карточ­ки с 0, в третий и четвертый - кар­точки с 1, ... , в девятнадцатый и двадцатый - карточки с 9. На этот раз выполнено условие b). Разрешим менять местами любые две карточки. При таком перемещении расстояние между восемью парами «одноименных» карточек не меняется, между дву­мя - меняется; таким образом, сум­ма всех этих расстояний...

Полная система инвариантов

Иногда вместо универсального ин­варианта проще найти и использовать полную систему инвариантов. Систе­ма инвариантов <f1, f2, f3> на­зывается полной, если равенства,

f1(a) = f1(p),

f2(a) = f2(p), (5)

fk(a) = fk(p).

имеют место одновременно тогда и только тогда, когда позиции a и p эквивалентны.

В чем суть этого определения? Если позиции a и p эквивалентны, то, поскольку f1, f2,…, fk - инварианты, каждое из равенств системы (5) все равно выполняется. «В эту сторону» полнота еще ни при чем. Если бы инварианты f1, f2,…, fk были уни­версальными, то эквивалентность позиций пир вытекала бы из любого равенства систе­мы (5). Нам не дана их универсальность, но зато требуется, чтобы одновремен­ное выполнение равенств системы (5) влекло эквивалентность позиций a и p . Именно в этом суть понятия полноты. Та­ким образом, хотя некоторые из инвариантов f1, f2,…, fk могут на неэквивалентных по­зициях a и p принимать одинаковое значение , значение набора

< f1, f2,…, fk > на них различны.

Полная система инвариантов — это обобщение понятия универсаль­ного инварианта: если f - универ­сальный инвариант, то система <f>, состоящая из одного инварианта, ко­нечно, полна.

Задача 3. В таблице 2х2 записываются целые числа. Разре­шается, во-первых, в любом столбце одновременно: к одному числу приба­вить 2, из другого — вычесть 2 и, во-вторых, в любой строке одновре­менно: к одному числу прибавить 3, из другого — вычесть 3. Какие таб­лицы эквивалентны?

Рассмотрим три функции: для лю­бой таблицы

a= a b

c d

обозначим через g(a) сумму а + b + с + d, через q (a) - остаток от деления числа а + b на 2 и через r (а) — остаток от деления числа а + с на 3. Функции g, q, r являются инвариантами. Не очень трудно до­казать, что произвольная таблица a эквивалентна таблице

0 q(a)

r(a) g(a)—q(a)—r(a)

Следовательно, из равенств

g(a) = g(p),

q(a) = q(p),

r(a) = r(p).

вытекает что таблицы a и р эквива­лентны одной и той же таблице и, значит, эквивалентны между собой. И обратно: эквивалентность таблиц a и р влечет равенства (6), поскольку g, q и r—инварианты. Таким обра­зом, <g, q, r> - полная система.

Задачи.

1.26. Решите задачу для таблиц n x n, в которых разрешаются те же преобразования, что и в задаче 3. Естественно ожидать полную систему из 2n- -1 инвариантов.

1.27. Если f1, f2, fk - инварианты и g — числовая функция от k аргументов, то функция h: h(a) = g(f1(a), f2(a),..., fk(a)) (7) является инвариантом (ср. с упражнением 2). Проверьте.

1.28.Если h — инва­риант, a <f1, f2,…, fk> - полная систе­ма инвариантов, то существует такая число­вая функция g от k аргументов, что выпол­няется (7) (ср. с упражнением 3). Докажите.

1.29. Множество М — множество точек числовой плоскости, то есть множество пар <х, у> действительных чисел. Единственный допустимый переход: <x, y>а <y, x>. Пусть

f1(x, y) = xy ,

f2(x, y) = x + y.

Доказать, что <f1, f2> - полная система инвариантов.

1.30. Множество М — множество точек пространства или множество троек <x, y, z> действительных чисел. Раз­решены переходы

< x, y, z >а <y, x, z > и <x, y, z >а < x, z, y >. Пусть

f1( x, y, z ) = xyz,

f2 (x, y, z) = ху + уz + zх,

f3(x, y, z ) = х + у + z.

Доказать, что <f1, f2, f3> — полная система инвариантов.

1.31. Множество М состоит из всевозможных наборов (или кор­тежей) <х1, x2, x3, …, xn> действительных чисел (n фиксировано). Разрешается менять местами любые два соседних числа. Найти полную систему инвариантов.

В отличие от задач 1 — 3, которые были просто задачами олимпиадного типа, упражнения 11—13 играют важ­ную роль в алгебре многочленов. Ин­варианты в них интересны не для ре­шения вопроса об эквивалентности (который ясен и без них), а сами по себе — как полезные функции.

1.32.Даны розетка с п дырками и элект­ронная лампа с n штырями. Дырки зануме­рованы от 1 до n (рис. 9). Можно ли зануме­ровать штыри от 1 до n так, чтобы при любом включении в розетку один из штырей попадал в дырку со своим номером?

1.33. Многие знают «игру в 15»: в коробоч­ке 4x4 лежат 15 шашек с номерами от 1 до 15; разрешается за один ход передвинуть в пустую клетку одну из шашек, соседних с ней. Можно ли превратить положение a в положение p (рис. 10)? Найдите для этой игры универсальный инвариант.

1	2	3	4		1	2	3	4
5	6	7	8		5	6	7	8
9	10	11	12		9	10	11	12
13	14	15			13	15	14

а p

1.34. На клетчатой доске 11x11 отмечено 22 клетки так, что на каждой вертикали и на каждой горизонтали отмечено ровно 2 клетки. Два расположения отмеченных кле­ток эквивалентны, если, меняя любое число раз вертикали между собой и горизонтали между собой, мы из одного расположения можем получить другое. Сколько существует неэквивалентных расположении отмеченных клеток?

1.35. Испанский король решил перевесить по-своему портреты своих предшественников в круглой башне замка. Однако он хочет, чтобы за один раз меняли местами только два портрета, висящих рядом, причем это не должны быть портреты королей, один из которых царствовал сразу после другого. Кроме того, ему важно лишь взаимное расположение портретов, и два расположе­ния, отличающиеся поворотом круга, он считает одинаковыми. Доказать, что, как бы сначала ни висели портреты, король может по этим правилам добиться любого нового их расположения.

1.36. Все целые числа от 1 до 2n выписаны в строчку. Затем к каждому числу прибавили номер того места, на котором оно стоит. Доказать, что среди полученных сумм най­дутся хотя бы две, дающие при делении на 2n одинаковый остаток.

1.37. Вернемся к задаче 1 с фишками в круге и разрешим теперь двигать две фишки как в разные стороны, так и в одну сторону. Найти для этой задачи универсальный ин­вариант.

1.38. В таблице 3x3 расставлены числа +1 и -1. Разрешается менять знак одновре­менно у всех элементов строки или столбца. Докажите, что:

a) число орбит равно 16;

b) каждая орбита содержит ровно 32 элемента;

c) произведение всех чисел любого квад­рата 2x2 в таблице является инвариантом;

d) произведения чисел в четырех квадра­тах, указанных на рисунке 11, образуют пол­ную систему инвариантов.

Решать эти задачи можно в любом поряд­ке; ясно, что одни помогают другим.

ґ		ґ		ґ		ґ
ґ		ґ
				ґ		ґ

	ґ	ґ			ґ	ґ
	ґ	ґ
					ґ	ґ

1.39. Вектор <а, b>, где a, b—целые числа, разрешается заменять одним из векто­ров <а + b, b>, <a—b, b>, <b, a>. Найти универсальный инвариант.

1.40. Пару векторов <а, b>, <с, d>, где а, b, с, d — целые числа, разрешается заме­нять на одну из пар <а+b, b>, <c+d, d>; <a - b, b>, <c – d, d>; <b, a>, <d, c>. Найти полную систему инвариантов.

2.Четность плюс инвариант

2.1.На доске написаны натуральные числа 1, 2, 3,…, 100. Разрешается стереть любые два числа и записать модуль их разности, после чего колличество написанных чисел уменьшается на 1. Может ли после 99 таких операций остаться записанным на доске число 1 ?

Решение .

Подсчитаем общую сумму начальных 100 чисел :

1 + 2 + 3 + …+ 100 = 5050.

Эта сумма оказалась четной . Переходя к следующему набору чисел , мы фактически в этой сумме заменяли сумму двух чисел на их разность. Но сумма и разность двух целых чисел имеют одинаковую четность, поэтому общая сумма записанных чисел останется четной. Следовательно , эта сумма равной 1 быть не может.

О т в е т : не может.

2.2. На доске написаны 8 плюсов и 11 минусов . Разрешается стереть любые два знака и написать вместо них плюс , если они одинаковы, и минус если они различны. Какой знак останется на доске после 18 таких операций?

2.3.На главной диагонали шашечной доски 10 на 10 стоят 10 шашек, все в разных клетках. За один ход разрешается выбрать любую пару шашек и передвинуть каждую из них на одну клетку вниз. Можно ли за несколько таких ходов поставить все шашки на нижнюю горизонталь?

2.4. На столе стоят вверх дном 7 стаканов. Разрешается за один раз перевернуть любые 4 стакана. Можно ли через несколько шагов поставить все стаканы в нормальное положение?

Решение.

Поставим в соответствии стакану, стоящему нормально, +1, а стоящему вверх дном, - 1. Инвариантом здесь будет произведение чисел, соответствующих всем 7 стаканам, так как при изменении знака у 4 сомножителей произведение не меняется. Но в начальном положении это произведение равно -1, а значит, стать +1 оно никогда не сможет.

2.5. На столе стоят 7 перевернутых стаканов. Разрешается одновременно переворачивать любые два стакана. Можно ли добиться того, чтобы все стаканы стояли правильно?

2.6. На столе стоят вверх дном 9 стаканов. Разрешается за один раз перевернуть любые 4 стакана . Можно ли за несколько таких ходов поставить все стаканы в нормальное положение?

2.7.Три кузнечика играют в чехарду : если кузнечик из точки А прыгает через кузнечика , находящегося в точке В , то он окажется в точке С , симметричной точке А относительно точки В. В исходном положении кузнечики занимают три вершины квадрата. Могут ли они ,играя в чехарду, попасть в четвертую его вершину?

Решение.

Введем на плоскости систему координат так, чтобы три вершины квадрата, в которых находятся кузнечики, имели координаты (0; 0),

(0; 1) и (1; 0). При указанных прыжках каждая из координат кузнечиков или остается неизменной, или изменяется в ту или иную сторону на четное число (рис 12) х

Так как в начальном положении

по меньшей мере одна из координат каждой из трех точек

четна , то она при прыжках останется четной: четность хо

тя бы одной из двух каждой из точек есть инвариант.

Поэтому попасть в М один из кузнечиков

не может Ответ: не может.

2.8.Имеется 30 карточек, каждая из которых выкрашена с одной стороны в красный, а с другой – в синий цвет. Карточки разложили подряд в виде полосы так, что у 8 карточек сверху оказался синий цвет. За один разрешается перевернуть любые 17 карточек. Можно ли за несколько ходов добиться того, чтобы полоса стала полностью: а) красной; б) синей?

Задача 1: На доске написано де­сять плюсов и пятнадцать минусов. Разрешается стереть любые два зна­ка и написать вместо них плюс, если они одинаковы, и минус в противном случае. Какой знак останется, на дос­ке после выполнения двадцати четырех таких операций.

Решение.

Заменим каждый плюс числом 1, а каждый минус чис­лом —1. Разрешенная операция опи­сывается тогда так: стираются любые два числа и записывается их произве­дение. Поэтому произведение всех написанных на доске чисел остается неизменным. Так как вначале это произведение равнялось —1, то и в конце останется число —1, то есть знак минус.

Это рассуждение можно было про­вести иначе. Заменим все плюсы ну­лями, а минусы—единицами, и за­метим, что сумма двух стираемых чи­сел имеет ту же четность, что и число, записываемое вместо них. Так как

сначала сумма всех чисел была нечет­ной (она равнялась 15), то и последнее оставшееся на доске число будет не­четным, то есть единицей, и, значит, на доске останется минус.

Наконец, третье решение задачи можно получить, заметив, что в ре­зультате каждой операции число ми­нусов либо не изменяется, либо умень­шается на два. Поскольку сначала число минусов было нечетным, то и в конце останется один минус.

Проанализируем все три решения.

Первое решение основывалось на неизменяемости произведения на­писанных чисел, второе—на неизменяе­мости четности их суммы и третье — на неизменяемости четности числа минусов. В каждом решении нам уда­лось найти инвариант: произведение написанных чисел, четность суммы, четность числа минусов. Решение последующих задач также основывается на удачном под­боре инварианта.

2.9. На доске напи­сано несколько плюсов и минусов. Разре­шается стереть любые два знака и написать вместо них плюс, если они различны, и ми­нус в противном случае. Докажите, что по­следний оставшийся на доске знак не зависит от порядка, в котором производились сти­рания.

2.10. В таблице 4х4 знаки «+» и «—» расставлены так, как показано на рисунке 13. Разрешает­ся изменить знак на противополож­ный одновременно во всех клетках, расположенных в одной строке, в одном столбце или вдоль прямой, параллельной какой-нибудь из диаго­налей (в частности, в любой угловой клетке). Можно ли с помощью этих операций получить таблицу, не со­держащую ни одного минуса?

Решение.

Заменим плюсы и минусы числами 1 и –1. В качестве инварианта можно взять произведение чисел, находящихся в клетках, которые заштрихованы на рисунке 14, поскольку оно в результате

разре­шенной операции все время сохраняет первоначальное значение, равное -1. Но, значит, среди заштрихованных чисел всегда будет оставаться -1, следовательно, получить таблицу, не содержащую ни одного минуса, нель­зя.

2.11.Решите задачу 2 для таблиц, изображенных на рисунках 15 - 17.

2.12. На доске написано несколько нулей, единиц и двоек. Раз­решается стереть две неравные цифры и вместо них написать одну цифру, отличную от стертых (2 вместо 0 и 1, 1 вместо 0 и 2, 0 вместо -1 и 2). Докажите, что если в результате нескольких таких операций на доске останется одна-единственная цифра, то она не зависит от порядка, в ко­тором производились стирания.

Решение.

Обозначим через х0, х1, х2 число нулей, единиц и двоек соответственно. Выполнив один раз разрешенную операцию, мы изменим каждое из этих чисел на 1 и, следова­тельно, изменим четность всех трех чисел. Когда на доске остается одна цифра, два из чисел х0, x1, х2 ста­новятся равными нулю, а .третье — единице. Значит, с самого начала два из этих чисел имеют одну четность, а третье—другую. Поэтому незави­симо от того, в каком порядке произ­водятся стирания, в конце единице может равняться лишь одно из чисел х0, х1, x.2, которое с самого начала имело не ту четность, что два других.

Из приведенного решения видно, что если числа х0, х1, х2 имеют одну и ту же четность, то мы не сможем добиться, чтобы на доске осталась одна-единственная цифра. Докажите, что если среди чисел х0, х1 х2 есть как четные, так и нечетные, и, кроме того, хотя бы два из них отличны от нуля, то существует такой порядок стираний, что в результате на доске останется' одна цифра.

Изменим условие задачи 3: по­требуем, .чтобы одни и те же две нерав­ные цифры стирались два раза, а вместо них записывалась одна цифра, отличная от стертых. Предположим, что снова после некоторого числа опе­рации на доске осталась одна-единственная цифра. Можно ли зара­нее, по числу нулей, единиц и двоек, предвидеть, какая это цифра?

Рассуждение с четностью здесь не помогает, ибо в результате выполне­ния каждой операции одно из чисел х0, х1, x2 меняет свою четность, а два других сохраняют четность, так что числа, имевшие разную четность, могут теперь получить одну и ту же четность. Однако можно заметить, что остатки от деления чисел х0, х1, х2 на 3 изменяются каждый раз таким образом, что равные остатки остаются равными, а неравные оста­ются неравными. Дальнейшие рас­суждения повторяют решение зада­чи 3.

2.13. В каждой клетке таблицы 8х8 написано некоторое целое число. Разрешается выбирать в таблице любой квадрат размерами 3х3 или 4х4 и увеличивать на еди­ницу все стоящие в клетках выбранно­го квадрата числа. Всегда ли можно с помощью таких операций преобразо­вать исходную таблицу в таблицу, у которой вес числа делятся на З?

Решение.

Нет, не всегда. Най­дем сумму чисел, написанных в за­штрихованных на рисунке 6 клетках. Поскольку любой квадрат размерами 4х4 содержит 12 заштрихованных клеток, а квадрат размерами 3х3— 6 или 9 таких клеток, то в результате описанной операции остаток от деле­ния на 3 этой суммы (чисел, стоящих в заштрихованных клетках) не будет меняться. Поэтому, если с самого на­чала найденная сумма не делится на 3, то среди заштрихованных клеток все время будут сохраняться клетки, в которых написанные числа не крат­ны трем.

2.14.Из всякой ли таблицы можно в условиях задачи 4 получить таблицу, не содержащую четных чисел?

2.15.Числа I, 2, 3, ...., n расположены в некотором порядке. Разрешается менять местами любые два рядом стоящих числа. Докажите, что если проделать нечетное число таких операций, то наверняка полу­чится отличное от первоначального расположения чисел 1, 2, 3, ...,n.

Решение.

Пусть a1, a2,…, an— произвольная перестановка из чисел 1, 2, 3, ..., п. Будем говорить, что числа аi, и аj, образуют в этой перестановке инверсию, если i<j, но ai>aj, то есть большее из этих чисел предшествует меньшему. Поменяв ме­стами два соседних числа в переста­новке, мы увеличим или уменьшим число инверсий на 1. Проделав же не­четное число таких операций, мы из­меним четность числа инверсий, а значит, изменим и перестановку.

2.16.Докажите, что утверждение задачи 2.15 останется справедли­вым, если разрешить менять местами любые два числа в перестановке.

Указание.

Докажите, что любые два чис­ла можно поменять местами, проделав нечетное число раз операцию, описанную в задаче 2.12.

Переход от одной перестановки чисел 1, 2, 3, .... п к другой переста­новке этих чисел, при котором какие-нибудь два числа меняются местами, а остальные остаются на месте, называется транспозицией. Результат задачи 2.16 можно сформулировать так: выполнив нечетное число транс­позиций, мы изменим перестановку

2.17. В различных пунк­тах кольцевого автодрома в одно и то же время в одном направлении старто­вали 25 автомобилей. По правилам гонки автомобили могут обгонять друг друга, но при этом запрещен двойной обгон. Автомобили финиши­ровали одновременно в тех же пунктах, что и стартовали. Докажите, что во время гонки было четное число обгонов.

Решение.

Окрасим один из автомобилей в желтый цвет, а остальным автомобилям присвоим номера 1, 2, 3, ..., 24 в том порядке, в каком они располагаются на старте за жел­тым автомобилем. В центре автодро­ма установим световое табло, на кото­ром после каждого обгона будем ука­зывать номера автомобилей в том по­рядке, в каком они следуют за жел­тым автомобилем. Тогда обгон, в котором не участвует желтый авто­мобиль, приводит к тому, что на све­товом табло меняются местами два соседних числа.

Посмотрим, что произойдет, если какой-нибудь автомобиль обгонит желтый. Если перед этим обгоном числа на табло образовывали переста­новку а1, а2,…, а24 , то после об­гона они образуют перестановку а2, а3,…, а24, а1. Заметим, что к такой же перестановке можно прийти, вы­полнив последовательно 23 транспо­зиции: а1, а2, а3,…, а24 а а2, а1, а3,…, а24 а а2, а3, а1,…, а24 а а2, а3, а1,…, а24 а… а а2, а3,…,а1, а24 а а2, а3,…, а24, а1

Если же желтый автомобиль со­вершил обгон, то из перестановки а1, а2, ..., а24 получим пере­становку а24, а1, а2, а3,…, а23. Этот переход также можно заменить двадцатью тремя транспозициями.

Таким образом, любой обгон сводится к нечетному числу транспо­зиций. Если бы общее число обгонов было нечетным, то нечетным оказалось бы и общее число транспозиций. Ос­тается воспользоваться результатом задачи 2.16.

3. Графы

Графом на плоскости называется конечное множество точек плоскости, некоторые из которых соединены линиями. Эти точки называются вершинами графа, а соединяющие их линии – ребрами. Число ребер, исходящих из вершины графа, называется степенью этой вершины.

С графами мы встречаемся чаще , чем это, возможно, кажется на первый взгляд. Примерами графа может служить любая карта дорог, электросхема, чертеж многоугольника и т. д.

Теория графов возникла в 1736 г., когда Леонард Эйлер опубликовал первую статью о графах. Начиналась она с разбора широко известной теперь задачи о кенигсбергских мостах. Долгое время считалось, что теория графов применяется главным образом для решения логических задач, а сама теория рассматривалась как часть геометрии. Однако в ХХ веке были найдены широкие приложения теории графов в экономике, биологии, химии, электронике, сетевом планировании, комбинаторике и других областях науки и техники. В результате она стала бурно развиваться и превратилась в самостоятельную разветвленную теорию.

Задачи на соответствие между множествами .

3.1.В пяти корзинах А, Б, В, Г и Д лежат яблоки пяти разных сортов. В каждой из корзин А и Б находятся яблоки 3-го и 4-го сорта, в корзине В – 2-го и 3-го , в корзине Г – 4-го и 5-го, в корзине Д – 1-го и 5-го. Занумеруйте корзины так, чтобы в корзине №1 имелись яблоки 1-го сорта ( по меньшей мере одно ), в корзине №2 – яблоки 2-го сорта и т. Д

Решение.

Изобразим два множества множество корзин и множество их номеров. В каждом из этих множеств по пять элементов обозначим их точками

Установим соответствие между этими двумя множествами так, чтобы условия задачи выполнялись. Будем соответствующие элементы двух множеств соединять сплошными линиями, а не соответствующие – пунктирными или совсем не соединять. Так как яблоки первого сорта лежат только в корзине Д, то именно этой корзине и нужно дать номер 1; проведем сплошную линию между точками Д и 1. Далее номер 2 можно присвоить только корзине В, а после этого номер 5 – лишь корзине Г. Наконец, номера 3 и 4 дадим корзинам А и Б ( в любом порядке ).

Ответ: корзины расположились, начиная с №1, в последовательном порядке Д, В, А, Б, Г или в порядке Д, В, Б, А, Г.

3.2. Петр, Геннадий, Алексей и Владимир занимаются в одной детской спортивной школе в разных секциях: гимнастики, легкой атлетики, волейбола и баскетбола. Петр, Алексей и волейболист учатся в одном классе. Петр и Геннадий на тренировки ходят пешком вместе, а гимнаст ездит на автобусе. Легкоатлет не знаком ни с волейболистом, ни с баскетболистом. Кто в какой секции занимается?

3.3.Футбольные команды пяти школ города учавствуют в розыгрыше кубка. В финал кубка выходят две команды. До соревнований пять болельщиков высказали прогнозы, что в финал выйдут команды:

1) Б и Г, 2) В и Д , 3) Б и В, 4) А и Г, 5) Г и Д.

Один прогноз оказался полностью неверным, в остальных была правильно названа только одна из команд-финалисток. Какие команды вышли в финал?

3.4. Три товарища – Владимир, Игорь и Сергей – окончили один и тот же педагогический институт и преподают математику, физику и литературу в школах Тулы, Рязани и Ярославля. Владимир работает не в Рязани, Игорь – не в Туле. Рязанец преподает не физику, Игорь – не математику, туляк преподает литературу. Какой предмет и в каком городе преподает каждый из них?

3.5. Среди офицеров А, Б, В и Г – майор, капитан и два лейтенанта. А и один из лейтенантов – танкисты, Б и капитан – артиллеристы, А младше по званию, чем В. Определите род войск и воинское звание каждого из них.

3.6. В стране Радонежии некоторые города связаны между собой авиалиниями. Из столицы выходит 1985 авиалиний, из города Дальнего одна, а из остальных городов - по 20 линий. Докажите, что из столицы можно добраться до Дальнего.

Решение.

Рассмотрим множество городов, до которых можно добраться из столицы. Это граф: его вершины - города, ребра - авиалинии, их соединяющие. Из каждой вершины графа выходит столько ребер, сколько всего авиалиний выходит из соответствующего города. Граф содержит нечетную вершину - столицу. Поскольку число нечетных вершин в графе четно, в нем есть еще одна нечетная вершина. Этой вершиной может быть только город Дальний.

Задачи, при решении которых используются вершины, стороны и диагонали многоугольника

3.7. Можно ли организовать футбольный турнир девяти команд так, чтобы каждая команда провела по четыре встречи?

Решение

Изобразим каждую команду точкой, а проведенную ею встречу – отрезком, исходящим из этой точки. Девять точек лучше расположить так, чтобы при последовательном соединении их отрезками образовался выпуклый девятиугольник.

Задача сводиться к следующей: можно ли девять точек соединить отрезками так, чтобы из каждой точки выходили четыре отрезка? Другими словами, существует ли граф с деятью вершинами, у которого степень каждой вершины равна 4?

Прежде всего проведем все стороны девятиугольника; они будут означать, что каждая команда провела две встречи.

Для того чтобы получить еще две встречи будем, например, соединять все вершины диагоналями через одну ( рис. 19 ). ( Целесообразно для всех держаться одной и той же системы проведения из них отрезков, иначе решение усложнится. ) После этого все получается.

Ответ: можно.

3.8. Можно ли провести футбольный турнир восьми команд так, чтобы каждая команда провела: а) по четыре встречи; б) по пять встреч

3.9. Можно ли провести футбольный турнир семи команд так, чтобы каждая команда провела по три встречи?

Решение.

Попытки решить эту задачу тем же методом, что и предыдущие задачи, приводят к неудаче. Возникает подозрение, что провести турнир таким образом нельзя.

Для того чтобы доказать нашу гипотезу, попробуем вместо рисунка подсчитать общее число встреч, которые надо провести командам. Оно равно 7 (3/2). Но это число не является целым.

Ответ: нельзя.

3.10. Докажите что общее число вершин графа, которые имеют нечетную степень четно.

3.11. В трех вершинах правильного пятиугольника расположили по фишке. Разрешается передвигать их по диагонали в любую свободную вершину. Можно ли таким образом добиться того, чтобы одна из фишек вернулась на свое место, а две другие поменялись местами?

3.12. Дан правильный 45-и угольник. Можно ли так расставить в его вершинах цифры от 0 до 9 так, чтобы для любой пары различных цифр нашлась сторона, концы которой занумерованы этими цифрами.

Указание.

Рассмотреть полный граф, вершины которого суть цифры от 0 до 9. Задача сводится к его обходу.

3.13. Докажите что общее число вершин графа, которые имеют нечетную степень четно.

Решение.

Обозначим число вершин графа, имеющих нечетную степень, через k, а степени таких вершин – соответственно через а1, а2,…, аk. Кроме того, у графа могут быть вершины с четной степенью; обозначим степени этих вершин соответственно через b1, b2,…, bn.

Допустим, что число k нечетно. Подсчитаем общее число ребер графа. Оно равно [(а1 + а2 +…+ аk) + (b1 + b2 +…+ bn)] /2.

Сумма в первых круглых скобках числителя полученной дроби есть число нечетное, как сумма нечетного числа нечетных слагаемых, а сумма во вторых скобках число четное. Но тогда весь числитель – число нечетное, а значит дробь не является натуральным числом. Мы пришли к противоречию.

3.14. Можно ли 15 телефонов соединить между собой так, чтобы каждый из них был связан ровно с 11 другими?

3.15. Девять школьников, разъезжаясь на каникулы, договорились, что каждый из них пошлет открытки пятерым из остальных. Может ли оказаться, что каждый из них получит открытки именно от тех друзей, которым напишет сам?

3.16. В шахматном турнире в один круг участвуют 17 шахматистов. Верно ли, что в любой момент турнира найдется шахматист, сыгравший к этому моменту четное число партий ( может быть ни одной )?

Задачи на обведение контура фигуры непрерывной линией

3.17. В 18 веке город Кенигсберг ( ныне Калининград в составе нашей страны ) был расположен на берегах реки и двух островах. Различные части города были соединены семью мостами (рис. 20). Можно ли обойти все эти мосты так, чтобы побывать на каждом из них ровно один раз?

Это и есть задача Эйлера о кенигсбергских мостах, о которой упоминалось в начале параграфа.

Решение.

Обозначим различные части города буквами А, В, С и К и изобразим их точками. Мосты изобразим линиями, соединяющими эти точки. Получим граф ( рис. 21).

Задача сводится к следующей: существует ли путь, проходящий по всем ребрам графа, причем по каждому ребру только один раз?

Рассмотрим два случая.

1) Предположим, что существует такой замкнутый путь. Тогда степень каждой вершины графа должна быть четной, так как, входя в какую-либо вершину, мы затем должны из нее выйти, причем по другому ребру. Что касается начала пути, то после выхода из него мы должны в конце концов в него и вернуться, поскольку путь замкнутый. Однако на рисунке 20 нет ни одной вершины, степень которой была бы четной. Значит этот случай невозможен.

2)Пусть существует такой незамкнутый путь; например, пусть он начинается в вершине А, а заканчивается в С.

Тогда из вершин А и С должно выходить уже нечетное число ребер, а из промежуточных вершин В и К – по-прежнему четное число. Но на рисунке степени вершин В и К нечетны. Следовательно, и этот случай отпадает.

Ответ: нельзя.

Хотя рассуждение проведенное при решении задачи 3.13, выполнено для частного случая, оно носит общий характер:

1)если существует замкнутый путь, проходящий по всем ребрам графа, причем по каждому ребру только один раз, то степени всех вершин графа четные,

2)если существует аналогичный незамкнутый путь, то степени начала и конца пути нечетные, а остальных вершин – четные.

Эйлер в своей статье доказал и обратные утверждения. Пусть граф связный, т. е. любые две его вершины можно связать путем, проходящим по его ребрам. Тогда путь, проходящий по всем ребрам графа, причем по каждому ребру только один раз, существует лишь в следующих двух случаях:

когда степень каждой вершины четная (в этом случае путь замкнут),

когда граф имеет только две вершины А и В с нечетной степенью (тогда путь не замкнут и имеет своими концами вершины А и В ) .

3.18.Можно ли обвести карандашом, не отрывая его от бумаги и не проводя по одной линии дважды:

а) квадрат с диагоналями,

б)правильный пятиугольник с диагоналями?

3.19. Можно ли из проволоки длиной 12 дм изготовить каркас куба с ребром длины 1 дм, не ломая проволоку на части?

3.20. Можно ли граф, изображенный на рисунке 22, обвести карандашом, не отрывая его от бумаги и не проходя ни одной линии дважды? Если можно, то как?

3.21. В точке А расположен гараж для снегоочистительной машины (рис. 23). Водителю машины было поручено убрать снег с улиц части города изображенной на рисунке. Может ли он закончить свою работу на том перекрестке, где находится гараж, если по каждой улице своего участка города водитель будет проезжать только один раз?

3.22. В марсианском метро 100 станций. От любой станции до любой Другой можно проехать. Забастовочный комитет хочет закрыть проезд через одну из станций так, чтобы между всеми остальными стан­циями был возможен проезд. Докажите, что такая станция найдется.

3.23. В тридевятом царстве каждые два города соединены дорогой с односторонним движением. Докажите, что существует город, из которого в любой другой можно проехать не более чем по двум дорогам.

3.24. В городе на каждом перекрестке сходится четное число улиц. Известно, что с любой улицы города можно проехать на любую другую. Докажите, что все улицы города можно объехать, побывав на каждой по одному разу.

Разные задачи на графы.

3.25. В углах шахматной доски 3х3 стоят 4 коня: 2 белых (в соседних углах) и два черных. Можно ли за несколько ходов (по шахматным правилам) поставить коней так, чтобы во всех соседних углах стояли кони разного цвета?

Решение.

Отметим центры клеток доски и соединим отрезками пары отмеченных точек, если из одной в другую можно пройти ходом коня. Мы получим граф, содержащий «цикл» из восьми точек и одну изолированную точку (рис. 24). Перемещение коней по доске соответствует движению по ребрам этого цикла. Ясно, что при движении по циклу нельзя изменить порядок следования коней.

3.26. Выпишите в ряд цифры от 1 до 9 так, чтобы число, составленное из двух соседних цифр, делилось либо на 7, либо на 13.

Решение.

Напишем цифры на листе. Соединим стрелками те цифры, которые могут следовать друг за другом (рис. 25). Теперь ясно, что первой идет 7, затем 8 и 4. Поскольку 8 уже использована, то стрелки, идущие в нее, надо убрать. После 4 идет 9, поскольку к девятке другого пути нет. Дальше идет 1 и так далее.

Ответ: 784913526.

3.27. В школьном турнире в один круг играют шесть шахматистов: Алеша, Боря, Витя, Гриша, Дима и Костя. Ежедневно игрались три партии, и весь турнир окончился в пять дней. В первый день Боря играл с Алешей, а во второй – с Костей. Витя в четвертый день играл с Костей, а в пятый с Димой. Кто с кем играл в каждый день турнира?

Решение.

Обозначим шахматистов соответственно точками А, Б, В, Г, Д и К, а сыгранные ими партии – отрезками, соединяющими эти точки.

Точки лучше располагать так, чтобы при последовательном их соединении они стали вершинами правильного шестиугольника.

Первый день турнира. По условию в этот день Боря играл с Алешей. С кем играл Витя? Только с Гришей, так как с Димой и Костей он играл в другие дни. Следовательно, третью партию в первый день играли Дима с Костей. Построим соответствующий граф (рис. 26).

Второй день турнира. В этот день Боря играл с Костей, поэтому Витя, учитывая первый и пятый дни, мог играть лишь с Алешей (рис. 27).

Третий день турнира. Витя, с учетом всех предыдущих и последующих турнира, мог играть только с Борей. Так как Дима уже играл с Костей и Гришей, то в этот день он играл с Алешей (рис. 28). Значит Гриша играл с Костей.

Четвертый день турнира. Здесь нетрудно определить, кто с кем играл: Витя – с Костей, Алеша – с Гришей, Боря с Димой (рис.29) .

Пятый день турнира (рис. 30).

3.28. В одном купе поезда ехали четыре пассажира. Среди них не было трех человек, которые прежде были знакомы друг с другом, но один был знаком с тремя остальными. Докажите, что эти три последних пассажира прежде не были знакомы друг с другом.

3.29. Каждые две из шести ЭВМ соединены проводом. Можно ли все эти провода раскрасить в один из пяти цветов так, чтобы из каждой ЭВМ выходили пять проводов разного цвета?

Решение.Для решения начертим выпуклый шестиугольник

и проведем в нем все диагонали (рис. 31). Пусть каждая вершина шестиугольника означает однуB из ЭВМ, а каждый отрезок провод, соединяющий две ЭВМ. Занумеруем различные цвета натуральными числами от 1 до 5 для того, чтобы отличать их друг от друга. Начнем например с вершины Апроведем из нее отрезки всех пяти цветов. Перейдем к вершине В и из нее проведем четыре отрезка всех цветов с №2 по №5, учитывая, что отрезок ВА, выходящий из этой вершины, уже окрашен в цвет №1. Затем займемся вершиной С. И т. д. В итоге получаем положительный ответ на вопрос задачи.

Ответ: можно.

На рисунке 31 каждые две вершины графа соединены своим ребром. Такой граф называется полным.

3.30. На туристском слете выяснилось, что каждый юноша знаком с 8 девушками, каждая девушка знакома с 6 юношами. Кого на слете больше: юношей или девушек?

3.30. На кружке, в котором участвуют шесть школьников, было дано шесть задач. Каждый школьник решил две задачи, и каждую задачу решили два школьника. Докажите, что разбор задач можно организовать так, чтобы каждый школьник изложил решение одной из решенных им задач и все задачи были разобраны.

Решение.

Изобразим школьника точкой, а решенную им задачу – линией исходящей из этой точки. Пусть один из школьников обозначен точкой А.. Проведем из нее линию. Так как каждую задачу решили два школьника , то проведенная линия соединяет точку А с другой точкой В, которая обозначает второго школьника, решившего ту же задачу. Так как каждый школьник решил две задачи, то из точки В должна выходить еще одна линия, которая соединяет точку В с еще одной точкой С и т. д.

Возможны следующие случаи.

Может получиться шестиугольник. Тогда утверждение задачи выполняется.

Может получиться четырехугольник и «двуугольник» ; последнее возможно тогда, когда два школьника решили одни и те же задачи.

Могут получиться два треугольника.

Могут получиться три «двуугольника».

Этим исчерпываются все возможности. В каждом из рассмотренных случаев утверждение задачи выполняется.

3.31. На столе в приемной парикмахерской лежат журналы. Каждый клиент парикмахерской просмотрел два журнала; каждый журнал просмотрели три человека; для каждой пары журналов имеется только один клиент, который их просмотрел. Сколько журналов и сколько клиентов в приемной парикмахерской?

Решение.

Обозначим журнал точкой, а клиента, просмотревшего этот журнал – отрезком, выходящим из этой точки.

Возьмем одну такую точку А. Так как каждый журнал просмотрели три человека, то из точки А должны выходить три отрезка. Так как каждый клиент просмотрел два журнала, то каждый

Отрезок соединят две точки. (рис. 32).

Поскольку каждую пару журналов просмотрел один человек, то нужно каждую пару точек соединить отрезком. Получаем четырехугольник с диагоналями (рис. 33). Проверьте еще сами, что здесь все три условия задачи выполняются.

Может возникнуть вопрос: а не существует ли еще хотя одна , пятая точка Е, такая, что все условия задачи выполняются? Тогда из каждой из пяти точек будет выходить не по три, а по четыре отрезка, а это противоречит условиям задачи.

Ответ: 4 журнала, 6 клиентов.

3.32. В одном учреждении каждый сотрудник выписывает две газеты, каждую газету выписывает пять человек и каждую пару газет выписывает только один человек. Сколько человек в учреждении и сколько они выписывают газет.

3.33. Шесть точек, из которых никакие три не лежат на одной прямой соединены всевозможными отрезками и каждый отрезок окрашен в черный или красный цвет. Докажите, что найдется треугольник с вершинами в данных точках, у которого все стороны черные, или треугольник, у которого все стороны красные.

Решение.

Возьмем одну из шести точек А1более четырех отрезков ( по обобщенному принципу Дирихле ). Пусть отрезки А1А2, А1А3 и А1А4 – красные. Рассмотрим два случая.

Допустим, что среди отрезков А2А3, А2А4 и А3А4 имеется красный, например отрезок А2А3. Тогда у треугольника А1А2А3 все стороны красные. Именно этот вариант изображен на рисунке 34.

Если допустим, что среди отрезков А2А3, А2А4 и А3А4 нет красного, тогда все эти отрезки – черные, а следовательно у треугольника А2А3А4 все стороны черные.

3.34. Докажите, что если в задаче 3.33 вместо шести точек взять пять, треугольник с одноцветными сторонами может и не найтись.

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

3.36. 17 ученых из разных стран переписываются между собой на одном из трех языков: английском, французском или русском. Докажите, что среди них найдутся трое, которые переписываются между собой на одном и том же языке.

Решение.

Обозначим каждого из ученых точкой и соединим эти точки всевозможными отрезками. Точки расположим так, чтобы никакие три из них не лежали на одной прямой. Так как каждый ученый переписывается с 16 остальными, то из каждой точки выходит 16 отрезков. Каждый из отрезков, означающий переписку ученых на английском языке, окрасим в черный цвет, на французском – в красный, на русском – в белый.

Рассмотрим два случая.

Пусть среди отрезков, соединяющих точки А2, А3, А4, А5, А6 и А7 попарно между собой, имеется черный, скажем А2А3. Тогда у треугольника А1А2А3 все стороны черные, т. е. соответствующая тройка ученых переписываются между собой на английском языке.

Пусть среди этих отрезков нет черного. В этом случае отрезки между шестью точками А2, А3, А4, А5, А6 и А7 окрашены не более, чем в два цвета – красный и белый. Тогда на основании утверждения задачи 3.33 среди отрезков, соединяющих эти точки, имеются три, составляющие треугольник со сторонами одного цвета.

3.37. На плоскости даны п точек, из которых никакие три не лежат на одной прямой. Они соединены всевозможными отрезками, и каждый отрезок окрашен в один из четырех различных цветов. При каком наименьшем п обязательно найдется треугольник с одноцветными сторонами с вершинами в трех из данных точек?

3.38. Последовательность из 36 нулей и единиц начинается с пяти нулей. Среди пятерок подряд стоящих цифр встречаются все 32 возможные комбинации. Найдите пять последних цифр последовательности.

3.39. Докажите, что можно расположить по кругу символы 0 и 1 так, чтобы любой возможный набор из n символов, идущих подряд, встретился.

Указание.

Рассмотреть граф, вершины которого суть слова длины n-1. Две вершины u и v соединяются стрелкой, если существует слово длины n, у которого u является началом, а v - концом.

4. Раскраски

Говорят, что фигура покрашена в несколько цветов, если каждой точке фигуры приписан определенный цвет. Бывают задачи, где раскраска уже дана, например для шахматной доски, бывают задачи, где раскраску с данными свойствами нужно придумать, и бывают задачи, где раскраска используется как идея решения.

Задачи

4.1. Из шахматной доски вырезали две противоположные угловые клетки. Докажите, что оставшуюся фигуру нельзя разрезать на «домино» из двух клеток

Решение.

Каждая фигура «домино» содержит 1 белую и 1 черную клетку. Но в нашей фигуре 32 черных и 30 белых клеток (или наоборот).

4.2. Можно ли все клетки доски 9х9 обойти конем по одному разу и вернуться в исходную клетку?

Решение.

Каждым ходом конь меняет цвет клетки, поэтому, если существует обход, то число черных клеток равно числу белых, что неверно.

4.3. Дан куб 6х6х6. Найти максимально возможное число параллелепипедов 4х1х1 (со сторонами параллельными сторонам куба), которые можно поместить в этот куб без пересечений.

Идея решения.

Легко поместить 52 параллелепипеда внутрь куба. Докажем, что нельзя больше. Разобьем куб на 27 кубиков 2х2х2. Раскрасим их в шахматном порядке. При этом образуется 104 клетки одного цвета (белого) и 112 - другого (черного). Осталось заметить, что каждый параллелепипед содержит две черных и две белых клетки.

Ответ: 52.

4.4. Прямая раскрашена в 2 цвета. Докажите, что найдутся 3 точки А, В, С одного цвета такие, что AB = ВС.

4.5. Раскрасьте прямую в 3 цвета так, чтобы нельзя было найти трех точек А, В, С разного цвета таких, что AB = ВС.

5. Плоскость раскрашена а) в 2 цвета, б) в 3 цвета. Докажите, что найдутся 2 точки одного цвета, расстояние между которыми равно 1

Идею, вынесенную в заглавие, хорошо иллюстрирует следующая задача. 4.6. Имеется квадрат 8Х8, у которого удалены две угловые клетки, расположенные на одной диагонали. Можно ли этот квадрат замостить костяшками домино размерами 1Х2? Решение дает нам правильная «шахматная» раскраска этой доски. Каждая костяшка домино закрывает две клетки разного цвета, в то время как клеток черного и белого цветов различное количество.

А вот еще две задачи на эту идею.

4.7. Участок прямоугольной формы разбит на квадраты, образующие n рядов по m квадратов в каждом ряду. Каждый квадрат является отдельным участком, соединенным калитками со всеми соседними участками. При каких m и n можно обойти все квадратные участки, побывав в каждом по одному разу, и вернуться в первоначальный?

Решение.

Раскрасим квадраты в шахматном порядке. При каждом переходе меняется цвет квадрата. Поэтому, если такой маршрут возможен, то число шагов должно быть четным, т. е. m или n четно. Осталось проверить, что в этом случае искомый маршрут возможен.

4.8. Все мы в детстве играли в «морской бой». Напомним, что играется он на квадрате 10Х10, на клетчатой бумаге. «Линкором» в этой игре называется «корабль» 1х4. В связи с этим возникает вопрос: можно ли весь квадрат для морского боя разрезать на 25 линкоров? А кстати, ответьте еще на один вопрос: какое наименьшее число «выстрелов» надо сделать, чтобы наверняка хотя бы один раз попасть в линкор, одиноко плавающий по морю?

Решение.

Раскрасим клетки в 4 цвета, как на рис. 36. Каждый «линкор» закрывает четыре клетки разного цвета. Но клеток цвета 2 всего 26, а «линкоров» должно быть 25.

Эта же раскраска помогает ответить и на второй вопрос. Наименьшее число выстрелов равно числу клеток цвета 4, т. е. 24.

5. Задачи с целыми числами. Четные и нечетные числа

Обычно четные и нечетные числа связывают только с натуральными числами. Здесь мы распространим их на любые целые числа. Целое число называется четным, если оно делится на 2, и нечетным, если оно на 2 не делится.

Любое четное число можно представить в виде 2а, а любое нечетное – в виде 2а + 1, где а – целое число.

Два целых числа называются числами одинаковой четности, если оба они четные или оба нечетные. Два целых числа называются числами разной четности, если одно из них четное, а другое нечетное.

Рассмотрим свойства четных и нечетных чисел важные, для решения задач.

Если хотя бы один множитель произведения двух (или нескольких) чисел четен, то и все произведение четно.

Если каждый множитель произведения двух ( или нескольких ) чисел нечетен, то и все произведение нечетно.

Сумма любого количества четных чисел есть число четное.

Сумма четного и нечетного чисел есть число нечетное.

Сумма четного количества нечетных чисел есть число четное; сумма нечетного количества нечетных чисел есть число нечетное.

Задачи

5.1. В пятиэтажном доме с четырьмя подъездами подсчитали число жителей на каждом этаже и, кроме того, в каждом подъезде. Могут ли все полученные 9 чисел быть нечетными?

Решение.

Обозначим число жителей на этажах соответственно через а1, а2, а3, а4, а5, а число жителей в подъездах – соответственно через b1, b2, b3, b4. Тогда общее число жителей дома можно подсчитать двумя способами – по этажам и по подъездам:

a1 + а2 + а3 + а4 + а5 = b1 + b2 + b3 + b4.

Если бы все эти 9 чисел были нечетными, то сумма в левой части записанного равенства была бы нечетной, а сумма в правой части – четной. Следовательно, это невозможно.

Ответ: не могут.

5.2. В футбольном турнире в один круг участвуют 15 команд. Докажите, что в любой момент турнира найдется команда, которая сыграла к этому моменту четное число матчей (может быть, ни одного ).

Решение.

Обозначим число матчей, проведенных первой, второй, третьей и т. д. командами, через а1, а2, а3,…, а15.

Допустим, что все эти 15 чисел нечетны. Подсчитаем общее число матчей, проведенных командами. Оно равно

( а1 + а2 +…+ а15)/2.

Но числитель дроби есть число нечетное, как сумма нечетного числа нечетных слагаемых. Тогда общее число матчей есть число дробное. Получили противоречие.

Утверждение задачи есть частный случай одной из теорем теории графов.

5.3. Четно или нечетно произведение

( 7а + b – 2c +1 )( 3a – 5b + 4c + 10 ),

где числа a, b, c – целые?

Решение.

Можно перебирать случаи, связанные с четностью или нечетностью чисел а, b, c (8 случаев!), но проще поступить иначе. Сложим множители:

( 7a + b – 2c + 1 ) + ( 3a – 5b + 4c + 10) =

= 10a – 4b + 2c + 11.

Так как полученная сумма нечетна, то один из множителей данного произведения четен, а другой нечетен. Следовательно, само произведение четно.

Ответ: четно.

5.4. Пусть а1, а2, а3,…, а25 – целые числа, а с1, с2, с3,…, с25 – те же самые числа, взятые в другом порядке. Докажите, что число

(а1 – с1)(а2 – с2)(а3 – с3) … (а25 – с25)

является четным.

5.5. Четно или нечетно число

1 – 2 + 3 – 4 + 5 – 6 +…+ 993 ?

Решение.

Разность 1 – 2 имеет ту же четность, что и сумма 1 + 2, разность 3 – 4 – ту же четность, что и сумма 3 + 4, и т. д. Поэтому данная сумма имеет ту же четность, что и сумма

1 + 2 + 3 + 4 + 5 + 6 +…+ 993.

Из 993 слагаемых последней суммы 496 четных и 497 нечетных, следовательно, сумма нечетно.

О т в е т: нечетно.

5.6. На прямой расположено несколько точек. Затем между каждыми двумя соседними точками поставили еще по точке. И т. д. Докажите, что после каждой такой операции общее число точек будет нечетным.

Указание.

Если имеется п точек и к ним добавляется еще п – 1 промежуточных точек, то общее число точек становится нечетным, так как п+(п–1) = =2п – 1.

5.7. Найдите все целые значения а, при которых число

x 3 + ax2 + 5x + 9

нечетно для всех целых значений х.

5.8. На семи карточках написали числа 1, 2, 3, 4, 5, 6 и 7. Затем карточки перевернули, перемешали и на обратных сторонах написали те же числа. Числа, написанные на обеих сторонах каждой карточки, сложили и полученные суммы перемножили. Четно или нечетно полученное произведение?

Решение.

Допустим, что произведение нечетно. Для этого все 7 множителей должны быть нечетными. Но тогда у четырех карточек, у которых на одной стороне написаны нечетные числа 1, 3, 5, 7, на другой стороне должны быть числа четные. Однако четных чисел здесь - только три. Следовательно, этот случай невозможен.

Ответ: четно.

5.9. Докажите, что в любой компании число тех людей, которые знакомы с нечетным числом членов компании, четно.

Решение.

Обозначим число людей, которые имеют в компании нечетное число знакомых, через k, а число знакомых этих людей соответственно через a1, a2,…, ak . Кроме того, число людей, знакомых с четным числом членов компании, обозначим через n, а число знакомых этих людей соответственно через b1,b2,…,bn. Тогда общее число знакомств равно

( a1 + a2 +…+ ak + b1 + b2 +…+ bn )/ 2

Сумма b1 + b2 +…+ bn четна, так как все ее слагаемые четны.

Тогда для того, чтобы эта дробь была равна целому числу, сумма

a1 + a2 +…+ ak , должна быть четной. Но все слагаемые последней суммы нечетны, поэтому число k слагаемых суммы может быть только четным.

5.10. Докажите, что не существует многогранника, у которого 1997 граней – треугольники, а остальные грани – четырехугольники и шестиугольники.

5.11. Окружность разделили на 40 равных дуг и в 40 точках деления поставили по шашке. Среди шашек 25 белых и 15 черных. Докажите, что среди шашек найдутся белая и черная, которые стоят на концах одного диаметра.

Решение.

Допустим, что это не верно. Рассмотрим любую белую шашку и диаметр, на котором она стоит. Тогда по нашему допущению на другом конце этого диаметра должна стоять тоже белая шашка. Получается, что всего белых шашек ( как и черных ) четное число. Но последнее противоречит условию задачи.

5.12. Сумма номеров домов одного квартала равна 99, а соседнего квартала той же улицы – 117. Найдите номера всех домов этих кварталов.

5.13.В некотором натуральном числе произвольно переставили цифры. Докажите, что сумма полученного числа с исходным не может быть равна 999…9 (125 девяток).

Решение.

Обозначим исходное число через а, число, полученное из него после перестановки цифр – через b.

Допустим, что равенство

а + b = 999…9 (125 девяток)

возможно. Тогда при сложении чисел а и b не может быть переноса единицы в следующий разряд. Так как сумма цифр чисел а и b равны, то сумма цифр у числа а + b в два раза больше, чем у числа а, а значит она четна. Но с другой стороны , эта сумма равна 9 125, а следовательно, нечетна. Мы получили противоречие.

5.14. Какое наибольшее количество натуральных чисел можно записать в строку так, чтобы сумма любых трех соседних чисел была четной, а сумма любых четырех соседних чисел – нечетной?

Решение.

Обозначим последовательные натуральные числа строки через а1, а2, а3 и т. д.

По условию суммы

а1 + а2 + а3, а2 + а3 + а4, а3 + а4 + а5, а4 + а5 + а6

и другие четны. Вычитая из каждой суммы, начиная со второй, предыдущую получим, что разности

а4 - а1, а5 - а2, а6 - а3,…

четны, а следовательно, имеют одинаковую четность пары чисел

а4 и а1, а5 и а2, а6 и а3 и т. д.

Выпишем нечетные суммы, состоящие из четырех соседних чисел: а1 + а2 + а3+ а4 = (а1 + а2 + а3)+ а4 ,

а2 + а3 + а4+ а5 = (а2 + а3 + а4)+ а5,

а3 + а4 + а5+ а6 = (а3 + а4 + а5)+ а6,…

Отсюда следует, что числа а4, а5, а6 и т. д. нечетны. Но тогда сумма а4 + а5 + а6 нечетна, а это противоречит условию.

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

Рассуждая аналогично , устанавливаем, что числа а4, а5 нечётны, а следовательно , по предыдущему, нечетны и числа а1, а2 .Тогда, так как сумма а1 + а2 + а3 чётна , то число а3 чётно .

Сделаем ещё проверку и убедимся в том, что если взять пять чисел а1, а2, а3, а4, а5 , где число а3 чётно, а остальные нечётны, то каждая из сумм а1 + а2 + а3, а2 + а3 + а4, а3 + а4 + а5 чётна, а каждая из сумм а1 + а2 + а3 + а4 , а2 + а3 + а4 + а5 нечётна.

Ответ: 5.

5.15.Можно ли на клетчатой бумаге, закрасить 25 клеток так, чтобы у каждой из них было: а) четное, б) нечетное число закрашенных соседей? (клетки называются соседями, если у них общая сторона )

Решение.

Предположим, что удалось закрасить 25 клеток требуемым образом. Попробуем найти число общих сторон закрашенных клеток и придем к противоречию. Сосчитаем, сколько у каждой клетки общих сторон с соседями, сложим полученные числа и сумму разделим пополам (так как каждую общую сторону мы считали при этом дважды ). У каждой клетки – нечетное число соседей, и клеток 25. Сумма 25 нечетных чисел нечетна и поэтому нацело на 2 не делится.

Ответ: а) можно, б) нельзя.

Такое же рассуждение показывает, что при любом нечетном n, закрасить n клеток так, чтобы у каждой было нечетное число закрашенных соседей, невозможно. В случае любого четного n такая раскраска возможна.

5.16. Существует ли замкнутая ломаная, которая пересекает каждое свое звено ровно один раз и состоит из: а) 6 звеньев, б) 7 звеньев ?

Простые и составные числа

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

Принято считать, что число 1 не относится ни к простым, ни к составным числам.

Отсюда следует, что множество натуральных чисел можно разбить на такие три подмножества: множество простых чисел, множество составных чисел и множество содержащее единственный элемент 1.

Справедлива следующая теорема.

Любое натуральное число, большее 1, можно и притом единственным образом представить в виде произведения простых чисел.

Это предложение называется основной теоремой арифметики натуральных чисел.

Среди простых делителей натурального числа могут быть равные, и их произведение можно записать в виде степени. Тогда разложение натурального числа а на простые множители можно представить в следующем виде:

a = p1 k1 p2 k2 … pnkn ,

где p1, p2,…, pn - различные простые числа, k1, k2,…, kn – натуральные.

Задачи

5.17.К двузначному числу приписали такое же число. Может ли полученное число быть простым?

5.18. К числу, являющемуся произведением двух последовательных натуральных чисел, приписали справа число 21. Докажите, что полученное число – составное.

5.19. Натуральные числа a и b таковы, что 31a = 54b. Докажите, что число a + b – составное.

Решение.

Так как число 31а делится на 54 и числа 31 и 54 – взаимно простые, то а делится на 54: a = 54n; где nОN. Тогда

31 54 n = 54b, b = 31n.

Отсюда a + b = 54n + 31n = 85n, а следовательно, число a + b является составным.

5.20. Натуральные числа a и b удовлетворяют условию 15a = 32b. Может ли число a – b быть простым? Если может – постройте пример; если не может – докажите.

5.21. Назовите все натуральные n, при которых число n4 + 4 –составное.

Решение.

Попробуем разложить выражение n4 + 4 на множители с целыми коэффициентами. Мы привыкли к тому, что сумма квадратов на множители с целыми коэффициентами не раскладывается. В данном случае это делается с помощью приема «плюс – минус» следующим образом:

n4 + 4 = (n4 + 4 + 4n2) - 4n2 = (n2 + 2)2 - 4n2 = (n2 + 2n + 2)( n2 - 2n + 2).

Очевидно, множитель n2 + 2n + 2 всегда больше 1. Второй множитель n2 - 2n + 2 может быть равным 1:

n2 - 2n + 2 = 1, n2 - 2n + 1 = 0, (n – 1)2 = 0, n = 1.

Так как при n = 1 множитель n2 + 2n + 2 принимает значение 5, являющееся простым числом, то значение n = 1 нужно отбросить.

Ответ: все n не равные 1.

5.22. Докажите, что любое число вида а = 101010…101 (n нулей, n + +1 единица, где n > 1) – составное.

Решение.

Преобразуем число а, учитывая, что всего у него 2n + 1 цифр, а следовательно, первая единица – разряда 2n:

a = 101010…101 = 102n + 102n-2 + 102n-4 +…+ 102 + 1 =

= (1/(102 -1))(102 – 1)(102n + 102n-2 +…+102 +1) =

= (1/99)(102n+2-1) = (1/99)((10n+1)2 – 1) = (1/99)(10n+1+1)( 10n+1-1).

Теперь рассмотрим два случая.

Пусть n четно.

Тогда сумма 10n+1+1 делится на 11, причем частное от такого деления больше 1, так как 10n+1+1 >11; разность 10n+1-1 делится на 9, причем частное также больше 1, так как 10n+1+1 >11; разность 10n+1-1 делится на 9, причем частное также больше 1. Получилось составное число

а = ((10n+1+1)/11) ((10n+1-1)/9).

Пусть n нечетно.

В этом случае разность 10n+1-1 делится на 102 – 1= 99 и частное больше 1, поскольку 10n+1-1 > 99.

5.23. Докажите, что все числа вида

10001,100010001,1000100010001,…

составные.

5.24. Докажите, что число 8(35k + 55n) – 5 при любых натуральных k и n является составным.

5.25. Какое наибольшее число простых чисел может быть среди 15 последовательных натуральных чисел, больших 2?

Решение.

Очевидно, простые числа нужно искать среди нечетных. Из 15 последовательных натуральных чисел имеется 7 или 8 нечетных. Среди любых трех последовательных натуральных чисел ровно одно делится на 3, поэтому среди 7 или 8 последовательных нечетных натуральных чисел имеется 2 или 3 числа, делящихся на 3. Если их отбросить, то останется 5 или 6 нечетных чисел.

Нужно еще убедиться, что такие 6 простых чисел возможны. Например, если взять такие 15 последовательных натуральных чисел: 3, 4, 5, 6,…, 17, то среди них – 6 простых. 3, 5, 7, 11, 13, 17.

О т в е т: 6.

5.26. Составьте из простых чисел все возможные арифметические прогрессии с разностью 6 и числом членов, большим 4.

5.27. Докажите, что все числа p, p + 2, p + 4 являются простыми только в случае, когда они образуют тройку 3, 5, 7.

Решение.

Рассмотрим несколько случаев, в зависимости от p.

При p = 2 число p +2 = 4 – составное, поэтому значение p = 2 отпадает.

При p = 3 получим тройку 3, 5, 7, о которой упоминается в условии задачи.

При p = 5 число p + 2 = 7 – простое, но число p + 4 = 9 – составное, значит, p = 5 нужно отбросить.

При p = 7 число p + 2 = 9 – составное.

При p = 11 число p + 4 = 15 – тоже составное.

Возникает предположение, что подходит только p = 3. Докажем его.

Нетрудно заметить, что значение p = 5, p = 7, p = 11 не подходили потому, что или p + 2 или p + 4 делятся на 3. Убедимся, что так будет всегда при простом p>3.

Простое число, большее 3, не делится на 3 и, следовательно, при делении на 3 может давать в остатке только 1 или 2. Рассмотрим оба случая.

Пусть p при делении на 3 дает в остатке 1: p = 3k + 1 (kОN). Тогда число p + 2 = (3k + 1) + 2 = 3k = 3 делится на 3, причем частное от этого деления больше 1. Значит число p + 2 составное.

Пусть p = 3k + 2 (kОN). Тогда число p + 4 = (3k + 2) + 4 = 3k + 6 – составное.

5.28. Найдите все такие p, что числа p, p + 10 и p + 20 – простые.

Задачи этого пункта – это, по существу, числовые ребусы. Своеобразие таких задач в том, что одна из двух компонент действия получается из другой путем перестановки или зачеркивания цифр.

Задачи на зачеркивание цифр в натуральном числе

5.29. Найдите все натуральные числа, которые при зачеркивании последней цифры уменьшаются в 14 раз.

Решение.

Обозначим искомое число через 10x + y, где x – количество десятков числа, y – его последняя цифра. Тогда

10x + y = 14x, y = 4x.

Так как y есть цифра, то и x – цифра, причем не превосходящая 2. Полагая x = 1, 2, находим, что соответственно y = 4, 8.