Математика (с ответами). Всероссийская олимпиада школьников в Москве (2022-2023 год) - часть 13

Следовательно, четвертая и пятая цифры исходного числа — тоже нули,

 

и после пятого укорачивания мы 

получим  число  (

k

/10)

3

 = (

n

/100)

2

.  Поскольку  в  разложение  числа,  являющегося  одновременно  точным 

квадратом  и  точным  кубом,  все  простые  множители  входят  в  степенях,  кратных  6,  это  число  является 
точной шестой степенью. 

Критерии

. Показано, что вторая и третья цифры исходного числа — нули, дальнейшего содержательного 

продвижения нет: 

3 балла

. 

За использование без обоснования того факта, что число, являющегося одновременно точным квадратом 
и точным кубом, является и точной шестой степенью, 

оценка не снижается

. 

10. На  столе  есть  две  кучки  камней,  в  которых  соответственно  100  и  101  камень.  Двое  играют  в  игру,
делая ходы по очереди. За ход разрешается взять кучку, убрать из неё какое-то количество камней (хотя 
бы  один)  и  разбить  оставшиеся  в  этой  кучке  камни  на  две  непустые  кучки.  Проигрывает  тот,  кто  не 
может сделать ход. Кто выиграет при правильной игре: тот, кто делает первый ход, или его соперник?

 

(М. Туревский) 

Ответ

.  Тот,  кто  делает  первый  ход. 

Решение

.  Пусть  первого  игрока  зовут  Петей,  а  второго  —  Васей. 

Первым ходом Петя уберет из кучки 101 один камень, а оставшиеся разделит на кучки из 1 (про которую 
можно забыть) и 99 камней. Теперь докажем более общий факт: если на столе лежат кучки из 2

k

 и 2

k

–1 

камней, то проигрывает тот, чья очередь ходить. 

Заключительный этап, 2022–2023 учебный год

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

Предъявим ещ¨

е один инвариант. В стро-

ке всего

125

2

пар, состоящих из буквы А и буквы Б. Назов¨

ем

такую пару

левой

, если в ней А стоит левее Б, и

правой

иначе.

Покажем, что при операции количество левых пар не изменя-
ется. Из этого будет следовать невозможность требуемого, ибо
при развороте строки все пары меняют тип, а значит, количе-
ство левых пар меняет ч¨

етность.

Рассмотрим одну операцию с куском длины

2

y

. При этой

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

y

пар, со-

держащих е¨

е и букву из куска; столько же таких пар осталось,

и все эти пары были и стали одного и того же типа.

Значит, осталось проследить за парами букв в самом куске.

Но каждая пара сменила свой тип дважды: когда кусок развер-
нулся и когда все буквы заменили на другие. Значит, количество
левых пар в куске также не изменилось.

Замечание.

Можно показать, что по количеству левых пар

восстанавливается сумма номеров мест букв А (и наоборот). Та-
ким образом, инвариант в этом решении — тот же, что и в преды-
дущем замечании.

Комментарий.

Неверный инвариант или инвариант, кото-

рый не всегда отличает строку от е¨

е обратной — 0 баллов.

Сформулирован верный инвариант и доказано, что он ВСЕ-

ГДА отличает строку и е¨

е обратную — 3 балла.

5

XLIX Всероссийская математическая олимпиада школьников

В решении с подсч¨

етом пар АБ и БА не учитываются или

неверно учитываются пары, в которых одна буква внутри куска,
а другая вне — снимается 2 балла.

Вводится «локальная» нумерация букв в куске и в этой ну-

мерации доказывается, что сумма номеров А не меняется, но
нет объяснения, как эта сумма связана с «глобальной» суммой
в строке — снимается 1 балл.

9.3. Каждое натуральное число, большее 1000, окрасили либо в крас-

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

1

?

(

С. Берлов

)

Ответ.

 

Не

 

может.

Первое

 

решение.

 

Предположим,

 

что

 

это

 

возможно.

 

Заключительный этап, 2022–2023 учебный год

включающей сегмент, отрезаемый хордой

BC

и находящийся

по другую сторону от вершины

A

— 1 балл.

Доказательство существования двух точек равенства (вер-

шина

A

и середина дуги

BAC

) — 1 балл.

Баллы по предыдущим пунктам не суммируются.
Решение верное, но упущен случай, когда точки

A

и

X

на-

ходятся в разных полуплоскостях относительно прямой

BC

—

6 баллов.

9

Заключительный этап, 2022–2023 учебный год

9.5. Если на столе лежит несколько кучек камней, считается, что на

столе

много камней

, если можно найти

50

кучек и пронумеро-

вать их числами от

1

до

50

так, что в первой кучке есть хотя

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

100

кучек по

100

камней в каждой. Найдите наибольшее

n

6

10 000

такое, что после удаления из исходных кучек любых

n

камней на столе вс¨

е равно останется много камней. (При уда-

лении камней кучка не распадается на несколько.)

(

Д. Храмцов

)

Ответ.

n

= 5099

.

Решение.

Если удалить полностью

51

кучку, то, очевидно,

не останется много камней. Значит, искомое значение

n

меньше

5100

. (Альтернативно, можно удалить из всех кучек по

51

кам-

ню.)

Заключительный этап, 2022–2023 учебный год

9.8. У Пети есть

10 000

гирь, среди них нет двух гирь равного веса.

Также у него есть чудо-прибор: если положить в него 10 гирь,
он сообщит сумму весов каких-то двух из них (при этом неиз-
вестно, каких именно). Докажите, что Петя может использовать
чудо-прибор так, чтобы через некоторое время указать на одну
из гирь и точно назвать е¨

е вес. (В чудо-прибор нельзя класть

другое количество гирь.)

(

С. Берлов, Т. Коротченко

)

Решение.

Покажем, что Петя сможет определить вес одной

гири, даже если у него

8 000

гирь. Положим

n

= 4 000

.

Лемма.

Для любых

n

гирь Петя может найти две гири,

для которых он знает их суммарный вес.

Заключительный этап, 2022–2023 учебный год

Доказательство того, что один ответ прозвучал не менее

C

10

n

/C

2

n

раз — 1 балл.

Доказана лемма (возможно, при

n

= 10000

) — 4 балла.

Во в целом верном решении при доказательстве леммы упу-

щен случай, когда хорошая пара содержит

a

или

b

— снимается

2 балла.

Доказательство утверждения «если 9 элементов лежат в 10

десятках, на которые дали одинаковый ответ, то эти 9 элементов
содержат пару с такой суммой» — 1 балл.

15

XLIX Всероссийская математическая олимпиада школьников

10 класс

10.1. Прямые, содержащие стороны данного остроугольного тре-

угольника

T

, покрасили в красный, зел¨

еный и синий цвета. За-

тем эти прямые повернули вокруг центра описанной окружности
данного треугольника по часовой стрелке на угол

120

◦

(прямая

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

T

.

(

Л. Емельянов

)

для других точек

L

,

M

пересечения одноцветных прямых. Та-

ким образом, треугольник

KLM

получается из

DEF

поворот-

ной гомотетией с центром

O

и коэффициентом

2

. Тогда

KLM

подобен

DEF

с коэффициентом 2, следовательно, равен

ABC

.

10.2. У 100 школьников есть стопка из 101 карточки, которые про-

нумерованы числами от

0

до

100

. Первый школьник перемеши-

вает стопку, затем бер¨

ет сверху из получившейся стопки по од-

ной карточке, и при каждом взятии карточки (в том числе при
первом) записывает на доску среднее арифметическое чисел на
всех взятых им на данный момент карточках. Так он записыва-
ет 100 чисел, а когда в стопке оста¨

ется одна карточка, он воз-

вращает карточки в стопку, и далее вс¨

е то же самое, начиная

с перемешивания стопки, проделывает второй школьник, потом
третий, и т.д. Докажите, что среди выписанных на доске 10000
чисел найдутся два одинаковых.

(

А. Грибалко

)

10.4. С одной стороны теннисного стола выстроилась очередь из

n

девочек, а с другой — из

n

мальчиков. И девочки, и мальчики

пронумерованы числами от 1 до

n

в том порядке, как они сто-

ят. Первую партию играют девочка и мальчик с номерами 1, а
далее после каждой партии проигравший вста¨

ет в конец своей

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

n

неч¨

етно, то в

последней партии играли девочка и мальчик с неч¨

етными номе-

рами.

(

А. Грибалко

)

Решение.

Будем изображать турнир в виде таблицы

n

×

n

,

19

XLIX Всероссийская математическая олимпиада школьников

в которой и столбцы, и строки пронумерованы числами от

1

до

n

. Столбцы будут соответствовать девочкам, а строки — маль-

чикам. Тогда каждая партия зада¨

ется клеткой, координаты ко-

торой соответствуют номерам девочки и мальчика, играющих
в этой партии. Поставим сначала фишку в клетку

(1

,

1)

. После

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

Раскрасим

 

клетки

 

таблицы

 

в

 

n

 

цветов

 

по

 

диагоналям,

 

иду-

щим

 

вправо-вниз:

 

первую

 

диагональ

 

—

 

в

 

первый

 

цвет,

 

вторую

 

—

 

во

 

второй,

 

.

 

.

 

.

,

 

n

-ю

 

диагональ

 

—

 

в

 

n

-й

 

цвет,

 

а

 

следующие

 

диаго-

нали

 

—

 

снова

 

в

 

цвета

 

с

 

первого

 

по

 

(

n

 

−

 

1)

-й.

 

Заметим,

 

что

 

после

 

каждой

 

партии

 

номер

 

цвета

 

клетки,

 

в

 

которой

 

находится

 

фиш-

ка,

 

увеличивается

 

на

 

1

 

по

 

модулю

 

n

.

 

Так

 

как

 

всего

 

в

 

турнире

 

бы-

ло

 

проведено

 

n

2

 

партий,

 

что

 

кратно

 

n

,

 

то

 

в

 

конце

 

фишка

 

нахо-

дится

 

в

 

клетке

 

n

-го

 

цвета,

 

то

 

есть

 

на

 

главной

 

диагонали

 

(далее,

 

говоря

 

«диагональ»,

 

мы

 

будем

 

иметь

 

в

 

виду

 

именно

 

эту

 

диаго-

наль).

 

Пусть

 

финальная

 

клетка

 

в

 

маршруте

 

фишки

 

расположе-

на

 

в

 

столбце

 

с

 

номером

 

m

,

 

тогда

 

требуется

 

доказать,

 

что

 

число

 

Заключительный этап, 2022–2023 учебный год

клетки до не¨

е. Все пути от клеток первого цвета до следующей

клетки

n

-го цвета должны быть такими же, как и рассматрива-

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

(1

,

−

1)

. Действительно, если бы фишка из

клетки

(

a

−

1

, b

)

сделала ход вверх, а из клетки

(

a, b

−

1)

— впра-

во, то в клетку

(

a, b

)

она бы не попала, а если из этих клеток

она делала ходы вправо и вверх соответственно, то попала бы
в одну клетку дважды; поэтому из каждых двух таких клеток
фишка делала одинаковые ходы.

Без ограничения общности будем считать, что

k < m

. Клет-

ки диагонали, находящиеся левее финальной клетки, будем на-
зывать

левыми

, а находящиеся правее —

правыми

. Пронумеруем

левые клетки числами от

1

до

m

−

1

, а правые — от 1 до

n

−

m

(и те, и другие нумеруем, двигаясь вправо-вниз). Посмотрим, в
каком порядке фишка обходила эти клетки. С левых клеток она
смещалась на

k

клеток вправо (поскольку с них в клетку пер-

вого цвета она делала ход вправо), а с правых клеток — на

k

−

1

клетку вправо. Значит, для левых клеток нам важен лишь оста-
ток от деления номера на

k

, а для правых — от деления на

k

−

1

.

При этом, если правых клеток меньше

k

, то можно увеличить

n

на

2(

k

−

1)

, добавив

2(

k

−

1)

правых клеток; это не повлияет

на дальнейшие рассуждения. Для удобства заменим все номера
клеток на соответствующие остатки, прич¨

ем для правых клеток

вместо остатка

0

будем использовать число

k

−

1

.

Пусть число

m

при делении на

k

да¨

ет остаток

d

. Тогда пер-

вый переход с левых клеток на правые был с числа

0

на число

k

−

d

, и в этот момент все клетки с нул¨

ем в левой части были

посещены. На диагонали остались только числа от

1

до

k

−

1

.

Дальше цепочка переходов между правыми и левыми клетками
выглядит так:

k

−

d

→ · · · →

d

. В этой цепочке каждое число

от

1

до

k

−

1

встречается два раза, начинается она на правых

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

первого типа

, а с левых на

правые —

второго

. Тогда в цепочке

k

−

1

переход первого типа

и

k

−

2

перехода второго, и они чередуются.

Докажем, что каждые два числа в цепочке, симметричные

относительно е¨

е центра, дают в сумме

k

. Для крайних чисел это

21

XLIX Всероссийская математическая олимпиада школьников

верно. Каждые два симметричных перехода имеют один тип,
поэтому в них по модулю

k

−

1

(для переходов первого типа) или

по модулю

k

(для переходов второго типа) прибавляется одно

и то же число. Значит, сумма следующих двух симметричных
чисел (которые ближе к центру цепочки) снова равна либо

1

по

модулю

k

−

1

, либо

0

по модулю

k

. Но сумма самих чисел не

меньше

2

и не больше

2

k

−

2

, поэтому она может быть равна

только

k

.

Предположим, что число

m

ч¨

етно, и рассмотрим два случая.

1) Число

k

неч¨

етно. Тогда центральный переход в цепочке

имеет второй тип. У правой нижней клетки диагонали неч¨

етный

номер, поскольку число

n

−

m

неч¨

етно, а

k

−

1

ч¨

етно. Левая верх-

няя клетка диагонали тоже имеет неч¨

етный номер, поэтому при

переходе первого типа ч¨

етность числа меняется. Пусть с числа

1

переход первого типа происходит на число

2

s

. Тогда по модулю

k

−

1

переходы первого типа выглядят так:

1

→

2

s

,

2

→

2

s

+ 1

,

. . . ,

k

−

1

→

2

s

+

k

−

2

. Суммы чисел в этих парах являются по-

следовательными неч¨

етными числами, поэтому при делении на

k

−

1

они дают все неч¨

етные остатки по два раза. В частности,

есть переход, в котором сумма чисел равна 1 по модулю

k

−

1

.

Как показано выше, эта сумма равна

k

. Но тогда для этого пе-

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

2) Число

k

ч¨

етно. Тогда у центрального перехода в цепочке

первый тип. Последняя левая клетка имеет неч¨

етный номер, так

как число

m

−

1

неч¨

етно, а

k

ч¨

етно. У первой правой клетки то-

же неч¨

етный номер, значит, при переходе второго типа ч¨

етность

числа не меняется. Аналогично первому случаю можно пока-
зать, что среди них найд¨

ется переход, пара чисел в котором да¨

ет

сумму

k

, и получаем такое же противоречие.

Замечание.

После описания того, в каком порядке фиш-

ка обходит клетки диагонали (с левых сдвигается вправо на

k

клеток, а с правых — на

k

−

1

) решение можно завершить

по-другому.

Пронумеруем все клетки диагонали числами от

1

до

n

слева

направо. Провед¨

ем стрелку из каждой клетки в клетку, в кото-

22

Комментарий.

В решении произвед¨

ен переход к таблице

n

×

n

— 0 баллов.

Доказано только, что номера имеют одинаковую ч¨

етность —

0 баллов.

Сформулировано и доказано только, что сумма номеров

да¨

ет остаток 1 при делении на

n

; иными словами, что последняя

клетка будет на главной диагонали — 1 балл.

Доказано, что во всех клетках одной диагонали, кроме глав-

ной, ходы были одинаковы — 1 балл.

Доказано, что все ходы из главной диагонали до конечной

клетки направлены в одну сторону, а после — в другую — 0 бал-
лов.

Доказано, что последняя клетка на диагонали, а также что

разница между соседними посещениями клеток главной диаго-
нали равна

k

или

k

+ 1

— 3 балла. Это продвижение не сумми-

руется с предыдущими.

23

10.5. Найдите наибольшее натуральное число

n

, для которого произ-

ведение чисел

n

,

n

+ 1

,

n

+ 2

, . . . ,

n

+ 20

делится на квадрат

какого-то одного из них.

(

А. Храбров

)

23

Комментарий.

Только пример — 1 балл.

Доказано лишь, что число доминошек ч¨

етно — 0 баллов.

Критерии решения с путями из хороших (лежащих в квад-

ратах

2

×

2

) доминошек следующие.

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

ещ¨

е хотя бы одна хорошая, и есть идея построения пути из этих

доминошек — 1 балл.

Для полного решения задачи осталось решить проблему за-

25

XLIX Всероссийская математическая олимпиада школьников

цикливания и пересечения путей из доминошек, при этом НЕТ
разбиения на области сдвигом сетки и построения из них графа
с ч¨

етными степенями вершин, и есть пример — всего 3 балла.

Для полного решения задачи осталось решить проблему за-

цикливания и пересечения путей из доминошек, при этом ЕСТЬ
разбиение на области сдвигом сетки и построения из них графа
с ч¨

етными степенями вершин, и есть пример — 5 баллов.

Попытка закрыть проблему зацикливания тем, что в таком

случае получается область неч¨

етной области, БЕЗ полного и

верного доказательства — 0 баллов.

Задача решена, но с доказательством пересечения путей

есть незначительные ошибки — 6 баллов.

Критерии решения с разбиением на области, каждая из ко-

торых содержит хорошую (лежащую в квадрате

2

×

2

) доминош-

ку, следующие.

Разбиение на области, в каждой из которых действительно

есть хотя бы одна хорошая доминошка (но это не доказано) — 1
балл.

Есть разбиение на области и доказательство, что задача ре-

шена, если бы мы доказали, что в каждой области есть хотя бы
одна хорошая доминошка; но само это утверждение не доказано
или содержит существенные ошибки — всего 3 балла.

Есть разбиение на области и доказательство, что задача ре-

шена, если бы мы доказали, что в каждой области есть хотя бы
одна хорошая доминошка, но само это утверждение доказано с
небольшими помарками — 5 или 6 баллов.

Попытки подсч¨

ета числа границ квадратов

2

×

2

(внутренних

или

 

внешних),

 

не

 

довед¨енные

 

до

 

верного

 

решения

 

—

 

0

 

баллов.

 

10.7.

 

Дана

 

трапеция

 

ABCD

,

 

в

 

которой

 

AD

  // 

BC

,

 

а

 

лучи

 

AB

 

и

 

DC

пересекаются в точке

G

. Общие внешние касательные к окруж-

ностям, описанным около треугольников

ABC

и

ACD

, пересе-

каются в точке

E

. Общие внешние касательные к окружностям,

описанным около треугольников

ABD

и

BCD

, пересекаются в

точке

F

. Докажите, что точки

E

,

F

и

G

лежат на одной пря-

мой.

(

А. Кузнецов

)

Решение.

Пусть прямая

EC

повторно пересекает окруж-

ность

(

ABC

)

в точке

X

, а прямая

EA

повторно пересекает

26

Комментарий.

Доказано, что каждая переменная не мень-

ше

a

— 1 балл.

Ответ с примером без обоснований — 0 баллов.
Неполное решение, основанное на методе множителей

Лагранжа (не упоминается, что точка минимума существует
и/или что точка минимума не является граничной) — 0 баллов.

Неполное решение, основанное на

pqr

-методе. Например, не

доказывается строго, что при фиксации отношения

q/r

в точке

максимума какие-то два корня совпадают. Как правило, в ка-
честве «доказательств» приводятся или подмены утверждений
на равносильные («тут ещ¨

е были решения, а тут нет, поэтому

какие-то два совпадают»), или неформализуемые рассуждения
про движения графиков («график движется непрерывно, поэто-
му корни совпадают») — 0 баллов.

29

Заключительный этап, 2022–2023 учебный год

Итак, мы показали, что 300 чисел, выписанных на 1-м, 2-м и

100-м шагах, могут принимать не более 299 различных значений.
Следовательно, какие-то два из них равны.

Комментарий.

Зафиксируем следующие продвижения:

(а) Выбираемые на первом шаге карточки различны.
(б) На втором шаге получаются целые и полуцелые средние

арифметические.

(в) Остающиеся после последнего шага карточки различны.
(г) Не может быть такого, что кто-то взял на первом шаге

карточку 50, и у кого-то после последнего шага осталась кар-
точка 50.

Тогда следующие комбинации продвижений оцениваются

следующим образом:

(а)+(б)+(в) без дальнейших продвижений — 0 баллов.
(а)+(б), при этом найдено количество элементов в объеди-

нении множеств возможных средних арифметических на 1 и 2
шаге — 1 балл.

(а)+(б)+(г) — 1 балл.
(а)+(в)+(г) — 1 балл.
(а)+(б)+(в)+(г) — 1 балл.
(а)+(б)+(в)+(г), при этом найдено количество элементов в

объединении множеств возможных средних арифметических на
1 и 2 шаге — 2 балла.

Задача решена для набора чисел

1

,

2

,

. . .

,

101

, но не сведена

к исходной — 6 баллов.

11.3. В каждой строке таблицы

100

×

n

в некотором порядке стоят

числа от 1 до 100, числа в строке не повторяются (в таблице

n

строк и

100

столбцов). Разрешается поменять местами в строке

два числа, отличающиеся на 1, если они не стоят рядом. Ока-
залось, что с помощью таких операций нельзя получить двух

31

XLIX Всероссийская математическая олимпиада школьников

(C3) Основные свойства проективных отображений (двой-

ное отношение четыр¨

ех точек сохраняется при центральной про-

екции, проективное отображение однозначно задается образами
тр¨

ех точек и т.д.) считаются известными.

XLIX Всероссийская математическая олимпиада школьников

(Z3) Сч¨

ет углов без построения новых точек, подобие тре-

угольников

T

b

и

T

c

.

(Z4) Доказано, что

AT

,

P Q

,

B

1

C

1

параллельны, и все они

перпендикулярны биссектрисе

AI

.

(Z5) Доказано, что пят¨

ерки точек

X

,

B

0

,

I

,

Q

,

C

и

P

,

B

,

I

,

Y

,

C

0

лежат на одной окружности.

(A) Схема оценивания официального решения (пересечение

тр¨

ех радикальных осей).

(A0) Доказано, что четыр¨

ехугольники

P BM A

1

и

A

1

M QC

вписанные (или что

P Q

— прямая Симсона точки

A

1

относи-

тельно треугольника

ABC

) — 0 баллов.

(A1)

Явно

сформулировано

и

доказано,

что

че-

тыр¨

ехугольник

AP A

1

Q

вписанный — 1 балл.

(A2) Доказано, что точки

P

,

B

0

,

C

1

лежат на одной пря-

мой — 1 балл.

(A3) Доказано, что четыр¨

ехугольник

P B

0

QC

0

вписанный —

2 балла.

(B) Схема оценивания решения, в котором доказывается,

что

B

0

C

0

H

— прямая Симсона точки

A

1

относительно треуголь-

ника

XT Y

.

0

(и

Y C

0

11.5. Изначально на доске написано 10 единиц. Гриша и Глеб играют

в игру, делая ходы по очереди. Своим ходом Гриша возводит

36

Заключительный этап, 2022–2023 учебный год

некоторые 5 чисел на доске в квадрат. Глеб своим ходом выби-
рает несколько (возможно, ни одного) чисел на доске и увели-
чивает каждое из них на 1. Если в течение

10 000

ходов на доске

появится число, делящееся на 2023, то побеждает Глеб, иначе
побеждает Гриша. Кто из игроков имеет выигрышную страте-
гию, если первым ходит Гриша?

(

Г. Никитин

)

Ответ.

Побеждает Гриша.

Решение.

Заметим, что

2023 = 7

·

17

2

. Гриша разобь¨

ет чис-

ла на доске на две группы по 5 и будет возводить в квадрат
числа из первой группы и из второй группы по очереди. Легко
видеть, что квадраты целых чисел, не кратных 7, при делении
на 7 могут давать лишь остатки 1, 2 и 4. Следовательно, по-
сле увеличения максимум на 2 числа на доске будут давать при
делении на 7 только остатки 1, 2, 3, 4, 5 и 6. Значит, ни одно
из чисел не будет делиться 7, а поэтому не будет делиться и на
2023.

Замечание.

Существуют и другие решения.

Комментарий.

Число

2023

неверно разложено на простые

множители, но это не влияет на решение задачи — снимается
1 балл.

При переборе квадратичных вычетов по модулю

7

пропущен

вычет, отличный от

0

— снимается 2 балла.

Приведено рассуждение, решающее задачу для простых чи-

сел

p

вида

8

k

+ 7

, но в качестве

p

выбрано составное число или

число,

 

не

 

являющееся

 

делителем

 

2023

 

—

 

не

 

более

 

2

 

баллов.

Заключительный этап, 2022–2023 учебный год

(A)–(С). Продвижения (B1) и (B2) не суммируются, все осталь-
ные — суммируются.

(G) В неоконченном сч¨

етном решении оцениваются лишь

продвижения, явно сформулированные в работе и имеющие гео-
метрический смысл.

(M1) Решение не работает лишь в некотором специальном

случае (например, одна из вершин

X

,

Y

,

Z

,

T

— середина ребра

тетраэдра) — снимается 1 балл.

(M2) Использование неверных стереометрических утвер-

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

XY ZT

— прямоугольник (или, эквивалентно, что в этом че-

тыр¨

ехугольнике есть параллельные стороны) не оценивается.

(A0) Используется без доказательства, что прямые

XY

,

ZT

и

AC

пересекаются в одной точке — баллы не снимаются.

(A) Построены (и явно определены) точки

Q

и

R

из офи-

циального решения (в частности, указано, что каждая из них
лежит на продолжении ребра тетраэдра и продолжениях двух
сторон четыр¨

ехугольника

XY ZT

) — 1 балл.

(B1) Доказано, что точка

P

лежит на прямой

QR

— 1 балл.

(B2) Доказано, что

P

есть середина отрезка

QR

— 2 балла.

(C0) Утверждение о том, что середины отрезков с концами

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

(C1) Задача сведена к тому, что на прямых

AC

и

BD

есть

такие точки

U

и

V

, что

P

есть середина отрезка

U V

— 1 балл.

11.7. Назов¨

ем многочлен

P

(

x

)

бицелозначным

, если числа

P

(

k

)

и

P

0

(

k

)

целые при любом целом

k

. Пусть

P

(

x

)

— бицелозначный

многочлен степени

d

, и пусть

N

d

— произведение всех составных

чисел, не превосходящих

d

(произведение пустого множества со-

множителей считаем равным 1). Докажите, что старший коэф-
фициент многочлена

N

d

·

P

(

x

)

— целый.

(

И. Богданов, Г. Челноков

)

Решение.

Многочлен

P

(

x

)

называется

целозначным

, если

P

(

k

)

— целое число при любом целом

k

. Нам надо доказать, что,

39

Итак,

C

,

D

—

k

-сеть и

(

k

+ 1)

-сеть. Сумма их стоимостей та-

кая же, как у

A

и

B

. Значит, они обе оптимальны. Таким об-

разом, для сети

A

удалось выкинуть выделенный город и най-

ти оптимальную

k

-сеть с оставшимися выделенными городами.

Теперь можно построить требуемую нумерацию в обратном по-
рядке (начиная с пустой

N

-сети).

Комментарий.

В 0 баллов оценивается:

a) Описание структуры

k

-сети.

b) Попытка построить решение на использовании (неверно-

го) свойства наследуемости.

c) Разбор случаев маленького

N

.

d) Нахождение номера вершины

A

, если ребро

AB

имеет

строго наименьшую цену.

e) Попытка решить жадным алгоритмом без указания, в ка-

кой момент мы отойд¨

ем от жадного алгоритма.

43