Математикадан облыстық олимпиада, 2003-2004 оқу жылы, 11 сынып

Жәмилә оң бүтін $n$ санын таңдап оны Махамбетке хабарлайды. Өз кезегінде Махамбет оң бүтін $k$ санын таңдап оны Жәмиләға хабарлайды. Жәмилә қағазға әртүрлі $n$ шеңбер сызып, әрқайсысы осы шеңберлердің ең болмағанда біреуінде жататындай әртүрлі $k$ нүкте таңдайды. Сонан соң ол осы $k$ нүктені ғана қалдырып, шеңберлердің бәрін өшіріп тастайды. Қалған нүктелер бойынша шеңберлердің ең болмағанда біреуін дәл анықтау үшін Махамбет таңдаған $k$ саны ең кемінде қаншаға тең болу керек?

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

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

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

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

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