Зачем делить в комбинаторике

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

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

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

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

Замечание.

Эта задача про известный факт, что различных простых циклов на вершинах имеется

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

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

Чтобы получить искомую четверку точек, нам нужно совместить пару точек с одной прямой и пару точек с другой прямой. Так как каждой паре точек с одной прямой может соответствовать любая пара точек с другой прямой, количества пар точек нужно перемножить: четверок, и столько же зелёных точек пересечения, которые нужно было посчитать.

Замечание. Подумайте, сработал ли бы наш способ, если бы было известно, что три отрезка пересеклись в одной точке?

Первую ладью можно поставить на любую из клеток, вторую — на любую из клеток независимо от того, куда поставили предыдущим шагом первую ладью. Так как мы выбираем несколько объектов последовательно, и количество способов выбрать следующий объект не зависит от того, что выбрано ранее, мы должны перемножить числа и . Но мы для себя говорим “первая” ладья и “вторая” — а на самом деле эти ладьи одинаковые. Поэтому способы, когда на клетку поставили первую ладью, а на клетку — вторую, и наоборот, когда на клетку поставили вторую ладью, а на клетку — первую, одинаковы. Значит, все способы посчитаны дважды. Таким образом, произведение нужно ещё поделить на : получаем .

Первую точку можно выбрать десятью способами. Каждую из следующих восьми точек можно выбрать двумя способами: она должна быть соседней с одной из ранее выбранных точек (иначе получится самопересекающаяся ломаная). Поскольку начало и конец при таком подсчёте различаются, а в ломаной – нет, результат нужно разделить на . Следовательно, всего имеется ломаных.

Сначала выберем того студента, у которого профессор спросит домашнее задание. Им может быть любой из гриффиндорцев, итого способов. Затем нам нужно выбрать того, кто будет писать контрольную. Так как это должен быть другой школьник, есть вариантов выбора. Мы выбираем два объекта последовательно, и вне зависимости от выбора первого объекта второй мы можем выбрать всегда одинаковым количеством способов. Значит, чтобы получить общее количество вариантов, посчитанные выше способы необходимо перемножить: .

Главное отличие от предыдущей задачи состоит в том, что нам не важно, какой ингредиент мы выберем первый, а какой вторым. Но сначала посчитаем количество способов, как будто нам важен порядок. Первый ингредиент можно выбрать способами, второй — способами, так как это должен быть другой ингредиент. Так как выбор последовательный и независимый, способы перемножаются, и всего получается вариантов. Но каждый из интересующих нас на самом деле вариантов мы посчитали дважды: скажем, когда Гарри выбирает аконит и рог двурога, мы эти варианты посчитали, во-первых, когда первым выбирается аконит, а вторым — рог двурога, а во-вторых, когда первым выбирается рог двурога, а уже затем аконит. Итак, на самом деле в вариантах каждый нужный нам вариант посчитан дважды. Значит, чтобы найти настоящее количество способов, нам надо найденное число, то есть , поделить пополам: способов.

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

Сразу отметим, что порядок выбора нам не важен: так, партия Рон против Гарри — то же самое, что партия Гарри против Рона!

Но сначала сосчитаем, сколькими способами мы можем выбрать упорядоченную пару.

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

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

Значит, чтобы найти нужное нам количество партий, достаточно число разделить на два: партий было сыграно.

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

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

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

Сначала посчитаем количество способов отправить две команды без дополнительного условия, что в командах должно быть хотя бы по одному человеку. У каждого смешарика есть три варианта: либо пойти в первую команду, либо во вторую, либо остаться на базе. Будем последовательно для каждого выбирать судьбу. Так как выбор последовательный и независимый, получается способов.

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

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

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

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

Посчитаем количество способов выбрать 3 книги у первого школьника, книг 6 и при выборе нам не важен порядок, поэтому оно равно Аналогично для второго количество способов выбрать 3 книги равно

В итоге количество комбинаций таких троек равно

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

Всего у нас 5 чётных и 5 нечётных цифр. Поэтому количество -значных последовательностей цифр(в отличие от чисел может стоять 0 в начале), у которых по три чётных и нечётных цифры, равно

Теперь посчитаем количество последовательностей, начинающихся с 0. Для этого достаточно посчитать количество идущих после этого 0 -значных последовательностей, у которых две чётных и три нечётных цифры. Аналогично случаю для -значных получаем, что оно равно

В итоге количество -значных чисел, у которых по три чётных и нечётных цифры, равно

Первую ладью можно поставить 64 способами, и она будет бить 15 клеток, включая свою. Значит, для второй ладьи будет всего 49 клеток куда ее можно поставить. Так как ладьи одинаковые, то каждую позицию мы посчитали 2 раза и поэтому ответ

Чтобы число было кубом, нужно, чтобы степень каждого числа делилась на . Если мы возьмем одну карточку со степенью и одну со степенью , то они в произведении будут кубом только, если изначальные степени были кубами. Значит, в этом случае у нас варианта.

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

Получаем ответ .

Проведем через 2 вершины и центр квадрата прямые, параллельные осям, как на картинке.

Заметим, что выделенные на картинке цветом треугольники равны по двум углам и стороне. Значит, если одна вершина с координатами , то следующая , затем по аналогичным соображениям следующая вершина и последняя . Тогда из условия, что все координаты неотрицательные получаем, что числа неотрицательны. Отсюда и . Значит, для значения у нас вариант и для значения у нас вариант, но если , то не получится квадрат. Итого: вариантов для пар , но заметим, что в квадрате изначальную вершину можно выбрать четырьмя способами. Значит, четырём парам значений и соответствует один квадрат. Таким образом, квадратов .

Для делимости числа на обязательно нужно поставить последней цифру , поскольку нулей в записи числа нет. Зафиксируем последнюю цифру. Останутся цифры в количестве соответственно, всего цифр.

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

В итоге получаем ответ

Так как число делится на 5, то на 9-м месте может стоять только пятёрка. После этого нужно на оставшиеся 8 мест распределить 8 цифр: 3 семёрки, 3 тройки, пятерку и двойку. Всего перестановок будет 8!, но так как есть повторяющиеся цифры, то ответ будет: