Дискретно-непрерывная математика (стр. 43 )

а)

б) Пусть А=(а;α), В = (b; (β)— точки с целочисленными координатами, причем b>а≥0, α>0, β>0, a А'=(a; -α) — точка, симметричная А относительно оси ОХ. Доказать, что число траекторий из А в В равно числу траекторий из А' в В.

в) Пусть х > 0, у > 0. Доказать, что число всех траекторий из (0; 0) в (х; у), не имеющих вершин на оси ОХ, равно

г) Доказать, что среди Тп,0 траекторий, которые соединяют (0; 0) с (п; 0), существует:

1) ровно траекторий, не имеющих вершин на оси ОХ, кроме крайних точек (0; 0) и (п; 0);

2) ровно траекторий, которые не пересекают ось ОХ.

26. а) Доказать, что среди любых шести человек обнаружится или трое знакомых или трое незнакомых.

б) Если 17 ученых состоят в переписке друг с другом по трем различных научным темам, причем каждая пары ученых ведет переписку лишь по одной теме, то всегда найдутся трое ученых, переписывающиеся по одной и той же теме. Доказать это.

в) Пусть ап - последовательность натуральных чисел, которая образована по следующему закону:

Предположим, что есть ап+1 точек, никакие три из которых не лежат на одной прямой. Каждые две точки соединены отрезком одного из п цветов. Доказать, что существует треугольник с вершинами в данных точках, стороны которого имеют один и тот же цвет.

г) Доказать, что

где е — основа натуральных логарифмов.

27. Рассмотрим на плоскости множество точек, никакие три из которых не лежат на одной прямой; соединим каждые две точки отрезком одного из цветов — красного или черного. Пусть l(k, m) - наименьшее натуральное число такое, что среди любых l(k, m) точек найдется или k точек, соединенных красными отрезками, или m точек, соединенных черными отрезками. Доказать,

Микромодуль 18

Алгоритмы комбинаторики

5.13. Расписания - как примеры комбинаторных

задач

1. Календарное планирование. Вся человеческая деятельность планируется во времени: без этого невозможна координированная работа предприятий и производственных участков, по графику идет строительство большой электростанции и детской спортивной площадки, строго во времени расписанны исследования, проведимые космонавтами на борту орбитальной станции, даже время выхода из дома на работу и рабочие, и служащие, и ученые, и инженеры определяют, руководствуясь графиком работы городского транспорта или движения пригородных поездов.

Расписание - это синоним организованности, одно из важнейших средств эффективного выполнения любого рода деятельности, любого рода работ. Чем лучше составлено расписание, тем выше производительность работы, тем меньше затраты (особенно «нервной энергии»), которые связаны с той или иной деятельностью, тем лучше и сами достигаемые результаты, и условия их достижения.

Так что расписания необходимо уметь составлять, да и притом возможно лучше — оптимально, как говорят математики.

Расписания — и часто неплохие — люди научились составлять давно, но составление оптимального расписания стало возможным с тех пор, как к этой работе были привлечении электронные вычислительные машины. Правда, помощь ЭВМ требуется в составлении расписаний для сравнительно сложных комплексов работ, оптимальные расписания для многих простых случаев можно составить и, как говорят, вручную. Однако для этого прежде всего необходимо поставить задачу составления оптимального расписания как математическую задачу, и хотя это сделать довольно просто, но на первый взгляд все же неочевидно.

2. Формулирование математических задач. Начиная c первого класса, люди привыкают думать о задаче как о требовании найти некоторое неизвестное поначалу число, которое удовлетворяет условиям задачи. Выраженные словами условия задачи необходимо перевести на язык алгебраических формул, которые связывают обозначаемое через х неизвестное с исходными данными некоторой «цепочкой отношений» (уравнений, преобразований). Проложив такую «цепочку отношений» от исходных данных к неизвестному, не так уже вычислить вычислить и само неизвестное.

Пример. Поезд шел со скоростью 36 км/ч, затем на перегоне, равном 1,5 км, поезд шел равноускоренно с ускорением 0,1 м/сек2. Найти время, в течение которого поезд прошел перегон.

Очевидно, что легко связать слово «равноускоренно» с формулой

и обнаружить, что S, v0, а задыны условиями задачи, составить уравнение

и найти t, правильно применяя формулу решения квадратного уравнения к нашему случаю

(5.43)

учтя при этом, что t≥0.

Решения, подобные (5.43), где представлен способ решения задачи (связывающая с неизвестным исходные данные, замененные буквами, «цепочка отношений») без выполнения самых вычислений, называют, решениями в общем виде, формульными решениями.

Решение некоторой задачи в общем виде, которое составлено в форме четкой инструкции, точно следуя которой получают однозначный правильный ответ в каждом конкретном случае (при подстановке исходных данных), называют алгоритмом.

В начальной математике, где приходится решать сравнительно простые задачи, не предъявляется сколько-нибудь серьезных требований к строгости, единообразию и обозримости представления способа решения задачи — разговор заходит разве что об аккуратности записи отыскания конечного результата.

Алгоритмы решения задач будем записывать с помощью блок-схем (образец блок-схемы представлен на рис. 5.13).

Рис. 5.13. Блок-схема алгоритма вычислении произведения первых N натуральных чисел.

В так называемых «задачах на доказательство» — обычно некоторого тождества – требовалось проложить «цепочки отношений», связывающие элементарными преобразованиями левые и правые части равенств. Это те же задачи, но как бы с известными ответами. В задачах на построение в геометрии нужно было найти некоторый неизвестный графический объект, определенной условиями задачи конфигурации (окружность, треугольник, угол и т. п.). Здесь объект поиска - не число, более того, здесь обычно еще требуется выполнить построение с помощью некоторых инструментов - например, одного циркуля или одной линейки.

Общим для этих рассмотренных типов задач является то, что с самого начала известно, к какому классу принадлежат искомые объекты (первый - к числам, второй - геометрическим фигурам), с помощью каких операций (арифметических вычислений или вычерчиваний) можно найти эти объекты. Расписания мы тоже поначалу будем формально представлять, а потом уже - строить.

3. Представление расписаний. Существуют различные способы представления расписаний - достаточно вспомнить университетские расписания, футбольный календарь или программу телевидения.

На рис. 5.14 и рис. 5.15 изображенны два способа графического представления расписаний: в первом случае - в виде временной диаграммы, во второму - в виде сетевого графика.

На временных диаграммах наглядно отображается выполнение некоторой задачи во времени, при этом все выполнение задачи разбивается на отдельные этапы — работы, каждая отдельная работа представляется отрезком, по длине равным продолжительности выполнения работы в выбранном масштабе времени. На диаграмме начало отрезка соответствует моменту времени начала работы, конец отрезка - моменту окончания работы.

Рис. 5.14. Примерная временная диаграмма подготовки произведения по украинской литературе.

1. Продумывание темы, основных высказываемых мыслей, наметка плана произведения. 2. Просмотр литературы, подбор материалов, эпиграфа, цитируемых высказываний. 3. Составление подробного огдавления, плана - по абзацам. 4. Окончательный подбор материалов, высказываний, цитат согласно плану, шлифовка плана произведения по абзацам. 5. Печатание черновика. 6. Перепечатка набело, проверка произведения.

Сетевым графиком (или стрелочной диаграммой) обычно представляют логическую взаимосвязь во времени отдельных работ, на которые разбивается выполнение некоторой задачи. На рис. 5.15 сетевой график представлен в так называемой форме «вершины-работы». На рисунке кружочками, называемыми вершинами сетевого графика, обозначены отдельные работы, на которые расчленяется общий комплекс работ, стрелочки информируют о взаимозависимости очередности выполнения работ. Так из рис. 5.15 видно, что приступить к выполнению работы 5 следует (разумно, дóлжно) только после того, как выполнены работы 2 и 3.

Рис. 4.15. Сетевой график подготовки вечера, посвященного творчеству драматурга.

1. Предварительное обсуждение программы вечера, выделение ответственных по разделам. 2. Определение индивидуальных исполнителей, продумывание их выступлений. 3. Обсуждение плана подготовки сцен из пьес драматурга, подбор исполнителей. 4. Выяснение вопроса о возможности приглашения на вечер известных поэтов, артистов, демонстрации документального кинофильма. 5. Составление плана обеспечения вечера (оформление зала, реквизит для спектакля). 6. Окончательное обсуждение и согласования программы и сроков проведения вечера, списка приглашений. 7. Подготовка индивидуальных выступлений. 8. Репетиции индивидуальных выступлений. 9. Подготовка ролей в спектаклях. 10. Первая репетиция сцен. 11. Вторая репетиция сцен. 12. Подготовка костюмов. 13. Подготовка декораций и стендов для оформления зала. 14. Оформление зала. 15. Генеральная репетиция. 16. Доставка кинофильма. 17. Приглашение на вечер. 18. Проведение вечера.