Curiosity: catracho is a nickname for boys from Honduras. Similarly, catracha is a nickname for girls from Honduras.

(a) given a catracha function $f$ and $k \in [n] := \{1,2, \dots , n\}$, let $a_k \in \mathbb{N}$ be the least positive integer such that $f^{a_k}(k)=k$ (such $a_k$ always exists, since $f^{f(k)}(k)=k$). Now, from $f^{f(k)}(k)=k$, changing $k$ by $f^{a}(k)$, we get $f^{f(f^{a}(k))}(f^{a}(k))=f^{a}(k) \Rightarrow f^{f^{a+1}(k)+a}(k)=f^{a}(k)$, so $a_k|(f^{a+1}(k)+a)-a$, or $a_k|f^{a+1}(k)$, for all $a \in \mathbb{Z}, a \ge 0$. Now, if $a=a_k-1$, we have $f^{a+1}(k)=k$, so $a_k|k$, for all $k \in [n]$. In particular, $a_1=1$, so $1$ is a fixed point of $f$. Let $p> \sqrt{n}$ be a prime number. Because $a_p|p$, we have $a_p = 1$ or $a_p = p$. If $a_p=p$, then the $p$ distinct numbers $p, f(p), f^2(p), \dots, f^{p-1}(p)$ are divisible by $p$, and they're on $[n]$, which is a contradiction, since $p^2>n$. So, $a_p=1$, which implies that $p$ is a fixed point of $f$, for all prime $p> \sqrt{n}$,. Because there are $ \pi (n) - \pi (\sqrt{n})$ such primes, and because $1$ is a fixed point of $f$, we conclude that $f$ has at least $\pi (n) - \pi (\sqrt{n}) +1 $ fixed points. (b) For each $n \in \mathbb{N}$, we say that a set $A \subset [n]$ is a $\sigma$-set if each element of $A$ is divisible by $|A|$. If we show that $[n]$ can be partitioned in some $\sigma$-sets, with exactly $\pi (n) - \pi (\sqrt{n}) +1$ of them having only one element, then such $f$ does exists, because given a $\sigma$-subset $A= \{ a_1 ,a_2 , \dots, a_{|A|} \} $, we can construct $f$ as $f(a_1)=a_2, f(a_2)=a_3, \dots, f(a_n)=a_1$. So, it remains to prove that such a partition always exists for $n \ge 36$. Let $S_0=\{ 1 \} \cup \{ q_1 \} \cup \dots \cup \{ q_b \}$, where $q_1, \dots, q_b$ are all the primes between $\sqrt{n}$ and $n$, greater than $\sqrt{n}$. The set $[n]-S_0$ is equal to $L_1 \cup L_2 \cup \dots \cup L_a$, where $a=\pi (\sqrt{n})$, $p_1 < p_2 < \dots < p_a$ are all the primes from 1 to $\sqrt{n}$ and $L_k$ is the set of all numbers in $[n]$ such that the least prime divisor of it is equal to $p_k$, for each $k=1,2, \dots , a$. Now, we'll run the algoritim below: Step 1: For $t=a, a-1, \dots, 1$, let $d_t=k_t . p_t + r_t$ be the number of multiples of $p_t$ in $[n]-S_{a-t}$. We'll construct the $\sigma$-sets $ \{ a_1, a_2 ,..., a_{p_t} \}, \dots, \{ a_{p_t(k_t-1)+1}, a_{p_t(k_t-1)+2} ,..., a_{p_t.k_t} \}$ as the following: $\{ a_1, \dots , a_{|L_t \cap ([n]-S_{a-t})|} \} = L_t \cap ([n]-S_{a-t})$, and $a_1 > \dots > a_{|L_t \cap ([n]-S_{a-t})|}$; $\{ a_{|L_t \cap ([n]-S_{a-t})|+1}, \dots , a_{k_t . p_t} \} \rightarrow (([n]-S_{a-t})\cap \{p_t, 2p_t, \dots \}$ and $a_{|L_t \cap ([n]-S_{a-t})|+1}> \dots > a_{k_a . p_a}$, where the $\rightarrow$ means that we take all we can from $(([n]-S_{a-t})\cap \{p_t, 2p_t, \dots \}$ in a decreasing order. Now, let $S_{a-t+1}= S_{a-t}\cup \{ a_1, a_2 ,..., a_{p_a} \} \cup \dots \cup \{ a_{p_a(k_a-1)+1}, a_{p_a(k_a-1)+2} ,..., a_{p_a.k_a} \}$. Step 2: If you ran the preceding step to $t$, run it to $t-1$ (remember to start on $t=a$). When we do the step 1 for some $t$ on the algorithm, we take all the numbers on $[n]$ in which the least prime factor is $p_t$ to create $S_{a-t+1}$ (and some other numbers divisible by $p_t$), since we take all numbers in $L_t$, because the numbers in $S_{a-t}$ that belong to $L_t$ were taken before. Also, note that $\{ a_1,a_2, \dots, a_{|L_t \cap ([x]-S_{a-t}| \}}$ is NOT a $\sigma$-subset (we take all we can from $L_t \cap ([x]-S_{a-t})$), so, at first, we can always take all the elements from $L_t \cap ([x]-S_{a-t})$ (if $L_t \cap ([x]-S_{a-t})= \emptyset$, we take nothing, for example), unless the number of elements in $([x]-S_{a-t})$ is grater than the number of elements we want to take, that is, $p_t.k_t$. It only remains to prove that there's at most $p_t.k_t$ elements in $L_t \cap ([x]-S_{a-t})$, in order to take all the numbers in $L_t$. We can do it by induction (making $t=a,a-1,\dots, 2$). First, observe that $S_{a-t} -S_0$ have only numbers divisible by $p_a, \dots, p_{t+1}$, so if the the numbers $2p_t , 3p_t , \dots , (p_t-1)p_t, (p_t+1)p_t$ are in [n], they aren't in $S_{a-t} -S_0$, and clearly they aren't on $S_0$, so they aren't on $S_{a-t}$. Also, for $p_t$ odd, they aren't in $L_t$. So, because $ L_t \subset \{ p_t, 2p_t, \dots \}$ and $\{ p_t, 2p_t, \dots \} - L_t$ has at least $p_t-1 \ge r_t$ elements, $L_t$ has at most $p_t.k_t$ elements, as we whised. Observe that, for $p_1=2$, this can't be truth. Because of that, we have that $S_a$ can be $[n]$ or $[n]- \{ 2 \}$, since we took the numbers in a decreasing order. Edited: It may be possible that $2p_t , 3p_t , \dots , (p_t-1)p_t$ are in $[n]$, but $(p_t+1)p_t$ isn't in $[n]$. If this is the case, we have that, by writing $n=q^2+r$, with $q,r \ge 0 $ integers such that $0 \le r \le 2q$, $p_t \le q$ (by choice) and $p_t > q - 1$ (because $p_t(p_t+1)>n>q(q-1)$. Thus, $p_t=q$, which implies that $n<p_t(p_t+1)=q^2+q$, or $r<q$. So, the only numbers in $[n]$ that are divisible by $p_t$ are $p_t, 2p_t, \dots, p_t^2$, and that means that the only numbers in $L_t \cap ([x]-S_{a-t})$ are $p_t$ and $p_t^2$, so $|L_t \cap ([x]-S_{a-t})|=2$ and that's at most $p_tk_t$ elements anyway. At the end, we obtain a set $S_a$ that can be written as a partiton of $\sigma$-subsets, and it can be equal to $[n]$ or $[n]- \{ 2 \}$, since in the last step of our algorithm, the $\sigma$-subsets to be attached on $S_{a-1}$ has 2 elements each, so at the end we can attach all the remaining numbers ou we can't only attach 2, since 2 is the least number divisible by $p_1=2$ and we construct the $\sigma$-subsets in decreasing order. If $S_a=[n]$, then we reached our goal. else, let's see more... Let $\{ a, b, c \}$ be the last $\sigma$-set created on the penultimate step of the algorithm. Because $n \ge 36$, the 5 least numbers to enter in the $\sigma$-subsets in the penultimete step are $36, 24, 18, 12, 6$, since those five numbers are the least ones that are divisible by 3 and that belong to $(([n]-S_{a-2})\cap \{3, 6, \dots \}$. Hence, we have that $\{ a, b, c \} = \{36, 24, 18 \}$, if $r_2=2$; $\{ a, b, c \} = \{24, 18, 12 \}$, if $r_2=1$; $\{ a, b, c \} = \{18, 12, 6 \}$, if $r_2=0$. In each case, if we replace $\{ a, b, c \}$ and $ \{ 2 \}$ by $ \{ a, 2 \}$ and $\{ b, c \}$, we have now a partition of $[n]$ in $\sigma$-subsets. Finnaly, the problem is solved!

Above: I'm sorry. But it isn't really explained why we can always take all the elements from $L_t \cap ([n]-S_{a-t})$. What if there are not enough multiples of $p_t$?

For $t=a$ this is not a problem. But maybe for small $t$ we have taken so many numbers that $\{p_t, 2p_t, ...\}$ that there are not enough numbers in $\{p_t, 2p_t, ...\} - L_t - S_{a-t}$ so that we can take all the numbers in $L_t - S_{a-t}$.

Let $S$ be the set of numbers we wish to partition. Let $p_1, .., p_a$ be the primes that are less than the square root of $n$. For $i<a+1$ let $W_i$ be the set of numbers in $S$ whose smallest prime factor is $p_i$, let $M_i$ be the set of numbers in $S$ that are multiples of $p_i$ and let $H_i = M_i - W_i$. Note that $p_i(p_i+1) \le p_a^2 \le n$. Let $N mod x$ denote the remainder of $N$ when divided by $x$, it can take a value from $1$ to $x$. Assume that $H_a \ge p_a - (W_i mod p_a)$ (I am referring to the cardinalities here). Let an "excellent" set be a set that has a small prime cardinality and such that all of its elements are divisible by its cardinality. Let $t=a$. Firstly I construct excellent sets from $M_t$ (making sure to take members of $W_t$ first). This is possible because of the inequality above. I give preference to bigger numbers. I do this until there are less than $p_t$ numbers in $M_t$. Now redefine $S$, $M_i$, $W_i$, $H_i$ so that I eliminate from these sets all the numbers that I just took. ,' Now repeat this process for $t=a-1$ instead of $a$, and then for $t=a-2$, etcetera, for $t=1$. Notice that we always have $H_i \ge p_i-1$ (and so the inequality $H_i \ge p_i - (W_i mod p_i)$ because we haven't taken the numbers $2p_i$, ..., $(p_i-1)p_i$, $(p_i+1)p_i \le n$ yet. So we can always repeat this process. The only possible problem is when $i=1$ because $(p_i+1)p_i$ is already taken and so the inequality doesn't hold! We also have to verify the inequality for $t=a$, so my solution is not yet complete. edit: I have found a complicated way to fix for $t=1$, it's pretty ugly so I won't describe it, it uses multiples of 3 and 2. And $n \ge 36$. I have found also how to prove for $t=a$, but the proof is very computational so I won't describe it here. I'm sorry

This problem is mine. I would like to remark that in the original formulation, part $b$ asks to prove that for all $n$, there exists $f$ with at most $\pi(n) - \pi(\sqrt{n}) + 2$ fixed points. And of course the Honduran flavour is not my artwork

Juan Ortiz, thanks for notice those "holes" in my solution. I think there're some points to explain. When we do the step 1 for some $t$ on the algorithm, we take all the numbers on $[n]$ in which the least prime factor is $p_t$ to create $S_{a-t+1}$ (and some other numbers divisible by $p_t$), since we take all numbers in $L_t$, because the numbers in $S_{a-t}$ that belong to $L_t$ were taken before. Also, note that $\{ a_1,a_2, \dots, a_{|L_t \cap ([x]-S_{a-t}| \}}$ is NOT a $\sigma$-subset (we take all we can from $L_t \cap ([x]-S_{a-t})$), so, at first, we can always take all the elements from $L_t \cap ([x]-S_{a-t})$ (if $L_t \cap ([x]-S_{a-t})= \emptyset$, we take nothing, for example), unless the number of elements in $([x]-S_{a-t})$ is grater than the number of elements we want to take, that is, $p_t.k_t$. It only remains to prove that there's at most $p_t.k_t$ elements in $L_t \cap ([x]-S_{a-t})$, in order to take all the numbers in $L_t$. We can do it by induction (making $t=a,a-1,\dots, 2$). First, observe that $S_{a-t} -S_0$ have only numbers divisible by $p_a, \dots, p_{t+1}$, so the numbers $2p_t , 3p_t , \dots , (p_t-1)p_t, (p_t+1)p_t$ aren't in $S_{a-t} -S_0$, and clearly they aren't on $S_0$, so they aren't on $S_{a-t}$. Also, for $p_t$ odd, they aren't in $L_t$. So, because $ L_t \subset \{ p_t, 2p_t, \dots \}$ and $\{ p_t, 2p_t, \dots \} - L_t$ has at least $p_t-1 \ge r_t$ elements, $L_t$ has at most $p_t.k_t$ elements, as we whised. Observe that, for $p_1=2$, this can't be truth. Because of that, we have that $S_a$ can be $[n]$ or $[n]- \{ 2 \}$, since we took the numbers in a decreasing order. OBS: I've added this on my preceding post!

This problem is beautiful but I think the statement is pretty awful. I would have liked something like this a lot more Given an integer $n \ge 36$, let $\mathcal{K} = \{1, 2, ... n\}$. A function $f$ is given such that $f : \mathcal{K} \mapsto \mathcal{K}$ that satisfices: \[f^{f(k)}(k) = k \]for each $k \in \mathcal{K}$. What's the minimum number of fixed points $f$ can have? Anyway here's my solution in spanish, kinda lazy to translate from my notes, maybe I'll later: