Нестандартные задачи по математике

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= a b

c d

обозначим через 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. Решите задачу для таблиц n x 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> - полная система инвариантов.

1.30. Множество М — множество точек пространства или множество троек <x, y, z> действительных чисел. Раз­решены переходы

 Скачать реферат