Смекни!
smekni.com

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

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

x1(бi) == x2(бi) = …= x i - 1(бi) = x i+1 (бi) =...= xn-1(бi)=0,

xi(бi)=1,

xn(бi)-=n- 1.

Следовательно, q (бi) -= il+ п (п— 1) и r(бi) = i. Кроме того, qn) =nn и rn) = 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)]2; g(a) = [r(а) - 2]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). Разрешим менять местами любые две карточки. При таком перемещении расстояние между восемью парами «одноименных» карточек не меняется, между дву­мя - меняется; таким образом, сум­ма всех этих расстояний...

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

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

f1(a) = f1(p),

f2(a) = f2(p), (5)

fk(a) = fk(p).

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

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

<f1, f2,…, fk > на них различны.

Полная система инвариантовэто обобщение понятия универсаль­ного инварианта: если 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. Решите задачу для таблицnx n, в которых разрешаются те же преобразования, что и в задаче 3. Естественно ожидать полную систему из 2n- -1 инвариантов.

1.27. Если f1, f2, fk- инварианты и g числовая функция от k аргументов, то функция h: h(a) = g(f1(a), f2(a),..., fk(a)) (7) является инвариантом (ср. с упражнением 2). Проверьте.

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

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

f1(x, y) = xy ,

f2(x, y) = x + y.

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