2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

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

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 16:47 


01/10/10

2116
Израиль (племянница БизиБивера)
На математической олимпиаде Тайваня 1992 (а их олимпиады традиционно сильные (китайцы, как-никак)) предлагалась следующая задача (приобщаю оригинальный текст и перевод):

Find the greatest positive integer A with the following property: For every
permutation of the thousand numbers 1001, . . . , 2000, the sum of some ten
consecutive terms is greater than or equal to A.

Найти наибольшее натуральное число А, обладающее следующим свойством:
При любой перестановке чисел 1001, ..., 2000 сумма некоторых 10 последовательных элементов больше или равна А.

(Если это то, о чём я подумала, то тогда...)

Ответ будет 15005. Почему?
Сумма всех чисел с 1001 по 2000 равна 3001*500=1500500. Разобьём перестановку из 1000 чисел на 100 десятков. Если в каждом десятке сумма меньше 15005, то общая сумма будет меньше 1500500.
С другой стороны, перестановка 2000, 1001, 1999, 1002, 1998, 1003, ..., 1501, 1500 доказывает, что суммы 15006 и выше может и не быть.


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

Помогите, пожалуйста, разобраться.
Заранее благодарна!

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


11/12/05
10054
По крайней мере перевод с английского корректен.

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 18:13 
Заслуженный участник


06/05/11
278
Харьков
Все верно.

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 18:19 


01/10/10

2116
Израиль (племянница БизиБивера)
bnovikov в сообщении #449269 писал(а):
Все верно.

Кстати, ссылку на задачу забыла дать (она там последняя):
http://www.imomath.com/othercomp/Twn/TwnMO92.pdf

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 19:32 


08/05/08
954
MSK
А если даны числа: $1, 2,..11$ и берется любая последовательность из десяти элементов?

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 20:08 


01/10/10

2116
Израиль (племянница БизиБивера)
e7e5 в сообщении #449290 писал(а):
А если даны числа: $1, 2,..11$ и берется любая последовательность из десяти элементов?

Разве не 56?

-- Пн май 23, 2011 20:17:46 --


Сумма всех 11 чисел равна 66.
Если взять 10 последовательных элементов, то одно число останется за бортом. Вариантов всего два - взять первые 10 или последние 10. В первом случае за бортом останется последнее число, во втором - первое. Наименьшее из этих двух чисел не превосходит 10, значит сумма остальных десяти чисел - не меньше 56. Возможна перестановка, при которой числа 57 (и выше) не будет. Например, 10, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11.

Разве не так?

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 20:27 


08/05/08
954
MSK
В чем тогда состоит стойкое ощущение неправильного решения для бОльшего числа элементов подпоследовательности последовательности $1,2,...n$?

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 20:34 


01/10/10

2116
Израиль (племянница БизиБивера)
e7e5 в сообщении #449316 писал(а):
В чем тогда состоит стойкое ощущение неправильного решения для бОльшего числа элементов подпоследовательности последовательности $1,2,...n$?

Вот теперь до меня дошло, что можно было иначе решить. Ведь это ж мне повезло, что там 1000 членов и нужна сумма десяти, а $10 | 1000$. Могло же быть, скажем, 999 элементов!

(Оффтоп)

Вы, случайно, не педагог?

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 20:45 


08/05/08
954
MSK
И какое же общее решение если из последовательности $1,2,..n$ выделяется подпоследовательность $n_i, n_{i+1},...n_{i+k}$ и ищется натуральное число $A$ ( по аналогии с исходной задачей)?

(Оффтоп)

нет, не педагог, просто любитель

 Профиль  
                  
 
 Re: Не совсем понятно условие задачи о перестановках
Сообщение23.05.2011, 20:47 
Заслуженный участник


02/08/10
629
Xenia1996 в сообщении #449322 писал(а):
e7e5 в сообщении #449316 писал(а):
В чем тогда состоит стойкое ощущение неправильного решения для бОльшего числа элементов подпоследовательности последовательности $1,2,...n$?

Вот теперь до меня дошло, что можно было иначе решить. Ведь это ж мне повезло, что там 1000 членов и нужна сумма десяти, а $10 | 1000$. Могло же быть, скажем, 999 элементов!

(Оффтоп)

Вы, случайно, не педагог?

Аналогично.
Разобьём на десятки, вот только в последнюю десятку впихнём 990-ый элемент.
Таким образом сумма всех десяток будет равнятся от $\frac{ 3001\cdot 999}{2}+1001$ до $\frac{3001\cdot 999}{2}+1999$. Значит хотя бы 1 десяток содержит как минимум
$$\left\lceil \frac{\frac{ 3001\cdot 999}{2}+1001}{100}\right\rceil$$
Пример можно взять также аналогичный)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

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



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

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


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

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