Закончить наме­ченное решение

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= 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 <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₂> - полная система инвариантов.

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

< x, y, z >à <y, x, z > и <x, y, z >à < x, z, y >. Пусть

f₁( x, y, z ) = xyz,

f₂ (x, y, z) = ху + уz + zх,

f₃(x, y, z ) = х + у + z.

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

1.31. Множество М состоит из всевозможных наборов (или кор­тежей) <х₁, x₂, x₃, …, x_n> действительных чисел (n фиксировано). Разрешается менять местами любые два соседних числа. Найти полную систему инвариантов.

В отличие от задач 1 — 3, которые были просто задачами олимпиадного типа, упражнения 11—13 играют важ­ную роль в алгебре многочленов. Ин­варианты в них интересны не для ре­шения вопроса об эквивалентности (который ясен и без них), а сами по себе — как полезные функции.

1.32.Даны розетка с п дырками и элект­ронная лампа с n штырями. Дырки зануме­рованы от 1 до n (рис. 9). Можно ли зануме­ровать штыри от 1 до n так, чтобы при любом включении в розетку один из штырей попадал в дырку со своим номером?

1.33. Многие знают «игру в 15»: в коробоч­ке 4x4 лежат 15 шашек с номерами от 1 до 15; разрешается за один ход передвинуть в пустую клетку одну из шашек, соседних с ней. Можно ли превратить положение a в положение p (рис. 10)? Найдите для этой игры универсальный инвариант.

1	2	3	4		1	2	3	4
5	6	7	8		5	6	7	8
9	10	11	12		9	10	11	12
13	14	15			13	15	14

а p

1.34. На клетчатой доске 11x11 отмечено 22 клетки так, что на каждой вертикали и на каждой горизонтали отмечено ровно 2 клетки. Два расположения отмеченных кле­ток эквивалентны, если, меняя любое число раз вертикали между собой и горизонтали между собой, мы из одного расположения можем получить другое. Сколько существует неэквивалентных расположении отмеченных клеток?

1.35. Испанский король решил перевесить по-своему портреты своих предшественников в круглой башне замка. Однако он хочет, чтобы за один раз меняли местами только два портрета, висящих рядом, причем это не должны быть портреты королей, один из которых царствовал сразу после другого. Кроме того, ему важно лишь взаимное расположение портретов, и два расположе­ния, отличающиеся поворотом круга, он считает одинаковыми. Доказать, что, как бы сначала ни висели портреты, король может по этим правилам добиться любого нового их расположения.

1.36. Все целые числа от 1 до 2n выписаны в строчку. Затем к каждому числу прибавили номер того места, на котором оно стоит. Доказать, что среди полученных сумм най­дутся хотя бы две, дающие при делении на 2n одинаковый остаток.

1.37. Вернемся к задаче 1 с фишками в круге и разрешим теперь двигать две фишки как в разные стороны, так и в одну сторону. Найти для этой задачи универсальный ин­вариант.

1.38. В таблице 3x3 расставлены числа +1 и -1. Разрешается менять знак одновре­менно у всех элементов строки или столбца. Докажите, что:

a) число орбит равно 16;

b) каждая орбита содержит ровно 32 элемента;

c) произведение всех чисел любого квад­рата 2x2 в таблице является инвариантом;

d) произведения чисел в четырех квадра­тах, указанных на рисунке 11, образуют пол­ную систему инвариантов.

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

´		´		´		´
´		´
				´		´

	´	´			´	´
	´	´
					´	´

1.39. Вектор <а, b>, где a, b—целые числа, разрешается заменять одним из векто­ров <а + b, b>, <a—b, b>, <b, a>. Найти универсальный инвариант.

1.40. Пару векторов <а, b>, <с, d>, где а, b, с, d — целые числа, разрешается заме­нять на одну из пар <а+b, b>, <c+d, d>; <a - b, b>, <c – d, d>; <b, a>, <d, c>. Найти полную систему инвариантов.

2.Четность плюс инвариант

2.1.На доске написаны натуральные числа 1, 2, 3,…, 100. Разрешается стереть любые два числа и записать модуль их разности, после чего колличество написанных чисел уменьшается на 1. Может ли после 99 таких операций остаться записанным на доске число 1 ?

Решение .

Подсчитаем общую сумму начальных 100 чисел :

1 + 2 + 3 + …+ 100 = 5050.

Эта сумма оказалась четной . Переходя к следующему набору чисел , мы фактически в этой сумме заменяли сумму двух чисел на их разность. Но сумма и разность двух целых чисел имеют одинаковую четность, поэтому общая сумма записанных чисел останется четной. Следовательно , эта сумма равной 1 быть не может.

О т в е т : не может.

2.2. На доске написаны 8 плюсов и 11 минусов . Разрешается стереть любые два знака и написать вместо них плюс , если они одинаковы, и минус если они различны. Какой знак останется на доске после 18 таких операций?

2.3.На главной диагонали шашечной доски 10 на 10 стоят 10 шашек, все в разных клетках. За один ход разрешается выбрать любую пару шашек и передвинуть каждую из них на одну клетку вниз. Можно ли за несколько таких ходов поставить все шашки на нижнюю горизонталь?

2.4. На столе стоят вверх дном 7 стаканов. Разрешается за один раз перевернуть любые 4 стакана. Можно ли через несколько шагов поставить все стаканы в нормальное положение?

Решение.

Поставим в соответствии стакану, стоящему нормально, +1, а стоящему вверх дном, - 1. Инвариантом здесь будет произведение чисел, соответствующих всем 7 стаканам, так как при изменении знака у 4 сомножителей произведение не меняется. Но в начальном положении это произведение равно -1, а значит, стать +1 оно никогда не сможет.

2.5. На столе стоят 7 перевернутых стаканов. Разрешается одновременно переворачивать любые два стакана. Можно ли добиться того, чтобы все стаканы стояли правильно?

2.6. На столе стоят вверх дном 9 стаканов. Разрешается за один раз перевернуть любые 4 стакана . Можно ли за несколько таких ходов поставить все стаканы в нормальное положение?

2.7.Три кузнечика играют в чехарду : если кузнечик из точки А прыгает через кузнечика , находящегося в точке В , то он окажется в точке С , симметричной точке А относительно точки В. В исходном положении кузнечики занимают три вершины квадрата. Могут ли они ,играя в чехарду, попасть в четвертую его вершину?

Решение.

Введем на плоскости систему координат так, чтобы три вершины квадрата, в которых находятся кузнечики, имели координаты (0; 0),

(0; 1) и (1; 0). При указанных прыжках каждая из координат кузнечиков или остается неизменной, или изменяется в ту или иную сторону на четное число (рис 12) х

Так как в начальном положении

по меньшей мере одна из координат каждой из трех точек

четна , то она при прыжках останется четной: четность хо

тя бы одной из двух каждой из точек есть инвариант.

Поэтому попасть в М один из кузнечиков

не может Ответ: не может.

2.8.Имеется 30 карточек, каждая из которых выкрашена с одной стороны в красный, а с другой – в синий цвет. Карточки разложили подряд в виде полосы так, что у 8 карточек сверху оказался синий цвет. За один разрешается перевернуть любые 17 карточек. Можно ли за несколько ходов добиться того, чтобы полоса стала полностью: а) красной; б) синей?

Задача 1: На доске написано де­сять плюсов и пятнадцать минусов. Разрешается стереть любые два зна­ка и написать вместо них плюс, если они одинаковы, и минус в противном случае. Какой знак останется, на дос­ке после выполнения двадцати четырех таких операций.

Решение.

Заменим каждый плюс числом 1, а каждый минус чис­лом —1. Разрешенная операция опи­сывается тогда так: стираются любые два числа и записывается их произве­дение. Поэтому произведение всех написанных на доске чисел остается неизменным. Так как вначале это произведение равнялось —1, то и в конце останется число —1, то есть знак минус.

Это рассуждение можно было про­вести иначе. Заменим все плюсы ну­лями, а минусы—единицами, и за­метим, что сумма двух стираемых чи­сел имеет ту же четность, что и число, записываемое вместо них. Так как

сначала сумма всех чисел была нечет­ной (она равнялась 15), то и последнее оставшееся на доске число будет не­четным, то есть единицей, и, значит, на доске останется минус.

Наконец, третье решение задачи можно получить, заметив, что в ре­зультате каждой операции число ми­нусов либо не изменяется, либо умень­шается на два. Поскольку сначала число минусов было нечетным, то и в конце останется один минус.

Проанализируем все три решения.

Первое решение основывалось на неизменяемости произведения на­писанных чисел, второе—на неизменяе­мости четности их суммы и третье — на неизменяемости четности числа минусов. В каждом решении нам уда­лось найти инвариант: произведение написанных чисел, четность суммы, четность числа минусов. Решение последующих задач также основывается на удачном под­боре инварианта.

2.9. На доске напи­сано несколько плюсов и минусов. Разре­шается стереть любые два знака и написать вместо них плюс, если они различны, и ми­нус в противном случае. Докажите, что по­следний оставшийся на доске знак не зависит от порядка, в котором производились сти­рания.

2.10. В таблице 4х4 знаки «+» и «—» расставлены так, как показано на рисунке 13. Разрешает­ся изменить знак на противополож­ный одновременно во всех клетках, расположенных в одной строке, в одном столбце или вдоль прямой, параллельной какой-нибудь из диаго­налей (в частности, в любой угловой клетке). Можно ли с помощью этих операций получить таблицу, не со­держащую ни одного минуса?

Решение.

Заменим плюсы и минусы числами 1 и –1. В качестве инварианта можно взять произведение чисел, находящихся в клетках, которые заштрихованы на рисунке 14, поскольку оно в результате

разре­шенной операции все время сохраняет первоначальное значение, равное -1. Но, значит, среди заштрихованных чисел всегда будет оставаться -1, следовательно, получить таблицу, не содержащую ни одного минуса, нель­зя.

2.11.Решите задачу 2 для таблиц, изображенных на рисунках 15 - 17.

2.12. На доске написано несколько нулей, единиц и двоек. Раз­решается стереть две неравные цифры и вместо них написать одну цифру, отличную от стертых (2 вместо 0 и 1, 1 вместо 0 и 2, 0 вместо -1 и 2). Докажите, что если в результате нескольких таких операций на доске останется одна-единственная цифра, то она не зависит от порядка, в ко­тором производились стирания.

Решение.

Обозначим через х0, х1, х2 число нулей, единиц и двоек соответственно. Выполнив один раз разрешенную операцию, мы изменим каждое из этих чисел на 1 и, следова­тельно, изменим четность всех трех чисел. Когда на доске остается одна цифра, два из чисел х0, x1, х2 ста­новятся равными нулю, а .третье — единице. Значит, с самого начала два из этих чисел имеют одну четность, а третье—другую. Поэтому незави­симо от того, в каком порядке произ­водятся стирания, в конце единице может равняться лишь одно из чисел х0, х1, x.2, которое с самого начала имело не ту четность, что два других.

Из приведенного решения видно, что если числа х0, х1, х2 имеют одну и ту же четность, то мы не сможем добиться, чтобы на доске осталась одна-единственная цифра. Докажите, что если среди чисел х0, х1 х2 есть как четные, так и нечетные, и, кроме того, хотя бы два из них отличны от нуля, то существует такой порядок стираний, что в результате на доске останется' одна цифра.

Изменим условие задачи 3: по­требуем, .чтобы одни и те же две нерав­ные цифры стирались два раза, а вместо них записывалась одна цифра, отличная от стертых. Предположим, что снова после некоторого числа опе­рации на доске осталась одна-единственная цифра. Можно ли зара­нее, по числу нулей, единиц и двоек, предвидеть, какая это цифра?

Рассуждение с четностью здесь не помогает, ибо в результате выполне­ния каждой операции одно из чисел х0, х1, x2 меняет свою четность, а два других сохраняют четность, так что числа, имевшие разную четность, могут теперь получить одну и ту же четность. Однако можно заметить, что остатки от деления чисел х0, х1, х2 на 3 изменяются каждый раз таким образом, что равные остатки остаются равными, а неравные оста­ются неравными. Дальнейшие рас­суждения повторяют решение зада­чи 3.

2.13. В каждой клетке таблицы 8х8 написано некоторое целое число. Разрешается выбирать в таблице любой квадрат размерами 3х3 или 4х4 и увеличивать на еди­ницу все стоящие в клетках выбранно­го квадрата числа. Всегда ли можно с помощью таких операций преобразо­вать исходную таблицу в таблицу, у которой вес числа делятся на З?

Решение.

Нет, не всегда. Най­дем сумму чисел, написанных в за­штрихованных на рисунке 6 клетках. Поскольку любой квадрат размерами 4х4 содержит 12 заштрихованных клеток, а квадрат размерами 3х3— 6 или 9 таких клеток, то в результате описанной операции остаток от деле­ния на 3 этой суммы (чисел, стоящих в заштрихованных клетках) не будет меняться. Поэтому, если с самого на­чала найденная сумма не делится на 3, то среди заштрихованных клеток все время будут сохраняться клетки, в которых написанные числа не крат­ны трем.

 2.14.Из всякой ли таблицы можно в условиях задачи 4 получить таблицу, не содержащую четных чисел?

 2.15.Числа I, 2, 3, ...., n расположены в некотором порядке. Разрешается менять местами любые два рядом стоящих числа. Докажите, что если проделать нечетное число таких операций, то наверняка полу­чится отличное от первоначального расположения чисел 1, 2, 3, ...,n.

Решение.

Пусть a1, a2,…, an— произвольная перестановка из чисел 1, 2, 3, ..., п. Будем говорить, что числа аi, и аj, образуют в этой перестановке инверсию, если i<j, но ai>aj, то есть большее из этих чисел предшествует меньшему. Поменяв ме­стами два соседних числа в переста­новке, мы увеличим или уменьшим число инверсий на 1. Проделав же не­четное число таких операций, мы из­меним четность числа инверсий, а значит, изменим и перестановку.

2.16.Докажите, что утверждение задачи 2.15 останется справедли­вым, если разрешить менять местами любые два числа в перестановке.

Указание.

Докажите, что любые два чис­ла можно поменять местами, проделав нечетное число раз операцию, описанную в задаче 2.12.

Переход от одной перестановки чисел 1, 2, 3, .... п к другой переста­новке этих чисел, при котором какие-нибудь два числа меняются местами, а остальные остаются на месте, называется транспозицией. Результат задачи 2.16 можно сформулировать так: выполнив нечетное число транс­позиций, мы изменим перестановку

2.17. В различных пунк­тах кольцевого автодрома в одно и то же время в одном направлении старто­вали 25 автомобилей. По правилам гонки автомобили могут обгонять друг друга, но при этом запрещен двойной обгон. Автомобили финиши­ровали одновременно в тех же пунктах, что и стартовали. Докажите, что во время гонки было четное число обгонов.

Решение.

Окрасим один из автомобилей в желтый цвет, а остальным автомобилям присвоим номера 1, 2, 3, ..., 24 в том порядке, в каком они располагаются на старте за жел­тым автомобилем. В центре автодро­ма установим световое табло, на кото­ром после каждого обгона будем ука­зывать номера автомобилей в том по­рядке, в каком они следуют за жел­тым автомобилем. Тогда обгон, в котором не участвует желтый авто­мобиль, приводит к тому, что на све­товом табло меняются местами два соседних числа.

Посмотрим, что произойдет, если какой-нибудь автомобиль обгонит желтый. Если перед этим обгоном числа на табло образовывали переста­новку а1, а2,…, а24 , то после об­гона они образуют перестановку а2, а3,…, а24, а1. Заметим, что к такой же перестановке можно прийти, вы­полнив последовательно 23 транспо­зиции: а1, а2, а3,…, а24 à а2, а1, а3,…, а24 à а2, а3, а1,…, а24 à а2, а3, а1,…, а24 à… à а2, а3,…,а1, а24 à а2, а3,…, а24, а1

Если же желтый автомобиль со­вершил обгон, то из перестановки а1, а2, ..., а24 получим пере­становку а24, а1, а2, а3,…, а23. Этот переход также можно заменить двадцатью тремя транспозициями.

Таким образом, любой обгон сводится к нечетному числу транспо­зиций. Если бы общее число обгонов было нечетным, то нечетным оказалось бы и общее число транспозиций. Ос­тается воспользоваться результатом задачи 2.16.