正方形の充填に関するErdősの予想

単位正方形を$k\times k$に等分するとき，$k^2$個の正方形の一辺の長さの総和はちょうど$k$となるため，$f(k^2)\geq k$が成り立つ．
逆に一辺の長さが$d_1,d_2,\dots,d_{k^2}$の正方形が単位正方形の中に置けたとすると，Cauchy–Schwarzの不等式より
$$ d_1+\cdots+d_{k^2}\leq \sqrt{k^2}\sqrt{d_1^2+\cdots+d_{k^2}^2}\leq k $$
となるため$f(k^2)\leq k$が成り立つ．

単位正方形を$k\times k$に等分し，そのうち1つの正方形を取り除いて，代わりに一辺の長さが$1/(2k)$の正方形を2つ配置する．このとき$k^2+1$個の正方形の一辺の長さの総和はちょうど$k$となるため，$f(k^2+1)\geq k$が成り立つ．
$f(k^2+1)\geq k$の証明

$c=0$の場合は上で述べた通りである．$c=-1$の場合，単位正方形を$k\times k$に等分し，そのうち一つを取り除くと一辺の長さの総和は$k-(1/k)$となるのでよい．
$c\geq 1$の場合，単位正方形を$k\times k$に等分し，右下の$c\times c$の正方形を連結して$(c+1)\times (c+1)$に等分しなおす．このとき正方形の個数は$k^2-c^2+(c+1)^2=k^2+2c+1$となり，一辺の長さの総和は$k+(c/k)$となる．
$c\leq -2$の場合，単位正方形を$k\times k$に等分し，右下の$(-c)\times (-c)$の正方形を連結して$(-c-1)\times (-c-1)$に等分しなおす．このとき正方形の個数は$k^2-(-c)^2+(-c-1)^2=k^2+2c+1$となり，一辺の長さの総和は$k+(c/k)$となる．

$g(k^2+1)\geq k$が成り立つことはすでに見たので，$g(k^2+1)\leq k$を示せばよい．単位正方形の中に$k^2+1$個のまっすぐな正方形$S_1,S_2,\dots,S_{k^2+1}$が置かれており，どの2つの正方形も周以外で重なっていないとする．$S_i$の一辺の長さを$d_i$とし，$\sum_{i=1}^{k^2+1}d_i > k$と仮定して矛盾を導く．単位正方形が$0\leq x\leq 1,\ 0\leq y\leq 1$となるような座標を取る.$0\leq a<1/k$に対し，$k$本の直線
$$ L_j(a) : x=a+(j/k)\quad (j=0,1,\dots,k-1) $$
を考える．
直線$L_j(a)\ (k=3)$
ここで関数$m_{ij}(a)$を
$$ m_{ij}(a) = \begin{cases}1&(S_i\cap L_j(a)\neq\emptyset)\\0&(S_i\cap L_j(a)=\emptyset)\end{cases} $$
により定めると
\begin{align*} \int_{a=0}^{1/k}\biggl(\sum_{i=1}^{k^2+1}\sum_{j=0}^{k-1}m_{ij}(a)\biggr)da &= \sum_{i=1}^{k^2+1}\biggl(\sum_{j=0}^{k-1}\int_{a=0}^{1/k}m_{ij}(a)da\biggr)\\ &=\sum_{i=1}^{k^2+1}d_i>k \end{align*}
となるため，左辺の被積分関数の値が$k^2$よりも真に大きくなるような$a$が$0\leq a<1/k$の範囲に存在する．以下このような$a$を固定し，$L_j(a)$のことを単に$L_j$で表す．$m_i=\sum_{j=0}^{k-1}m_{ij}(a)$と定めると，$a$の取り方より
$$ \sum_{i=1}^{k^2+1}m_i \geq k^2+1\quad \cdots (1) $$
である．次に集合$\{1, 2, \dots, k^2 + 1\}$を三つの部分に分ける：
\begin{align*} A := \{i\in \{1,2,\dots,k^2+1\}\mid m_i=0\},\\ B := \{i\in \{1,2,\dots,k^2+1\}\mid m_i=1\},\\ C := \{i\in \{1,2,\dots,k^2+1\}\mid m_i\geq 2\}. \end{align*}
すると不等式(1)は
$$ \#B+\sum_{i\in C} m_i \geq \#A+\#B+\#C $$
と書き換えられるので，移項すると
$$ \#A \leq \sum_{i\in C} (m_i-1)\quad\cdots (2) $$
となる．ここで各$i$に対して$d_i$を評価する．

• $i\in A$のとき，$S_i$は直線$L_0,L_1,\dots,L_{k-1}$のいずれとも交わらないので$d_i\leq 1/k$となる．
• $i\in B$のとき，$S_i$は直線$L_0,L_1,\dots,L_{k-1}$のうちちょうど一つと交わるので
  $$ d_i= \sum_{j=0}^{k-1}\mu(S_i\cap L_j) $$
  である（$\mu$は線分の長さを表す）．
• $i\in C$のとき，$S_i$は直線$L_0,L_1,\dots,L_{k-1}$のうちちょうど$m_i$個と交わるので
  $$ d_i\geq \dfrac{m_i-1}{k},\quad m_id_i = \sum_{j=0}^{k-1}\mu(S_i\cap L_j) $$
  であり，これらと$m_i\geq 2$を合わせると
  $$ d_i \leq m_id_i-d_i \leq \sum_{j=0}^{k-1}\mu(S_i\cap L_j)-\dfrac{m_i-1}{k} $$
  と評価できる．

以上の評価を合わせると
\begin{align*} \sum_{i=1}^{k^2+1}d_i & \leq \dfrac{\#A}{k}+\sum_{i\in B}\sum_{j=0}^{k-1}\mu(S_i\cap L_j)+\sum_{i\in C}\sum_{j=0}^{k-1}\mu(S_i\cap L_j) - \sum_{i\in C}\dfrac{m_i-1}{k}\\ & = \dfrac{1}{k}\left(\#A-\sum_{i\in C}(m_i-1)\right)+\sum_{i=1}^{k^2+1}\sum_{j=0}^{k-1}\mu(S_i\cap L_j)\\ &\leq k \end{align*}
となる（最後の行で不等式(2)を用いた）．これは$\sum_{i=1}^{k^2+1}d_i>k$という仮定に反している．以上で$g(k^2+1)\leq k$が示された．