Интересная функция

[DARIUS]

$ Дана функция f:X\to X$ ,где $X=\{1,2,3...100\}$ для нее выполняются условия $(1)$ $f(x)\neq x $ для всех $x=1,2...100$ $(2)$ для любого подмножества $A$ , $|A|=40$,$A\bigcap f(A)\neq0$ .Найти наименьшее $k$ ,что для любой функции$f $,существует подмножнство$B$ множества$X$,$|B|=k$,что выполняется $ B\bigcup f(B)=X$

[Null]

Ну $k > 68$

[DARIUS]

А как подступиться к решению?

[Dave]

Докажите, что $X$ можно разбить на 3 множества $L$, $M$ и $C$, таких, что $f(L)=M$ и $f(C)=C$. В свою очередь, $C$ можно разбить на 2 множества $D$ и $E$ так, что $f(D) \supseteq E$, $f(E) \subseteq D$ и

$$d \leqslant 2e , \eqno (1)$$

где $d=|D|$, $e=|E|$. ($C$ есть набор циклов функции $f$, для разбиения взять через один или почти через один элементы в каждом цикле.) Если $l=|L|$, $m=|M|$, то

$$l+m+d+e=100 . \eqno(2)$$

Потом нужно заметить, что если $A=L \cup E$, то $A \cap f(A)=\varnothing$, значит

$$l+e<40 . \eqno (3)$$

Кроме этого, $L \cup D$ всегда можно взять в качестве $B$. Сложите $(1)$, $(2)$ и $(3)$ и получите оценку $l+d \leqslant 69$, откуда следует

Null в сообщении #834601 писал(а):

Ну $k > 68$

Чтобы доказать, что $k$ меньше $69$ может не подойти, приведите пример, когда в $(1)$ достигается равенство, $m=1$, а в левой части $(3)$ - максимально возможная сумма.