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

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

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

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

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

а                                                           

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, образуют полную систему инвариантов.

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

´