Задача с натуральным рядом

[grizzly]

Rusit8800 в сообщении #1364052 писал(а):

Хорошо, а почему меньше нельзя?

Хорошо, давайте двигаться не спеша. Возьмите числа числа от 1 до 9 (среднее равно 5) и докажите строго, что для любой перестановки этих чисел найдутся 3 подряд идущих числа, таких что их сумма будет не меньше 15. С этой задачей должен справиться ученик 5-го класса (даже 4-го).

[Rusit8800]

wrest в сообщении #1364059 писал(а):

Тогда сформулируйте условие задачи же уже.

Что вам не нравится в условии?По поводу термина "перестановка" расстановка я вам все разъяснил. Здесь

wrest в сообщении #1364059 писал(а):

В каждой перестановке найдется подпоследовательность длиной 10 такая, что...

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

Rusit8800 в сообщении #1363877 писал(а):

сумма которых не меньше $A$.

[worm2]

Я про (100; 10) пока не готов писать.

Но "краевой эффект" могу продемонстрировать на примере (10; 4).
Вот "каноническое" расположение:
10, 1, 8, 3, 6, 5, 4, 7, 2, 9.
Оно даёт максимальную сумму 22.
А вот мы загнали в края значения побольше:
10, 5, 4, 1, 8, 7, 2, 3, 6, 9.
Вуаля, максимальная сумма 20.

[Rusit8800]

grizzly в сообщении #1364061 писал(а):

Хорошо, давайте двигаться не спеша. Возьмите числа числа от 1 до 9 (среднее равно 5) и докажите строго, что для любой перестановки этих чисел найдутся 3 подряд идущих числа, таких что их сумма будет не меньше 15. С этой задачей должен справиться ученик 5-го класса (даже 4-го).

Господи, точно, как же я был слеп!
Ограничимся пока частным случаем, которого достаточно для решения частной задачи - $n \vdots k, n = tk$.
Эта делимость - условие того, что последовательность можно разбить на целое число групп по $k$ чисел, не обязательно идущих подряд. Если предположить, что, $\[{s_j} < \frac{{k(n + 1)}}{2}\]$, то

$$\[{s_j} + {s_{j + 1}} + \ldots + {s_{j + (n - k)}} < \frac{{n(n + 1)}}{2}\]$$

что противоречит условию.

-- 27.12.2018, 15:56 --

Здесь я сделал не хорошо - я за $s_i$ определил именно $k$ подряд идущих цифр а не $k$ произвольных чисел, но суть ясна.

-- 27.12.2018, 15:58 --

Хотя, мне кажется, в учетом идеи о средних, можно обобщить этот вывод для любого $n$, только нужно брать среднее не для группы из $k$ чисел, а для одного числа.

[grizzly]

worm2
Вы пошли на поводу у ТС в сторону максимального усложнения задачи. Я же предлагаю перед тем, как рассматривать общий случай, решить первоначальную задачу -- и потом уже на основании этого решения рассмотреть общий случай.

А первоначальная задача (A; B) от общего случая отличается тем, что в ней A кратно B. В этом случае никаких краевых условий возникать не может и ход решения совершенно очевиден. Общий случай (с краевыми условиями) проще, думаю, будет рассмотреть после решения первоначальной задачи.

-- 27.12.2018, 16:00 --

А, вот уже, я опоздал -- ТС успел в последний момент спасти несколько очков репутации

[Rusit8800]

grizzly в сообщении #1364083 писал(а):

с краевыми условиями

Что это вообще означает? Вы уже как минимум третий, кто об этом говорит.

[grizzly]

Rusit8800
Просто запишите полностью решение задачи (A; B) в случае, когда A кратно B, а потом посмотрите, в чём не срабатывает это решение в общем случае (посмотрите пример (10;4) в сообщении worm2).

Вы должны сами "расшифровать", о чём мы говорим. Иначе какой интерес?

[worm2]

Только сейчас понял, что случай, когда $m$ кратно $k$ (по крайней мере, когда оба чётные), очень простой...

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Олимпиадные задачи (М)»

[Rusit8800]

Все, что удалось пока сделать - сделать оценку $A$ в общем случае.
Пусть $n=kt+r$, причем $\[n \equiv r\bmod k\]$. Разобьем последовательность на $t$ групп по $k$, и на оставшуюся группу с $r$ числами. Обозначим за $s_n$ - сумму всех чисел, $s_k$ -возможные средние суммы чисел интересующих нас группах, $s_r$ - возможные суммы чисел в оставшейся группе из $r$ чисел.
Ясно, что $s_n=ts_k+s_r$ и

$$\[\sum\limits_{i = 1}^r i = \frac{{r(r + 1)}}{2} \leqslant {s_r} \leqslant \sum\limits_{i = 1}^r {\left( {n - (i - 1)} \right)} = r(kt + r) - \frac{{r(r - 1)}}{2}\]$$

С учетом этого минимальное среднее значение $s_k$ равно

$$\[{s_{k\min }} = \frac{{{s_n} - \sum\limits_{i = 1}^r {\left( {n - (i - 1)} \right)} }}{t} = \frac{{\frac{{(kt + r)(kt + r + 1)}}{2} - \left( {r(kt + r) - \frac{{r(r - 1)}}{2}} \right)}}{t} = \frac{{k(n - r + 1)}}{2}\]$$

откуда

$$ A \geqslant \frac{{k(n - r + 1)}}{2} $$

, значит

$$\[A \geqslant \left\lfloor {\frac{{k(n - r + 1)}}{2}} \right\rfloor \]$$

При четных $n,k$ оценка является точной, что можно доказать, обобщив пример grizzly.
Если $k$ нечетное, то оценка может быть и не точной - пример worm2 с $n=6$ и $k=3$.
Она неточная и в случае $n=10$, $k=4$, тогда

$$\[A = 20 \geqslant \left\lfloor {\frac{{4(10 - 2 + 1)}}{2}} \right\rfloor = 18\]$$

-- 27.12.2018, 20:46 --

Оценку при $r=0$ можно улучшить - заменить пол на потолок. Действительно, из предыдущих рассуждений следует, что

$$\[A \geqslant \frac{{k(n + 1)}}{2}\]$$

Заметим, что

$$\[\frac{{kt(n + 1)}}{2} = n\]$$

, и что если $n$ четно и $k$ нечетно, то $\[\frac{{k(n + 1)}}{2} \notin \mathbb{Z}\]$, а значит

$$\[t\left\lfloor {\frac{{k(n + 1)}}{2}} \right\rfloor < \frac{{kt(n + 1)}}{2} = n\]$$

то есть число $A=\[\left\lfloor {\frac{{k(n + 1)}}{2}} \right\rfloor \]$ не удовлетворяет условию задачи, поскольку слишком мало. Значит остается увеличить его на $1$, заменив пол на потолок, причем, поскольку $\[\left\lceil {\frac{{k(n + 1)}}{2}} \right\rceil > \frac{{k(n + 1)}}{2}\]$, то число $\[A = \left\lceil {\frac{{k(n + 1)}}{2}} \right\rceil \]$ удовлетворяет условию задачи.
Во всех остальных случаях $\[\frac{{k(n + 1)}}{2} \in \mathbb{Z}\]$, и пол можно безболезненно поменять на потолок. Новая оценка является точной для примера worm2.

-- 27.12.2018, 20:51 --

Вообще, кстати, рассуждения верны для любого $r$, так что везде можно поменять пол на потолок. Далее, как показывает пример worm2, повышать оценку на $1$ нельзя, иначе она превысит значение $A$ для $n=6$ и $k=3$.

[grizzly]

Rusit8800
Хорошая попытка и аккуратные вычисления. Но это не совсем то. Да Вы и сами видите, что построили противоречие:

Rusit8800 в сообщении #1364143 писал(а):

При четных $n,k$ оценка является точной
...
Она неточная и в случае $n=10$, $k=4$

А причина в том, что для этого примера Вы сделали такую разбивку (1 3 6 8) (2 4 5 7) (9 10).

Rusit8800 в сообщении #1364143 писал(а):

пример worm2 с $n=6$ и $k=3$

И это тоже не в эту логику. Там $r=0$ и справедливы простые рассуждения рассмотренного частного случая.

-- 27.12.2018, 21:10 --

Да, верно, что при $r=0$ работает округление вверх.

Rusit8800 в сообщении #1364143 писал(а):

пример worm2, повышать оценку на $1$ нельзя, иначе она превысит значение $A$ для $n=6$ и $k=3$.

Нет, $r=0$ это просто другая задача, намного более простая. Не стоит пока смешивать одно с другим.

[Rusit8800]

grizzly в сообщении #1364152 писал(а):

что для этого примера Вы сделали такую разбивку (1 3 6 8) (2 4 5 7) (9 10).

Для $(n,k)=(10,4)$ я вообще не делал разбивку, я поверил словам

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

Вуаля, максимальная сумма 20.

grizzly в сообщении #1364152 писал(а):

Там $r=0$ и справедливы простые рассуждения рассмотренного частного случая.

А что конкретно здесь не в ту логику? В примере $(6,3)$ используется, во первых,

$$\[A \geqslant \frac{{k(n + 1)}}{2}\]$$

а во-вторых тот факт, что если предположить, что $A=10$, то сумма чисел второй тройки будет равна $21-10=11$, что приводит к противоречию, ибо $A=10$ означает, что не найдется тройка с суммой $11$ и более. Это достаточно простые рассуждения, вы же о них говорите? Из них я и пришел в общем случаю - заменил пол на потолок.

grizzly в сообщении #1364152 писал(а):

Нет, $r=0$ это просто другая задача, намного более простая. Не стоит пока смешивать одно с другим.

Я вас не понял. Я имел в виду, что если оценка

$$\[A \geqslant \left\lceil {\frac{{k(n - r + 1)}}{2}} \right\rceil \]$$

претендует на общность, то нельзя ее повышать на $1$ без ограничения общности

$$\[A \geqslant \left\lceil {\frac{{k(n - r + 1)}}{2}} \right\rceil +1\]$$

, иначе будет противоречие с примером $(6,3)$

[grizzly]

Rusit8800 в сообщении #1364159 писал(а):

Для $(n,k)=(10,4)$ я вообще не делал разбивку

А это что?

Rusit8800 в сообщении #1364143 писал(а):

$$\[{s_{k\min }} = \frac{{{s_n} - \sum\limits_{i = 1}^r {\left( {n - (i - 1)} \right)} }}{t} =...\]$$

То что под знаком суммы в числителе, это как раз и есть (9, 10) в обсуждаемом примере.

Rusit8800 в сообщении #1364159 писал(а):

я поверил словам

Это Вы правильно сделали. А вот что не заметили противоречия с Вашим выводом -- это неправильно.

Rusit8800 в сообщении #1364159 писал(а):

Я вас не понял. Я имел в виду, что если оценка ...
претендует на общность

А я имел в виду, что ещё рано претендовать на общность (тем более, что есть противоречащий пример этой оценке пример). Пока не хватает понимания более простых случаев.

-- 27.12.2018, 22:10 --

Rusit8800 в сообщении #1364159 писал(а):

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

Да, о них. Когда я писал то сообщение, ещё не было добавки про потолок. Я её сразу одобрил, как только заметил.

[wrest]

Тогда уж, в качестве обобщения, сразу ищите и минимальную.
Для (10,4) это 24, например:
1, 6, 7, 10, 2, 5, 8, 9, 3, 4

[Rusit8800]

grizzly в сообщении #1364161 писал(а):

То что под знаком суммы в числителе, это как раз и есть (9, 10) в обсуждаемом примере.

Ну ок, да, так и есть, и в чем же противоречие? Оценка дает $A \geqslant 18$.