NF杯2024(K)

　まず，以下を示す．

補題 1． 正の整数 $x, y$ が $x^y = y^x$ を満たすならば， $(x,y) = (k,k), (2,4), (4,2)$ である $(k$ は正の整数$)$．

証明

　$2\leq x \lt y$ であるような解が $x = 2, y=4$ に限ることを示せばよい．有理数 $a\gt 1$によって $y = ax$ と置くと $(x^{a})^{x} = (ax)^{x}$となるので，これを解くと $x = a^{\frac{1}{a-1}}$ を得る．既約分数表示 $a = \frac{p}{q}$ を取ると $$x = a^{\frac{1}{a-1}} = \left(\dfrac{p}{q} \right)^{\frac{q}{p-q}}$$ であり，これが整数となる必要がある．特に $x^{p-q} = \frac{p^q}{q^q}$ が整数だから，$q^q = 1$の必要がある．よって $q=1$で，$p=2$ なら $x=2, y=px = 4$が得られる．$p\geq 3$ の場合，$p = x^{p-1} \geq 2^{p-1}$ という不等式に反するので解なし．よって $x=2, y=4$ に限られ，$y\lt x$ の場合も考えることで補題の主張を得る．(証明終)

　条件式で $X, Y$ を入れ替えることで，$f(X)^{f(Y)} = f(Y)^{f(X)}$ を得る．よって任意の $X, Y$ に対して，組 $(f(X), f(Y))$ は次の集合 $S$ に属す．

$$S \coloneqq \{ (2,4), (4,2), (1,1), (2,2), \dots , (2024, 2024) \}$$

$U = \{ 1,2,\dots, 2024 \}$とおき，$(f(U), f(\varnothing))$ で場合分けを行う．

　$(f(U), f(\varnothing)) = (k,k)$ の場合，すべての $X\subset U$ で $f(X) = k$ である．実際，任意の$X$に対して$Y$を補集合 $X \setminus{U}$とすれば $$f(X)^{f(Y)} = f(U)^{f(\varnothing)} = k^{k}$$ を得るが，$k^k \neq 16$ に注意すれば， $(f(X), f(Y)) = (k,k)$ とならねばならない．そして任意の $X\subset U$ に対して $f(X) = k$ である関数 $f$ は明らかに条件を満たす．この場合，$k$ の 選択に応じて $2024$ 個の関数 $f$ を得る．

　$(f(U),f(\varnothing)) = (4,2)$ の場合を考える ($(2,4)$ の場合も同様に議論できる)．この場合，次が成り立つ．

補題 2． $f(U) = 4, f(\varnothing) = 2$ を仮定する．このとき，任意の $X\subset U$に対して $f(X) \in \{ 2,4 \}$ であり，次が成り立つ：

1. $f(X) = 2$ ならば $f(U-X) = 4$．
2. $f(X) = f(Y)$ ならば $f(X) = f(Y) = f(X\cup Y) = f(X\cap Y)$

証明

　$f(X)^{f(U-X)} = f(U)^{f(\varnothing)} = 16$ であり，$(f(X), f(U-X)) \in S$ に注意すれば $f(X)\in { 2,4 }$ および主張1. が従う． 主張2. は $f(X) = f(Y) = 2$ の場合は $$f(X\cup Y)^{f(X\cap Y)} = 2^2 = 4$$ となるような $(f(X\cup Y), f(X\cap Y)) \in S$ が $(2,2)$ に限られることから従う．$f(X) = f(Y) = 4$ の場合も同様である．

　主張2. より $f(X) = f(Y) = 4$ ならば $f(X\cap Y) = 4$ なので，特に $X\cap Y \neq \varnothing$ である．$X, Y$ が $1$ 点集合のときを考えれば，これは $f(\{ i \}) = 4$ であるような $i$ が高々 $1$ 個であることを意味する．

Case 1. すべての $i$ で $f(\{ i \}) = 2$ である場合．

　補題2. の主張2. を繰り返し用いることで $f(U) = f(\{ 1 \} \cup \dots \cup \{ 2024 \}) = 2$ が得られるので矛盾．

Case 2. ある一つの $i$ で $f(\{ i \}) = 4$ である場合．

　$i=1$ の場合を考える (他の $i$ でも同様)． $2\leq j\leq 2024$ を満たす整数 $j$ について $f(\{ j \}) = 2$ なので，補題2. の主張1, 2. より $\{ 2,3,\dots, 2024 \} = U \setminus{\{ 1 \}}$ の任意の部分集合 $X$ に対して $f(X) = 2, ~ f(U-X) = 4$ が従う．$U-X$ は $1$ を含む $U$ の部分集合全体を走ることから，$1\in Y$ ならば $f(Y) = 4$ となる．これによりすべての部分集合に対する $f$ の値が定まる．

このように構成された関数が条件を満たすことの確認．

　逆に，ある $i \in \{1, 2, \ldots, 2024 \}$ によって $$f(X) = \begin{cases} 2 \quad (i\notin X) \\ 4\quad (i\in X) \end{cases}$$ と与えられる関数 $f$ が問題の条件を満たすことを示す．実際，任意の $X,Y \subset U$ に対し，

• $i\notin X, Y$ ならば， $i\notin X\cup Y, X\cap Y$ だから $f(X)^{f(Y)} = 2^2 = f(X\cup Y)^{f(X\cap Y)}$，
• $i\in X, Y$ ならば， $i\in X\cup Y, X\cap Y$だから $f(X)^{f(Y)} = 4^4 = f(X\cup Y)^{f(X\cap Y)}$，
• $i\in X, i\notin Y$ ならば(逆の場合も同様)， $i\in X\cup Y$, $i\notin X\cap Y$だから $f(X)^{f(Y)} = 4^2 = f(X\cup Y)^{f(X\cap Y)}$．

　よって $1\leq i\leq 2024$ に対し，問題の条件と $(f(U), f(\varnothing)) = (4,2)$ を満たす関数が一つ定まるので，$(2,4)$の場合も考慮して $4048$ 個の関数 $f$ を得る．

　以上より，求める個数は $2024 + 4048 = \textbf{6072}$ 個．