Тег «комбинаторика»

Полуинвариант

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

Лучше всего рассмотреть, как решать такие задачи, на примерах.

Задача 1. В квадрате 20\times20 стоят 400 ненулевых чисел. Можно изменить знак у всех чисел, стоящих в одном столбце или в одной строке. Докажите, что за конечное число таких операций можно добиться того, что сумма чисел, стоящих в любой строке или в любом столбце, будет неотрицательной. Читать полностью ‘Полуинвариант’ »

Теорема Холла, или теорема о свадьбах

Филип Холл

Филип Холл (Philip Hall, 1904–1982) — английский математик, большая часть работ которого относится к теории групп и связанным с ней разделам алгебры. Так, первая теорема Холла относится к разрешимым группам. Теорема Холла о свадьбах, доказанная им в 1935 году, является одним из основных комбинаторных принципов. Возможно, самый важный его вклад в математику — полиномы Холла, которые играют важную роль в теории представлений групп.

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

Перенумеруем юношей и девушек числами от 1 до n. Номера девушек запишем по строкам, номера юношей — по столбцам. Элемент, стоящий в i-й строке и j-м столбце таблицы равен 1 тогда и только тогда, когда брак между девушкой с номером i и юношей с номером j возможен, и 0 в противном случае. Иногда все девушки могут выйти замуж, а иногда поженить всех невозможно. Читать полностью ‘Теорема Холла, или теорема о свадьбах’ »

Комбинаторная задача

Интересная задачка по комбинаторике, которая заставляет задуматься (см. задачник по алгебре и анализу М.И. Башмакова, Б.М. Беккера, В.М. Гольхового и Ю.И. Ионина).

Задача. Имеется десять различных ящиков, шесть неразличимых белых шаров и шесть неразличимых черных шаров. Сколькими способами можно разложить все шары по ящикам так, чтобы в каждом ящике оказался хотя бы один шар?

Вся сложность комбинаторики состоит в том, чтобы понять. Здесь трудно что-то выучить наизусть. Как только заканчиваются простейшие задачи, приходит конец и “лобовому’’ применению формул для числа сочетаний, размещений и перестановок (ага, а если еще взять соединения с повторениями, то начинается полная путаница!). В любой более-менее неочевидной комбинаторной задаче нужно четко понимать, как подсчитать варианты так, чтобы ничего не пересчитать несколько раз и чтобы никакой вариант не остался неучтенным. И вот когда становится ясным алгоритм такого пересчета, задача решается сразу же. Читать полностью ‘Комбинаторная задача’ »

Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. “Комбинаторика’’

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

Комбинаторика нужна, причем нужна она и тем, кто планирует изучать математику дальше (так, она является основой для изучения теории вероятности), она нужна и тем, кто хочет в дальнейшем заниматься программированием (в частности, пригодится при изучении конечных автоматов). Встречаются комбинаторные задачки и в других науках, на школьном уровне – в химии, а дальше – везде, где применяется теория вероятности. Еще комбинаторика полезна для интеллектуального развития. Другие задачи, другие способы их решения. Читать полностью ‘Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. “Комбинаторика’’’ »