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

Назовем инвариант 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 — инвариант, 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 суммы номеров ящиков, в которых лежат карточки.