Добавление элемента

[Dave]

Дано натуральное число $n$. Придумайте алгоритм, который в любое заданное подмножество $A_n=\{1,2,\dots,n\}$, содержащее менее половины элементов $A_n$, добавляет ровно один отсутствующий в нём элемент из $A_n$ так, чтобы выходные множества для разных входных заведомо отличались.

[iifat]

Стрвнно как-то. Подмножеств всего $2^n$, менее половины элементов в половине их (для чётных чуть поменьше), то бишь $2^{n-1}$. Чисел же всего $n$ — где-то да совпадёт неизбежно, нет?

[Sonic86]

iifat в сообщении #721430 писал(а):

Стрвнно как-то. Подмножеств всего $2^n$, менее половины элементов в половине их (для чётных чуть поменьше), то бишь $2^{n-1}$. Чисел же всего $n$ — где-то да совпадёт неизбежно, нет?

Нет. Надо отображать $C_n^k$ множеств мощности $k$ в $C_n^{k+1}$ множеств мощности $k+1$ добавлением элемента. А $C_n^k\leqslant C_n^{k+1}$ и лишь при нечетном $n, k=\frac{n-1}{2}$, $C_n^k=C_n^{k+1}$. Для $n=1,...,5$ отображения явно существуют, их можно руками выписать (например, при $k=1$ можно отображать $\{x\}\to\{x,x+1\}$).
Мне пока не очевидно, как доказать хотя бы то, отображение существует. Но, видимо, есть.
Короче, нормальная задача.

[iifat]

Sonic86 в сообщении #721446 писал(а):

Нет

Вы правы. Тогда вырисовывается что-то типа задачи о паросочетаниях. Надо будет посмотреть теорию — когда она там решаема.

[Sonic86]

iifat в сообщении #721479 писал(а):

Тогда вырисовывается что-то типа задачи о паросочетаниях.

Угу.

iifat в сообщении #721479 писал(а):

Надо будет посмотреть теорию — когда она там решаема.

Там страшно (можно свести к симметричной задаче БЛП, но решения не симметричны, видимо). Не факт, что общие критерии помогут, м.б. надо использовать специфику задачи.

Мои 3 копейки:
Пусть $f_{n,k}:\binom{A_n}{k}\to\binom{A_n}{k+1}$ - искомое отображение ($\binom{X}{k}$ - множество всех подмножеств мощности $k$ множества $X$). $k<\frac{n}{2}$. Ясно, что если $f_{n,k}$ существует, то $f_{n+1,k}$ существует (можно взять $f_{n+1,k}=f_{n,k}\cup g_{n,k}$, где $g_{n,k}$ получается дополнением отображения $f_{n,k-1}$ элементом $n$: $g_{n,k}:\{n+1\}\times\operatorname{Dom} f_{n,k-1}\to\{n+1\}\times\operatorname{Im} f_{n,k-1}$). И тогда достаточно найти $f_{n,k}$ для нечетных $n$, $k=\frac{n-1}{2}$, т.е. когда мощности множеств $\binom{A_n}{k},\binom{A_n}{k+1}$ совпадают.
upd: Построение $f_{n+1,k}$ через объединение непересекающихся $f_{n,k}$ и $f_{n,k-1}$ является обобщением формулы $\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}$, что как минимум любопытно.

Можно выписать циклически симметричное отображение для $k=2$ (т.е. если $12\to 123$, то $23\to 234, 34\to 345$ и т.п.), а для $k=3$ уже не получается так просто.

Дальше у меня не получается пока.

[TOTAL]

Dave в сообщении #721422 писал(а):

так, чтобы выходные множества для разных входных заведомо отличались.

Входные и выходные множества - это что? Что от чего должно отличаться?

[Dave]

TOTAL в сообщении #721847 писал(а):

Dave в сообщении #721422 писал(а):

так, чтобы выходные множества для разных входных заведомо отличались.

Входные и выходные множества - это что? Что от чего должно отличаться?

Вход - любое подмножество $A_n$ с менее чем $\frac n 2$ элементами, выход - это же подмножество с добавлением одного элемента.

[TOTAL]

Dave в сообщении #721938 писал(а):

TOTAL в сообщении #721847 писал(а):

Dave в сообщении #721422 писал(а):

так, чтобы выходные множества для разных входных заведомо отличались.

Входные и выходные множества - это что? Что от чего должно отличаться?

Вход - любое подмножество $A_n$ с менее чем $\frac n 2$ элементами, выход - это же подмножество с добавлением одного элемента.

Что от чего должно отличаться?

[iifat]

TOTAL в сообщении #721942 писал(а):

Что от чего должно отличаться?

Вы таки хотите, чтобы ТС произнёс волшебные слова "инъективное отображение", или у вас более далеко идущие планы?

[TOTAL]

iifat в сообщении #721943 писал(а):

TOTAL в сообщении #721942 писал(а):

Что от чего должно отличаться?

Вы таки хотите, чтобы ТС произнёс волшебные слова "инъективное отображение", или у вас более далеко идущие планы?

Я хотел понять условие задачи. Это был далеко или близко идущий план? Сейчас даже такого плана не осталось.

[Sonic86]

TOTAL в сообщении #721949 писал(а):

Я хотел понять условие задачи.

Для всех $n,k<\frac{n}{2}$ построить инъективное отображение $f_{n,k}$, отображающее множество всех подмножеств $A_n$ мощности $k$ в множество всех подмножеств $A_n$ мощности $k+1$ такое, что для всякого $X$ $f_{n,k}(X)=X\cup\{a\}, a\in A_n\setminus X$.

Dave, а у Вас есть решение? Я, честно говоря, устал строить $f_{n,k}$ индуктивно. Неужели нужны какие-то комбинаторные теоремы или утверждения о паросочетаниях?

[Alexander Evnin]

Любителям теории графов хорошо известно следующее
достаточное условие существования совершенного паросочетания в двудольном графе.

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

В данной задаче степень произвольной вершины первой доли
(число способов добавить к выбранному подмножеству новый элемент) больше $n/2$,
а второй (число способов удалить элемент) - меньше $\frac{n}{2}+1$, что влечёт выполнение указанного условия.

Известны алгоритмы трудоёмкости $O(k^3)$ и даже $O(k^{5/2})$ (здесь $k$ - число вершин графа) нахождения максимального паросочетания в двудольном графе.

[Dave]

Alexander Evnin в сообщении #722229 писал(а):

Известны алгоритмы трудоёмкости $O(k^3)$ и даже $O(k^{5/2})$ (здесь $k$ - число вершин графа) нахождения максимального паросочетания в двудольном графе.

Alexander Evnin, спасибо Вам за информацию, но если рассматривать множества мощности $m$, а $m=\frac {n-1} 2$, то $k$ у нас будет равно $2C_n^m=C_{n+1}^{(n+1)/2}$ и, учитывая, что $C_{2n}^n \sim \frac {2^{2n}} {\sqrt{\pi n}},$ уже при $n>20 \; \; O(k^{5/2})$ будет очень велико и стандартные алгоритмы вряд ли будут иметь практическое значение.

Sonic86 в сообщении #722014 писал(а):

Dave, а у Вас есть решение?

Да, алгоритм у меня есть. Он довольно прост и требует порядка $O(n)$ операций, вне зависимости от $m$ ($k$ в Ваших обозначениях).

Sonic86 в сообщении #722014 писал(а):

Я, честно говоря, устал строить $f_{n,k}$ индуктивно.

Никогда не отчаивайтесь

Sonic86 в сообщении #722014 писал(а):

Неужели нужны какие-то комбинаторные теоремы или утверждения о паросочетаниях?

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