Let $n$ be a positive integer. Suppose for any $\mathcal{S} \subseteq \{1, 2, \cdots, n\}$, $f(\mathcal{S})$ is the set containing all positive integers at most $n$ that have an odd number of factors in $\mathcal{S}$. How many subsets of $\{1, 2, \cdots, n\}$ can be turned into $\{1\}$ after finitely many (possibly zero) applications of $f$?
Problem
Source: Philippine Mathematical Olympiad 2024 P4
Tags: function, combinatorics, number theory
Tintarn
20.02.2024 13:16
Just to make sure that I got the wording correctly: For $n=3$, we would have that $\{1,2,3\}$ turns into $\{1\}$ immediately (as both $2$ and $3$ have an even number of factors) while $\{1,2\}$ would turn into $\{1,3\}$ and vice versa, so that we never end up with $\{1\}$ in that case?
InternetPerson10
20.02.2024 16:25
Tintarn wrote: Just to make sure that I got the wording correctly: For $n=3$, we would have that $\{1,2,3\}$ turns into $\{1\}$ immediately (as both $2$ and $3$ have an even number of factors) while $\{1,2\}$ would turn into $\{1,3\}$ and vice versa, so that we never end up with $\{1\}$ in that case? Yes.
Tintarn
20.02.2024 16:38
First let us note that $f$ is bijective (on the power set of $\{1,2,\dots,n\}$), i.e. we can reconstruct $S$ from knowing $f(S)$.
Indeed, we can first reconstruct whether $1$ is in $S$, then which prime numbers are in $S$, then which products of two primes are in $S$ etc. since each time we already know it for all proper divisors and then by parity also for the new number itself. This proves the claim.
OK, so now we are really asked to study the length of the orbit of $\{1\}$ under $f$.
Clearly, the first iterate is $\{1,2,\dots,n\}$. The next image is all numbers with an odd number of divisors, i.e. all perfect squares.
The next image is all numbers with an odd number of square divisors, i.e. all numbers with all exponents in the prime factorization being $0,1 \pmod{4}$.
The next image is then all fourth powers.
Iterating this argument, we see that we always get some congruence condition on the exponents, namely $0 \pmod{1} \mapsto 0 \pmod{2}\mapsto 0,1 \pmod{4} \mapsto 0 \pmod{4} \mapsto 0,1,2,3 \pmod{8} \mapsto 0,2 \pmod{8} \mapsto 0,1 \pmod{8} \mapsto 0 \pmod{8} \mapsto \dots$.
Here it is clear that the pattern will be $0 \pmod{2^k}$ after $2^k$ steps (easily proved by induction).
So the length of the orbit will be $2^k$ if $2^k$ is maximal with $2^{2^k} \le n$ (so that there are $2^k$-th powers besides $1$).
Another way to write it would be as $2^{\lfloor \log_2(\log_2(n))\rfloor}$.