ここでは、厳密な証明を示します。
解法が知りたい方は、解説を先にお読みください。
また、以降は正方形の一辺の長さは \(1\) であり、タイルを \(xy\) 平面に配置するとして説明します。

あるタイルのペア \((a,b)\) が一辺を完全に共有しているとき、またその時に限り辺を張ったグラフを考えます。
このとき、グラフの各連結成分ごとに、タイルの塊をそれぞれ十分離して置いても一辺を完全に共有するペアの数は変わりません。
また、各連結成分ごとに以下の条件を満たすように平行・回転移動することができます。

• 全てのタイルの全ての角が格子点 ( \(x,y\) 座標がともに整数であるような点) に位置する。
  • \(1\) つのタイルを上記の条件を満たすように置けば、そのタイルと一辺を完全に共有するタイルも条件を満たすことが確認でき、芋づる式に上記の条件を確認できます。

こうすることで、全てのタイルの全ての角が格子点に位置するような最適解が存在することが示されました。

また、連結成分が \(2\) つ以上となる場合は、連結成分を \(2\) つ選択して片方の最右の辺の \(1\) つともう片方の最左の辺の \(1\) つとが完全に一致するように平行移動させることで一辺を完全に共有するタイルのペアが増加します。なので、最適解において \(N\) 枚のタイルが \(1\) つの連結成分を成すことも証明できました。

現在の配置について、バウンディングボックス (各辺が \(x\) 軸または \(y\) 軸に平行な矩形) を考えます。このバウンディングボックスの全ての角も格子点に位置します。
タイルの配置の方法から、少なくともこのバウンディングボックスの周長と同じだけ、各タイルの周長が空費されていることがわかります。

バウンディングボックスの面積は \(N\) 以上であるべきであり、その中で周長が最小であるもの (のうち \(1\) つ) は解説で言及した \(k \times k\) および \(k \times (k+1)\) のパターンです。
少なくとも上記のパターンの周長ぶんだけ各タイルの周長を空費する必要がありますが、解説で示したタイルの配置はこの必要最低限の空費量を実際に達成します。

よって、解説で示した解法の正当性が示されました。