86344 (612727), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

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 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 [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 не равном п:

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

x_i(бi)=1,

x_n(б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)]²; 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₁(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= a b

c d

Характеристики

Список файлов курсовой работы