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

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

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

$c=0$の場合は上で述べた通りである．$c=-1$の場合，単位正方形を$k\times k$に等分し，そのうち一つを取り除くと一辺の長さの総和は$k-(1/k)$となるのでよい．
$c\ge 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\le -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)\ge k$が成り立つことはすでに見たので，$g(k^2+1)\le 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\le x\le 1,0\le y\le 1$となるような座標を取る.$0\le a<1/k$に対し，$k$本の直線
$$L_j(a):x=a+(j/k)(j=0,1,\dots ,k-1)$$
を考える．
直線$L_j(a)(k=3)$
ここで関数$m_{ij}(a)$を
$$m_{ij}(a)=\{\begin{array}{ll}1& (S_i\cap L_j(a)\ne \mathrm{\varnothing })\\ 0& (S_i\cap L_j(a)=\mathrm{\varnothing })\end{array}$$
により定めると
$$\begin{array}{rl}{\int }_{a=0}^{1/k}(\sum _{i=1}^{k^2+1}\sum _{j=0}^{k-1}{m}_{ij}(a))da& =\sum _{i=1}^{k^2+1}(\sum _{j=0}^{k-1}{\int }_{a=0}^{1/k}{m}_{ij}(a)da)\\ & =\sum _{i=1}^{k^2+1}{d}_i>k\end{array}$$
となるため，左辺の被積分関数の値が$k^2$よりも真に大きくなるような$a$が$0\le 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\ge k^2+1\cdots (1)$$
である．次に集合$\{1,2,\dots ,k^2+1\}$を三つの部分に分ける：
$$\begin{array}{r}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\ge 2\}.\end{array}$$
すると不等式(1)は
$$\mathrm{\#}B+\sum _{i\in C}{m}_i\ge \mathrm{\#}A+\mathrm{\#}B+\mathrm{\#}C$$
と書き換えられるので，移項すると
$$\mathrm{\#}A\le \sum _{i\in C}(m_i-1)\cdots (2)$$
となる．ここで各$i$に対して$d_i$を評価する．

• $i\in A$のとき，$S_i$は直線$L_0,L_1,\dots ,L_{k-1}$のいずれとも交わらないので$d_i\le 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\ge {\displaystyle \frac{m_i-1}{k}},m_i{d}_i=\sum _{j=0}^{k-1}\mu (S_i\cap L_j)$$
  であり，これらと$m_i\ge 2$を合わせると
  $$d_i\le m_i{d}_i-d_i\le \sum _{j=0}^{k-1}\mu (S_i\cap L_j)-{\displaystyle \frac{m_i-1}{k}}$$
  と評価できる．

以上の評価を合わせると
$$\begin{array}{rl}\sum _{i=1}^{k^2+1}{d}_i& \le {\displaystyle \frac{\mathrm{\#}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}{\displaystyle \frac{m_i-1}{k}}\\ & ={\displaystyle \frac{1}{k}}(\mathrm{\#}A-\sum _{i\in C}(m_i-1))+\sum _{i=1}^{k^2+1}\sum _{j=0}^{k-1}\mu (S_i\cap L_j)\\ & \le k\end{array}$$
となる（最後の行で不等式(2)を用いた）．これは$\sum _{i=1}^{k^2+1}{d}_i>k$という仮定に反している．以上で$g(k^2+1)\le k$が示された．