|
Курсовая работа по математике
Нестандартные задачки по математике
Студент: Игнатьева Ольга Михайловна
физико - математический факультет 4 курс
Научный управляющий: Емельченков Евгений Петрович
СГПУ
2001
1. Инварианты
Инвариантом некого преобразования либо системы действий именуется величина (либо свойство), остающаяся неизменной при этом преобразовании.
часто встречаются задачки, в которых спрашивается, можно ли в итоге неких действий получить тот либо другой итог. Главным способом решения схожих задач является нахождение характеристики исходного объекта, которое не изменяется после выполнения таковых действий, - это и есть инвариант. Если конечный объект задачки не владеет отысканным свойством, то он, разумеется, не может быть получен в итоге этих действий из исходного объекта.
Полуинвариант - величина, изменяющаяся лишь в одну сторону (т.Е. Которая может лишь возрастать либо лишь уменьшаться). Понятие полуинварианта частенько употребляется при подтверждениях остановки действий.
1. Имеется квадратная таблица 10х10, в клеточки которой в последовательном порядке вписаны натуральные числа от 1 до 100: в первую строчку - числа от 1 до 10, во вторую - от 11 до 20 и т. Д. Докажите, что сумма S всех 10 чисел таблицы, из которых никакие два не стоят в одной строке и никакие два не стоят в одном столбце, постоянна. Найдите эту сумму.
Решение.
Обозначим слагаемое исходной суммы S из первой строчки через а1 , из второй - через 10 + а2, из третьей - через 20 + а3 и т. Д., Наконец, из десятой - через 90 + а10.
тут каждое из натуральных чисел а1, а2, …,а10 заключено в пределах от 1 до 10 , причем эти числа попарно различны, так как, если бы, к примеру, а1 = а2 , то числа а1 и 10 + а2 стояли бы в одном столбце таблицы. Получаем:
S = а1 + ( 10 + а2 ) +( 20 + а3 ) + …+ ( 90 +а10 ) =
= ( 10 + 20 +…+ 90 ) + ( а1 + а2 +…+ а10 ) =
= 450 + (а1 + а2 +…+ а10 ).
Поскольку числа а1, а2,…, а10 попарно различны и принимают все целые значения от 1 до 10 , то каждое из натуральных чисел от 1 до 10 входит в сумму а1 + а2 +…+ а10 в качестве слагаемого ровно один раз. Следовательно,
а1 + а2 +…+ а10 = 1 + 2 +3 +… + 10 = 55,
S = 450 + 55 = 505.
Сумма S и является инвариантом : если в ней одни слагаемые заменить другими, но так, чтоб все слагаемые новой суммы стояли в таблице в различных строчках и в различных столбцах, сумма воспримет, тоже самое значение.
Ответ : 505.
2. На каждой клеточке шахматной доски 8х8 написали произ-ведение номера строчки, в которой расположена клеточка, на номер её столбца. Избрали 8 клеток, из которых никакие две не стоят в одной строке и никакие две не стоят в одном столбце. Докажите, что произведение чисел, написанных в этих клеточках, постоянно, и вычислите его .
3. Лист бумаги разорвали на 5 кусков, некие из этих кусков разорвали на 5 частей, а некие из этих новейших частей разорвали еще на 5 частей и т. Д. Можно ли таковым методом получить 1994 куска бумаги ? А 1997 ?
Решение.
При каждом разрывании листа либо одного куска бумаги на 5 частей общее число кусков возрастает на 4 . Поэтому число кусков бумаги на каждом шаге может иметь лишь вид 4k + 1 (k-
натуральное число ). Это выражение и является инвариантом.
Так как 1994 нельзя представить в виде 4k + 1 , то число кусков, равное 1994 , получиться не может, а 1997 = 4k + 1 при k = = 499 ,следовательно, 1997 кусков получиться могут.
4. Имеется два листа картона. Каждый из них разрезали на 4 куска, некие из этих кусков разрезали еще на 4 куска и т. Д. Можно ли таковым методом получить 50 кусков картона? А 60 ?
5. Каждое натуральное число от 1 до 50000 заменяют числом равным сумме его цифр. С получившимися цифрами делают ту же операцию, и так поступают до тех пор, пока все числа не станут однозначными. Сколько раз посреди этих однозначных чисел встретится каждое из целых чисел от 0 до 8?
Решение.
Указанные однозначные числа в последовательном порядке таковы : 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2,3, 4, 5, 6, 7, 8, 0,… .
Эта закономерность сохраняется и дальше. В самом деле, при замене натурального числа суммой его цифр остаток от деления числа на 9 остается постоянным, поэтому при переходе от каждого натурального числа к следующему остаток от деления числа на 9 возрастает на 1 либо перескакивает от 8 к 0. Для того чтоб узнать, сколько таковых групп цифр по 9 цифр в каждой, разделим 50000 на 9 с остатком : 50000 = 9 5555 + 5.
Следовательно, таковых групп 5555 . Еще одну, неполную группу образуют последние 5 цифр : 1, 2, 3, 4, 5.
Ответ : 1, 2, 3, 4, 5 - по 5556 раз , 6, 7, 8, 0 - 5555 раз .
6.На доске написаны числа 1, 2, 3, …, 125 . Разрешается стереть любые два числа и написать заместо них остаток от деления суммы этих чисел на 11 . После 124 таковых операций на доске осталось одно число. Какое это число?
7.Первый член последовательности равен 1 , а каждый следующий, начиная со второго, выходит прибавлением к предыдущему члену суммы его цифр. Может ли в данной последовательности встретиться число 765432?
8.Круг разбит на 6 равных секторов, в каждом из которых стоит по одной шашке. Одним ходом разрешается любые две шашки передвинуть в соседние секторы , причем так, чтоб одна шашка двигалась по часовой стрелке, а другая - против. Можно ли за несколько таковых ходов собрать все шашки в одном секторе.
9.Круг разбит на 6 равных секторов, в которых расставлены числа 0, 1, 2, 0, 2, 1 ( в указанном порядке ). Разрешается за один ход сразу добавлять одно и то же число к двум стоящим рядом числам. Можно ли за несколько таковых ходов добиться того, чтоб все 6 чисел, стоящие в секторах были равны?
Решение.
Пусть на неком шага в секторах оказались в последовательном порядке числа а1, а2, а3, а4, а5, а6. Составим такую сумму : S = а1 - а2 + а3 - а4 + а5 - а6 .
После каждого хода она не изменяется, так как любая из разновидностей а1 - а2 , а3 - а4 , а5 - а6 при увеличении уменьшаемого и вычитаемого на одно и то же число сохраняет свое значение; следовательно, она является инвариантом . Но в начальном положении S = 0 - 1 + 2 - 0 + 2 - 1 = 2 , а в конечном , когда каждое из шести чисел равно одному и тому же числу , S = 0. Поэтому сделать равными все шесть чисел нельзя.
Ответ : нельзя.
10.В верхушках выпуклого шестиугольника записаны числа 8, 3, 12, 1, 10, 6 (в указанном порядке). За один ход разрешается к4 хоть каким двум числам в соседних верхушках прибавить одно и то же число. Можно ли за несколько таковых ходов получить в последовательном порядке шестёрку чисел 5, 2, 14, 6, 13, 4?
11.Даны четыре числа 3, 4, 5, 6. За один ход разрешается написать четыре новейших числа, заменив каждое из исходных чисел средним арифметическим трех остальных. Докажите, что за несколько таковых ходов нельзя получить набор 1, 3, 5, 8.
12.В каждой клеточке доски 5 х 5 посиживает жук. В некий момент все жуки переползают на соседние (по горизонтали либо вертикали) клеточки . Докажите , что после этого остается по крайней мере одна пустая клеточка .
13. На волшебство-яблоне растут бананы и ананасы. За один раз разрешается сорвать с нее два плода. Если сорвать два банана либо два ананаса, то вырастет еще один ананас, а если сорвать один банан и один ананас, то вырастет один банан. В итоге остался один плод. Какой это плод, если понятно, сколько бананов и ананасов росло вначале?
Решение.
Четность числа бананов не изменяется, если число бананов было четным, то оставшийся плод ананас, если число бананов было нечетным, то - банан.
14. На прямой стоят две фишки: слева красная, справа синяя. Разрешается создавать всякую из двух операций: вставку двух фишек одного цвета подряд (меж фишками либо с краю) и удаление пары соседних одноцветных фишек (меж которыми нет остальных фишек). Можно ли с помощью таковых операций бросить на прямой ровно две фишки: слева синюю, а справа красную?
Решение.
Рассмотрим число разноцветных пар (не лишь соседних), где левая фишка красная, и заметим, что четность этого показателя не изменяется. Но в исходной ситуации наш показатель равен 1, а в хотимой ситуации - нулю. Поэтому перейти к хотимой ситуации нереально.
15. На полуострове Серобуромалин живут хамелеоны: 13 серых, 15 бурых и 17 малиновых. Если 2 хамелеона различных цветов встречаются, то они оба меняют свой цвет на третий. Может ли случиться, что в некий момент все хамелеоны на полуострове станут одного цвета?
Указание.
Рассмотрите остатки от деления чисел Б бурых, С серых и М малиновых хамелеонов на 3 и проверьте, что попарные разности у этих остатков не изменяются.
16. Докажите, что в игре «15» нельзя поменять местами фишки «15» и «14», оставив другие на месте.
мысль решения.
Рассмотрим «пустое поле» как отдельную фишку. Мы можем лишь поменять «пустую фишку» с соседними. Поскольку пустая фишка обязана попасть на исходное поле, число наших операций обязано быть четным. Поэтому мы можем получить конфигурации, отличающиеся от начальной лишь четным числом перестановок.
17. На 44 деревьях, расположенных по кругу, посиживали по веселому чижу. Время от времени какие-то два чижа перелетают на соседнее дерево - один по часовой стрелке, а другой - против. Могут ли все чижи собраться на одном дереве?
Решение.
Пронумеруем деревья по кругу с 1-го по 44-е. Сумма номеров деревьев, на которых посиживают чижи или не изменяется, или миниатюризируется на 44, или возрастает на 44. Тем самым, остаток от деления данной суммы номеров на 44 не изменяется. Вначале этот остаток равен 22, а если все чижи усядутся на одно дерево, то он будет равен нулю. Поэтому чижи не сумеют собраться на одном дереве.
18. Можно ли разрезать выпуклый 17-угольник на 14 треугольников?
общественная постановка задачки.
При помощи инвариантов решаются задачки следующего типа: даны мно-жество М (элементы его мы будем именовать «позициями») и правило, по которому разрешается переходить от одной позиции к другой; можно ли из данной позиции а перейти за не-сколько шагов в другую данную пози-цию p? Более общественная задачка: как. Для случайной пары позиций а, p уста-новить, можно ли из а за несколько шагов перейти в р?
разумеется, описанные ситуации об-ладают следующим свойством: если из позиции a можно перейти в пози-цию р и из p можно перейти в пози-цию h, то из a можно перейти в h. Это свойство именуется транзитив-ностью.
Рассмотрим конкретную задачку.
задачка 1. Круг разделен на n секторов, в которых как-то расстав-лены n фишек. Разрешается одно-временно передвинуть любые две фиш-ки: одну -- на один сектор по часовой стрелке, другую -- на один сектор в противоположном направлении. Мож-но ли из позиции M, в которой в каж-дом секторе стоит' по одной фишке, перейти к позиции V, в которой все фишки собраны в каком-нибудь од-ном секторе?
В данной задачке, не считая характеристики транзитивности, имеет место также следующее принципиальное свойство: если из позиции a можно перейти в пози-цию р, то и из р можно перейти в a. Это свойство именуется симмет-ричностью.
Свойство симметричности соблю-дается не во всех задачках рассмат-риваемого типа; к примеру, в шах-матах пешки назад не ходят. В данной статье мы ограничимся задачками, для которых условие симметричности выполнено.
Условимся считать, что из хоть какой позиции a можно «перейти» в нее же. Это свойство именуется рефлексив-ностью.
Назовем позиции a и p эквива-лентными, если по заданным прави-лам из a можно перейти в p (ввиду предположенной симметричности это равносильно тому, что из p можно пе-рейти в a). Эквивалентность позиций a и p мы будем обозначать так: a~ p; неэквивалентность -- так: a ~/ p.
Поскольку эквивалентность позиций рефлексивна, симметрична и транзитивна, исходное множество М разбивается на непустые непересекающиеся подмножества (рис. 1): М = M1UM2UM3U... В каждом из подмножеств Mi, все позиции экви-валентны: если a из Мi, и p из Mi, то a~ p. Если же позиции a и p принадлежат различным подмножест-вам: a из Mi p из Mj ( i непревзойденно от j ), то a и p не эквивалентны ). Подмножества Мi мы будем именовать орбитами. Повторим еще раз: если мы находимся в позиции a, принадлежащей какой-нибудь орбите Mi, то мы можем, перемещаясь по данной орбите, пере-браться из позиции a в всякую другую позицию, принадлежащую орбите. С другой стороны, сойти с данной орбиты, т. Е. Перебраться с по-зиции a на позицию p, принадлежа-щую хоть какой другой орбите, мы не можем. Орбит может быть как конечное, так и нескончаемое число. Впрочем, если множество М естественно, то, ра-зумеется, и число орбит естественно. Инвариант. Числовая функция f, определенная на множестве «позиций» M, назы-вается инвариантной функцией, либо инвариантом, если на эквивалент-ных позициях она воспринимает одина-ковые значения: если a~ р, то f(а) = f(р). (1)
задачка 1 (продолжение). Пусть п = 2т. Раскрасим секторы через один в серый и белый цвет. Тогда при каждом перемещении число фишек в белых секторах или не изменяется (рис. 2), Или увеличи-вается на 2 (рис. 3), Или умень-шается на 2 (рис. 4). Для случайной расстановки a фишек по секторам обозначим через б (а) число фишек в белых секторах. Рассмотрим сейчас такую функцию g.
0, если б (a) четно,
g(a) =
1, если б (a) нечетно.
Из произнесенного выше вытекает, что эта функция g (четность числа фишек в белых секторах) является инвариан-том. Поскольку п = 2т, для конеч-ной позиции v имеем g(v) = 0. Если т = 2k+ 1, то n/2 нечетно. Означает, для начальной позиции w имеем g(w) =1. Из того, что g(w) непревзойденно от g(v) вытекает, что позиции w и v не эквивалентны. Таковым образом, в этом случае
(п = 2 т, т = 2 k + 1) из позиции w нельзя перейти в пози-цию v. Ну, а если т =2 k? Тогда n/2 четно и g(w) = g(v) = 0. В этом случае инвариант g не дает способности установить эквивалентны позиции w и v либо нет.
Дело в том, что если f - инвариант, то из f(a.) = f(p), вообще говоря, ничего не вытекает. Если f(a) непревзойденно от f(p) то позиции а и p не эквивалентны (это следует из (1)). Если же f(a) = f(p), то позиции а и р могут быть как эквивалентными, так и не эквива-лентными: инварианту не запрещается на различных орбитах воспринимать однообразные зна-чения. (К примеру, неизменная функция, т. Е. Функция, которая на всех элементах из М воспринимает одно и то же значение, тоже инвариантна.)
Как же быть? Попытайтесь для какого-нибудь п вида 4k перейти от позиции w, к позиции v... Почему-то не удается. Попробуем отыскать другой , более узкий инвариант.
Занумеруем секторы (скажем, по часовой стрелке) от 1 до n. Для про-извольной расстановки а.фишек по секторам обозначим через xk (а) количество фишек в k-м секторе при расстановке a.
Рассмотрим сейчас такую функцию q:
q (a)= 1 x1 (a) + 2 x2 (a) +3x3(a) +
+ ... + n xn(a). (2)
Является ли функция q инвариантом?
случайное допустимое переме-щение (рис. 5) Затрагивает 4 слагае-мых суммы (2):
... + i xi (a) + (i + 1) xi+1 (a) + ...+ (j - 1) xj -1(a) + j x j(a)+ … (3)
При перемещении , изображенном
... + i [xi(a) - 1] + (i + 1) [xi+1(a) + 1]+
+…+(j - 1) [xj-1(a) + 1] + j [x j (a) - 1] +…
просто проверяется, что обе суммы равны. Итак, q - инвариант! Нет,
мы забыли, что n-й сектор граничит с первым. Означает, есть еще 3 возмож-ности. Подсчет, аналогич-ный лишь что произведенному, показы-вает, что в случае, изображенном на рис. 6, q (a) уменьшится на п, а в случае возрастет на п. В третьем случае q (а), естественно, не поменяется. Итак, за одно переме-щение значение функции q может поменяться, но лишь на п. Следовательно, функция r, значение которой на расстановке a равно остатку. От деления числа q (a) на п, есть ин-вариант.
Для позиции v (если все п фишек собраны в 1-м секторе)
x1(v) = x2(v) =…= xl -1(v) = xl+1(v) = …=xn (v) = 0,
xl(v) = n.
означает, q (v) = l n и r (v) = 0 (каковы бы ни были п и l ). С другой стороны,
x1(w) = x2(w) =…= xn(w) = 1. означает, q(w) = 1 + 2 + 3 +…+ n = (n(n+1))/2
Если n = 2m, то q(w) = nm + m и r(w) = т =/0 . Сле-довательно, при четном п получаем r(w) =/ r(v). Итак, при четном п по-зиции w и v не эквивалентны.
Если же п = 2т + 1, то q(w) = n(m + 1) и r(w) = 0. таковым образом, при нечетном п мы опять имеем: r (и) -- r (v). выходит, что при нечетном п вопрос об эквива-лентности позиций w и v опять остается открытым.
Универсальный инвариант
Назовем инвариант 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 не равном п:
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) -= 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 -- инвариант, a f -- универсаль-ный инвариант, то существует таковая число-вая функция 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= 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> реальных чисел. Раз-решены переходы
< x, y, z > <y, x, z > и <x, y, z > < x, z, y >. Пусть
f1( x, y, z ) = xyz,
f2 (x, y, z) = ху + уz + zх,
f3(x, y, z ) = х + у + z.
Доказать, что <f1, f2, f3> -- полная система инвариантов.
1.31. Множество М состоит из всевозможных наборов (либо кор-тежей) <х1, x2, x3, …, xn> реальных чисел (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.
Решение.
|
