перемешиваем мультимножества с одинаковой суммой

[maxal]

Пусть $n\geq 2$ - целое число.

Даны два мультимножества $A,B$ размера $n$ содежащие действительные числа из интервала $(0,n-\frac12)$, причем сумма элементов в каждом мультимножеств равна $n$.
Докажите, что существует подмультимножество $C\subset A\cup B$ такое, что $C$ содержит хотя бы один, но не все, элементы $A$ и содержит хотя бы один, но не все, элементы $B$, а сумма элементов $C$ отличается от $n$ не более чем на $\frac12$.

[ИСН]

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

И всё-таки рискнём. Наименьший элемент каждого (мульти)множества не превосходит 1. Попробуем обменять их друг на друга. Если их разность не превосходит $1\over2$ - то вот она, победа; а если превосходит - тогда менять не надо, но тогда меньший из них сам по себе меньше $1\over2$, ну так и передадим его в другое множество без обмена, за просто так, и это-то и получится наше $C$.

[grizzly]

maxal в сообщении #1429803 писал(а):

действительные числа из интервала $(0,n-\frac12)$

И судя по этому условию, подразумевалось что-то более сложное.

[svv]

(déjà vu)

ИСН в сообщении #1429939 писал(а):

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

cf.:

ИСН в сообщении #829213 писал(а):

Я давно убедился: если Вам померещилось что-то простое в любой задаче от arqady, пересмотрите свои доводы. В них что-то не так.

[maxal]

ИСН, спасибо, это нечёткость формулировки с моей стороны - по сути были пропущены условия $A\not\subset C$ и $B\not\subset C$ (именно поэтому "перемешивание"). Исправил.

grizzly, да, конечно!

svv, и на старуху бывает проруха

[Dendr]

Без картинок сложно воспринимать, но рисовать не в чем сейчас, поэтому максимально описательно в конце...

Разумеется, если в множествах есть общие элементы, то ответ очевиден. Поэтому считаем, что $A\cap B=\varnothing$

Немного очевидной арифметики.
Пусть мы подобрали такое множество $C$ . Очевидно, его дополнение до $A\cup B$ тоже удовлетворяет всем условиям.
Введем обозначения:
$A_1=C\cap A, B_1=C\cap B$
$A_2=A\setminus A_1, B_2=B\setminus B_1$
По построению, $C=A_1\cup B_1; \overline{C}=A_2\cup B_2$

Обозначая малыми буквами соответственные суммы множеств, получим следующие соотношения:
$a_1+a_2=b_1+b_2=n; a_1+b_1=n+\delta; a_2+b_2=n-\delta$
где $-0.5<\delta<0.5$
Следовательно, $b_1=a_2+\delta; b_2=a_1-\delta$
Иными словами, утверждение задачи эквивалентно следующему: найдутся такие подмножества множеств $A$ и $B$ (непустые, и их дополнения непустые), что их суммы отличаются не более, чем на 1/2.

Упорядочим оба исходных множества и рассмотрим последовательности их кумулятивных сумм - начинаются они, разумеется, с наименьшего элемента (который не более 1), а заканчиваются числом $n$. Если в этих последовательностях найдутся два члена, отличающиеся друг от друга менее чем на 1/2, "обменный блок" найден.
Также можно заметить, что предпоследние члены в обеих последовательностях не меньше 1/2, но не больше $n-1$ (максимальный элемент множества по определению не меньше 1, но не больше $n-1/2$).

Помеcтим на числовой оси точки с этими подсуммами на интервале от 0 до $n$ - для множества $A$ сверху, для $B$ - снизу. Далее считаем, что точки не совпадают. Длины отрезков, понятно, соответствуют числам множества.

Рассмотрим пока для множества $A$. Внутри интервала $(0, n)$ расставлена $n-1$ точка. Самая левая из них может находиться где угодно на полуинтервале $(0, 1)$, а вот самая правая - не правее от $n-1$.
Итак, на числовую ось уложены отрезки неубывающей слева направо длины, всего их $n-1$, и суммарная длина не превышает $n-1$. Следовательно, существует точка $X_A$, слева от которой лежат отрезки длины не больше 1.

Предположим, что она не крайняя слева, и для $B$ тоже (если нет - переназовем множества и см. дальше).
У нас два множества, поэтому и точки тоже две. Выберем левую. Без ограничения общностей считаем, что она разделяет два отрезка, полученные из множества $A$. Кроме того, она лежит на одном из отрезков, относящихся к $B$, и длина этого отрезка менее единицы, поэтому расстояние до одного из его концов менее 1/2.

Если же $X_A$ - крайняя слева, это значит, что наименьший элемент $A$ меньше единицы, а остальные - больше, но тогда, по построению, все они находятся на интервале $(1, 1+\frac{1}{n-1})$, и числовая ось справа от $X$ разбита на отрезки длины чуть больше единицы, всего их $n-1$.
Если это выполняется и для $B$, то мы просто обмениваем два наибольших элемента (например) - разница не превышает $\frac{1}{n-1}$, что нам и нужно. Исключение - случай двойки, но он тривиален, разбирается "вручную".

Пусть для $B$ не выполняется: точка $X_B$ не крайняя левая. Тогда, чтобы условие в задаче не выполнялось, все точки этой последовательности должны находиться:
- посередине между каждого отрезка (для $A$, кроме правого
- левее от $X_A-1/2<1/2$.
Если точек первого типа нет, то одно из чисел должно быть больше $n-2$, что противоречит условию.
Если есть хотя бы две точки первого типа, то видно, что в $B$ есть число, близкое (с точностью $\frac{1}{n-1}$) к целому, и мы обмениваем его с необходимым набором "почти единиц".
Если ровно одна точка первого типа, это значит, что сумма всех элементов $B$, кроме двух наибольших, равна $S=X_A-1/2<1/2$, наибольшее число - "почти полуцелое", тогда дробная часть промежуточного числа отличается от целого на величину не более $1/2-S+\frac{1}{n-1}$ - то есть ближе к целому, чем 1/2. Это значит, что, подобрав нужное количество "почти единиц", мы найдем "обменную часть" из $A$

[maxal]

Dendr в сообщении #1429980 писал(а):

У нас два множества, поэтому и точки тоже две. Выберем левую. Без ограничения общностей считаем, что она разделяет два отрезка, полученные из множества $A$. Кроме того, она лежит на одном из отрезков, относящихся к $B$, и длина этого отрезка менее единицы, поэтому расстояние до одного из его концов менее 1/2.

Этот конец может быть точкой $0$, что ничего нам не дает.

[Dendr]

Тогда укладываем отрезки (длина каждого - элемент множества) на окружность длины $n$, начиная с некоторой фиксированной точки на ней - местного "начала координат". Одно множество - по внешней стороне, второе - по внутренней; получатся два кольца, оба строго замкнуты, каждая под-дуга имеет длину не более $n-1/2$

И утверждение задачи эквивалентно следующему: существует такая укладка отрезков, при которой найдутся две точки (не вообще, а разделители отрезков) на внешнем и внутреннем кольцах соответственно отстоят друг от друга на расстояние не более 1/2.

Крайний случай - все точки одного множества собрались на дуге (0, 1/2). Это значит, что сумма всех элементов, кроме одного, строго равна 1/2 - а тот один равен $n-1/2$ - как раз ограничение на величину элемента, то есть короче такая дуга быть не может. В другом множестве есть по крайней мере один элемент, который не более единицы. Если мы начинаем укладку с него, то его второй конец окажется на интервале (0, 1) - то есть как раз на расстоянии не более, чем 1/2, от второго конца этой дуги.
Стало понятно: эти два элемента и соберем в множество $C$. Их сумма, очевидно, заключена в интервале $(n-1/2, n+1/2)$.

Теперь перейдем к более общему случаю.
Рассмотрим расстановку отрезков с неубыванием длины. Очевидно, что существует хотя бы один отрезок длины не меньшей 1. Когда мы уложим предпоследний отрезок, он накроет "дальним" концом точку с координатой (по окружности) $1/2<X_A<n-1$.
Отступление: неравенство будет нестрогим в последнем сравнении тогда и только тогда, когда данное множество состоит из одних лишь единиц - следовательно, можно из второго множества взять произвольное подмножество, его сумма, очевидно, будет отличаться от ближайшего целого не более, чем на 1/2, и для формирования $C$ достаточно набрать необходимое количество единиц.

То же проделаем со вторым множеством, получим точку $1/2<X_B<n-1$. Полагаем для определенности, что $X_A<X_B$ (как и выше предлагалось, полагаем, что $A\cap B=\varnothing$, так что равенства не возникает).
Интервал $(0, X_B)$ оказался разбит на $n-1$ меньших интервала, и длина каждого строго меньше единицы. Поэтому любая точка, отвечающая множеству $A$ находится на расстоянии не большем, чем 1/2, хотя бы до одного из концов интервала, на который она попала. Если этот интервал где-то посередине, то выбираем элементы, соответствующие отрезкам слева от нее из одного множества и справа - из другого. Так мы гарантируем нужную сумму.

Впрочем, точки могли скопиться на первом интервале, находясь на расстоянии 1/2 до нуля и большем - до второго конца... но этот случай - ура! - уже рассмотрен выше.

[Dendr]

Dendr в сообщении #1430542 писал(а):

Интервал $(0, X_B)$ оказался разбит на $n-1$ меньших интервала, и длина каждого строго меньше единицы.

Конечно, это чушь. Средняя меньше единицы, но не обязательно же длина любого.

Вернемся к "рисовке" на кругу - есть "внешность" окружности (длиной $n$), состоящая из дуг неубывающей длины, и такая же "внутренность. Пусть в начале совмещены "нули", и мы рассмотрим все пары "внешняя-внутренняя" точки, выпишем соответствующую им длину дуги (чтобы различать из, назовем эти интердугами) между ними, измеряя от "внешней" до "внутренней" точки по часовой стрелке. Пар (включая "нули") $n^2$, и набор длин заключен от нуля до $n-1$: последняя дуга перед замыканием не может быть меньше 1. Если хотя бы одна из длин интердуг меньше либо равна 1/2, мы нашли подходящие обменные блоки.

Пусть таких интердуг нет, значит, длина наименьшей интердуги $d_1>1/2$. Повернем внутренний круг, совмещая эти две точки. Длина остальных интердуг уменьшится на величину $d_1$. Если хотя бы одна из них стала меньше либо равной 1/2, то обменные блоки найдены. В противном случае, следующая по величине интердуга равна $d_2>d_1+1/2>2\cdot1/2$.

Продолжаем следовать этому алгоритму, дойдем до интердуги $d_2_n_-_2>(2n-2)\cdot1/2=n-1$
Но такой интердуги, как указано выше, нет. Следовательно, если утверждение задачи не выполнилось, то все возможные интердуги перебраны, то есть (отбрасывая "нулевую") $2n-2>n^2-1 \Longleftrightarrow n^2-2n+1=(n-1)^2<0$

Но, так как $n$ натуральное, неравенство не выполняется никогда, следовательно, утверждение задачи доказано.

Однако, у нас мультимножества, и тут кроется подводный камень.
Пусть в $B$ имеется $0<k<n-1$ нолей, а в $A$ - ни одного (если есть хоть один, обмениваем нули, и готово). В этом случае, для $B$ мы расставим меньшее количество дуг, но по крайней мере, две (иначе одно из чисел равно $n$). Тогда всего интердуг будет $2n$. Алгоритм не изменится, а условие перебора всех дуг изменится на $2n-2>2n-1$, что опять-таки не выполняется.
Противоречие.
$\qed$