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

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

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

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

физико тАУ математический факультет 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, образуют полВнную систему инвариантов.

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