61plus wrote: Let $f:X\rightarrow X$, where $X=\{1,2,\ldots ,100\}$, be a function satisfying: 1) $f(x)\neq x$ for all $x=1,2,\ldots,100$; 2) for any subset $A$ of $X$ such that $|A|=40$, we have $A\cap f(A)\neq\emptyset$. Find the minimum $k$ such that for any such function $f$, there exist a subset $B$ of $X$, where $|B|=k$, such that $B\cup f(B)=X$. 1) for any $x\in X$ , have $f(x)\not\equiv x$; Find the minimum of positive integer $k$...

Given any element $x\in X$, taking $f$ 101 times, we eventually must reach a number we've seen before. We must hence see a cycle appear. We can divide up $X$ based on the cycles the elements eventually devolve into; that is, separate $X$ into its smallest parts $X_1, X_2, \ldots$ closed under application of $f$. Since neither the conclusion nor the hypothesis statements have anything to do with $X$ other than its structure related to $f$, we can work with these sets $X_i$ and combine the results in the end. We'll work with $X_1=N$ and the other sets will follow similarly. We define $f^{-1}(A)=\{x: f(x)\in A\}$, and define $f^{-k}(A)$ in the usual inductive way. Let us divide $N$ into the pure cycle $N_1$ and the rest, $N_2=N-N_1$. For elements $x$ in $N_2$, we define $g(x)$ to be the largest $k$ with $f^{-k}(\{x\})\neq \emptyset$. Now define a coloring on elements in $N_2$ as follows: color all elements $x$ with $g(x)=0$ red, and for elements $x$ with $g(x)=n>0$, color $x$ red if all elements in $f^{-1}(\{x\})$ are colored white, and white otherwise. This coloring has the property that $f(x)$ is white for any red $x$, and for any white $y$ there's a red $x$ with $f(x)=y$. Call the set of red elements $R$. We show that the maximal "independent set", or the largest set of elements in $N$ not containing $x$ and $f(x)$ both, is at most 1 less than the minimal "covering set", or the smallest set of elements $Z$ in $N$ with $Z\cup f(Z)=N$. We can prove this as follows: clearly $R$ is both a covering set and an independent set in $N_2$, so all we have to do is look at $N_1$. What we're going to do is add elements to $R$ from $N_1$ which are not immediately excluded by the "independent set" condition. So if we think of $N$ as a chain where the elements are linked by application of $f$, then $N_1$ is a loop; we break this loop into those connected to a red element in $N_2$ and those connected to no red elements. Suppose that there is at least one element of the latter. We get alternating chains of those that are and those that aren't connected to red elements, which we'll call red and white chains respectively. If we look at a white chain, we can add the first element, third element, fifth element, and so on into $R$ and not break the "independent set" status of $R$. We can do this for all white chains, and by the end, $R$ has both the "independent set" property and the "covering set" property. It has the former because of the way we added elements to it, and it has the latter because the old $R$ covered all of $N_2$, and the way we added elements to $R$ forces all elements of $N_1$ to be covered too. In this case, we've found an "independent covering set" so the minimum covering set is at most the size of the maximum independent set. Now the issue is if there are no red chains, and every element in $N_1$ is only connected to white elements in $N_2$. We call these "untouched" cycles; every other cycle is "touched". In this case, $N_1$ is independent of $N_2$: we can add any element of $N_1$ we want to $R$ and must cover all elements of $N_1$. So we create an independent set by choosing alternating elements; if $|N_1|$ is even then we can do this with no problem, creating both an independent set and a covering set. If $|N_1|$ is odd then we must have some consecutive pair of elements not in $R$ to get an independent set, and we must have some consecutive pair of elements in $R$ to get a covering set. In all cases, though, we find a covering set with at most one element more than an independent set, and our statement is proven. Note that we have proven additionally that there can only be a difference of $1$ if the cycle is both untouched and odd; in any other case we have found an independent covering set. So let us look now not at just $N$ but at all $X_1, X_2, \ldots$. We find that the statement we're given says that the sums of the sizes of all the maximum independent sets in $X_1, X_2, \ldots$ is at most $39$, and we find that what we're asked for is the minimum possible sum of covering set sizes. We know that the minimum covering set is at most one more than the maximum independent set, so the minimum possible sum is at most the maximum independent set size of the whole configuration plus the number of odd untouched cycles. Pick a maximum independent set $C$. (Note that the "touchedness" of each cycle does not depend on which $C$ we choose.) Suppose that $\ell=|C|$ (so that $\ell\leq 39$), and $m$ is the number of odd untouched cycles; then we're trying to maximize $m+\ell$. Let us prove $99\geq 2m+\ell$. For every element in $X$, either it's in $C$, or it's not in $C$ but is in an untouched odd cycle, or it's neither. The number of elements in $C$ is of course $\ell$. There are at least 2 elements not in $C$ in every untouched odd cycle, because at least half of them are not. So $100\geq \ell+2m$. We must reduce the left side by one. How many elements are not counted in $\ell+2m$? If there's some untouched odd cycle bigger than size 3, then there's at least one leftover element. Otherwise all untouched odd cycles are of size 3. If there is a touched cycle or untouched even cycle, then the cycle also contains at least one element not in $C$, so again there's at least one leftover element. Otherwise, all cycles are untouched 3-cycles. But since $100$ is not divisible by 3, we must have at least one element left over, which must be connected to an untouched cycle somehow. Since this cycle is untouched, there must be a white element attached to it, and then a red element attached to this white one. One of these two is not in $C$, and is clearly not in an untouched cycle. So in every case, we cannot have equality in $100\geq \ell+2m$; we must have $99\geq \ell+2m$. Add this to $39\geq \ell$ to get $2m+2\ell\leq 138$, or $m+\ell\leq 69$. So the maximum possible is $69$. We can force $k=69$ with the following arrangement: $f(1)=f(2)=\ldots=f(9)=10, f(10)=11,$ and for $0\leq r\leq 29$ we have $f(3r+11)=3r+12, f(3r+12)=3r+13, f(3r+13)=3r+11$. Given any 40 number set $A$, either two of them are in some set $\{3r+11, 3r+12, 3r+13\}$ in which case you're good, or there are at most $30$ numbers wasted on them forcing all of $1, 2, \ldots 10$ to be in $A$; then $f(1)=10$ and you're still good. But given any 68 numbers $B$, either not all of $1, 2, \ldots 9$ are in $B$ or there are at most $59$ elements among $10, 11, 12, \ldots 100$, and that means that among the sets $\{10, 11, 12, 13\}, \{14, 15, 16\}, \ldots \{98, 99, 100\}$ there is some set containing only one element of $B$. In either case, $B\cup f(B)\neq X$. But the $69$ elements $B=\{1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 15, 17, 18, \ldots 98, 99\}$ cover $X$ just fine. So the answer is $k=69$. Please comment if you find that this solution is wrong or unclear, and I'll try to illuminate.

This is secretly combo. Also, this is a pretty bad writeup (and the ``proof" to Claim 1 is more like a sketch), but anyway... Consider the canonical directed (and simple by condition 1) graph $G$ on labeled vertices $1, 2, \dots, 100$ with the edge $i \to j$ if $f(i) = j$. Condition 2 then tells us that the maximal independent set of $G$ has $\leq 39$ vertices, and asks us to find the largest possible minimal vertex cover: let this be denoted by $k(G)$. The answer is $\boxed{69}$. For a construction, consider the following graph $G$. Then an independent set can contain at most one vertex from each cycle, and at most $9$ vertices from the last component, for a total of $30 \cdot 1 + 9 = 39$. Similarly, a vertex cover will have at least two vertices from each cycle, and at least $9$ vertices from the last component, for a total of $30 \cdot 2 + 9 = 69$ vertices. [asy][asy] size(8cm); defaultpen(linewidth(0.75)); pair A = dir(90); pair B = dir(210); pair C = dir(330); for (int i = 0; i <= 3; ++i) { if (i == 2) { A = shift(3,0)*A; B = shift(3,0)*B; C = shift(3,0)*C; continue; } dot(A); dot(B); dot(C); draw(A--B,arrow=Arrow(TeXHead)); draw(B--C,arrow=Arrow(TeXHead)); draw(C--A,arrow=Arrow(TeXHead)); A = shift(3,0)*A; B = shift(3,0)*B; C = shift(3,0)*C; } dot((5,0),linewidth(2)); dot((6,0),linewidth(2)); dot((7,0),linewidth(2)); draw(brace((10,-1),(-1,-1),1)); dot((12,0)); dot((14,0)); dot((16,3)); dot((16,-3)); dot((16,1),linewidth(2)); dot((16,0),linewidth(2)); dot((16,-1),linewidth(2)); draw(Arc((13,1),sqrt(2),230,310),arrow=Arrow(TeXHead)); draw(Arc((13,-1),sqrt(2),50,130),arrow=Arrow(TeXHead)); draw((16,3)--(14.2,0.3),arrow=Arrow(TeXHead)); draw((16,-3)--(14.2,-0.3),arrow=Arrow(TeXHead)); draw(brace((17,3),(17,-3),1)); defaultpen(fontsize(10pt)); label("30 cycles", (4.5,-3)); label("8 nodes", (18,0),dir(0)); [/asy][/asy] We now show necessity. The pith of the problem is the following: Claim 1. A connected graph with $n$ nodes, each with outdegree $1$, has a maximal independent set of size $\geq \frac{n-1}{2}$. Equality holds only if the graph contains an odd cycle. Proof. The claim obviously holds for cycles and for trees (even ignoring their root). But such graphs are a set of trees branching from a central cycle. Thus, we are done. Note that, as a corollary, for any connected graph that isn't an odd cycle, the maximal independent set is also a vertex cover. Moreover, for any graph where equality holds, the minimal vertex cover has size $\frac{n+1}{2}$ by adding a vertex from the odd cycle. $\square$ Color red all vertices whose connected component has equality in Claim 1, and these components have size $c_1, c_2, \dots, c_\ell$. Then the number of blue vertices is $100 - (c_1 + \dots + c_\ell)$, and the number of blue vertices is a maximal independent set is $\leq 39 + \tfrac{1}{2}\ell - \tfrac{1}{2}(c_1 + \dots + c_\ell)$ (by the claim). Shorthanding $S = c_1 + \dots + c_\ell$, the number of vertices in a minimal vertex cover is \begin{align*} k(G) &\leq \underbrace{\tfrac{1}{2}\ell + \tfrac{1}{2}S}_{\text{red vertices}} + \underbrace{\min(99 - S, 39 + \tfrac{1}{2}\ell - \tfrac{1}{2}S)}_{\text{blue vertices}}\\ &= \min(99 - \tfrac{S}{2} + \tfrac{\ell}{2}, 39 + \ell). \end{align*}Finally, $c_i \geq 3$, so $S \geq 3\ell$ and $k(G) \leq \min(99 - \ell, 39 + \ell) \leq 69$, as desired.

Consider the arrow graph of $f$ on $X$. Note that each connected component looks like a directed cycle with a bunch of trees coming off of each vertex of the cycle. For each connected component $C$, let $\alpha(C)$ be the maximum number of elements of $C$ we can choose such that their image under $f$ is disjoint from them, and let $\beta(C)$ be the minimum number of vertices of $C$ we can choose such that them and their image cover $C$. We have the following key claim. Claim: We have $\alpha(C)\ge\beta(C)-1$. Proof: It suffices to show that given a subset $D\subseteq C$ such that $D$ and $f(D)$ cover $C$, we can find a subset $D'\subseteq C$ such that $|D'|\le |D|$ and such that there is at most one pair of elements from $D'$ that are adjacent. Label the edges of $C$ with ordinal numbers in the following way. Label the edges of the cycle with $1$, and for any edge with depth $k$ into the tree it's in (with depth $1$ for edges incident to the cycle), label it with $\omega^k$. Suppose we're given $D\subseteq C$ such that $D$ and $f(D)$ cover $C$. Call an edge bad if both of its endpoints are in $D$. We'll show that either all the bad edges are on the central cycle, or there is a way to modify $D$ such that its cardinality does not increase, and the sum of the weights of the bad edges decreases. Since we can't have infinite decreasing sequences of ordinals (lol overkill), we'll reduce the problem to the case where the only bad edges are on the central cycle. Suppose we have a bad edge $a\to f(a)$ with weight $\omega^k$ for $k\ge 2$. Modify $D$ by removing $f(a)$ from $D$ and adding $f(f(a))$ if it is not already present. If $f(f(a))$ is already present, then size of $D$ decreases and the set of bad edges becomes a strict subset of what it was before, so the sum of their weights goes down. If $f(f(a))$ is not already present, then the size of $D$ doesn't change, and we lose at least one bad edge with weight $\omega^k$, and potentially gain many bad edges with weights $\omega^{k-1}$ or $\omega^{k-2}$, so the total weight sum goes down. Suppose we have a bad edge $a\to f(a)$ with weight $\omega$. Then, $f(a)$ is part of the central cycle of $C$. If $f(f(a))$ is already present, delete $f(a)$, so the size of $D$ doesn't change, and the set of bad edges becomes a strict subset of what it was before, so the sum of their weights goes down. Now suppose $f(f(a))$ is not already present. If there are elements that map to $f(f(a))$ in the tree rooted at $f(f(a))$ that are in $D$, then we can simply delete $f(a)$, and by the same logic as before, we're fine. So now suppose that there are no elements in the tree rooted at $f(f(a))$ that map to it. Then, deleting $f(a)$ and adding $f(f(a))$ removes an edge of weight $\omega$ and only adds edges of weight $1$, so the size of $D$ stays the same and the sum of the weights goes down. This shows that we can reduce $D$ down such that the only bad edges of $D$ are on the central cycle. Call a vertex of the central cycle deficient if it does not have any elements of $D$ one level above it in the tree rooted at the vertex, or in other words, a vertex is deficient if it will not be covered by $D\cup f(D)$ if we remove all the cycle elements from $D$. Note that all elements of $D$ on the cycle are deficient since there are no bad edges not on the cycle. Fixing $D$ and changing which subset of deficient vertices we choose, the claim reduces to the following: Suppose we have a directed cycle of length $m$, and some $k$ of the vertices are said to be deficient. There is a subset $D$ of the deficient vertices such that all the deficient vertices are covered by either $D$ or the image of $D$ of minimal size such that at most on edge of the cycle has both endpoints in $D$. To prove this, split the deficient vertices into contiguous blocks. First suppose that the entire cycle is not a block. Each block acts independently, and is isomorphic to a directed path. It is clear that in this case, it is optimal to pick every other vertex from each block, and any other selection covering every vertex of the block with it and its image will be of larger size. Thus, it suffices to look at the case where all vertices are deficient. In this case, it is again clearly optimal to select $(m+1)/2$ of the vertices such that there is only one bad edge, so we're done. This completes the proof of the claim. $\blacksquare$ Let $\mathcal{C}$ be the set of connected components. We see that \[39\ge \sum_{C\in\mathcal{C}}\alpha(C)\ge \sum_{C\in\mathcal{C}}\beta(C) - |\mathcal{C}|.\]If $|\mathcal{C}|\le 30$, then we see that \[\sum_{C\in\mathcal{C}}\beta(C)\le 69,\]so we can select a subset $B\subseteq X$ such that $B|\le 69$ and $B\cup f(B)=X$. If $|\mathcal{C}|\ge 31$, then from each connected component, select all but some vertex with nonzero indegree (this exists since there are no isolated vertices) to make up $B$. We see then that $|B|\le 100-|\mathcal{C}|=69$ again. Thus, in all cases, we can select valid $B$ with $|B|\le 69$. It suffices to construct $f$ such that the minimal such $B$ has size $69$. To do this, let the arrow graph of $f$ be made up of $29$ disjoint $3$-cycles, and a component consisting of a $3$-cycle $a\to b\to c\to a$ with another vertex $x\to a$, and $9$ vertices $y_1,\ldots,y_9$ pointing to $x$. This satisfies the second condition of the problem, since any $A$ satisfying $A\cap f(A)=\emptyset$ can take at most $1$ from each $3$-cycle, and at most $12$ from the last component. Any $B$ satisfying $B\cup f(B)=X$ must have at least $2$ from each of the $3$-cycles, and at least $11$ from the last component, for a total of at least $29\cdot 2+11=69$, as desired. We can get $69$ by selecting exactly $2$ from each $3$-cycle, and everything but $x$ and $c$ from the last component. This shows that the answer to the problem is $\boxed{69}$.

We claim that the answer is $k=69$. The construction is the same as other users pointed out. Now we prove $k\le 69$. Let $S$ denote the set of maximal cardinality such that $S\cap f(S) = \emptyset$. If there are more than one such $S$, take the one with $f(S)$ maximal. Let $T=f(S)$. Let $U = X \setminus {S \cup T}$. Note that $\vert S \vert \le 39$ and $\vert T \vert \le 39$. Hence $\vert U \vert \ge 22$. We have the following claims about the structure of $S,T,U$: Claim 1 : $f(U)=S$ Proof : For any $u\in U$, look at $S'=S\cup \{u\}$. Note that if $f(u) \not \in S$ and since $f(u) \neq u$, we have $S' \cap f(S') =\emptyset$. This contradicts the maximality of $S$. Claim 2 : For any distinct $u_1,u_2 \in U$, $f(u_1)\neq f(u_2)$. Proof : Assume FTSOC for some $u_1,u_2 \in U$, $f(u_1)=f(u_2)=s \in S$. Let $S'= S \setminus \{s\} \cup \{u_1,u_2\}$. Note that $S'$ contradicts the maximality of $S$. Let $\{u_i\}_{i=1}^{n}$ denote the members of $U$. Let $s_i=f(u_i)$. Claim 3 : For any distinct $s_1,s_2$, $f(s_1)\neq f(s_2)$. Proof : Assume $f(s_i)=f(s_j)=t$ for some $t\in T$. Let $S' = S\setminus \{s_i\} \cup \{u_i\}$. Then note that $S'\cap f(S') = \emptyset$. However $f(S') = T \cup \{s_i\}$. So $\vert f(S')\vert > \vert f(S) \vert$. Contradiction. Now note that $\{s_i\}_{i=1}^{n}$ are mapped to $n$ unique elements of $T$. Hence $\vert T \vert \ge n = \vert U\vert$. Now from $\vert S \vert \le 39$ we have $\vert T \vert + \vert U \vert \ge 61$. Hence $\vert T \vert \ge 31$. Now take $B= S \cup U$ and note that $B\cup f(B) = X$ and $\vert B \vert \le 69$. This gives $k\le 69$. $\square$

Solved with mueller.25 and Gabrupro, we actually got $k \le 69$ fairly quickly but believed the answer was $k = 68$ for a while until we found the construction . This seems to be the simplest solution on thread too. Consider the directed graph induced by $f$. First, ignore the direction of each arrow and consider the maximal matching, say it is of size $M$ (so it has $2M$ vertices), now add in orientations of arrows. Call the two sets of the matching $X$ and $Y$ such that every vertex in $X$ maps to something in $Y$. Notice that there cannot be $\le 40$ outside the matching since then the second condition is contradicted, so we must have $100 - 2M < 40 \implies M > 30 \implies M \ge 31$ So, by picking $M$ vertices in $X$ along with the $100-2M$ vertices outside the matching, to be in $B$, we can ensure we use at most $(100-2M) + M = 100 - M \le 69$ vertices. For a construction, consider $30$ triangles, an involution and the rest of the vertices mapping to one of the things in the involution, this works and so we are done. $\blacksquare$

Consider an directed graph with vertices in $\{1,2,\cdots, 100\}$. Draw an edge $x \to f(x)$ for $x=1,2,\cdots,100$. Observe that if I start from a fixed vertex and walk $101$ steps, I visit the same vertex twice. Therefore, the path I trace is a path leading to a cycle. Now undirect all edges (there are multiple edges if $f(f(x))=x$). Call a set $S$ bad if $S\cap f(S)=\emptyset$, i.e. $S$ is an independent set in the undirected graph. Claim: In a connected component of $k$ vertices, there exists an independent set of $\frac{k-1}{2}$ vertices. Proof: Note a connected component is a pseudotree (has $k$ edges and $k$ vertices) since we can uniquely map each vertex to an edge. If the cycle is even the graph is bipartite, and at least the set of vertices of one color has at least $\frac k2$ vertices. If the cycle has odd length, the removal of one vertex makes it bipartite. Now if a connected component with $k$ vertices and a maximal independent set of size $l$, call its beauty $2l-k$. We previously proved $2l-k\ge -1$. We also know $\sum k=100$ since there are 100 vertices and $\sum l \le 39$ because there is no bad set with $40$ vertices. Now let $g(v)$ denote the set of vertices that eventually leads to $v$. Claim: $2l-k=-1$ if and only if the component has an odd cycle and $|g(v)|$ is odd for all $v$ in the cycle. Proof: Note $g(v)$ is of the form $\{w, f(w), f^2(w), \cdots, v=f^{|g(v)-1|}(w)\}$. This means I can pick $w$ and remove $w,f(w)$ without changing the beauty. Thus assume $|g(v)|\in \{1,2\}$. Let $S$ be the set of vertices not in the cycle. Select all vertices in $S$, remove $S$ and $f(S)$. The cycle breaks down so the remaining vertices in the cycle is bipartite so $2l\ge k$. Now, we want to maximize the number of vertices in the digraph's minimum dominating set i.e. $B$ with $|B|$ minimized satisfying $B\cup f(B)=T$. Note in a graph with $2l-k=-1$, this is clearly $\frac{k+1}{2}$. I claim in all other graphs, the minimum dominating set has at most the size of the maximal independent set. First, in both graphs, we keep on taking a vertex $v$ with zero indegree if removing $v,f(v)$ doesn't remove a vertex in the cycle. To get the minimum dominating set, if I end up disconnecting the cycle, then the cycle becomes a (disjoint union of) paths and the result is clear because after the cycle gets removed the graph is bipartite. Therefore, the answer is at most the maximal independent set plus number of graphs with beauty -1. I claim the answer is at most 69. If more can be achieved, there exists at least 31 graphs with beauty -1, for 31 triangles and at most 7 other vertices. Since connected components have size at least 1, the dominating set for the 7 other vertices can be achieved with 6, so we have $|B|\le 62+6=68$. On the other hand, 69 is achievable with 30 triangles and a star graph with 9 vertices (plus an edge)

The fact that $k=68$ fails can be illustrated by a nice example, as above. To show that $k=69$ works approach the problem greedily: Pick any 40-element set of vertices. From condition ii), it has a directed edge, say $y \to f(y)$. Put $y$ in $B$. Exclude $y, f(y)$ form the graph. Continue until the graph has <40 vertices. It will have precisely 38, and $B$ will have 31 elements, since so far I have produced 31 pairs. Now put all 38 remaining vertices in B and clearly $B\cup f(B)=X$ while $|B|=69$