Комбинации с участием геометрических объектов

Комбинации с участием геометрических объектов.

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

Задача 1.

На некоторой окружности отмечены 34 красных и 165 синих точек. Сколько можно построить различных хорд с концами в точках:

а) одинакового цвета

б) разного цвета

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

Данную задачу можно решить несколькими способами. Рассмотрим подробно каждый из них.

1 способ – правило произведения.

Отвечая на вопросы задачи, выясним отдельно, сколько хорд получится с концами в точках красного цвета и сколько с концами в точках синего цвета, затем просуммируем полученные результаты.

Выбираем на первое место произвольную точку, на втрое место останется на одну точку меньше. Используем правило произведения.

Цвет точки	Первое место		Второе место	Результат
Красный	34	x	33	1122
Синий	165	х	164	27060

  Из каждой красной точки можно провести 33 хорды, при этом каждую из них мы сосчитали дважды, поэтому чтобы получить конечный ответ, разделим полученный результат пополам:

 – хорд, с концами в красных точках

 = 13530 – хорд, с концами в синих точках

561+13530 = 14091– хорд, с концами в точках одинакового цвета

Аналогично рассуждая, найдем, сколько можно построить хорд с концами в точках разного цвета:

 = 19701

2 способ – комбинаторные числа.

Для того, чтобы верно определить комбинаторный объект, соответствующий объекту задачи, проведем следующие рассуждения:

1)    наша комбинация неупорядоченная (точки на окружности не пронумерованы и не имеет значения, в каком порядке составляются хорды)

2)    повторения при составлении хорд не допускаются (две точки участвуют в образовании только одной хорды)

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

После подстановки получим:

Существует так же третий способ решения задачи  – метод перебора. Для нашего случая данный метод является неудобным, т.к. одним из главных критериев его применимости является обозримое число перебираемых комбинаций, а таковых у нас немало. Метод перебора займет много времени, если не прибегнуть к помощи вычислительной техники.

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

Задача 2.

На одной прямой отмечено 5 точек, а на параллельной ей прямой — 7 точек. Сколько существует треугольников с вершинами в этих точках?

 

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

Подсчитаем отдельно количество треугольников каждого вида. Используем второй способ (комбинаторные числа). Наша комбинация неупорядоченная (порядок точек не важен)  и повторы не допускаются (выбор точки допускается единожды), значит, мы можем использовать формулу сочетание без повторения, получаем . Осталось выбрать последнюю точку треугольника на другой прямой, это можно сделать 7 способами. Используем правило произведения, так как одновременно нужно выбрать три точки. Итак, всего треугольников первого вида:  , по аналогичным рассуждения получаем  – треугольников второго вида. Конечный ответ сможем записать, пользуясь правилом суммы:

Данная задача является примером одновременного использования нескольких правил в решении.

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