В.проба-2020

Ian · Сообщение **Ian** » 01 фев 2020, 17:09

: image567.jpg (84.53 KiB) 12111 просмотра

Сегодня была олимпиада для абитуриентов "Высшая проба", проводит вроде ВШЭ, некоторые задачи достойны международных олимпиад и я пока не знаю как решить

Ian · Сообщение **Ian** » 02 фев 2020, 08:18

Вот такое грубое решение задачи 5.
Пусть число слагаемых

m
В основном случае

|S|> 2 и

m\geq 3
Рассмотрим окружность типа тригонометрической, но длины

\frac S{100}. На ней вверх и вниз от 0 (который справа) отложим дуги длиной по 1/100, они образуют критическую область, но не покрывают окружность. Будем набирать сумму чисел в таком порядке, чтобы она оставалась возможно меньше по модулю, и наматывать на окружность. Сумма всех чисел попадет в 0, но она соответствует n=100 и не считается. Если сумма некоторых 1...(m-1) чисел попала в критическую область, то она требуемая (совпала с 0 с точностью до 1/100 по модулю

\frac S{100} при числе оборотов меньше 100) Если же все (m-1) чисел на дуге - дополнении к критической области, длина этой дуги

\frac{|S|-2}{100}, то найдутся 2 частичных суммы,расположенных друг от друга не дальше чем

\frac{|S|-2}{100(m-2)}. Тогда у частичной суммы, которая является их разностью, это будет расстояние по окружности до 0, и она не будет в критической области, если

\frac{|S|-2}{100(m-2)}>\frac 1{100}, противоречие |S|>m с тем , что все числа не больше 1 по модулю. И тоже надо еще проверить, что у найденной частичной суммы не только положение на окружности искомое, но и число оборотов меньше 100, что вроде бы можно обеспечить порядком набора исходных чисел

zykov · Сообщение **zykov** » 03 фев 2020, 05:11

Ian писал(а):Source of the post Вот такое грубое решение задачи 5.
Пусть число слагаемых m

Мне кажется, там проще.

Интервал $[0, \frac{S}{100}]$ можно разбить на не более чем $m$

кусков каждый размером не более чем $\frac{1}{100}$ , т.к. $S \leq m$ . В принципе не важно как разбивать. Можно разбивать по $\frac{1}{100}$ , а в конце сколько останется меньше. Тогда количество кусков может быть меньше $m$

. Можно разбивать ровно по $\frac{S}{100m}$ . Каждому числу (числу вообще) можно сопоставить один такой кусок - сначала смотрим в какой интервал $[\frac{nS}{100}, \frac{(n+1)S}{100}]$ попало число, потом в этом интервале в какой кусок.

Далее упрядочим как-нибудь наши числа (опять не важно, как) и рассмотрим суммы $x_1$

,

, ..., $x_1+x_2+...+x_{m-1}$ . Всего количество таких сумм $m-1$

. Если одна из них попала в первый или последний кусок, то она удовлетворяет неравенству. Если же ни одна в эти два куска не попадает, то все $m-1$

как-то размещаются в оставшихся $m-2$

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

Ian · Сообщение **Ian** » 03 фев 2020, 07:09

Я еще думал как обеспечить n<100. При произвольном порядке частичная сумма может выскочить за S

zykov · Сообщение **zykov** » 03 фев 2020, 07:31

Ian писал(а):Source of the post При произвольном порядке частичная сумма может выскочить за S

Я имел ввиду знакопостоянные $x_i$

(для определенности, положительные).
Этого достаточно.

Вначале можно провести процедуру регуляризации. Если есть два числа в сумме дающие не более единицы по абсолютной величине, то их можно заменить их суммой. Количество чисел уменьшается на один, сумма не меняется. Решение для новой задачи автоматом даёт решение для исходной задачи. И так далее.
Либо придем к одному числу (тут решение тривиальное), либо модуль суммы любых двух будет более 1. Это значит, что нет нулей, что нет разных знаков. И вообще либо все больше 0.5 по модулю, либо максимум одно число меньше или равно 0.5 по модулю (если оно равно $a>0$

, то все остальные $>1-a$

).

Ian · Сообщение **Ian** » 03 фев 2020, 11:53

В сети пишут школьники, которые решили 6-ю. Не так уж и сложно.
Точка внутри тетраэдра порождает его разбиение на 4 новых, с вершинами в некоторых из вершин исходного тетраэдра и этой точке. Каждая из 21 точек увеличивает число тетраэдров в разбиении на 3, а вначале был один. Итого 64 тетраэдра
Объем исходного

\frac{8^3\sqrt 2}{12}=60,34 значит в разбиении найдется один объемом меньше 1
Почему дали 21 точку, хватило бы и 20ти

zykov · Сообщение **zykov** » 03 фев 2020, 12:27

Ian писал(а):Source of the post Почему дали 21 точку, хватило бы и 20ти

Может чтобы было проще показать без калькулятора, что $\frac{8^3 \sqrt 2}{12} < 64$ .
( $8^2=64$

и $2\sqrt2<3$ , т.к. $8<9$

.)

Портал Естественных Наук, версия 1.1