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

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

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

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

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

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

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

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

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

ПитерГор 2015

ПитерГор 2016

ПитерГор 2017

ПитерГор 2018

ПитерГор 2019

ПитерГор 2020

ПитерГор 2021

ПитерГор 2022

ПитерГор 2023

ПитерГор 2024

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

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

Задача 1#82676

Таблица $100×100$ заполнена числами как показано на рисунке:

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

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

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

Подсказка 1

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

Подсказка 2

Диагональная в 3 цвета! Тогда в каждом прямоугольнике из 3х клеток будет каждый цвет. Тогда попробуем воздействовать на каждый цвет по отдельности так, чтобы сумма в таких прямоугольниках не изменилась.

Подсказка 3

Если в каких-то клетках прибавляем, в каких-то надо отнимать.

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

Рассмотрим раскраску таблицы в три цвета, как показано на рисунке:


1	2	3	…	1

2	3	1	…	2

3	1	2	…	3

$...$	$...$	$...$	$...$	$...$

1	2	3	…	1

Если в исходной таблице к числам цвета 2 прибавить единицу, а из чисел цвета 3 вычесть единицу, то мы получим такую перестановку, что набор чисел сохранится. А сумма в каждой тройке тоже.

Ответ: Можно

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

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

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

Задача 2#82677

Дана последовательность $a n$ : 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, $...$
(одна единица, две двойки, три тройки, четыре четверки и т.д.) и еще одна последовательность $bn$ такая, что $abn =ban$ для всех натуральных $n$ .

Известно, что $bk = 1$ при некотором $k> 100$ . Докажите, что $bm =1$ при всех $m >k$ .

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

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

Подсказка 1

Для начала давайте поймем что-то про последовательность {a_i}. Как минимум поймем на каких местах у нас стоит число k. Это важно для нас, так как если мы хотим выбрать какое-то конкретное m(и посмотреть откуда же может быть получено противоречие), то нам надо понимать, как связан номер и значение a_m. Как зависит значение от m?

Подсказка 2

Для любых номеров m, которые располагаются между t(t + 1)/2 + 1 и (t + 1)(t + 2)/2, a_m = t + 1. Если от нас требуется доказать, что начиная с какого-то номера у нас b_i = 1, не будем мелочиться и докажем, начиная почти для всех(с какого-то маленького), по индукции. Но давайте, для начала, так сказать, для создания благоприятной обстановки, поймем, как все таки делать индукцию. Ведь переход от n к n + 1 здесь кажется странным. Однако переход от k(k + 1)/2 к (k + 1)(k + 2)/2 выглядит более разумно, ведь мы знаем все значения a_i, для i из этого отрезка.

Подсказка 3

Верно, переход такой нам легко дается, так как a_i из этого промежутка равно t + 1, а значит, это b_(t + 1), но для всех меньших мы доказали. Что осталось написать по этой задаче? Является ли это полным решением?

Подсказка 4

Не является, так как t + 1 не всегда входят в уже доказанный промежуток. Для t = 1, 2 - это неверно. Значит, надо в качестве базы использовать t >= 3. Но это подходит под условие нашей задачи, а значит, если у нас b_k = 1, то и все последующие будут равны 1.

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

Возьмём число $m : t(t+1)+ 1≤ m ≤ (t+1)(t+2) 2 2$ , заметим, что для любого такого $m$ $a = t+1 m$ , тогда $b = b = a t+1 am bm$ , тогда если $bm =1$ , то $abm =1$ , тогда $bt+1 =1$ , и наоборот.

Значит, $bt+1 = 1 ⇐⇒ bm = 1$ для $t(t+1) (t+1)(t+2) m ∈ [ 2 + 1; 2 ]$

Значит, и $bt+1 ⁄=1 ⇐⇒ bm ⁄= 1$

Если $b3 =1$ , то

2× 3 3× 4 ∀m ∈ [-2-+ 1;-2--]:bm = 1 т.е. b4 = b5 =b6 = 1

Докажем тогда по индукции, что $∀m > 3 bm = 1.$

База уже есть. Переход будем делать от $m ∈ [3;t(t+21)]$ к $m ∈[3;(t+1)2(t+2)].$

Заметим, что $t+ 1< t(t+21)$ при $t>3 ⇒ bt+1 = 1$ , но по предположению индукции $∀m ∈ [t(t+21)+ 1≤ m≤ (t+1)2(t+2)]:bm =1$ , значит,

∀m ≥3 :bm = 1, если b3 = 1

Аналогичными рассуждениями

∀m ≥3 :bm ⁄= 1, если b3 ⁄= 1

Итого т.к. $bk =1$ , $k> 100$ , то $b3 =1$ , а значит, $∀m > 3$ :

bm = 1⇒ ∀m > k bm =1

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

Задача 3#82678

В неравнобедренном треугольнике $ABC$ проведена биссектриса $AK$ . Диаметр $XY$ его описанной окружности перпендикулярен прямой $AK$ (порядок точек на описанной окружности $B − X− A − Y − C$ ). Окружность, проходящая через точки $X$ и $Y$ , пересекает отрезки $BK$ и $CK$ в точках $T$ и $Z$ соответственно. Докажите, что если $KZ = KT$ , то $XT ⊥Y Z$ .

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

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

Подсказка 1

Если сделать аккуратный чертеж, то кажется, что продолжения ХТ, АК и YС пересекаются в одной точке на описанной окружности треугольника АВС.

Подсказка 2

Предыдущий факт сложно доказывать напрямую, стоит применить обратный ход.

Подсказка З

Обозначим пересечение луча АК с описанной окр-тью АВС за L. Пересечение LХ и LY с ВС обозначим Т₁ и Z₁. Хотим показать, что XТ₁Z₁Y является вписанным. Используя, что дуги ВL и LС равны (из-за биссектрисы), можно посчитать сумму противоположных углов данного четырехугольника. Следующий шаг — показать равенство Т₁К и КZ₁.

Подсказка 4

Чтобы показать равенство Т₁К и КZ₁:

Подсказка 5

Осталось показать, что такой четырехугольник единственный. Пересечением чего является центр описанной окружности вписанного четырехугольника? Посмотрите, где лежит центр окружности описанной около XT₁Z₁Y.

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

Применим обратный ход. Обозначим пересечение луча $AK$ с $(ABC )$ за $L.$ Пересечение $LX$ и $LY$ с $BC$ обозначим $T 1$ и $Z. 1$ Теперь нам надо доказать, что $XY Z1T1$ вписанный и $KZ1 = KT1,$ так как получится, что точки $T$ и $Z$ из условия совпадают с ними.

$PIC$

∠XY L = ⌣-LYX-= ⌣-XY-B+-⌣-BY-L = ⌣-BT1X+-⌣-LT1C-=∠LT1C 2 2 2

Тогда получили, что $T1XY Z1$ вписанный, так как внутренний угол равен противоположному внешнему. Теперь обратим внимание на то, что треугольники $XYL$ и $T1Z1L$ подобные, а в прямоугольном треугольнике высота и медиана образуют равны углы со сторонами. Поэтому так как $LK$ высота в треугольнике $XY L,$ то $LK$ является медианой в треугольнике $LT1Z1.$ Значит, $K$ середина $T1Z1,$ откуда получаем то, что мы хотели в начале.

Заметим, что четырехугольник из условия единственный, ведь его центр лежит на серединном перпендикуляре к $XY$ и на перпендикуляре к $BC,$ восставленному в $K.$

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

Задача 4#82679

Дано $101$ -значное число $a$ и произвольное натуральное число $b.$ Докажите, что найдется такое не более чем $102$ -значное число натуральное число $c,$ что любое число вида $caaa...ab$ — составное.

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

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

Из признака делимости на $10101+1$ (необходимо рассмотреть знакочередующуюся сумму блоков по $101$ цифре с конца) следует, что числа в которых количество $a$ в записи отличается на четное число имеют одинаковые остатки при делении на $101 10 +1.$
Заметим, что $101 10 +1 ≡11 0,$ а еще по лемме об уточнении показателя $101 10 +1$ не делится на $2 11 ,$ поэтому у $101 10 + 1$ есть простой делитель $p$ отличный от $11.$
Достаточно сделать так, чтобы $cb$ и $cab$ делились на $11$ и на $p$ соответственно. Такое $c$ существует и не превосходит $101 11× p≤ 10 + 1$ по китайской теореме об остатках.

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

Задача 5#82681

На плоскости отмечено 100 точек общего положения (т.е. никакие три не лежат на одной прямой). Докажите, что можно выбрать три отмеченные точки $A$ , $B$ , $C$ так, чтобы для любой точки $D$ из оставшихся 97 отмеченных точек, прямые $AD$ и $CD$ не содержали бы точек, лежащих внутри треугольника $ABC$ .

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

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

Подсказка 1

Прямые, соединяющие точки A, B, CЮ делят плоскость на 7 частей, включая треугольник внутри. Рассмотрите эти части. Точки D из каких частей нам подходят?

Подсказка 2

Видно, что подходящие части тем больше, чем больше угол АВС. Воспользуемся принципом крайнего и возьмём такие 3 точки, чтобы АВС был максимальным. Проверим, подходит ли нам этот случай, пойдя от противного: пусть они не подходят. Тогда в каких частях может находиться точка D?

Подсказка 3

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

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

Применим принцип крайнего: выберем среди всех троек точек треугольник $ABC$ с самым большим углом $B.$

Предположим, что точки $A$ , $B$ , $C$ не подходят. Тогда существует точка $D$ в объединении частей плоскости, одна из которых заключена между прямыми $AC$ и $AB,$ а другая — между прямыми $CA$ и $CB.$

При этом $D$ не может лежать внутри треугольника $ABC$ , иначе $∠ADC >∠ABC$ .

$PIC$

Рассмотрим случай, когда $D$ лежит между лучами $AC$ и $AB$ (когда $D$ и $A$ лежат в разных полуплоскостях относительно $BC$ ). Тогда

∠ABD = ∠ABC +∠CBD > ∠ABC

получаем противоречие. То же работает для случая, когда $D$ лежит между лучами $AC$ и $BC$ .

$PIC$

Оставшиеся два случая (когда $D$ и $C$ лежат в разных полуплоскостях относительно $AB$ ) рассматриваются аналогично: в них

∠ABD = ∠CBA +∠ABD > ∠ABC

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

Задача 6#82682

Дан многочлен $P(x)$ с целыми коэффициентами. Для некоторого натурального $n$ числа $P (0),P(1),...,P (2n+ 1)$ делятся на $22n$ . Докажите, что значения многочлена $P(x)$ во всех целых точках делятся на $2n 2$ .

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

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

Подсказка 1

Чтобы доказать, что у нас многочлен во всех точках кратен чему-то, бывает удобно представлять этот многочлен в виде, когда мы поделили его на какой-то другой с остатком, то есть представить P(x) = Q(x) * S(x) + R(x), и делили мы на многочлен на Q(x). Тогда если мы докажем, что во всех точках Q и R кратны чему-то, то докажем это и для P(x). Тогда, давайте сразу возьмём в качестве Q какой-то многочлен, который кратен 2^2^n. К примеру, x(x - 1)…(x - (2^n + 1)). Докажите, что такой многочлен действительно кратен 2^2^n, а после поймите какие условия тогда мы получаем на R(x).

Подсказка 2

Q(x) кратен, поскольку у нас произведениe k последовательных целых чисел кратно k!, и при этом у k! мы можем посчитать степень вхождения 2. В таком случае, на R(x) накладываются ровно такие же условия, как на P(x). А что значит, если многочлен, который принадлежит Z[x](поймите почему), и имеет степень меньшую, чем у Q, а также в хотя бы в deg(Q) подряд идущих целых точках кратен некоторому числу?

Подсказка 3

Это значит, что он кратен этому числу во всех целых точках, поскольку мы можем поделить на это целое число и индукцией показать, что если многочлен целочисленный в хотя бы t+1 подряд идущей целой точке, при том, что его степень не больше t, то он целочисленный во всех целых точках. Что тогда это нам даёт в рамках задачи?

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

Среди $2n +2$ подряд идущих целых чисел $x$ , $x − 1$ , …, $x− (2n +1)$ есть хотя бы $[(2n+ 2)∕2]$ кратных двум, хотя бы $[(2n+ 2)∕4]$ кратных $4$ , и т.д. Значит, суммарная степень вхождения $2$ в их произведение не меньше

∑ n k ∑ n−k n−1 n−2 n− 3 n [(2 +2)∕2 ]= 1+ [2 ]= (2 + 1)+2 + 2 +...+1= 2 k k

Поэтому все значения многочлена $Q(x)= x(x− 1)...(x− (2n +1))$ в целых точках кратны $22n.$

Поделим $P(x)$ на $Q(x)$ с остатком: $P(x)=Q (x)S(x)+R(x)$ . Поскольку старший член $Q(x)$ равен 1, $R (x)∈ ℤ[x]$ , причем $R(x)$ будет удовлетворять тем же условиям, которым удовлетворяет $P(x)$ , и к тому же будет иметь степень не выше $2n+ 1$ . Поделив его на $22n$ , мы получим многочлен степени не выше $2n+1$ , значения которого $2n+2$ подряд идущих целых точках целые. Из этого следует, что целыми являются все его значения в целых точках (это доказывается по индукции с использованием разностного многочлена). Таким, образом, у многочлена $R(x)$ все значения в целых точках кратны $22n$ , а тогда это верно и для многочлена $P (x)$ .

Курсы

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

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

Задача 7#82683

Турист прибыл на остров, где живут 100 волшебников, каждый из которых может быть рыцарем или лжецом. Он знает, что на момент его приезда один из ста волшебников — рыцарь (но не знает, кто именно), а остальные — лжецы. Турист может выбрать любых двух волшебников $A$ и $B$ и попросить $A$ заколдовать $B$ заклинанием Вжух!, которое меняет сущность (превращает рыцаря в лжеца, а лжеца в рыцаря). Волшебники выполняют просьбы туриста, но если в тот момент волшебник $A$ — рыцарь, то сущность $B$ действительно меняется, а если $A$ — лжец, то не меняется. Турист хочет после нескольких последовательных просьб одновременно знать сущность хотя бы $k$ волшебников. При каком наибольшем $k$ он сможет добиться своей цели?

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

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

Подсказка 1

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

Подсказка 2

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

Подсказка 3

Рассмотрите первый такой случай. А что было до?

Подсказка 4

В целом не за что зацепиться, кроме как за последний "вжух" в этом множестве. Разберем случаи роли человека, который мог его сказать?

Подсказка 5

Осталось лишь придумать пример...так как мы хотим узнать роль одного, попробуем минимизировать число людей, которые меняли свой облик!

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

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

Изначально такого множества точно нет. Рассмотрим первый момент, когда удалось про некоторое множество $A$ доказать, что в нем четное число рыцарей. Пусть последним ходом «Вжух!» говорил волшебник $b$ . Несложным переборов вариантов можно убедится, что на прошлом ходу симметрическая разность $A$ и $b$ тоже содержала четное количество рыцарей, что противоречит выбранному первому такому моменту.

_________________________________________________________________________________________________________________________________________________________________________________

Пример. Пусть все волшебники с $1$ -го по $99$ -го поменяют сущность $100$ -го. Легко видеть, что в результате он в любом случае станет рыцарем.

Ответ: 1

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Предыдущая подтема


1	2	3	…	100

101	102	103	…	200

$.. .$	$.. .$	$.. .$	$.. .$	$.. .$

9901	9902	9903	…	10000