Нестандартные задачи по математике
Курсовая работа по математике
Нестандартные задачи по математике
Студент: Игнатьева Ольга Михайловна
физико – математический факультет 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. Даны