Скачать

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

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

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

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

физико – математический факультет 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 треугольников?

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

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

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

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

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

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

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

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

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

Поскольку эквивалентность позиций рефлексивна, симметрична и транзитивна, исходное множество М разбивается на непустые непересекающиеся подмножества (рис. 1): М = M1UM2UM3U... В каждом из подмножеств Mi, все позиции экви­валентны: если aиз Мi, и из Mi, то a~ . Если же позиции a и принадлежат  разным подмножест­вам: aиз Mi из Mj ( iотлично отj), то a и не эквивалентны ). Подмножества Мiмы будем называть орбитами. Повторим еще раз: если мы находимся в позиции a, принадлежащей какой-нибудь орбите Mi, то мы можем, перемещаясь по этой орбите, пере­браться из позиции a в любую другую позицию,  принадлежащую орбите. С другой стороны, сойти с этой орбиты, т. е. перебраться с по­зиции a на позицию , принадлежа­щую любой другой орбите, мы не можем. Орбит может быть как конечное, так и бесконечное число. Впрочем, если множество М конечно, то, ра­зумеется, и число орбит конечно. Инвариант.Числовая функция 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, то /2 нечетно. Значит, для начальной позиции w имеем g(w) =1. Из того, что g(w) отлично отg(v) вытекает, что позиции w и v не эквивалентны. Таким образом, в этом случае

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

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

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

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

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

q(a)= 1 x₁ (a) + 2 x₂ (a) +3x₃(a) +

 + ... + n x_n(a).      (2)

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

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

... + i x_i(a) + (i + 1) x_i+1(a) + ...+ (j - 1) x_{j -1}(a)+ j x j(a)+ … (3)

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

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

 +…+(j – 1) (xj-1(a) + 1) + j(xj(a) - 1) +…

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

мы забыли, что -й сектор граничит с  первым. Значит, есть еще 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 и r (v) = 0 (каковы бы ни были п и l). С другой  стороны,

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

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

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

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

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

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

Как проверить, что некоторый ин­вариант 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-м сек­торе, все остальные — в п-м секторе. Под б мы будем, разумеется, пони­мать расстановку, при которой все фишек — в -м секторе.

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

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

x₁(бi) == x₂(бi) = …= x _{i - 1}(бi) = x _i+1 (бi) =...= x_n-1(бi)=0,

x_i(бi)=1,

x_n(бi)-=- 1.

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

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

Поскольку 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 — инвариант, af— универсаль­ный инвариант, то существует такая число­вая функция g, что выполняется (4).

1.22.Определимчерез универсальный инвариантrиз задачи 1 два новых инварианта: f(a) = (r(a))²; g(a) = (r(а) - 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). Разрешим менять местами любые две карточки. При таком перемещении расстояние между восемью парами «одноименных» карточек не меняется, между дву­мя - меняется; таким образом, сум­ма всех этих расстояний...

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

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

f₁(a) = f₁(),

f₂(a) = f₂(p),     (5)

f_k(a) = f_k(p).

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

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

<f₁, f₂,…, f_k > на них различны.

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

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

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

a=  a b

c d

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

0        q(a)

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

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

g(a) = g(),

q(a) = q(),

r(a) = r().

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

Задачи.

1.26. Решите задачу для таблиц x , в которых разрешаются те же преобразования, что и в задаче 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 <f₁,f₂,…, f_k> - полная систе­ма инвариантов, то существует такая число­вая функция g от k аргументов, что выпол­няется (7) (ср. с упражнением 3). Докажите.

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

f₁(x, y) = xy ,

f₂(x, y) = x + y.

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

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

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

f₁( x, y, z) = xyz,

f₂ (x, y, z) = ху + уz + zх,

f₃(x, y, z ) = х + у + z.

Доказать, что <f₁, f₂, f₃> — полная система инвариантов.

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

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

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

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

а                                                           

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

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

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

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

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

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

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

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

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

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