2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 перемешиваем мультимножества с одинаковой суммой
Сообщение12.12.2019, 01:11 
Модератор
Аватара пользователя


11/01/06
5660
Пусть $n\geq 2$ - целое число.

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

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


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

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

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


09/09/14
6328
maxal в сообщении #1429803 писал(а):
действительные числа из интервала $(0,n-\frac12)$
И судя по этому условию, подразумевалось что-то более сложное.

 Профиль  
                  
 
 Re: перемешиваем мультимножества с одинаковой суммой
Сообщение13.12.2019, 00:02 
Заслуженный участник


23/07/08
10626
Crna Gora

(déjà vu)

ИСН в сообщении #1429939 писал(а):
Во всех предыдущих случаях, когда мне казалось, что maxal сделал слишком слабое утверждение, в итоге оказывалось, что это я чего-то не понял.
cf.:
ИСН в сообщении #829213 писал(а):
Я давно убедился: если Вам померещилось что-то простое в любой задаче от arqady, пересмотрите свои доводы. В них что-то не так.

 Профиль  
                  
 
 Re: перемешиваем мультимножества с одинаковой суммой
Сообщение13.12.2019, 01:21 
Модератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: перемешиваем мультимножества с одинаковой суммой
Сообщение13.12.2019, 14:07 


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

Разумеется, если в множествах есть общие элементы, то ответ очевиден. Поэтому считаем, что $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$

 Профиль  
                  
 
 Re: перемешиваем мультимножества с одинаковой суммой
Сообщение13.12.2019, 18:05 
Модератор
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: перемешиваем мультимножества с одинаковой суммой
Сообщение16.12.2019, 16:14 


02/04/18
240
Тогда укладываем отрезки (длина каждого - элемент множества) на окружность длины $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 до нуля и большем - до второго конца... но этот случай - ура! - уже рассмотрен выше.

 Профиль  
                  
 
 Re: перемешиваем мультимножества с одинаковой суммой
Сообщение18.12.2019, 14:04 


02/04/18
240
Dendr в сообщении #1430542 писал(а):
Интервал $(0, X_B)$ оказался разбит на $n-1$ меньших интервала, и длина каждого строго меньше единицы.

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

Вернемся к "рисовке" на кругу - есть "внешность" окружности (длиной $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$

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

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



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

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


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

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