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

ПитерГор - задачи по годам → .11 ПитерГор 2023

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

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

Разделы подтемы ПитерГор - задачи по годам

ПитерГор 2014 и ранее

ПитерГор до 2014

ПитерГор 2015

ПитерГор 2016

ПитерГор 2017

ПитерГор 2018

ПитерГор 2019

ПитерГор 2020

ПитерГор 2021

ПитерГор 2022

ПитерГор 2023

ПитерГор 2024

Решаем задачи

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

Задача 1#89862

Пусть $f(x)$ — квадратный трёхчлен, $g(x)$ —многочлен степени 3. Может ли многочлен $f(g(x))$ иметь шесть различных корней, являющихся степенями 2?

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

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

Заметим, что многочлен $g(x)$ принимает каждое действительное значение не более 3 раз, так как у него степень ровно 3. Если $a$ — корень $f(g(x))$ , то $g(a)$ — корень квадратного трёхчлена $f(x) =⇒$ 6 корней у многочлена $f(g(x))$ достигаются только в том случае, если у $f(x)$ есть 2 различных корня, каждый из которых достигается ровно трижды многочленом $g(x)$ . Скажем, $a,b$ — корни $f(x)$ , $a1 a2 a3 2 ,2 ,2$ — корни многочлена $g(x)− a$ , $b1 b2 b3 2 ,2 ,2$ — корни многочлена $g(x)− b$ . Тогда справедливо следующее:

k1(x− 2a1)(x− 2a2)(x − 2a3)+a =g(x)=k2(x− 2b1)(x− 2b2)(x− 2b3)+b

Понятно, что $k = k ⁄= 0 1 2$ , как коэффициенты при $x3$ . Рассмотрим коэффициент при $x2$ у левой и правой части равенства:

a a a b b b k1(21 +2 2 + 23)= k1(21 +2 2 + 23)

a1 a2 a3 b1 b2 b3 2 + 2 +2 = 2 + 2 +2

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

Ответ: нет

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

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

Задача 2#89865

В треугольнике $ABC$ проведена медиана $BM$ . На продолжении стороны $AC$ за точку $C$ отмечена такая точка $D$ , что $BD = 2CD.$ Описанная окружность треугольника $BMC$ пересекает отрезок $BD$ в точке $N.$ Докажите, что $AC +BM >2MN.$

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

$PIC$

По условию $BNCM$ — вписанный четырехугольник. Следовательно, $∠DMB =∠DNC,$ поэтому треугольники $DMB$ и $DNC$ подобны.

Стало быть, $BMCN = BCDD-=2$ и, значит, $BM = 2CN$ .

Таким образом, $AC +BM =2(MC + CN )$ и осталось доказать, что $MC + CN >MN$ . Но это просто неравенство треугольника для $△MNC$ .

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

Задача 3#89867

Несократимые дроби $a b$ и $c d$ записали в виде чисто периодических десятичных дробей. Оказалось, что любая конечная последовательность подряд стоящих цифр, встречающаяся в первой десятичной дроби после запятой, встречается и во второй (тоже подряд и тоже после запятой). Докажите, что $b= d.$

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

Давайте для удобства считать, что $0≤ a< b$ и $0 ≤c< d$ , иначе вычтем целую часть дробей, не изменив дробную часть, получив $a$ и $c$ в нужном диапазоне (условие на несократимость дробей останется). Скажем, что

a c b = 0,(T1) d = 0,(T2),

(1)

$m1$ — количество цифр в записи $T1$ , $m2$ – количество цифр в записи $T2$ ( $T1$ и $T2$ — периоды наших дробей).

Рассмотрим последовательно написанный $T1$ $m2$ раз (такая последовательность в первой дроби есть), по условию она же есть, и во второй, причём в ней $m1m2$ цифр, значит, во второй дроби эта последовательность является сдвигом $T2$ , записанным $m1$ раз. Тогда скажем, что во второй дроби построенная последовательность перед первым $T2$ имеет кусок $k1$ , оставшийся кусок из $T1$ назовём $k2$ , то есть $---- T1 = k1k2$ . Тогда эта же последовательность во второй дроби выглядит как $k1$ , $T2$ , написанный $m1− 1$ раз, и остаток $k$ , причём $--- T2 =kk1$ . Обозначим рассматриваемую последовательность за $T$ ( $--------- -------- k1k2...k1k2 =T = k1k...k1k$ ), тогда:

a =0,(k1k2)=0,(T) b

(2)

c --- d =0,(kk1)= 0,k(T)

(3)

Скажем, $m$ — количество цифр в $T$ , $n$ —- количество цифр в $k$ . Тогда верно следующее:

a⋅10m =T,(T ) b

(4)

c ⋅10n = k,(T) d

(5)

c --- d ⋅10n+m = kT,(T)

(6)

Вычитая (2) из (4) и (5) из (6) соответственно, получаем:

a ⋅(10m − 1)= T b

(7)

c⋅10n(10m − 1)= T +k(10m − 1) d

(8)

Подставим $T$ из (7) равенства в (8), получим:

c⋅10n(10m − 1)= a ⋅(10m− 1)+k(10m− 1) d b

c n a n d ⋅10 = b +k =⇒ bc⋅10 = ad+ bdk

. . ad..b и bc⋅10n..d

Вспомним, что пары чисел $(a,b)$ и $(c,d)$ взаимно просты. Значит, $d..b .$ и $b⋅10n ..d .$ .

Докажем, что $n 10$ и $d$ взаимно просты. Из (1):

c ⋅(10m2 − 1)=T2 =⇒ c⋅(10m2 − 1)= T2d =⇒ 10m2 − 1...d, d

ибо $c$ и $d$ взаимно просты.

Если НОД $(10n,d)...p$ — простое, то $10m2 − 1$ уж точно на $p$ не делится, но тогда и на $d$ делиться не может, противоречие, тогда рассматриваемый НОД равен 1, что эквивалентно искомой взаимной простоте, откуда следует, что $b⋅10n ...d ⇐ ⇒ b ...d$ . Тогда у нас $d...b$ и $b...d =⇒ b=d$ , что и требовалось.

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

Задача 4#89869

За какое наименьшее число операций можно перекрасить в чёрный цвет белую доску $100× 100,$ если за одну операцию можно перекрасить в противоположный цвет любые 99 клеток любой горизонтали или любой вертикали?

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

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

Оценка.

Будем говорить, что выполнили операцию в клетке, если перекрасили все 99 клеток в строке или столбце кроме данной. Пусть были операции над строками в клетках $a1,a2,...,an$ и над столбцами $b1,b2,...,bk$ .

Отметим два факта:

1.: Количество операций четно, ведь операция меняет четность числа черных клеток, тогда достаточно показать, что $n +k ≥199$ .
2.: Порядок выполнения операций не влияет на конечный результат перекрашивания.

Если дважды к одной клетке в строке применить операцию, то ничего не изменится, поэтому можно считать, что таких ходов нет. Аналогично для столбцов. Если в строчке применить операцию к двум различным клеткам, то результатом этих двух ходов будет перекрашивание рассматриваемых клеток. Будем выделять пары таких ходов в столбцах и строках, обозначим такую пару ходов как операцию I-го типа (пусть их будет $r$ штук). Пусть после этого осталось $p$ ходов в строчках (обозначим как операцию II-го типа), $q$ ходов в столбцах (обозначим как операцию III-го типа) Отметим, что $p,q ≤100$ , так как в противном случае найдётся две клетки в одной строке или столбе, которые можно объединить в операцию I-го типа. Тогда хотим доказать, что

p+q +2r≥ 199

Рассмотрим несколько случаев:

1.

$p,q ≤ 99$

Тогда клеток НЕ находящихся в столбцах и строках, где были операции II-го или III-го типа $(100− p)⋅(100 − q)$ , а любая операция I-го типа перекрашивает не более двух клеток, тогда всего ходов хотя бы

p+ q+ 2⋅ (100−-p)(100− q)= 1002− 99(p+q)+ pq = 199+ (99 − p)(99− q)≥199 2

2.

$p =100,q =0$

После выполнения операций II-го типа останется ровно 100 белых клеток. $q = 0$ , значит, операций III-го типа нет, тогда для перекрашивания белых клеток понадобиться хотя бы 50 операций I-го типа. Получаем, что всего операций не меньше, чем $(100+2 ⋅50)= 200$ .

3.

$p =100,q ≥2$

После операций II-го типа останется ровно 100 белых клеток, причём по одной в каждой строке. После выполнения операций III-го типа белых клеток останется хотя бы $99q− 100$ (так как в каждом из q столбцов перекрашивается по 99 клеток, все они чёрные, кроме, может быть, 100 белых клеток, тогда после применения операции белыми станут хотя бы $99q − 100$ ). Тогда потребуется еще хотя бы $99q− 100$ ходов, значит, всего шагов не менее

100+ q+99q− 100 ≥200

4.

$p =100,q$ : — нечётное.

Этот случай невозможен по чётности количества ходов.

Случаи для $q = 100$ аналогичны случаям для $p =100$ .

_________________________________________________________________________________________________________________________________________________________________________________

Пример.

Выполним операцию III-го типа ко всем клеткам из первой строки. Это 100 ходов. Далее применим операцию I-го типа к парам из клеток первой строки (на пары разобьем последовательно , то есть 1-ая и 2-ая клетки, 3-яя и 4-ая, $...$ , 99-ая и 100-ая). Это ещё $2 ⋅50 =100$ ходов. Итого 200.

Ответ: 200

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

Задача 5#89870

Дано натуральное число $a> 1.$ Определим функцию

√ - f(n)= n +[a{n 2}].

Докажите, что существует такое натуральное $n,$ что $f(f(n))= f(n)$ , но $f(n)⁄= n.$

Напомним, что $[x]$ — целая часть $x,$ то есть наибольшее целое число, не превосходящее $x,$ а ${x} =x − [x]$ — дробная часть $x.$

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

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

Для решения задачи нам понадобится два классических утверждения из теории чисел.

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Дирихле. Для любого иррационального числа $𝜃$ и натурального числа $m$ найдется такое число $k$ , $1≤ k≤ m− 1$ , что $1- {k𝜃}< m$ или $1- {k𝜃}> 1− m$ .

_________________________________________________________________________________________________________________________________________________________________________________

Теорема Кронекера. Для любого иррационального числа $𝜃$ и любых чисел $α$ , $β$ , $0 ≤α <β < 1$ , найдется такое натуральное число $n$ , что ${n𝜃}∈ (α,β)$ .

_________________________________________________________________________________________________________________________________________________________________________________

Применим теорему Дирихле для $√ - 1 𝜃 = 2+ a$ и $m =a$ и найдем такое $1≤ k≤ a− 1$ , что

{ √- 1 } 1 { √- 1 } 1 k( 2+ a) < a или k( 2+ a) > 1− a.

______________________________________________________________________________________________________________________________________________________

В первом случае имеем неравенство $a−ak< {k√2}< a+1a−k$ . Применим теорему Кронекера для

𝜃 =√2, α= k и β = a+-1− {k√2}> k, a a a

получим, что найдется такое $n$ , что $k< {n√2}< a+1− {k√2} a a$ . Для этого $n$ имеем

k< a{n√2}< a(a+-1− {k√2})< a( a+1-− a−-k)= k+ 1. a a a

Следовательно, $√- [a{n 2}]=k$ и $f(n)= n+ k$ . Поскольку

k a− k √- √ - a+1- 1= a + a < {n 2}+{k 2} < a ,

дробная часть числа $√- (n+ k) 2$ меньше, чем $1 a$ , поэтому

√- [a{(n +k) 2}]=0.

В итоге $f(n)= n+ k,$ поэтому

f(f(n))= f(n+ k)= n +k= f(n)⁄= n

______________________________________________________________________________________________________________________________________________________

В случае ${k(√2 + 1)}> 1− 1 a a$ выполняется неравенство

a-− k √ - a+1-− k a < {k 2} < a .

Применяя теорему Кронекера для

√ - √ - k+ 1 k+ 1 𝜃 = 2, α= 1− {k 2}< -a-- и β =--a-,

получим, что найдется такое $n$ , что $√- k+1 1< {n 2}< -a-$ . Для этого $n$ имеем

k< a{n√2}< k+ 1.

Следовательно, $√- [a{n 2}]=k$ и $f(n)= n+ k$ . Поскольку

√ - √- 1< {n 2}+{k 2} <1− ka + k+a1-= a+a-1,

дробная часть числа $√- (n+ k) 2$ меньше, чем $1a$ , поэтому

[a{(n +k)√2}]=0.

В итоге $f(n)= n+ k,$ поэтому

f(f(n))= f(n+ k)= n +k= f(n)⁄= n

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

Задача 6#89872

Дан треугольник $ABC.$ Точка $X$ симметрична вершине $B$ относительно прямой $AC,$ а точка $Y$ симметрична $C$ относительно $AB.$ Касательная к описанной окружности треугольника $XAY,$ проведенная в точке $A,$ пересекает прямые $XY$ и $BC$ в точках $E$ и $F$ соответственно. Докажите, что $AE = AF.$

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

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

Пусть $B ′,C′$ — отражения $B,C$ относительно $A$ соответственно, $D$ — пересечение $YC ′$ и $XB ′$ .

Из определения точки $′ C$ и того факта, что $Y$ и $C$ симметричны относительно $AB$ , получаем, что прямая $AB$ проходит через середины отрезков $CY$ и $′ CC$ . Т.е. $AB$ — прямая, содержащая среднюю линию $′ △CC Y$ $⇒$ $AB ∥DY$ . Аналогично, $AC ∥DX$ . Из этих двух параллельностей следует, что $′ ′ ∠YC A= ∠XB A$ .

$PIC$

В силу симметрий из условия

∠C′AY = 180∘− ∠YAC = 180∘− 2∠BAC = 180∘ − ∠BAX =∠XAB ′

Вместе с предыдущим фактом получаем, что $△AC ′Y ∼ △AB ′X$ . Отсюда получим, что $′ YXCB′ = AAYX$ .

Также вспомним, что $△EAX ∼ △EY A$ , откуда следует, что

EX-= EX-AE-= AX- AX- EY AE EY AY AY

Теперь докажем, что $E$ , $B ′$ и $C′$ лежат на одной прямой по теореме, обратной к теореме Менелая:

DC′Y-EXB-′= DC-′YE-XB-′= AB-AY2-AX-= 1 C′Y EX B ′D B′D EX C′Y AC AX2 AY

В силу симметрии относительно $A$ получаем $AE = AF.$

Курсы

Всё необходимое для достижения цели

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

Задача 7#89873

В связном графе $G$ даны два непересекающихся множества вершин $X$ и $Y,$ между этими множествами нет ни одного ребра. Пусть в графе $G − X$ ровно $m$ компонент связности, а в графе $G − Y$ ровно $n$ компонент связности. Какое наименьшее количество компонент связности может быть в графе $G− (X∪ Y)?$

Напомним, что для множества вершин $W$ через $G − W$ обозначается граф, полученный из $G$ в результате удаления всех вершин множества $W$ и всех выходящих из них ребер.

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

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

Пример графа показан на рисунке. Множество $X$ содержит $m− 1$ вершину, множество $Y$ — $n− 1$ вершину.

$PIC$

_________________________________________________________________________________________________________________________________________________________________________________

Оценка. Для графа $G = (V,E)$ и некоторого множества его ребер $E′ ⊂ E$ через $G∖E′$ обозначим граф, получающийся из графа $G$ удалением всех его ребер, входящих в $E ′$ , т.е. граф $(V,E∖E′)$ .

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $G$ — связный граф, и пусть $E1$ и $E2$ — два непересекающихся множества его ребер. Обозначим через $ni$ ( $i= 1,2$ ) количество компонент связности графа $G ∖Ei$ . Тогда количество компонент связности графа $G ∖(E1∪ E2)$ не меньше, чем $n1+ n2− 1$ .

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство. Пусть в графе $H = G∖(E1∪E2)$ ровно $k$ компонент связности. Если добавить к $H$ все ребра из множества $E2$ , то получится $n1$ компонент связности. Поэтому если мы будем последовательно добавлять в граф $H$ те ребра из $E2$ , которые уменьшают число компонент связности, то, добавив в точности $k− n1$ ребер из $E2$ , получим $n1$ компонент связности (поскольку добавление каждого ребра уменьшает число компонент связности не более, чем на 1). Добавление остальных ребер из $E2$ уже не уменьшит количество компонент связности. Аналогично к графу $H$ можно добавить такие $k − n2$ ребер из множества $E1$ , что в итоге получаются все $n2$ компонент связности графа $G∖E2$ . Но если к графу $H$ добавить и те, и другие ребра (в общей сложности $(k − n )+ (k− n ) 1 2$ ребер), то граф станет связным. Следовательно, $(k− n)+ (k− n )≥ k− 1 1 2$ и, значит, $k ≥n + n − 1 1 2$ .

_________________________________________________________________________________________________________________________________________________________________________________

Обозначим через $vX$ и $vY$ количества вершин в множествах $X$ и $Y$ . Пусть $EX$ — множество ребер, хотя бы один конец, который лежит в $X$ , а $EY$ — множество ребер, хотя бы один конец которых лежит в $Y$ . Поскольку между вершинами из $X$ и $Y$ нет ни одного ребра, множества $EX$ и $EY$ не пересекаются. Тогда в графе $G ∖EX$ ровно $vX +m$ компонент связности (среди них $vX$ компонент состоят из одной вершины), в графе $G∖EY$ ровно $vY + n$ компонент связности, а в графе $G ∖(EX ∩EY )$ ровно $k+ vX + vY$ компонент связности, где $k$ — число компонент связности в графе $G− X − Y$ . Тогда по лемме