Тема ПитерГор (Санкт-Петербургская олимпиада)

ПитерГор - задачи по годам .09 ПитерГор 2022

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела питергор (санкт-петербургская олимпиада)
Разделы подтемы ПитерГор - задачи по годам
Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#70480

Можно ли на параболе y = x2  отметить точки A,B,C,D,  а на параболе y = 2x2  — точки E,F,G,H  так, чтобы выпуклые четырехугольники ABCD  и EFGH  оказались равными?

Источники: СпбОШ - 2022, задача 11.1(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Первое, что нужно сказать про эту задачу - это то, что на самом деле эта задача на конструктив, но при этом не как конкретный пример, который чем-то единственным образом задан, а просто приведение какого-то непонятного примера. Подумайте над тем, что будет, если два «вписанных» в параболу четырехугольника равны. А как тогда построить такой четырехугольник?

Подсказка 2

Верно, если они равны, то они совпадают наложением, а значит мы можем так повернуть параболы, что четырехугольник будет «вписан» в обе параболы. А как теперь самим построить пример?

Подсказка 3

Верно, мы можем взять две параболы так, чтобы они пересекались в 4 точках, и тогда четырехугольник, образованный точками пересечения будет нам подходить!

Показать ответ и решение

Достаточно расположить эти параболы на плоскости так, чтобы они пересекались в четырёх точках. Эти четыре точки взять в качестве A,B,C,D  и одновременно E,F,G,H.  Одинаковые четырёхугольники являются равными.

Ответ: да

Ошибка.
Попробуйте повторить позже

Задача 2#70481

В остроугольном треугольнике ABC  с углом 45∘ при вершине A  проведены высоты AD,  BE  и CF.  Луч EF  пересекает прямую BC  в точке X.  Оказалось, что AX||DE.  Найдите углы треугольника ABC.

Источники: Источник: СпбОШ - 2022, задача 11.2 (см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Даны параллельность и вписанность - это сразу же намекает нам на углы! Попробуем поотмечать, а потом воспользуемся условием на угол A) Что узнаем?

Подсказка 2

Понимаем, что AF = FC! Теперь мы можем посчитать достаточно большое количество углов на картинке...но все из них равны либо 90, либо 90/2. На что это может намекать? Обратим внимание на точку F.

Подсказка 3

Угол AFC в 2 раза больше чем AXC. Чем тогда является F для треугольника AXC? Когда мы это поймем, мы сможем по аналогии связать углы AFX=EFB и ACB. Не забываем про вписанность!)

Показать ответ и решение

PIC

Из условия следует, что AF =F C  . Из вписанностей ∠CDE = 45∘ , и теперь из параллельности ∠AXD = 45∘ . В треугольнике AXC  точка F  оказалась центром описанной окружности (равноудалена от вершин A  и C  и центральный угол в два раза больше вписанного). Поэтому 2∠ACB = ∠AF X = ∠BF E  , что вместе со вписанностью BF EC  дает ∠ACB = 60∘

Ответ:

 45∘,60∘,75∘

Ошибка.
Попробуйте повторить позже

Задача 3#70482

Иван и Кощей играют в следующую игру. Изначально на доске записан многочлен x− 1.  За один ход можно заменить многочлен f(x),  записанный на доске, на многочлен   n+1
ax   − f(− x)− 2,  где n  — степень многочлена f(x),  а a  — один из его вещественных корней. Игроки ходят по очереди, начинает Иван. Выигрывает тот игрок, после хода которого на доске будет написан многочлен, не имеющий вещественных корней. Сможет ли Иван победить Кощея?

Источники: СПБГОР - 2022, 11.3 (см. pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Вспомним полезную теорему про многочлен нечётной степени! Что в таком случае можно сказать про Ивана?

Подсказка 2

Да, он точно не проиграет, ведь на его ходе всегда будет получаться многочлен нечётной степени, у которого всегда есть хотя бы один вещественный корень! А что можно сказать про Кащея? Для ответа на этот вопрос: рассмотрите f(0), где f - многочлен чётной степени, с положительным старшим коэффициентом!

Подсказка 3

Да, поскольку у нас изначально многочлен равен x-1(корень 1), то Кащей может на каждом шаге брать вместо a - положительный корень предыдущего многочлена(который всегда существуют)! А тогда, у многочлена Кащея тоже всегда будет вещественный корень!

Показать ответ и решение

Ивану достаётся многочлен нечетной степени, поэтому он не может проиграть. Однако Кощей тоже не может проигрывать: для этого ему достаточно каждый раз выбирать положительный корень. Заметим, что свободный член всегда равен − 1.  Легко проверить, что при такой стратегии Кощея Ивану будут доставаться многочлены нечетной степени с чередующимися знаками коэффициентов (старший - положительный), и поэтому у них есть лишь положительные корни; а Кощею будут доставаться многочлены четной степени с положительным старшим коэффициентом и свободным членом − 1,  поэтому у них существует положительный корень

Ответ:

Нет

Ошибка.
Попробуйте повторить позже

Задача 4#70483

Будем говорить, что набор чисел a ,...,a
 1     m  сильнее набора чисел b,...,b ,
 1    n  если среди всех неравенств вида a > b
 i   j  количество верных неравенств не менее чем в 2  раза превосходит количество неверных. Докажите, что не существует трех наборов A,B,C,  таких, что  A  сильнее B,  B  сильнее C,  C  сильнее A.

Источники: СпбОШ - 2022, задача 11.4(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Нам дали факт о том, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных» и просят доказать, что какой-то факт не выполнен, скорее всего мы получим противоречие с тем, что какая-то величина будет одновременно больше и меньше какого-то числа или мы сможем показать, что она не меньше и не больше некоторой числа, а значит равна ему и такой случай уже намного проще разобрать.

Подсказка 2

Давайте теперь зафиксируем произвольную тройку (A_i, B_j, C_t) и распишем для неё условие, что A сильнее B, B сильнее C, C сильнее A. А сколько вообще может быть верных неравенств при таком условии? Может попробовать оценить сверху и снизу количество верных неравенств?

Подсказка 3

Действительно, количество верных неравенств не больше чем 2, мы показали это для произвольной тройки, а сколько всего троек? Теперь попробуем понять, как ограничить эту величину снизу. Мы не пользовались тем, что «количество верных неравенств не менее чем в 2 раза превосходит количество неверных». Как раз «не менее» намекает нам о том, что мы сможем оценить снизу.

Подсказка 4

Можно посмотреть на наборы A, B и поотвечать на вопросы. А сколько можно записать неравенств вида a_i > b_j? А сколько из них должны быть верными? А мы пользовались какими-либо особенностями множеств A и B или это можно сказать для любой пары множеств?

Подсказка 5

Ура, мы получили, что количество верных неравенств не меньше чего-то, но и не больше, а значит в точности равно этому числу. Это уже хорошее условие, но на самом деле мы знаем больше! Что должно выполняться, чтобы это равенство достигалось?

Подсказка 6

Верно, количество верных неравенств должно быть ровно в 2 раза больше количества неверных! Так как мы доказываем, что такого не бывает, то в какой-то из пар наборов количество верных больше, чем в 2 раза неверных, а для числа с каким свойством неравенство было бы выполнено для всех остальных чисел?

Подсказка 7

Верно, для наибольшего из всех чисел или для наименьшего, здесь мы пользовались принципом крайнего, который часто может встречаться в задачках, где что-то сравнивается. Вернёмся к условию, что A сильнее B, B сильнее C, C сильнее A, оно ведь тоже участвовало в оценке, тогда что должно быть верно, чтобы она достигалась? Как нам объединить это с прошлым фактом?

Подсказка 8

Давайте рассмотрим тройку с минимальный (для максимального тоже верно) числом из всех наборов, тогда одно из неравенств очевидно выполнено, а другое - нет. Что можно сказать про оставшееся, а сколько таких неравенств, где в тройке участвует минимальное (максимальное) число? А сколько должно должно быть верных неравенств в паре наборов?

Показать доказательство

Предположим противное. Пусть наборы

A = (a1,...,al),B = (b1,...,bm ),C =(c1,...,cn)

таковы, что A  сильнее B,B  сильнее C,C  сильнее A.  Можно считать, что число a1  наибольшее среди всех чисел этих трёх наборов. Для каждой тройки индексов i,j,k(1 ≤i≤ l,1≤ m,1≤ k≤ n)  посчитаем, сколько верных увтерждений имеется среди неравенств a > b,b >c ,c >a ,
 i  j j   k k   i  просуммируем эти числа по всем i,j,k  и обозначим полученную сумму через S.  Тогда

S ≤ 2lmn, (∗)

поскольку всего имеется lmn  троек и в каждой тройке не больше двух верных неравенств. Далее заметим, что каждое неравенство ai > bj  присутствует в n  таких тройках, поэтому в сумме S  оно учтено n  раз. По предположению среди неравенств ai > bj  не меньше 2lm
3  верных, поэтому вклад всех неравенств вида ai >bj  в сумму S  не меньше чем 2lmn.
3  Аналогично вклад всех неравенств вида b > c
 j   k  в сумму S  и вклад всех неравенств вида c > a
 k   i  в сумму S  также не меньше чем 2lmn.
3  Следовательно, суммарное количество верных неравенств не меньше чем 3⋅ 2lmn ≥S.
  3

Сопоставляя это с неравенством (∗),  заключаем, что в проделанных подсчётах все оценки являются равенствами. В частности, имеется в точности 2
3mn  верных неравенств вида bj > ck,  а в каждой тройке ai > bj,bj >ck,ck >ai  ровно два верных неравенства.

Рассмотрим теперь тройку чисел a1,bj,ck.  Среди неравенств a1 >bj,bj > ck,ck >a1  должно быть ровно два верных. Поскольку a1  — наибольшее число неравенство ck > a1  неверно, т.е. выолняется неравенство bj > ck.  Значит, все неравенства вида bj > ck  верные и всего их mn  штук. Но это противоречит тому, что их 2
3mn.  Стало быть, наше предположение неверно.

Ошибка.
Попробуйте повторить позже

Задача 5#70484

Высоты AA ,BB ,CC
  1   1   1  остроугольного треугольника ABC  пересекаются в точке H.  На касательную, проведенную из точки C  к описанной окружности треугольника AB1C1,  опущен перпендикуляр HQ  (точка Q  лежит внутри треугольника ABC  ). Докажите, что окружность, проходящая через точку B1  и касающаяся прямой AB  в точке A,  касается также и прямой A1Q.

Источники: СпбОШ - 2022, задача 11.3(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

На картинке даны какие-то касательные, присутствуют хорды - ну не просто же так! Стоит отметить равные между собой вписанные уголки в двух окружностях. Хочется доказать, что A₁Q- касательная…нет ли случайно походе конструкции на чертеже?

Подсказка 2

Из того, что AB - касательная, следует, что в двух окружностях на чертеже есть отсеченные дуги, равные удвоенному углу CAB. Мы знаем, что CQ - касательная. А хочется, чтобы A1Q стала касательной…можно ли их как-то связать? А как связать между собой окружности?

Подсказка 3

Если мы найдем преобразование, которой переведет СQ в А1Q, а окружности друг в друга, то мы сможем доказать, что A1Q тоже является касательной!

Показать доказательство

Обозначим через s
 1  описанную окружность треугольника AB C ,
   1 1  а через s
 2  — окружность, проходящую через точку B
  1  и касающуюся прямой AB  в точке A.  Хорды B1C1  и B1A  этих окружностей отсекают от них дуги одинаковой угловой величины. В самом деле, половины этих дуг в обоих случаях равны ∠B1AC1  : для окружности s1  это вписанный угол, а для s2  — угол между касательной и хордой.

Заметим также, что угол между прямыми CC1  и CQ  равен углу между прямыми AA1  и A1Q:  эти вписанные углы опираются на одну дугу HQ  в окружности с диаметром CH.

PIC

Точку пересечения прямой AA1  с окружностью s2  обозначим через P  и выделим на картинке два фрагмента: в окружности s1  проведена секущая HC1,  и на ней выбрана точка C;  в окружности s2  проведена секущая AP,  и на ней выбрана точка A1.  В каждом из этих двух фрагментов из точек на секущих проведены прямые под одинаковыми углами к секущим: CQ  и A1Q.  Первая из них касается s1,  и нам нужно доказать, что вторая касается s2.  Для доказательства нужно установить, что две описанные конфигурации подобны. Мы проверим это двумя способами. Углы треугольника, как обычно, будем обозначать греческими буквами, соответствующими названиям вершин.

Способ 1.(подсчёт отношения отрезков)

Угловые величины отсекаемых секущими дуг равны, поэтому остаётся проверить, что ACP1H = ACA1C1.  Отношение хорд AP  и C1H  (стягивающих равные дуги) равно отношению диаметров окружностей. Диаметр окружности s1  равен AH;  диаметр окружности s2  равен sin∠ACB11AB1 =sAinB∠1A .  Таким образом, CA1PH = AHAsBin1α-= sisinnγα.  С другой стороны, отношение высот ACAC11  равно отношению сторон ABBC,  которое по теореме синусов тоже равно sisinnγα.

PIC

Способ 2.(Поворотная гомотетия)

Рассмотрим поворотную гомотетию с центром в точке B1,  переводящую точку C1  в A  и C  в A1.  Она существует, ибо треугольники B1C1A  и B1CA1  подобны(и подобны треугольнику BAC  ). Окружность s1  перейдёт в s2,  ибо друг в друга переходят хорды B1C1  и B1A,  отсекающие равные дуги. При этом секущая CC1  окружности s1  переходит в секущую AA1  окружности s2,  и, следовательно, точка H  переходит в точку P.  Значит, первый фрагмент переходит во второй.

Ошибка.
Попробуйте повторить позже

Задача 6#70485

Найдите все пары ненулевых (не обязательно положительных) рациональных чисел x,y,  обладающие следующим свойством: любое положительное рациональное число можно представить в виде {rx}∕{ry} с положительным рациональным r.

Источники: СпбОШ - 2022, задача 11.6(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Давайте для начала причешем задачу. Если r - рациональное и положительное, то x,y - просто целые, так как можно построить явную биекцию между решениями при просто рациональных x,y и целых. Также, можно заметить, что если мы уберем целую часть числа r , то отношение из условия останется таким же, а значит, можно сказать, что 0 < r < 1 . А тогда можно сказать, что {(1 - r)x} = {-rx}, аналогично с y. Значит, можно считать, что y - натуральное, а х - целое. Значит, у нас, существенно, два случая - когда наша дробь - положительное число, и когда отрицательное. Попробуйте теперь найти такую дробь, которая не может быть представлена в таком виде как мы описали, и с теми условиями, которые мы доказали.

Подсказка 2

Сейчас будет приведено совсем не строгое, но тем не менее, наталкивающее на мысли, объяснение, почему нужно брать конкретную дробь, при разборе случая , когда дробь - положительное число. Давайте распишем {rx} как rx - [rx], {ry} как ry - [ry]. Тогда, для некоторого n/k = {rx}/{ry}, выполнено, что n*{ry} = k*{rx}. Значит, nry - n*[ry] = krx + k*[rx]. Что мы из этого можем получить? Если мы хотим прийти к противоречию, то можно попытаться взять какие - то k и n, такие, чтобы что-то в этом равенстве стало плохо. Сейчас целое число слева равно целому справа, а что можно подставить, чтобы слева, после преобразований, стало нецелое, а справа целое?

Подсказка 3

Возьмем n = x + 1, k = y. Тогда, во первых, сократятся rxy и rxy слева и справа, а в итого, останется уравнение {ry} = x * [ry] - y * [rx]. А значит, слева будет что - то между 0 и 1, а справа что-то целое. Пришли к противоречию. То есть, случай, когда дробь больше нуля разобран. Осталось подумать над случаем, когда наша дробь отрицательна. Можно попытаться найти контрпример, однако сразу непонятно как его строить, рассуждения из прошлого пункта непримиримы. Тогда скажем, что наша дробь равна некоторому a/b, где а - отрицательное и попытаемся доказать, что для любых а и b такое r найдется. И кажется, что в такой непонятной конструкции, как дробная часть, могут спасти только оценки значений. Попробуйте их применить(само собой, после избавления от знаменателей).

Подсказка 4

После избавления от знаменателей, у нас получается выражение brx - b*[rx] = ary - a[ry]. А значит, r - одно из решений уравнения r(bx - ay) = n, для некоторого целого n. При этом, мы можем сказать, что (без ограничения общности) х < 0, а значит, по нашим рассуждениям из первой подсказки, {rx} = 1 - {r|x|}. Подставьте это значение в наше уравнение и попробуйте подумать над максимальным и минимальным значением нецелое части.

Подсказка 5

Получим, что b = a{ry} + b{r|x|}. При r бесконечно близком к нулю, получается, что правая часть будет стремиться к нулю, что меньше b. При r бесконечно близким к 1, но меньшим ее, правая часть будет стремиться к a+b, что больше b. Значит, найдется промежуточное значение, при котором в нашем выражении будет достигаться равенство. А значит, для любой пары а и b из второго случая, мы привели пример. Значит, только для xy<0 выполнено требуемое.

Показать ответ и решение

Первое решение.

Разобьём плоскость на единичные квадраты линиями целочисленной решетки. Проведем прямую l  через начало координат O  и точку (x,y).  Поскольку x,y ∈ Q.  она имеет рациональный угловой коэффициент и проходит через какой-то узел решетки. Точка вида (rx,ry)  — это любая рациональная точка этой прямой. Проведем прямую через такую точку и левый нижний угол той клетки, в которую попала эта точка. Угловой коэффициент этой прямой равен как раз {rx}∕{ry}.

PIC

PIC

Совместим между собой все единичные квадраты, в которых есть точки прямой l.  В полученном квадрате прямая l  отобразится конечным количество отрезков, параллельных исходной прямой.

Предположим, что x  и y  одного знака. Тогда полученные отрезки имеют положительный угловой коэффициент. Один из них выходит из левого нижнего узла квадрата. Ясно, что из этого узла можно провести луч с положительным рациональным коэффициентом λ,  который пересечет правую сторону квадрата, не встретив по дороге точек ни одного из наших отрезков. Это число λ  нельзя представить в нужном виде.

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

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Так как в качестве r  можно взять любое положительное рациональное число, можно считать, что числа x  и y  целые. В этом случае замена числа r  на его дробную часть не изменит отношения {rx},
{ry}  значит, можно дополнительно считать, что 0< r< 1.  Наконец, замена r на 1− r  соответствует смене знаков чисел x  и y,  поскольку

{(1-− r)x}= {−rx}.
{(1 − r)y}  {−ry}

Таким образом, достаточно рассмотреть лишь случай, когда y  — натуральное число.
Пусть x  также является натуральным числом. Покажем, что уравнение

{rx}   x+1
{ry}-= -y--

не имеет решений относительно r.  Домножив на знаменатели и выразив дробную часть через целую, получим уравнение

y⋅rx− y⋅[rx]= x⋅ry− x ⋅[ry]+ {ry},

или, что то же самое,

{ry} =x ⋅[ry]− y⋅[rx].

Но это уравнение не может иметь решений, поскольку левая часть положительна и меньше 1,  а правая часть целая. Следовательно, если числа x  и y  одного знака, то требуемое r  не найдётся.
Пусть x  является отрицательным целым числом. Достаточно показать, что уравнение

{rx}= a  (∗)
{ry}  b

для любых натуральных чисел a  и b  имеет вещественное решение r.  Тогда

b⋅rx− b⋅[rx]=a ⋅ry− a⋅[ry]

и, значит, r  является решением линейного уравнения

(bx− ay)r= n

для некоторого целого n  и, в частности, должно быть рациональным числом. Домножив уравнение (∗)  на знаменатели и воспользовавшись тем, что {rx} =1 − {r|x|},  получим уравнение

b= a{ry} +b{r|x|}.

При r= 0  правая часть равна нулю и поэтому меньше левой. А при r,  близких к 1,  обе дробные части также будут близки к 1,  поэтому правая часть будет близка к a+ b  и, в частности, будет больше левой. Следовательно, при некотором промежуточном r  правая часть будет равна левой. Поэтому если числа x  и y  разных знаков, то требуемое r  обязательно найдётся.

Ответ:

подходят все пары, в которых xy <0

Ошибка.
Попробуйте повторить позже

Задача 7#70486

Есть 2n  карточек, на каждой написано число от 1  до n  (каждое — ровно на двух карточках). Карточки лежат на столе числами вниз. Набор из n  карточек называется хорошим, если на них каждое число встречается по одному разу. Барон Мюнхаузен утверждает, что он может указать 80  наборов по n  карточек, из которых хотя бы один заведомо окажется хорошим. При каком наибольшем n  слова барона могут быть правдой?

Источники: СпбОШ - 2022, задача 11.7(см. www.pdmi.ras.ru)

Подсказки к задаче

Подсказка 1

Задача непростая, поэтому давайте сначала "причёсывать" её, наблюдать какие-то интересные свойства. Например, если у нас набор из n карточек хороший, то оставшиеся n карточек тоже образуют хороший набор(пусть дополнительный набор). Понятно, что слишком большое n взять не получится. Попробуйте изучить, перебрать какие-то n. Понятно, что n=10, наверное, уже слишком много, а n=5, n=6 маловато.

Подсказка 2

Надеюсь, вы порешали сами задачку, и догадываетесь какое примерно максимальное n, а может у вас получилось построить пример для него. При n = 8 и больше уже указать такой набор будет нельзя, т.е. ответ к задаче n = 7. Понятно, что если докажем для 8, то и для больших тоже. Наша цель — предъявить такой способ разметки карточек, чтобы ни один из 80 выбранных наборов не оказался хорошим. Давайте в наших 80 произвольных наборах рассмотрим какую-то карточку A. Можем ли мы сделать так, чтобы она была во всех наборах?

Подсказка 3

Да, меняя наш набор на дополнительный, мы добьёмся присутствия A во всех наборах. А дальше нам глобально нужно убрать плохие наборы, чтобы остались хорошие, но в конце концов, продолжая так делать, всё равно останется плохой набор. Мы докажем, что всегда можно так занумеровать карточки, что все 80 наборов окажутся плохими. Давайте этим и займёмся. Попробуйте понять с помощью принципа Дирихле, хотя бы сколько ещё других карточек B у нас будет? Тогда сколько наборов у нас может оказаться плохими, если цифра на B будет такая же, как у A?

Подсказка 4

Давайте просто аккуратно посчитаем. Оставшихся карточек всего у нас 80 * 7 = 560. А оставшихся карточек, кроме A, у нас 15. Отсюда по принципу Дирихле у нас будет хотя бы 38 карточек B(обозначение из предыдущей подсказки). И вот теперь у нас есть хотя бы 38 наборов с карточками A и B! Тогда пусть на них и оказалось какое-то число 8, теперь все эти наборы плохие. У нас остались 14 карточек(A и B мы убрали) и не больше 42 наборов, где в теории ещё может быть хороший. А теперь аналогично делаем дальше! Попробуйте проделать эти же шаги самостоятельно(их не так много, поэтому лучше, чтобы избежать путаницы и ошибок, сделать всё). Теперь, дойдя до конца процесса, поймите, почему мы доказали оценку? Сколько наборов и карточек остаётся на последнем шаге?

Подсказка 6

Ага, на последнем шаге должен был остаться 1 набор и 4 карточки. Тогда, написав на двух из них число 2, а на двух других число 1, мы победим(даже с запасом)! Мы доказали то, что было написано в 3 подсказке. Осталось разобраться с примером. Мы увидели, что 80 карточек хватает с запасом, поэтому, скорее всего, достаточно брать меньше наборов и среди них будет один хороший. Подумайте, сколько будет достаточно? Это число явно выражается через n.

Подсказка 7

Покажем, что для 2n карточек, мы можем выбрать 2^(n-1) наборов, среди которых точно есть один хороший. Это можно сделать по индукции. База понятна. Пусть на столе лежит 2n+2 карточки, а для 2n мы доказали. Попробуем взять 2 произвольные карточки. Какие варианты тогда возможны? Нужно рассмотреть их и применить предположение индукции!

Подсказка 8

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

Показать ответ и решение

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

Покажем, что для n≥ 8  нельзя так указать 80  наборов, чтобы хотя бы один из них оказался хорошим. Для этого достаточно убедиться в том, что при n = 8  нельзя указать такие 80  наборов. Поскольку, барон выбирает наборы карточек, не зная, какие числа написаны на этих карточках снизу, мы можем считать, что изначально на карточках не было никаких надписей, а числа на карточках появляются уже после того, как выбор сделан. Наша цель — предъявить такой способ разметки карточек, чтобы ни один из 80  выбранных наборов не оказался хорошим.

Итак, пусть выбрано 80  наборов. Рассмотрим произвольную карточку A.  Меняя некоторые наборы на дополнительные, можно добиться того, что карточка A  будет присутствовать во всех наборах. Перечислим с учётом кратности все остальные карточки, встречающиеся в этих наборах. Всего будет перечислено 80⋅7= 560  карточек. Кроме карточки A  у нас имеется 15  карточек, значит, какая-то из них встретится не менее 38  раз(так как 37⋅15 =555< 560  ), назовём её карточкой B.  Напишем на карточках A  и B  число 8,  тогда те 38  (или более) наборов, в которых встречаются обе эти карточки, будут плохими. Уберём карточки A  и B,  останется 14  карточек и 42  (или менее) набора, среди которых должен найтись хотя бы один хороший.

Аналогично зафиксируем одну из оставшихся карточек C  и переделаем наборы так, чтобы карточка C  входила во все наборы. Выписав все остальные карточки, встречающиеся в наборах, получим 42⋅6= 252  карточки. Поскольку, помимо карточки C,  у нас имеется 13  карточек, какая-то из них — назовём её D  — встретится 20  раз(так как 19⋅13= 247 <252  ). Напишем на карточках C  и     D  число 7 — в результате все эти наборы станут плохими. Уберём карточки C  и D,  останется 12  карточек и 22  набора, среди которых опять должен найтись хороший.

Действуя аналогично, получим, что какие-то две карточки встретятся вместе хотя бы в 212⋅15= 10  наборах, напишем на них число  6  и выкинем, останется 10  карточек и 12  наборов. Тогда, поскольку 12⋅94= 513,  какая-то пара карточек встретится в одном наборе хотя бы 6  раз. Написав на этих карточках число 5  и выкинув, мы получим 8  карточек и 6  наборов. Какая-то очередная пара карточек встретится в одном наборе хотя бы 6⋅37 =2 47  раз, напишем на них число 4 и выкинем, в результате получим 6  карточек и 3  набора. Далее какая-то пара карточек встретится в одном наборе хотя бы 3⋅25 = 115  раз, записываем на них число 3  и выкидываем, останется   4  карточки и 1  набор. Напишем на двух карточках из этого набора число 1,  а на двух других — число 2,  тогда и этот набор также окажется плохим. Мы доказали, что всегда можно так занумеровать карточки, что все 80  наборов окажутся плохими.

Покажем теперь, что для 2n  карточек всегда можно выбрать 2n−1  наборов так, чтобы хотя бы один из них оказался хорошим. В нашем случае n= 7  и мы сможем выбрать 26 =64< 80  наборов, что решает задачу. Набор из 2n  карточек, на которых записаны  n  различных чисел(каждое — в двух экземплярах), будем называть двойным.

Пример 1. Докажем индукцией по n,  что для любого двойного набора из 2n  карточек всегда можно предъявить 2n−1  наборов, среди которых есть хороший. База n =1  очевидна.

Пусть на столе лежит двойной набор из 2n+ 2  карточек. Попробуем наудачу выбрать из них две одинаковые карточки, взяв произвольные карточки a  и b.  Самоуверенно отложим их в сторону. Если мы угадали, то на столе остался двойной набор из 2n  карточек, для которого, применив предположение индукции, можно указать 2n−1  наборов, среди которых есть хороший. Теперь для каждого указанного набора M  рассмотрим наборы

Ma = M ∪{a}, Mb = M ∪{b}.

Мы утверждаем, что среди наборов M
 b  и Ma  (а их в сумме получается ровно 2n  штук) непременно найдётся хороший(для исходного множества карточек) набор. Если карточки a  и b  и в самом деле одинаковые, это очевидно — подойдут даже два набора.

Предположим теперь, что на карточках a  и b  написаны разные числа(обозначим их также a  и b  ). Тогда в оставшемся множестве из 2n  карточек были “непарные” карточки с числами a  и b  — мысленно соединим их в новую пару и применим предположение индукции, указав n−1
2  наборов, среди которых есть хороший набор M,  содержащий по одной карточке из каждой пары. На самом деле он содержит ровно одно из чисел новой пары, скажем a,  и по одному представителю всех остальных пар. Но тогда набор Mb  в исходном множестве карточек является хорошим!

Пример 2. Построим граф, вершинами которого являются карточки. Каждую пару карточек с одинаковыми числами соединим красным ребром. Проивзольным образом разобьём карточки на пары и соединим карточки в каждой паре синим ребром. Полученный красно-синий граф(на самом деле мультиграф, поскольку между одной парой вершин может быть проведено и красное, и синее ребро) представляет собой несколько циклов чётной длины. Рассмотрим такой набор его вершин, что в каждом цикле вершины выбраны через одну, назовём его чередующимся набором. Тогда в этом наборе будет присутствовать ровно один конец каждого красного ребра и, значит, он будет хорошим. Проблема в том, что мы, т.е. Мюнхгаузен, не знаем как именно проведены красные рёбра. Но заметим, что любой чередующийся набор содержит ровно по одной вершине каждого синего ребра. Поэтому, указав все  n
2  наборов, содержащих ровно по одной вершине каждого синего ребра, мы заведомо укажем и чередующийся набор. Поскольку набор и его дополнение лишь одновременно могут быть чередующимися, из каждой пары взаимодополняющих наборов достаточно брать только один. Стало быть, достаточно указать лишь  n−1
2  наборов.

Ответ:

при n = 7

Рулетка
Вы можете получить скидку в рулетке!