Нестандартные задачи по математике (стр. 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не равном п:

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) -= il+ п (п— 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 суммы номеров ящиков, в которых лежат карточки.

Задачи

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= 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 <f₁,f₂,…, f_k> - полная система инвариантов, то существует такая числовая функция g от k аргументов, что выполняется (7) (ср. с упражнением 3). Докажите.

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

f₁(x, y) = xy ,

f₂(x, y) = x + y.

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