Областная олимпиада по математике, 2004 год, 11 класс

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

Комментарий/решение

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

Начнем. Джамиля и Махамбет выполнили все действия. Теперь Махамбет видит несколько точек на доске. Запишем все множества которые можно составить из точек вокруг которых можно нарисовать окружность, и рассортировать их по кол-ву элементов.(Напишите если считаете это не очевидным) Очевидно что Махамбет сможет найти из них множество Джамили только если кол-во элементов в одном из множеств Джамили не будет равно кол-ву элементов ни одному из множества возможных.

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

Если множество Джамили имеет более 2n то очевидно что Махамбет сможет его найти. Это всегда возможно если $k=2n^2$ $+1$. Так как возможное множество может иметь любое кол-во элементов от 1 до 2n, то Махамбет не может быть уверен в том что данное множество множество Джамили если в нем меньше 2n-1 элементов.