Нестандартные задачи по математике
Инварианты. Полуинвариант. Методы решения задач при помощи инвариантов. эквивалентность позиций. Инвариантная функция. Универсальный инвариант. Полная система инвариантов. Четность плюс инвариант. Теория графов, ее применение для решения задач.
| Рубрика | Математика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 12.11.2008 |
| Размер файла | 73,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Курсовая работа по математике
Нестандартные задачи по математике
Студент: Игнатьева Ольга Михайловна
физико - математический факультет 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.
Решение.
Подобные документы
Изучение нестандартных методов решения задач по математике, имеющих широкое распространение. Анализ метода функциональной, тригонометрической подстановки, методов, основанных на применении численных неравенств. Решение симметрических систем уравнений.
курсовая работа [638,6 K], добавлен 14.02.2010Структура текстовой задачи. Условия и требования задач и отношения между ними. Методы и способы решения задач. Основные этапы решения задач. Поиск и составление плана решения. Осуществление плана решения. Моделирование в процессе решения задачи.
презентация [247,7 K], добавлен 20.02.2015Теория инвариантов уравнения линии второго порядка от трех переменных, определение канонического уравнения. Общий пример решения задачи на определение вида и расположения поверхности, заданной относительно декартовой прямоугольной системы координат.
курсовая работа [1,1 M], добавлен 02.06.2013Способы решения логических задач типа "Кто есть кто?" методами графов, табличным способом, сопоставлением трех множеств; тактических, истинностных задач, на нахождение пересечения множеств или их объединения. Буквенные ребусы и примеры со звездочками.
курсовая работа [622,2 K], добавлен 15.06.2010Методы решения задач с экономическим содержанием повышенного уровня сложности. Выявление структуры экономических задач на проценты. Вывод формул для решения задач на равные размеры выплат. Решение задач на сокращение остатка на одну долю от целого.
курсовая работа [488,3 K], добавлен 22.05.2022Общая характеристика графов с нестандартными достижимостями, их применение. Особенности задания, представления и разработки алгоритмов решения задач на таких графах. Описание нового класса динамических графов, программной реализации полученных алгоритмов.
реферат [220,4 K], добавлен 22.11.2010Понятия максимума и минимума. Методы решения задач на нахождение наибольших и наименьших величин (без использования дифференцирования), применение их для решения геометрических задач. Использование замечательных неравенств. Элементарный метод решения.
реферат [933,5 K], добавлен 10.08.2014Граф как множество вершин (узлов), соединённых рёбрами, способы и сфера их применения. Специфика теории графов как раздела дискретной математики. Основные способы преобразования графов, их особенности и использование для решения математических задач.
курсовая работа [1,8 M], добавлен 18.01.2013Теория графов как математический аппарат для решения задач. Характеристика теории графов. Критерий существования обхода всех ребер графа без повторений, полученный Л. Эйлером при решении задачи о Кенигсбергских мостах. Алгоритм на графах Дейкстры.
контрольная работа [466,3 K], добавлен 11.03.2011Систематизация различных методов решения планиметрических задач. Обоснование рациональности решения планиметрической задачи методами дополнительных построений, подобия треугольников, векторного аппарата, соотношения углов и тригонометрической замены.
реферат [727,1 K], добавлен 19.02.2014
