Решение математических задач комбинаторными методами

Размещено на http://www.allbest.ru/

Введение

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

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

Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие в первую очередь умения рассчитывать, составлять планы и опровергать планы противника. Среди предметов, положенных в пирамиду, где 35 веков тому назад был похоронен египетский фараон Тутанхамон, нашли разграфленную доску с тремя горизонталями и 10 вертикалями и фигурки для древней игры "сенет", правила которой мы, вероятно, никогда не узнаем. Позже появились нарды, шашки и шахматы, а также их различные варианты (китайские и японские шахматы, японские облавные шашки "го" и т.д.). В каждой из этих игр приходилось рассматривать различные сочетания передвигаемых фигур, и выигрывал тот, кто их лучше изучил, знал выигрывающие комбинации и умел избегать проигрывающих.

Первое упоминание о вопросах, близких к комбинаторным, встречается в китайских рукописях, относящихся к XII - XIII вв. до н. э. (точно датировать эти рукописи невозможно, поскольку в 213 г. до н. э. император Цин Шихуан приказал сжечь все книги, так что до нас дошли лишь сделанные позднее копии). В этих книгах писалось, что все в мире является сочетанием двух начал - мужского и женского, которое авторы обозначали символами инь-янь. В рукописи "Же-ким" ("Книга перестановок") показаны различные соединения этих знаков по два и по три. Восемь рисунков из трех рядов символов изображали землю, гору, воду, ветер, грозу, огонь, облака и небо (некоторые рисунки имели и иные значения). Неудивительно поэтому, что сумма первых 8 натуральных чисел (т.е. число 36) воплощала в представлениях древних китайцев весь мир.

По мере углублений знаний понадобилось выразить и другие элементы мироздания с помощью тех же знаков инь-янь. Были составлены 64 фигуры, содержащие уже пять рядов черточек. Надо полагать, что автор рукописи "Же-ким" заметил удвоение числа рисунков при добавлении одного ряда символов. Это можно рассматривать как первый общий результат комбинаторики.

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

492

357

816

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

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

По комбинаторике различное множество интересных задач, но наиболее интересной и актуальной, нам показалась, тема «Очередь в кассу»

Цель данной работы: В данной работе мы рассмотрим общую задачу «Очередь в кассу», а также «Очереди и свойства сочетаний», «Блуждания по бесконечной плоскости» и на их примере решим задачи из этой области.

комбинаторика ломаный сочетание плоскость

1. Очередь в кассу

У кассы кинотеатра стоит очередь из m+ k человек, причем m человек имеют рубли, a k -- полтинники {монеты по 50 копеек). Билет в кино стоит 50 копеек, и в начале продажи билетов касса пуста. Сколькими способами могут располагаться в очереди люди с рублями и полтинниками так, что очередь пройдет без задержки, т. е. никому не придется ждать сдачу!

Например, если m = k = 2, то благоприятными будут лишь два случая: прпр и ппрр, где буква «п» означает полтинник, а буква «р» -- рубль. В четырех же случаях -- ррпп, рпрп, рппр и пррп -- возникает задержка. В первых трех случаях уже первый зритель не сможет получить сдачи, а в последнем случае у кассы задержится третий зритель.

При небольших значениях m и k задачу можно решить прямым перебором. Но если m и k сравнительно велики, то прямой перебор не поможет. Ведь число различных перестановок из m рублей и k полтинников равно P(m,k)= Уже при m = k = 20 число перестановок из 20 рублей и 20 полтинников равно , а это число больше ста миллиардов.

Итак, нам надо решить следующую комбинаторную задачу.

Найти число перестановок с повторениями из m рублей и k полтинников, таких, что для любого r, 1? r ? m+k, число полтинников среди первых r элементов перестановки не меньше числа рублей.

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

Как и во многих комбинаторных задачах, здесь полезно использовать геометрическую иллюстрацию. Возьмем координатную сетку и будем изображать каждую перестановку рублей и полтинников ломаной, соединяющей узлы сетки по следующим правилам: ломаная начинается в начале координат О(0; 0); каждому полтиннику соответствует звено ломаной, идущее вверх направо, а каждому рублю -- звено, идущее вверх налево (звено соединяет противоположные точки одного из квадратов координатной сетки). Например, последовательности соответствует ломаная, изображенная на рис. 1.

Ясно, что если в последовательности имеется m рублей и к полтинников. то концом ломаной окажется точка А(к - т; к + т). Число ломаных, ведущих из точки О в точку А, равно числу перестановок с повторениями из т рублей и k полтинников, т. е. Р(т, к). Выясним теперь, чем характеризуются ломаные, удовлетворяющие условию задачи. Если очередь в какой-то момент времени застопорилась, то это значит, что число рублей к этому моменту оказалось на 1 больше числа полтинников. Но тогда точка, движущаяся по ломаной, сделает влево на один шаг больше, чем вправо, и окажется на прямой x = -1 (для ломаной на рис. 1 на этой прямой лежит точка В(-1; 7); она указывает, что очередь остановится на 7-м шагу). Итак, всем перестановкам, при которых очередь останавливается и какой-то момент, соответствуют ломаные, имеющие точки на прямой х = -1. Обратно, если у ломаной есть точка на этой прямой, то очередь остановится.

Мы пришли, таким образом, к следующей геометрической задаче: найти число ломаных указанного вида, не пересекающих прямую X = -1.

Здесь, как часто бывает в комбинаторных задачах, выгоднее искать число «неблагоприятных» случаев, т. е. случаев, когда очередь задерживается. Если мы найдем это число, то, вычтя его из числа Р(к, т) = C. всех перестановок т рублей и k полтинников (общего число ломаных), получим ответ для нашей задачи.

Значит, получилась задача об отыскании числа ломаных, пересекающих прямую х = -1. Но если ломаная L пересекает прямую х =-1, то ее можно преобразовать следующим образом: взять наивысшую точку пересечения и часть ломаной L выше этой точки симметрично отразить в прямой х = -1. Такое преобразование ломаной L в Lґ показано на рис. 2. При этом преобразовании точка A(k - m; k + т), лежащая справа от прямой х = -1, переходит в симметричную ей точку А'(т - к - 2; к + m), лежащую слева от прямой х = -1. Таким образом, каждому пути из О в А, пересекающему прямую х = -1, соответствует путь из О в А'. Обратно, если ломаная Lґ ведет из О в А', то она по дороге должна хотя бы один раз пересечь прямую .x = -1 и, значит, может быть получена описанием выше образом из ломаной, соединяющей О с А и пересекающей указанную прямую.

Итак, число ломаных, соединяющих О с А и пересекающих прямую х = -1, равно числу ломаных, ведущих из О в А'.

Сосчитать же число ломаных, ведущих из О в А', совсем легко -- координаты точки А' равны т - к - 2 и к + т, a поэтому у такой ломаной должно быть к + 1 звеньев, направленных влево, и т - 1 звеньев, направленных вправо. Значит, общее число этих ломаных равно P(k +1, m - 1). Число же ломаных, не пересекающих прямую х = -1, выражается формулой

(1)

Итак, количество очередей, при которых не происходит задержки, равно ,где k- число полтинников, т - число рублей. В частности, если k=т, то очередь пройдет без задержки в случаях и задержится в случаях. При больших k= т очередь чаще всего задержится. Наша задача полностью решена.

Рассмотрим теперь некоторое обобщение этой задачи.

Кассир был предусмотрителен и в начале продажи билетов в кассе уже лежало q полтинников. Во скольких случаях пройдет без задержки очередь, состоящая из т обладателей рублей и к обладателей полтинников?

Геометрическое представление этой задачи будет почти таким же. Только запретной прямой теперь будет прямая х = - q - 1 (наличие q полтинников в кассе позволяет ломаной уклониться на q единиц влево без задержки очереди, а уклониться на q+ 1 единиц оно уже не имеет права). Поэтому теперь А'(т - к - 2q - 2; к + т), у Lґ звеньев влево к + q + 1, звеньев вправо т - q - 1, число неблагоприятных перестановок будет P(k + q+ 1, т - q - 1), а число благоприятных равно

(2)

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

Если же т > k + q, то очередь наверняка задержится -- общего числа полтинников в кассе и в очереди не хватит, чтобы дать сдачу всем владельцам рублей.

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

Сколькими способами можно расставить обладателей т рублей и k полтинников так, чтобы в любой момент (исключая, быть может, начальный и конечный) в кассе был хотя бы один полтинник?

Эта задача тоже решается методом подсчета ломаных. Но теперь надо искать ломаные, пересекающие прямую х = 0 лишь в начале координат и (при т = k) в точке А(0; 2k). Поскольку из условия задачи ясно, что впереди должны стоять два обладателя полтинника, то первого из них можно отвести в сторону, и тогда получим решенную выше задачу, но для случая, когда на т рублей приходится k - 1 полтинник. Поэтому число благоприятных расстановок при т < k равно

Если же m = k, то надо отвести в сторону и замыкающего очередь обладателя рубля. Мы получим ответ .

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

Т =Т₀Т_n-1 +Т₁Т_n-2 + ... + Т_s-1Т_n-s +...+Т_n-1Т₀ (3)

Для доказательства разобьем все варианты на классы, отнеся к s-му классу очереди, в которых лишь после того, как пройдут 2s покупателей, в первый раз обнаруживают отсутствие в кассе полтинников. В этом случае среди первых 2s покупателей имеется s человек с полтинниками и s человек с рублями, а число способов расстановки, при которых в кассе на первых 2s - 1 шагах был хотя бы один полтинник, равно, как мы видели, . Среди оставшихся 2п - 2s людей у п - s рубли и у п - s полтинники. Расставить их так, чтобы очередь и потом прошла благополучно, можно Т _n-s способами.

Всего по правилу произведения получаем, что в s-м классе будет T_s-1T_n-s расстановок. А так как общее число благополучных расстановок равно Т, то выполняется равенство (3). При этом Т₀ = 1.

Соотношение (3) встречается во многих задачах. Например, пусть имеется сантиметровая лента («портновский метр») длиной п + 1 см, которую надо разрезать на кусочки длиной 1 см. Причем режут ее, экономя усилия. На первом шагу производят разрез в некотором месте. На втором шагу намечают места разрезов двух полученных частей, накладывают их друг на друга соответствующим образом и одним взмахом ножниц производят разрез. На третьем шагу так же разрезают полученные четыре части и т. д. (если какая-нибудь часть имеет длину 1 см, то она не подвергается дальнейшим разрезам). Например, если от ленты длиной 2^k см каждый раз отрезать 1 см, то потребуется 2^k-1 разрезов, а если резать все получающиеся части пополам, то хватит k разрезов.

Можно доказать, что число В_n таких процессов, заканчивающихся разрезанием ленты на п + 1 сантиметровых кусочков, равно Т_n (два процесса считаются различными, если хотя бы на одном шагу они приводят к разным результатам). Доказательство основано на том, что процессы разрезания представляют в виде объединения п классов, где в s-й класс попадают разрезания, при которых на первом шагу левая часть имеет длину s см. Это сразу приводит к рекуррентному соотношению для В_n, совпадающему с соотношением (3) для Т_n . Так как, кроме того, B₀ = T₀ = 1, то для всех п имеем:

B_n =T_n= .

2. Очереди и свойства сочетаний

Выведенные в предыдущих пунктах формулы позволяют установить дальнейшие свойства числа сочетаний С.

1. Разобьем на классы все неблагоприятные перестановки из т букв «р» и k букв «п» -- при которых очередь в кассу задерживается. Отнесем к s-му классу все перестановки, для которых задержка впервые происходит на месте 2s + 1, тогда перед ним стоит s букв «р» и s букв «п», на нем стоит буква «р», а очередь вплоть до этого места проходит без задержки.

Ясно, что s может принимать значение 0, 1, 2, ..., т - 1. Найдем, сколько перестановок входит в s-й класс. На первых 2s местах могут стоять любые благоприятные перестановки из s букв «р» и s букв «п» -- ведь до места 2s + 1 очередь не останавливается. Как мы видели, число таких перестановок равно . Далее, на месте 2s + 1 стоит буква «р», а после нее -- любая перестановка оставшихся т - s - 1 букв «р» и k - s букв «п». Число этих перестановок равно

P(m-s-1, k-s) =

Таким образом, в силу правила произведения число неблагоприятных перестановок s-гo класса равно

Так как общее число неблагоприятных перестановок равно C_k, а число классов равно т - 1, то получаем при т < k соотношение

 (4)

Это соотношение является частным случаем формулы

, (5)

где q < m ? k + q (появляющееся считается равным нулю).

Формула (5) обобщает (4) на случай, когда у кассира было в запасе q полтинников.

2. Еще одно соотношение между числами получается следующим образом. Зададим число l, 1 ? l ? т, и разобьем множество всех благоприятных перестановок на классы, отнеся к s-му классу все перестановки, содержащие среди первых l элементов ровно s букв «р». Тогда число букв «п» среди первых l элементов равно l - s. Так как букв «п» должно быть не меньше, чем букв «р», то s удовлетворяет неравенствам 0 ? 2s ? l. Найдем число перестановок в s-м классе. Каждая такая перестановка распадается на две части: одна состоит из первых l букв, а другая -- из последних k + т - l букв. В первую часть входит l - s букв «п» и s букв «р». При этом так как вся перестановка благоприятна, то и ее часть, состоящая из первых l букв, тоже благоприятна. А из l - s букв «п» и s букв «р» можно составить , таких перестановок.

После того как пройдет первая часть перестановки, в кассе будет l - 2s полтинников. Вторая часть перестановки состоит из k - l + s букв «п» и т - s букв «р». Число перестановок, при которых эта часть очереди проходит без задержки, вычисляется по формуле (2) п. 2, в которой надо заменить q на l - 2s, т на т - s и k на k - l + s. Из этой формулы вытекает, что вторая часть перестановки может быть выбрана

способами. По правилу произведения получаем, что число перестановок в s-м классе равно

Так как общее число благоприятных перестановок из k букв «п» и т букв «р» равно то получаем тождество

(6)

Здесь через [l/2] обозначена целая часть числа ; считается равным нулю при р < 0.

3. Блуждания по бесконечной плоскости

Изучим блуждания на плоскости во всех четырех направлениях.

Представим себе, что из точки О (рис. 4) выходит 4ⁿ людей, которые делятся уже на 4 равные группы, идущие от точки О во все 4 стороны. На каждом перекрестке (точке с целочисленными координатами) дошедшие до него люди снова делятся на 4 группы и т. д. Мы хотим подсчитать распределение людей через п промежутков времени после выхода из точки О. Для этого достаточно подсчитать число путей, состоящих из п единичных отрезков и ведущих из точки О в точку А(р; q) (за единицу длины мы принимаем расстояние между соседними перекрестками). Не теряя общности, можно считать, что р ? 0, q ?0 (для отрицательных р или q надо брать ¦p¦или ¦q¦).

Чтобы задать любой путь из О в А, состоящий из п звеньев, занумеруем эти звенья по порядку числами 1, 2..... n. Для каждого из этих звеньев надо знать, в каком направлении он идет. Например, изображенный на рис. 4 путь приводит в точку

А (1;2) и задается последовательностью букв (л, н, н, п, п, в, в, в. п, в, п, н, л, л, в), где буква «п» означает движение вправо, «л» -- влево, «в» -- вверх и «н» -- вниз. Здесь п = 15, р = 1, q=2. Обозначим через X множество всех номеров звеньев, которые идут влево или вниз, а через Y множество всех номеров звеньев, которые идут вправо или вниз. Например, для пути на рис. 4 эти множества таковы:

X = {1, 2, 3, 12, 13, 14}, Y = {2, 3, 4, 5, 9, 11, 12}.

Рис. 4

Оказывается, эти два набора полностью определяют путь. Совсем легко найти те номера звеньев, которые идут вниз -- они входят и в X, и в Y (в примере это номера 2, 3 и 12). Движениям влево соответствуют числа из X, не входящие в Y (в примере -- число 1, 13, 14); вправо -- числа из Y, не входящие в X (в примере -- числа 4, 5, 9, 11); вверх -- числа, не входящие ни в X, ни и Y (и примере числа 6, 7, 8, 10, 15). Таким образом, задав множества X в Y, мы для каждого момента времени задаем направление движения, а тем самым и весь путь из точки О в некоторую точку А. Множества X и У можно задавать произвольно при одном лишь ограничительном условии -- после n шагов нам надо оказаться в точке А(р; q). Это условие позволяет найти число элементов в X и в Y. В самом деле, обозначим через х_п, х_л, х_в, х_н количество

звеньев, идущих соответственно вправо, влево, вверх и вниз. Тогда х_п - х_л = р, х_в - х_н= q, х_п + х_л + х_в+ х_н = п. Множество X состоит из к номеров, которым отвечают движения влево или вниз. Легко находим . Это понятно -- если из всех п движений убрать р движений вправо и q движений вверх, то мы как бы придем обратно в точку О. т. е. движений вниз и влево будет столько же. сколько оставшихся вверх и вправо -- они погашают друг друга. В нашем примере X состоит из 6 элементов.

В множестве Y берутся ходы вправо, а не ходы влево, их на р больше, чем ходов влево (за счет этого мы и попадаем в точку с абсциссой р). Ходы же вниз в обоих множествах X и Y одни и те же. Значит, в Y на р элементов больше, чем в X, т. е. р + к элементов. Поэтому множество Х можно выбрать

способами, множество Y- способами, и по правилу произведения число путей длины п, ведущих из точки О в

точку А(р; q), равно , где .

4. Самостоятельное решение задач

Задача №1.

а) Сколько существует треугольников, вершины которых являются вершинами данного выпуклого шестиугольника?

б) Сколькими способами можно построить замкнутую ломаную, вершинами которой являются все вершины правильного шестиугольника (ломаная может быть самопересекающейся)?

Решение.

а). треугольников.

б). 6!/12 = способов. (вершины можно обходить в любом порядке, но начинать можно с любой из 6 вершин в любом из 2 направлений).

Задача №2.

Докажем геометрическим путем формулу

где, 0 ? s ? k, 0 ? s ? n, рассмотрев разбиение множества всех путей из А(0;0) в M(k, n) на классы в соответствии с тем, через какую точку прямой DE (где D(k-s;n), E(k; n-s)) они проходят.

Решение.

D M

n

n-m

n-s X E

А k-s k-s+m k

За один шаг точка движется на единицу по горизонтали или по вертикали. Тогда из А(0;0) до М(k;n), необходимо сделать n+k шагов, при чем из них надо выбрать n шагов по вертикали. Следовательно, всего путей .

При этом каждый такой путь ровно в одной точке пересечет DE, следовательно все множество из путей можно разбить на классы (непересекающиеся подмножества) в соответствии с тем, через каждую точку DE проходит путь.

Найдем количество путей в каждом классе, т.е. для любых XЄ DE, Х имеет координаты X(k-s+m; n-m) где m=0;1;…..;s. Из точки А(0;0) до X(k-s+m; n-m) (k-s+m)+(n-m)=n+k-s шагов из них какие-то n-m по вертикали, т.е. всего от А до X путей.

Из точки X (k-s+m; n-m) до M(k;n) k-(k-s+m)+n-(n-m)= S шагов, из них какие-то m по вертикали, т.е. всего от X до M путей.

Тогда от А до M путей через Х: ?

Таким образом,

?=?+?+…+?+…++?

Задача №3.

Монету бросают 2n раз. Докажите, что число вариантов, при которых герб ни в один момент не выпал чаще решки, равно

Решение.

Пусть m - число выпавших гербов, тогда k = 2n-m - число решек. В любой момент гербов выпадало меньше, чем решек, следовательно, в частности после 2n подбрасываний: m ? k = 2n - m, следовательно m ? n

Далее, мы в условиях задачи об очереди в кассу: m - гербы - «рубли»,

k - решки - «полтинники».

Выпавших гербов не больше решек <=> очередь идет без задержки.

при m=0 = 0 = 0 = 0

только 1 вариант -

все решки

= 0

- очевидно

- коэффициент при

¦

- коэффициент при xⁿ :

= 1

Задача №4.

Автобусная сеть города устроена так. что:

1) с любой остановки можно попасть на любую другую бед пересадки;

2) для любой пары маршрутов найдется и притом единственная остановка, на которой можно пересесть с одного из этих маршрутов на другой;

3) на каждом маршруте ровно п остановок. Сколько автобусных маршрутов в городе?

Решение.

Вариант I.

В городе один маршрут, соединяющий все n остановок. Выполнены требования условия задачи: 1) и 3) - очевидно, 2) - по принципу «все черти зеленые».

Вариант II.

В городе более 1 маршрута. Тогда из условий 1) и 2) задачи следует, что для любой остановки существует маршрут, не содержащий ее.

Доказательство: А - произвольная остановка.

] A Є m (А- остановка на маршруте m)

mґ? m (более 1 маршрута)

А mґ - все доказано, т.е. нашелся маршрут, не содержащий А.

A Є mґ

A Є mґ

B Є mґ: В ? A не бывает маршрутов из одной остановки.

C Є m : С ? A

Размещено на http://www.allbest.ru/

По условию 1): mґґ, соединяющий В и С. По условию 2): А mґґ, иначе m и mґґ имели бы 2 общие остановки А и С.

А mґґ нашелся маршрут, не содержащий А¦.

Из условий задачи следует, что через каждую остановку проходит ровно n маршрутов.

Доказательство: ]B - произвольная остановка. m: B m (доказано выше)

B

m

A₁ A₂ …….. A_n

По условию 3) m имеет n остановок: A₁,A₂,….,A_n

По условию 1) m_k - маршрут, соединяющий B и A_k, где k 1,2,…, n.

По условию 2) a) такой маршрут m_k - единственный, т.к., иначе m_k и m?_k имеют 2 общие остановки В и A_k.

б). при k?l m_k?m_l, т.к. иначе m_k=m_l=mґ и m имеют 2 общие остановки А_k и A_l

В

А_k m

в). Любой маршрут, проходящий через B, должен иметь общую остановку А_k с маршрутом m, т.е. совпадает с одним из m_k.

Таким образом, m₁,m₂,…..,m_n - все различные маршруты через B¦.

Считаем количество маршрутов.

(n-1)

….

m

………………………….

…. …. …..

(n-1) (n-1)

m - какой-либо маршрут.

Выше доказано, что через каждую А_к проходит n маршрутов, т.е. (n-1) без учета маршрута m.

Из условия 2) любой маршрут, отличный от m, проходит ровно через одну А_к, т.е. все множество маршрутов состоит из m и n непересекающихся классов по (n-1) маршруту.

Общее количество маршрутов n(n-1)+1

Задача №5.

В городе насчитывается 57 автобусных маршрутов. Известно, что:

1) с любой остановки можно без пересадки попасть на любую другую;

2) для любой пары маршрутов найдется, и притом только одна, остановка, на которой можно пересесть с одного из этих маршрутов па другой:

3) на каждом маршруте не менее трех остановок. Сколько остановок имеет каждый из 57 маршрутов?

Решение.

Пусть m - один из маршрутов - имеет n остановок. Тогда любой другой маршрут mґ тоже имеет n остановок.

Доказательство: по условию 2). m и mґ персекаются в единственной остановке A.

С Є m: С ? А не бывает маршрутов

из одной остановки

D Є mґ: D ? А

По условию 1). mґґ- маршрут, соединяющий С и D, а по условию 3). mґґ имеет хотя бы одну остановку B отличную от С и D.

B m, B mґ, т.к. иначе mґґимел бы с m и mґ более одной общей остановки.

mґ

D

mґґ

B

С A m

Применим рассуждения решения задачи №4 (второго доказательства ). Следовательно m₁,…,m_n - все различные маршруты через B.

Тогда по условию 2).:

B_k = m_k ? mґ

B mґ

m₁ B_n

mґ m₂ m_n

B₁

B₂

A₁ A₂ ……… A=A_k=B_k ……………. A_n B_n

по условию 2).:k ? l => B_k ? B_l, иначе m_k и m_l имели бы 2 общие остановки: B и B_k=B_l

по условию 1).: любая остановка mґ совпадает с одной из B_k, т.к. любая остановка mґ может быть соединена маршрутом с B, а через B проходят только маршруты m₁,m₂,…,m_n=> остановка mґ соединена к B каким-то m_k. =>

=> данная остановка является B_k.

Т.о., B₁,B₂,….,B_n -все остановки mґ, mґимеет n остановок ¦.

Мы, в условиях задачи №4 => число маршрутов 57=n(n-1)+1, где n - число остановок на каждом маршруте. Из этого следует: n=8.

Задача №6.

Можно ли проложить в городе 10 автобусных маршрутов и установить на них остановки так, что какие бы 8 маршрутов ни были взяты, найдется остановка, не принадлежащая ни одному из этих маршрутов, а любые 9 маршрутов проходят через все остановки?

Решение.

Возможно, например, рассмотрим 10 прямых на плоскости у=kx+k², где k=1,2,…,10 - это маршруты автобусов.

Любые две из этих прямых пересекаются (т.к. прямые не параллельны, потому что у них различные k) в одной точке.

Пусть точки пересечения прямых и только они будут остановками.

Никакие 3 прямые не имеют общую точку пересечения, т.к. система линейных уравнений

у=k₁x+k₁² у-k₁x=k₁² несовместна

у=k₂x+k₂² <=> у-k₂x=k₂² по теореме

у=k₃x+k₃² у-k₃x=k₃² Кронекера - Капелли.

Действительно, ранг матрицы системы



1 - k₁

1 - k₂ равен 2;

1 - k₃

базисный минор

системы ранг расширенной матрицы

1 - k₁ k₁²

1 - k₂ k₂²

1 - k₃ k₃²

Базисный минор, т.к. определитель этой матрицы - определитель Вандермонда - равен - (k₃-k₂)(k₃-k₁)(k₂-k₁) ? 0

Проложены 10 маршрутов.

*) если взяты любые 8 маршрутов, то 2 оставшихся имеют общую остановку, не принадлежащую 8-ми взятым (иначе, через эту остановку проходят 3 маршрута).

**) если взяты любые 9 маршрутов, то любая остановка оставшегося маршрута принадлежит одному из 9-ти взятых (т.к. любая остановка оставшегося маршрута - это точка его пересечения с каким-либо другим маршрутом, т.е. одним из 9-ти взятых).

Следовательно, все остановки лежат на 9-ти взятых маршрутах.

Выводы по работе

Задачи на «Очередь в кассу» применимы к реальной жизни, поэтому необходимо заниматься их изучением. Такой вывод мы сделали после написания курсовой работы по данной темы. В нашей работе мы рассмотрели общую задачу на «Очередь в кассу», так же самостоятельно постарались решить некоторые задачи подобным методом.

Размещено на Allbest.ru