2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 14:38 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 15:42 
Аватара пользователя


15/11/15
1297
Москва
wrest в сообщении #1364059 писал(а):
Тогда сформулируйте условие задачи же уже.

Что вам не нравится в условии?По поводу термина "перестановка" расстановка я вам все разъяснил. Здесь
wrest в сообщении #1364059 писал(а):
В каждой перестановке найдется подпоследовательность длиной 10 такая, что...

вам следует дочитать
Rusit8800 в сообщении #1363877 писал(а):
сумма которых не меньше $A$.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 15:52 
Заслуженный участник
Аватара пользователя


01/08/06
3049
Уфа
Я про (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.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 15:54 
Аватара пользователя


15/11/15
1297
Москва
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$ чисел, а для одного числа.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 15:59 
Заслуженный участник
Аватара пользователя


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

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

-- 27.12.2018, 16:00 --

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 16:12 
Аватара пользователя


15/11/15
1297
Москва
grizzly в сообщении #1364083 писал(а):
с краевыми условиями

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 16:21 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 16:51 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Posted automatically
Сообщение27.12.2018, 19:36 


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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 20:13 
Аватара пользователя


15/11/15
1297
Москва
Все, что удалось пока сделать - сделать оценку $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$.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 21:06 
Заслуженный участник
Аватара пользователя


09/09/14
6328
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$ это просто другая задача, намного более простая. Не стоит пока смешивать одно с другим.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 21:39 
Аватара пользователя


15/11/15
1297
Москва
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)$

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение27.12.2018, 22:08 
Заслуженный участник
Аватара пользователя


09/09/14
6328
Rusit8800 в сообщении #1364159 писал(а):
Для $(n,k)=(10,4)$ я вообще не делал разбивку
А это что?
То что под знаком суммы в числителе, это как раз и есть (9, 10) в обсуждаемом примере.
Rusit8800 в сообщении #1364159 писал(а):
я поверил словам
Это Вы правильно сделали. А вот что не заметили противоречия с Вашим выводом -- это неправильно.

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

-- 27.12.2018, 22:10 --

Rusit8800 в сообщении #1364159 писал(а):
Это достаточно простые рассуждения, вы же о них говорите? Из них я и пришел в общем случаю - заменил пол на потолок.
Да, о них. Когда я писал то сообщение, ещё не было добавки про потолок. Я её сразу одобрил, как только заметил.

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение28.12.2018, 00:04 


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

 Профиль  
                  
 
 Re: Задача с натуральным рядом
Сообщение28.12.2018, 09:56 
Аватара пользователя


15/11/15
1297
Москва
grizzly в сообщении #1364161 писал(а):
То что под знаком суммы в числителе, это как раз и есть (9, 10) в обсуждаемом примере.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 49 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group