Копилки с монетами

Xenia1996 · Сообщение **Xenia1996** » 11 июн 2011, 10:49

2013 копилок с монетами расставлены в один ряд. В каждой копилке натуральное число монет в сегменте $$[1, 1000]$$

. Число монет в любых двух соседних копилках отличается ровно на 1. Общее число монет во всех копилках чётно.
Всегда ли можно разбить множество этих копилок (сами копилки разбивать нельзя, добавлять туда монеты тоже нельзя) на два непустых непересекающихся подмножества с одинаковым числом монет?

MrDindows · Сообщение **MrDindows** » 11 июн 2011, 11:50

Ага. Так как суммарное количество монет чётное - то на чётных позициях стоят копилки с нечётным количеством монет, а на нечётных позициях - с чётным. Выберем любую копилку на нечётной позиции с чётным количеством монет. Пусть в ней будет $$2n$$

монет. Остальные копилки разобьём на пары $a_i, a_{i+1}$ , Выбранную копилку иссесена пропускаем. Так вот, раскидаем теперь копилки по нашим множествам. Из $$503+n$$

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

Xenia1996 · Сообщение **Xenia1996** » 11 июн 2011, 12:04

MrDindows писал(а):Source of the post
Ага. Так как суммарное количество монет чётное - то на чётных позициях стоят копилки с нечётным количеством монет, а на нечётных позициях - с чётным. Выберем любую копилку на нечётной позиции с чётным количеством монет. Пусть в ней будет монет. Остальные копилки разобьём на пары $a_i, a_{i+1}$ , Выбранную копилку иссесена пропускаем. Так вот, раскидаем теперь копилки по нашим множествам. Из пар выбираем больший элемент пары и кидаем в первые кучу. Из оставшихся пар меньший элемент в эту же кучу. Остальное всё, в том числе и отмеченную копилку, кидаем во вторую кучу. Вот и всё.

Класс!
А теперь, разумеется, вопрос:
Почему я написала 2013, а не 2011 и как бы изменился от этого ответ на задачу?

MrDindows · Сообщение **MrDindows** » 11 июн 2011, 13:12

Не вижу подвоха) Ответ не изменился бы.

Xenia1996 · Сообщение **Xenia1996** » 11 июн 2011, 13:23

MrDindows писал(а):Source of the post
Не вижу подвоха) Ответ не изменился бы.

Значит, я не догоняю.
Тут тоже думают, что не изменился бы: [url=http://dxdy.ru/topic46793.html]http://dxdy.ru/topic46793.html[/url]

F(x) · Сообщение **F(x)** » 12 июн 2011, 01:16

смущает немного что при n=3 ответ другой. И с какого минимального n ответ будет утвердительным?

MrDindows · Сообщение **MrDindows** » 12 июн 2011, 10:42

Необходимо чтобы максимальное возможное число в копилке было не больше чем $\frac{n-1}{2}$

yourdomain.com