Нестандартные задачи по математике

Из приведенного решения видно, что если числа х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 дадим корзинам А и Б ( в любом порядке ).

 Скачать реферат