Курсовая работа: Нестандартные задачи по математике

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

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

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

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

f ₁ ( a ) = f ₁ ( p ),

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

f_k (a) = f_k (p).

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

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

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

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

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

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

a = ab

cd

обозначим через 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. Если f 1 , f 2 , fk - инварианты и g — числовая функция от k аргументов, то функция h : h ( a ) = g ( f 1 ( a ), f 2( a ),..., fk ( a )) (7) является инвариантом (ср. с упражнением 2). Проверьте.

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

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

f ₁ ( x , y ) = xy ,

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

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