СПБ олимпиада 2024

[Stensen]

Всем доброго здравия. Уважаемые, помогите решить. И всего более интересует вопрос, в какой литературе можно почитать про общие методы и подходы к решению такого рода задач (с разбором примеров). Подскажите пожалуйста.

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

2. Какое число больше: $^{97}\sqrt{2} +\; ^{102}\sqrt{2} +\; ^{100}\sqrt{2^{99}}$ или $4$ ?

3. Андрей записал в тетрадку натуральные числа $n, \; n^2,\; n^3,\; n^4$. Оказалось, что в их записи цифры $4, 5, 6, 7, 8, 9$ использовались поровну раз, и цифры $0, 1, 2, 3$ поровну раз, причем цифра $0$ - на один раз больше, чем цифра $4$. На какую цифру начинается число $n$?

[мат-ламер]

Stensen в сообщении #1661796 писал(а):

2. Какое число больше: $^{97}\sqrt{2} +\; ^{102}\sqrt{2} +\; ^{100}\sqrt{2^{99}}$ или $4$ ?

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

[Stensen]

мат-ламер в сообщении #1661814 писал(а):

Stensen в сообщении #1661796 писал(а):

2. Какое число больше: $^{97}\sqrt{2} +\; ^{102}\sqrt{2} +\; ^{100}\sqrt{2^{99}}$ или $4$ ?

Третье меньше корня из двух.

Третье же около двух? $ ^{100}\sqrt{2^{99}} =2^{\frac{99}{100}} \approx 2 <2 $

[мат-ламер]

Stensen в сообщении #1661818 писал(а):

Третье же около двух?

Кстати, да. Извиняюсь.

-- Пн ноя 18, 2024 10:11:07 --

Но какие-то оценки для каждого из сомножителя вы можете предложить? Для третьего слагаемого более точное что-нибудь есть?

[Shadow]

Сумма первых двух слагаемых сравнить с $2\cdot 2^{1/100}$

Потом АМ-ГМ для $2^{101/100}+2^{99/100}$

[Stensen]

Shadow в сообщении #1661822 писал(а):

Сумма первых двух слагаемых сравнить с $2\cdot 2^{1/100}$

Потом АМ-ГМ для $2^{101/100}+2^{99/100}$

Дико извиняюсь. Что такое АМ-ГМ ?

[worm2]

Что я могу рассказать про общий подход на примере задачи 1 (спойлер: я её пока не решил).
Общий подход называется "метод раскраски". Не знаю, где про него можно почитать (наверное, в какой-нибудь книжке "Методы решения олимпиадных задач"), но он состоит в том, что клетки раскрашиваются каждая в свой цвет, следуя какой-то регулярной схеме. Сразу хочу предупредить: это НЕ ТА раскраска, про которую говорится в задаче, а совсем другая! В условиях задачи логично было бы раскрасить доску в шахматном порядке, скажем, на плюсы и минусы, чтобы не путать с цветами задачи. Почему именно в шахматном? По условиям задачи получается, что за каждый ход раскрашивается ровно одна "плюсовая" клетка и ровно одна "минусовая". Следовательно, при любой раскраске у нас "плюсовые" клетки будут покрашены ровно столько же раз, сколько и "минусовые". Предположительно, это может пригодиться в дальнейшем решении.
Это стандартный путь решения, который сразу приходит матёрому олимпиаднику, так сказать, в спинной мозг. Но дальше нужно думать уже головным.
Задача нестандартная, хотя такое можно сказать про любую олимпиадную задачу, но вот конкретно эта за один стандартный шаг не решается.
Какие могут быть дальше рассуждения? По условию задачи из доски вырезаны 25 плюсов (ну или 25 минусов, зависит от того как раскрасим), значит, осталось 25 "плюсовых" клеток и 50 "минусовых".
Каждую клетку можно красить не более двух раз. Значит, 25 "плюсовых" клеток раскрашены не более 50 раз суммарно, значит, 50 "минусовых" тоже раскрашены не более 50 раз (среди них могут быть дважды покрашенные и ни разу не покрашенные, так что рассуждения типа "каждая раскрашена ровно один раз" никак не прокатывают).
Здесь я остановился, и мне с этой точки не видно решения. Возможно, это тупик, а выход из лабиринта где-то в другом месте. А возможно, разгадка близка, просто я недостаточно подумал.

Вот ещё стандартная раскраска: разбиваем доску на квадратики 2x2 клетки. В каждом квадратике клетки "раскрасим" А, Б, В и Г. Всего 25 клеток "А", 25 клеток "Б", 25 клеток "В" и ни одной клетки "Г" (их вырезали). Тоже пока не вижу тут путей дальнейшего движения.

Но это же хорошо, когда олимпиадная задача не решается одним только стандартным приёмом! На то она и олимпиадная.

Генри Роллинз (https://pikabu.ru/story/motivatsiya_na_urovne_filosofii_9289497) писал(а):

Когда Железо не желает сниматься с крюков, это самое большое добро, которое оно может тебе принести.

[Shadow]

Stensen в сообщении #1661823 писал(а):

Дико извиняюсь. Что такое АМ-ГМ ?

неравенство между средним арифметическим и средним геометрическим, в случае $a+b \ge 2\sqrt{ab}$

[Stensen]

Спасибо, буду размышлять

[worm2]

worm2 в сообщении #1661861 писал(а):

А возможно, разгадка близка, просто я недостаточно подумал.

Ну да, отсюда до разгадки совсем близко.
25 "плюсовых" клеток красятся не более 50 раз. А на каждом ходе одна "плюсовая" клетка обязательно красится. Следовательно, можно сделать максимум 50 шагов. На каждом шаге число зелёных клеток может вырасти не больше чем на 1. Значит, будет раскрашено в зелёный цвет не более 50 клеток.
Осталось только предъявить раскраску, в которой ровно 50 зелёных клеток. Но это легко можно сделать разными способами, я не буду приводить.
Хорошая задача: знание "приёмчиков" сильно облегчает решение, но на одном таком знании не получается её решить.

[мат-ламер]

мат-ламер в сообщении #1661819 писал(а):

Но какие-то оценки для каждого из сомножителя вы можете предложить? Для третьего слагаемого более точное что-нибудь есть?

Тут я имел в виду, что функция $f(x)=2^x$ выпукла и её график располагается выше касательной прямой.

[TOTAL]

Третье слагаемое можно представить в виде суммы $2^{-1/100}+ 2^{-1/100}$.
Четыре полученных (теперь почти одинаковых) слагаемых уже оценивайте с помощью указанного неравенства.

[svv]

Stensen в сообщении #1661796 писал(а):

3. Андрей записал в тетрадку натуральные числа $n, \; n^2,\; n^3,\; n^4$. Оказалось, что в их записи цифры $4, 5, 6, 7, 8, 9$ использовались поровну раз, и цифры $0, 1, 2, 3$ поровну раз, причем цифра $0$ - на один раз больше, чем цифра $4$. На какую цифру начинается число $n$?

Возьмём произвольное $n\in\mathbb N$. Пусть
$D(n)$ — число цифр ($Digits$) в записи числа $n$,
$T(n)=D(n)+D(n^2)+D(n^3)+D(n^4)$ — общее ($Total$) число цифр в записи этих степеней.
Назовём $n$ хорошим, если $T(n)\operatorname{mod}10=4$, а иначе плохим. Из условия видно, что у Андрея хорошее число $n$.

Функция $T$ — (нестрого) возрастающая. Посмотрим, как себя ведёт $T(n)$ при $10^m\leqslant n<10^{m+1}$, где $m\in\mathbb N$.
Поскольку $D(10^m)=m+1$, то
$T(10^m)=(m+1)+(2m+1)+(3m+1)+(4m+1)=10m+4$
Итак, число $10^m$ хорошее. И $10^{m+1}$, «открывающее» следующий разряд, тоже хорошее:
$T(10^{m+1})=10(m+1)+4$

К Вам вопросы:
1) Хорошее ли число $2\cdot 10^m$ ?
2) Может ли $n$ быть хорошим, если $2\cdot 10^m\leqslant n<10^{m+1}$ ? Почему?

[TOTAL]

В третьей задаче про Андрея, тетрадку и числа мало отсеять непроходные варианты, надо ещё привести пример для оставшегося. Надо?

[Stensen]

Спасибо, активно размышляю. Второй решил.

TOTAL в сообщении #1661973 писал(а):

В третьей задаче про Андрея, тетрадку и числа мало отсеять непроходные варианты, надо ещё привести пример для оставшегося. Надо?

Да, надо.