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.
Решение.
Пусть 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 дадим корзинам А и Б ( в любом порядке ).
Ответ: корзины расположились, начиная с №1, в последовательном порядке Д, В, А, Б, Г или в порядке Д, В, Б, А, Г.
3.2. Петр, Геннадий, Алексей и Владимир занимаются в одной детской спортивной школе в разных секциях: гимнастики, легкой атлетики, волейбола и баскетбола. Петр, Алексей и волейболист учатся в одном классе. Петр и Геннадий на тренировки ходят пешком вместе, а гимнаст ездит на автобусе. Легкоатлет не знаком ни с волейболистом, ни с баскетболистом. Кто в какой секции занимается?
3.3.Футбольные команды пяти школ города учавствуют в розыгрыше кубка. В финал кубка выходят две команды. До соревнований пять болельщиков высказали прогнозы, что в финал выйдут команды: