どちゃ楽 Q.82 「部分集合族が定義域の関数方程式」
Q.82 ☆12 [2015春合宿]
関数$f$は集合$S=\{1,2,3,\cdot n\}$の部分集合に対して定義され, $1$以上$2^{n}$以下の整数値を取る。このような$f$であって,以下の3つの条件を満たすような$f$はいくつ存在するか。ただし$\varnothing$は空集合を表す。
( i ) 任意の$S$の部分集合$X,Y$に対して,$f(X)+f(Y)\ge f(X\cup Y)+f(X\cap Y)$
( ii ) $X\neq Y$ ならば $f(X)\neq f(Y)$
( iii ) $ f(\varnothing ) =2^{n} $
この問題のツイート:
今回はゆっくり行きましょう。かなり長いので覚悟してください
まず春合宿とは日本数学オリンピックにおいて本選の次のものを指します。IMO日本代表選手最終選抜試験って感じで何問か出されるようで,今回の問題はそのうちの1問です。（実際に行ったことが無いのでよく知りませんが、どこか外国の数オリから取っている問題なのかもしれません。）それでは解答に入ります。
手始めに$X,Y$をいろいろ具体的に代入して考えてみるのが関数方程式の初手ですが,この問題では $X\subset Y$ のときに代入すると自明な不等式になってしまいます。（$X\cup Y=Y, X\cap Y=X$だから）それ以外の代入の仕方を見つけてみます。補集合とか… すると,次の 補題 1. を示すことができます。
( $S$を全体集合として ( i ) にて$Y=\overline{X}$ とします。)
補題 1. $f(X)+f(\overline{X})=2^{n}+1$ である。
証明. ( i ) にて$Y=\overline{X}$とすると,$X\cup \overline{X}=S$, $X\cap \overline{X}=\varnothing$ より
$f(X)+f(\overline{X})\ge f(S)+f(\varnothing ) = f(S)+ 2^{n} \, \tag{1}$
$S$のすべての部分集合$X$について,$(1)$の総和を取ると,
$\displaystyle\sum_{X\subset S}\left( f(X)+f(\overline{X})\right) \ge \displaystyle\sum_{X\subset S}\left( f(S)+2^{n} \right) \tag{2}$
$(2)$の左辺について,( ii )より$f$は単射であり,$X$が$S$の部分集合全体($2^{n}$個存在する)を動くとき,$f(X), f(\overline{X})$ は$1$以上$2^{n}$以下の整数全体を動く。よって,
$\displaystyle\sum_{X\subset S}\left(f(X)+f(\overline{X})\right)=2\displaystyle\sum_{k=1}^{2^{n}} k = 2^{n}(2^{n}+1)$
となる。$(2)$の右辺について,$f(S)+2^{n}$が$2^{n}$回だけ足されるから
$\displaystyle\sum_{X\subset S}\left( f(S)+2^{n} \right)=2^{n}\left(f(S)+2^{n}\right)$
となる。以上より,$(2)$は
$2^{n}(2^{n}+1)\ge 2^{n}(f(S)+2^{n})$
$\Leftrightarrow 1\ge f(S)$
となり,$1\le f(S)$であるから $f(S)=1$ 更にこのとき,総和の不等式において等号が成立していることから,各$X$に対して$(1)$の不等式も等号が成り立っていなければならない。
従って $f(X)+f(\overline{X})=1+2^{n}$ を得る。(証明終)
$f(X)$が分かれば自動的に $f(\overline{X})$ も分かることが示されました。新しいことが分かったので,もう一度 ( i )の代入操作に戻ってみましょう。すると次の 補題 2. が示されます。
補題 2. 任意の$S$の部分集合$X,Y$に対して,$f(X)+f(Y)=f(X\cup Y)+f(X\cap Y)$
証明. $N=2^{n}+1$ とおく。( i )にて $X,Y$をそれぞれ$\overline{X}, \overline{Y}$ に変え,
$f(\overline{X})+f(\overline{Y})\ge f(\overline{X}\cup \overline{Y})+f(\overline{X}\cap \overline{Y})\,\tag{3}$
補題 1.を用いると $f(\overline{X})+f(\overline{Y})=(N-f(X))+(N-f(Y))$
De Morgan の法則より
$f(\overline{X}\cup \overline{Y})+f(\overline{X}\cap \overline{Y})=f(\overline{X\cap Y})+f(\overline{X\cup Y}) = (N-f(X\cap Y))+(N-f(X\cup Y)) $
以上を$(3)$に代入して整理すれば
$f(X)+f(Y)\le f(X\cup Y)+f(X\cap Y)$
となるから,( i )の等号が常に成り立つ。(証明終)
実は( i )の等号だけが成り立っていたんですね。これで式がとても扱いやすくなりました。しかし次はどう代入しましょうか。いま値が判明しているのは$f(S),f(\varnothing)$ のみですから,なんとかそれらを用いつつ代入させることを考えます。また,常に$1\le f(X)\le 2^{n}$ですから,この等式の左辺または右辺を極端に小さいか,大きい値になるように代入すれば,他方の辺の値も有限個のケースに帰着できると考えられます。(ii)より$f$は全単射ですから, $f(X)=i$ ($i=1,2,\cdots 2^{n}$) となる $ X $ がただひとつ存在します。その$ X $を$S_{i}$と表すことにしてよいです。また,簡単のため $S_{2^{n}+1-i}=T_{i} $ とします。$T_{2}$について何か分かったりしないでしょうか。以下のように直和分割を用いて考えてみます。すなわち, $ X\cup Y=T_{2} $ でかつ $ X\cap Y=\varnothing $ となるような$ X,Y $を取ります。このとき与式に代入すれば…
$f(X)+f(Y)=f(T_2)+f(\varnothing )=2^{n+1}-1$
右辺が大きいため$f(X),f(Y)$の取る値はかなり限られます。実際, $(X,Y)=(T_1,T_2)$ とその並び替えしかありません。ところで$T_1=\varnothing$ でした。すなわち,$T_2$のいかなる2つの集合による$T_2$の直和分割に対しても, 必ず片方は空集合, もう片方は$T_2$そのものになってしまうことが必要であるという。$T_2\neq \varnothing$ ですから, ここから帰結されることは $T_2$の元の個数は1であるということてす。 実験に実験を重ねると, 次が成り立つのではと予想されます。次の形の補題で示してみます。
補題3. $ T_{2^{k}+1} $ ($ k=0,1,2,\cdots,n-1 $) の元の個数は1であることが必要である。
(証明) $i$をある一つの $0\le i\le n-2$ を満たす整数とする。 $T_{2^{k}+1}$ ($ k=0,1,\cdots, i $) の元の個数が1であると仮定する。まず目標は次の2段階に分かれる。
(1) $1\le m\le 2^{i+1}$ なる整数$ m $ について $T_{m} $ は $ T_{2}, T_{3}, T_{5},\cdots ,T_{2^{i}+1} $ らの和集合で表せる。
(2) $T_{2^{i+1}+1}$ の元の個数は1である。
(1) を示す。仮定より$ T_2, T_3, T_5,\cdots ,T_{2^{i}+1} $ は元を1つしか持たない集合であるため, どの2つについても共通部分は空集合となることに注意せよ。
まず $0\le m - 1\le 2^{i+1}-1$ より, 集合 $ \left\{0,1,2,\cdots, i \right\}$ の部分集合$U_{m}$がただ一つ存在して
$ m - 1=\displaystyle\sum_{t\in U_m}2^{t} $ のように2進展開される。
集合 $\displaystyle\bigcup_{t\in U_m} T_{2^{t} +1} $ を $V$ とおく。
$U_{m}=\left\{ a_1,a_2,\cdots, a_j \right\}$ とし, $f(X\cup Y)=f(X)+f(Y)-f(X\cap Y)$ を数回用いて $f(V)$ が以下のようにして求まる。
$f(V)=f(\displaystyle\bigcup_{t\in U_m - \{a_1\}} T_{2^{t} +1}) + f(T_{2^{a_1}+1}) - f(\varnothing)$
$=f(\displaystyle\bigcup_{t\in U_m - \{a_1,a_2\}} T_{2^{t} +1}) + f(T_{2^{a_1}+1}) + f(T_{2^{a_2}+1}) - 2f(\varnothing)$
$\cdots$
$ = (\displaystyle\sum_{t\in U_{m}} f(T_{2^{t}+1}) ) - (j-1)f(\varnothing) = \displaystyle\sum_{t\in U_{m}}( f(T_{2^{t}+1}) - f(\varnothing) ) + f(\varnothing) = 2^{n} -\displaystyle\sum_{t\in U_{m}} 2^{t} = 2^{n}+1-m = f(T_{m})$
従って $V=\displaystyle\bigcup_{t\in U_m} T_{2^{t} +1}=T_{m}$ となり, 和集合の形で書けることが分かったから (1)は示された。なお, $ m $が取れる値は $2^{i+1}$個であって, $ \left\{0,1,2,\cdots, i \right\}$ の部分集合の個数も$2^{i+1}$であるから, $ m $を動かせば$U_m $ は$ \left\{0,1,2,\cdots, i \right\}$の部分集合全体を動く。したがって, 逆に$T_{m}$ が $T_2, T_3, T_5,\cdots ,T_{2^{i}+1}$ らの和集合で表せるならば, $ m\le 2^{i+1}$ である。
このことに注意して (2) を示そう。
$X\cup Y=T_{2^{i+1}+1}$, $X\cap Y=\varnothing$ なる$X,Y$ を取って代入すると
$f(X)+f(Y)=2^{n+1}-2^{i+1}$
これらから $X,Y$の組としてありうるものは
$(X,Y)=(T_1,T_{2^{i+1}+1}), (T_2,T_{2^{i+1}}), \cdots, (T_{2^{i+1}+1},T_{1}) $ ですべてであるが, これらのうち最初と最後以外の組はすべて不適である。
なぜならば, それらの組であるとき $f(X),f(Y)\le 2^{i+1} $ であるから$X,Y$はともに $T_2, T_3, T_5,\cdots ,T_{2^{i}+1}$ らの和集合 として表せる。このとき $X\cup Y=T_{2^{i+1}+1}$もそのような和集合の形として表せるが, これでは$2^{i+1}+1\le 2^{i+1}$ が導かれるため不適。よって最初と最後以外の組である必要があり, $T_{2}$の場合と同様に $T_{2^{i+1}+1}$ は元を1つ持つ集合でなければならない。よって(2)が示された。
$T_2=T_{2^{0}+1}$ の元が1つであることと帰納法の仮定および(2)より, 補題3. が示された。 (証明終)
補題3.(1)はかなり重要です。ここから$i=n-2$とすれば $1\le m\le 2^{n-1}$ なる整数$ m $ について $T_m$ は $T_2, T_3, T_5,\cdots ,T_{2^{n-2}+1}$ らの和集合で表せると言えます。つまり,$T_2, T_3, T_5,\cdots ,T_{2^{n-2}+1}$ として要素数1の部分集合を割り当てれば,$T_{m} $もすべて決定します。（証明を見ると $ m - 1 $ の2進展開と$T_2,T_3,T_5,\cdots,T_{2^{i}+1}$のみが$T_{m}$の決定要因でした）(1)の方法と全く同様にして$T_2, T_3, T_5,\cdots ,T_{2^{n-1}+1}らから T_1,T_2,T_3,\cdots,T_{2^{n}}$ まで決定することが分かるから,$T_2,T_3,T_5,\cdots,T_{2^{n-1}+1}$ に要素数1の部分集合を割りあてる場合の数は$n!$ 通りあることから,そのような$n!$個の$f$が必要条件であります。
さて,このような$f$が元の条件を満たしていることを確認します。（十分性）
$X=T_x$, $Y=T_y$ とし, $\{0,1,\cdots,n-1\}$ の部分集合$U_x, U_y$ を取って $x-1=\displaystyle\sum_{t\in U_x}2^{t}$, $y-1=\displaystyle\sum_{t\in U_y}2\ ^{t}$ とする。
そして, $V_x=\displaystyle\bigcup_{t\in U_x}T_{2^{t}+1}$, $V_y=\displaystyle\bigcup_{t\in U_y}T_{2^{t}+1}$ と置くと, 補題3.(1) の計算と同じ方法で
$f(V_x)=2^{n}+1-x=f(T_x)$ より $T_x=V_x$ 同様に $T_y=V_y$
$X=V_x, Y=V_y$ だから
$X\cup Y=\displaystyle\bigcup_{t\in U_{x}\cup U_{y}}T_{2^{t}+1}$
$X\cap Y=\displaystyle\bigcap_{t\in U_{x}\cap U_y}T_{2^{t}+1}$
が成り立つ。($\cap$ のほうは$T_{2^{t}+1}$ が要素数1の集合であるからこそ成り立つ式である)
よって $f(X\cup Y)=2^{n}-\displaystyle\sum_{t\in U_{x}\cup U_{y}}2^{t}$
$f(X\cap Y)=2^{n}-\displaystyle\sum_{t\in U_{x}\cap U_{y}}2^{t}$
これらを元の関数方程式に代入して整理すれば
$f(X)+f(Y)\ge f(X\cup Y)+f(X\cap Y)$
↓
$(x-1)+(y-1)\le\displaystyle\sum_{t\in U_{x}\cup U_{y}}2^{t}+\displaystyle\sum_{t\in U_{x}\cap U_{y}}2^{t}$
左辺は $\displaystyle\sum_{t\in U_x}2^{t} + \displaystyle\sum_{t\in U_y}2^{t}$ に等しいからこの式は包除原理から明らかである。よって 必要条件であった$f$はいずれも条件をすべて満たす。
以上より, 答えは $n!$ 個である。
ひとこと
$T_m $ の元の個数は$m-1$の2進表示の1の個数とも見れたり、いろいろ2進数に絡んでくるところがあるようですね。 自分の過去の解法によると 補題2 を使わない証明でも解くことができます。(とんでもないほど複雑ですが） 超ムズかった… 高2の頃にこの問題に出会いましたが、自力で解き切るまで4ヶ月は掛かったことを覚えています。一歩ずつ解決に近づいていく体験ができた思い出の一問でした。
