Смекни!
smekni.com

Нестандартные задачи по математике (стр. 2 из 9)

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

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

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

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

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

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

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

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

+ ... + n xn(a).(2)

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

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

... + i xi(a) + (i + 1) xi+1(a) + ...+ (j - 1) xj -1(a)+ j x j(a)+ …(3)

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

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

+…+(j1) [xj-1(a) + 1] + j[xj(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) = lnи 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 принадлежат разным ор­битам и, таким образом, попарно не эквивалентны.