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

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

Условимся считать, что из любой позиции 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 из Mi p из 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. Если т = 2 k + 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. Для про­извольной расстановки а . фишек по секторам обозначим через x k (а) количество фишек в 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 [x i ( a ) - 1] + (i + 1) [x i +1( a ) + 1]+

+…+(j – 1) [x j -1( a ) + 1] + j [x j ( a ) - 1] +…

Легко проверяется, что обе суммы равны. Итак, q - инвариант! Нет,

мы забыли, что n -й сектор граничит с первым. Значит, есть еще 3 возмож­ности. Подсчет, аналогич­ный только что сделанному, показы­вает, что в случае, изображенном на рис. 6, q ( a ) уменьшится на п, а в случае увеличится на п. В третьем случае q (а) , конечно, не изменится. Итак, за одно переме­щение значение функции q может измениться, но только на п. Следовательно, функция r , значение которой на расстановке a равно остатку. от деления числа q (a) на п, есть ин­вариант.

Для позиции v (если все п фишек собраны в 1-м секторе)

x 1(v) = x 2(v) =…= x l -1(v) = x l+ 1(v) = …=x n (v) = 0,

x l(v) = n.

Значит, q ( v ) = l n и r ( v ) = 0 (каковы бы ни были п и l ). С другой стороны,

x 1( w ) = x 2( w ) =…= x n ( 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 не эквивалентны.