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

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

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

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

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

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

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

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

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

ПитерГор до 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	…	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)

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

Возьмём число $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)

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

Применим обратный ход. Обозначим пересечение луча $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)

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

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

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

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

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

∠ABD = ∠ABC +∠CBD > ∠ABC

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

Оставшиеся два случая (когда $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)

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

Среди $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)

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

Ответ: 1

Интенсивы

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

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


1	2	3	…	100

101	102	103	…	200

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

9901	9902	9903	…	10000