Нестандартные задачи по математике
Из приведенного решения видно, что если числа х0, х1, х2 имеют одну и ту же четность, то мы не сможем добиться, чтобы на доске осталась одна-единственная цифра. Докажите, что если среди чисел х0, х1 х2 есть как четные, так и нечетные, и, кроме того, хотя бы два из них отличны от нуля, то существует такой порядок стираний, что в результате на доске останется' одна цифра.
Изменим условие зада
чи 3: потребуем, .чтобы одни и те же две неравные цифры стирались два раза, а вместо них записывалась одна цифра, отличная от стертых. Предположим, что снова после некоторого числа операции на доске осталась одна-единственная цифра. Можно ли заранее, по числу нулей, единиц и двоек, предвидеть, какая это цифра?
Рассуждение с четностью здесь не помогает, ибо в результате выполнения каждой операции одно из чисел х0, х1, x2 меняет свою четность, а два других сохраняют четность, так что числа, имевшие разную четность, могут теперь получить одну и ту же четность. Однако можно заметить, что остатки от деления чисел х0, х1, х2 на 3 изменяются каждый раз таким образом, что равные остатки остаются равными, а неравные остаются неравными. Дальнейшие рассуждения повторяют решение задачи 3.
2.13. В каждой клетке таблицы 8х8 написано некоторое целое число. Разрешается выбирать в таблице любой квадрат размерами 3х3 или 4х4 и увеличивать на единицу все стоящие в клетках выбранного квадрата числа. Всегда ли можно с помощью таких операций преобразовать исходную таблицу в таблицу, у которой вес числа делятся на З?
Решение.
Нет, не всегда. Найдем сумму чисел, написанных в заштрихованных на рисунке 6 клетках. Поскольку любой квадрат размерами 4х4 содержит 12 заштрихованных клеток, а квадрат размерами 3х3— 6 или 9 таких клеток, то в результате описанной операции остаток от деления на 3 этой суммы (чисел, стоящих в заштрихованных клетках) не будет меняться. Поэтому, если с самого начала найденная сумма не делится на 3, то среди заштрихованных клеток все время будут сохраняться клетки, в которых написанные числа не кратны трем.
2.14.Из всякой ли таблицы можно в условиях задачи 4 получить таблицу, не содержащую четных чисел?
2.15.Числа I, 2, 3, , n расположены в некотором порядке. Разрешается менять местами любые два рядом стоящих числа. Докажите, что если проделать нечетное число таких операций, то наверняка получится отличное от первоначального расположения чисел 1, 2, 3, .,n.
Решение.
Пусть a1, a2,…, an— произвольная перестановка из чисел 1, 2, 3, ., п. Будем говорить, что числа аi, и аj, образуют в этой перестановке инверсию, если i<j, но ai>aj, то есть большее из этих чисел предшествует меньшему. Поменяв местами два соседних числа в перестановке, мы увеличим или уменьшим число инверсий на 1. Проделав же нечетное число таких операций, мы изменим четность числа инверсий, а значит, изменим и перестановку.
2.16.Докажите, что утверждение задачи 2.15 останется справедливым, если разрешить менять местами любые два числа в перестановке.
Указание.
Докажите, что любые два числа можно поменять местами, проделав нечетное число раз операцию, описанную в задаче 2.12.
Переход от одной перестановки чисел 1, 2, 3, п к другой перестановке этих чисел, при котором какие-нибудь два числа меняются местами, а остальные остаются на месте, называется транспозицией. Результат задачи 2.16 можно сформулировать так: выполнив нечетное число транспозиций, мы изменим перестановку
2.17. В различных пунктах кольцевого автодрома в одно и то же время в одном направлении стартовали 25 автомобилей. По правилам гонки автомобили могут обгонять друг друга, но при этом запрещен двойной обгон. Автомобили финишировали одновременно в тех же пунктах, что и стартовали. Докажите, что во время гонки было четное число обгонов.
Решение.
Окрасим один из автомобилей в желтый цвет, а остальным автомобилям присвоим номера 1, 2, 3, ., 24 в том порядке, в каком они располагаются на старте за желтым автомобилем. В центре автодрома установим световое табло, на котором после каждого обгона будем указывать номера автомобилей в том порядке, в каком они следуют за желтым автомобилем. Тогда обгон, в котором не участвует желтый автомобиль, приводит к тому, что на световом табло меняются местами два соседних числа.
Посмотрим, что произойдет, если какой-нибудь автомобиль обгонит желтый. Если перед этим обгоном числа на табло образовывали перестановку а1, а2,…, а24 , то после обгона они образуют перестановку а2, а3,…, а24, а1. Заметим, что к такой же перестановке можно прийти, выполнив последовательно 23 транспозиции: а1, а2, а3,…, а24 à а2, а1, а3,…, а24 à а2, а3, а1,…, а24 à а2, а3, а1,…, а24 à… à а2, а3,…,а1, а24 à а2, а3,…, а24, а1
Если же желтый автомобиль совершил обгон, то из перестановки а1, а2, ., а24 получим перестановку а24, а1, а2, а3,…, а23. Этот переход также можно заменить двадцатью тремя транспозициями.
Таким образом, любой обгон сводится к нечетному числу транспозиций. Если бы общее число обгонов было нечетным, то нечетным оказалось бы и общее число транспозиций. Остается воспользоваться результатом задачи 2.16.
3. Графы
Графом на плоскости называется конечное множество точек плоскости, некоторые из которых соединены линиями. Эти точки называются вершинами графа, а соединяющие их линии – ребрами. Число ребер, исходящих из вершины графа, называется степенью этой вершины.
С графами мы встречаемся чаще , чем это, возможно, кажется на первый взгляд. Примерами графа может служить любая карта дорог, электросхема, чертеж многоугольника и т. д.
Теория графов возникла в 1736 г., когда Леонард Эйлер опубликовал первую статью о графах. Начиналась она с разбора широко известной теперь задачи о кенигсбергских мостах. Долгое время считалось, что теория графов применяется главным образом для решения логических задач, а сама теория рассматривалась как часть геометрии. Однако в ХХ веке были найдены широкие приложения теории графов в экономике, биологии, химии, электронике, сетевом планировании, комбинаторике и других областях науки и техники. В результате она стала бурно развиваться и превратилась в самостоятельную разветвленную теорию.
Задачи на соответствие между множествами .
3.1.В пяти корзинах А, Б, В, Г и Д лежат яблоки пяти разных сортов. В каждой из корзин А и Б находятся яблоки 3-го и 4-го сорта, в корзине В – 2-го и 3-го , в корзине Г – 4-го и 5-го, в корзине Д – 1-го и 5-го. Занумеруйте корзины так, чтобы в корзине №1 имелись яблоки 1-го сорта ( по меньшей мере одно ), в корзине №2 – яблоки 2-го сорта и т. Д
Решение.
Изобразим два множества множество корзин и множество их номеров. В каждом из этих множеств по пять элементов обозначим их точками
Установим соответствие между этими двумя множествами так, чтобы условия задачи выполнялись. Будем соответствующие элементы двух множеств соединять сплошными линиями, а не соответствующие – пунктирными или совсем не соединять. Так как яблоки первого сорта лежат только в корзине Д, то именно этой корзине и нужно дать номер 1; проведем сплошную линию между точками Д и 1. Далее номер 2 можно присвоить только корзине В, а после этого номер 5 – лишь корзине Г. Наконец, номера 3 и 4 дадим корзинам А и Б ( в любом порядке ).
Другие рефераты на тему «Математика»:
Поиск рефератов
Последние рефераты раздела
- Анализ надёжности и резервирование технической системы
- Алгоритм решения Диофантовых уравнений
- Алгебраическое доказательство теоремы Пифагора
- Алгоритм муравья
- Векторная алгебра и аналитическая геометрия
- Зарождение и создание теории действительного числа
- Вероятностные процессы и математическая статистика в автоматизированных системах