大学数学基礎解説

板を固定できる釘の本数を求めよう！

離散数学,幾何

169

今回考えるのは次の問題です。

平面上の板 $D$ の周りに釘を刺して動かないようにする。どんな板も固定できるようにするには最低で何本の釘が必要か。

直感的には $3$ 本あればほとんどの板は固定できそうな気がしますが、これを数学的に証明したいと思います。

問題の定式化

まずは、「固定する」の部分を正確に定義しましょう

$D, X \subset R^{2}$ とする。 $D$ は空でない領域(連結な開集合)であるとする。 $X$ が $D$ を固定するとは、次の二つの条件を満たすことである。

$D \cap X = \emptyset$
任意の単位ベクトル $x$ に対して、ある $ε > 0$ が存在して、 $0 < a < ε$ ならば $(D + a x) \cap X \neq \emptyset$

$D$ を固定する $n$ 点集合が存在するとき、 $D$ は $n$ 点で固定できるという。

$D$ が板、 $X$ が釘を刺す位置を表すと思ってください。1つめの条件は、板自体に釘を刺してはいけないことを意味します。2つめの条件は、どんな方向に $D$ を平行移動しても、その距離が十分短ければ釘と重なってしまうという意味です。
なお、 $D + a := {x + a | x \in D}$ です。また、この定義では $D \cap X = \emptyset$ としていますが、 $X$ の元は $D$ の境界 $\partial D$ に含まれていると考えてしまっても問題ありません。

領域とは、連結な開集合のことです。

連結とは、簡単に言えばつながっている（任意の二点が曲線で結べる）ということだと思って差し支えないです。
開集合とは、境界を含まない集合のことです。

正確な定義は位相空間論を学んでください。

今回の目標は、次の定理を証明することです

$D$ が有界領域で、その境界 $\partial D$ が区分的になめらか単純閉曲線のとき、 $D$ は $4$ 点で固定できる。特に $D$ が平行四辺形でないとき、 $3$ 点で固定できる。

区分的になめらかとは、有限個の点を除いて $C^{1}$ 級であることと定義します。これは、「有限個の点を除けばどこでも接線が引けるし、点を動かすとその接線が連続的に変化するよ」ということです。いずれにせよ、よほど変な曲線でない限りこの性質を満たすので気にする必要はないです。

支配する方向

まずは準備として、 $X$ の各点が $D$ を固定するのにどれだけ寄与するかという概念を定式化してみましょう。

以後、

$S^{1} := {x \in R^{2} | | x | = 1}$

とします。

$D, X \subset R^{2}$ 、 $D$ を空でない領域とする。 $X \cap D = \emptyset$ とする。 $X$ が支配する方向 ${Fix}_{D} (X)$ とは、

${Fix}_{D} (X) = {x \in S^{1} | \exists ε > 0, 0 < \forall a < ε, (D + a x) \cap X = \emptyset}$

$x \in R^{2} ∖ D$ に対し、 ${Fix}_{D} (x) := {Fix}_{D} ({x})$ とし、これを $x$ が支配する方向という。

すなわち、 $X$ の位置に釘を打った場合、 $D$ を平行移動すると釘と重なってしまう「方向」の集合を ${Fix}_{D} (X)$ と書きます。定義から明らかなように、次の命題が示せます。

$D, X, Y \subset R^{2}$ 、 $D$ を空でない領域、 $X \cap D = Y \cap D = \emptyset$ とする。

$X$ が $D$ を固定する $⟺ {Fix}_{D} (X) = S^{1}$
${Fix}_{D} (X \cup Y) = {Fix}_{D} (X) \cup {Fix}_{D} (Y)$

いずれも定義から従う。

$X$ が $D$ を固定するための必要十分条件は、

$⋃_{x \in X} {Fix}_{D} (x) = S^{1}$

である。

この系より、あとは点 $x \in R^{2}$ に対する ${Fix}_{D} (x)$ の求め方を考えればいいことがわかります。ここで、簡単な記号を定義します。

$a \in R^{2} ∖ {0}$ に対し、

$H (a) := {x \in S^{1} | a \cdot x > 0}$

を $a$ を中点とする半円という。また、

$\overset{―}{H (a)} := {x \in S^{1} | a \cdot x \geq 0}$

とする。

以後、 $D \subset R^{2}$ は有界領域で、その境界 $\partial D$ が区分的になめらか単純閉曲線であるとします。

$x \in \partial D$ であり、 $\partial D$ は $x$ でなめらかであるとする。 $x$ での $\partial D$ の外向き単位法線ベクトルを $n_{x}$ とすると、

$H (n_{x}) \subseteq {Fix}_{D} (x) \subseteq \overset{―}{H (n_{x})}$

である。特に $x$ の近傍で $\partial D$ が線分である場合は、

${Fix}_{D} (x) = H (n_{x})$

直観的にも明らかでしょう。証明は煩雑に見えますが、やっていることは単純です。

$D$ に合同変換を施し、 $x$ が原点で、接線が $x$ 軸、単位法線ベクトルが $n = (0, 1)$ となるようにする。このとき陰関数定理から、ある $δ > 0$ が存在し、原点を中心とする開円板 $U_{δ}$ に対し、 $\partial D \cap U_{δ}$ の点は $C^{1}$ 級の関数 $f$ を用いて、 $(x, f (x))$ と表せる。また、

$D \cap U_{δ} = {(x, y) \in U_{δ} | y < f (x)}$

である。まずは上半円 $H (n) = {(s, t) \in S^{1} | t > 0}$ の点が原点によって固定されることを見よう。 $(s, t) \in H (n)$ を任意に取る。ロピタルの定理より、

$lim_{a \to + 0} \frac{f (- s a) + t a}{a} = lim_{a \to + 0} \frac{- s f^{'} (- s a) + t}{1} = - s f^{'} (0) + t = t > 0$

より、十分小さい $ε > 0$ をとれば、任意の $0 < a < ε$ なる $a$ に対して、 $f (- s a) + t a > 0$ である。よって、

$D \cap U_{δ} + (s a, t a) \supset {(x, y) \in U_{δ - a} | y < f (x - s a) + t a} ∋ (0, 0)$

であるから、 $H (n) \subseteq {Fix}_{D} (0)$ である。次に、下半円 $S^{1} ∖ \overset{―}{H (n)} = H (- n) = {(s, t) \in S^{1} | t < 0}$ の点が原点によって固定されないことを見よう。 $(s, t) \in H (- n)$ を任意に取り、 $ε > 0$ も任意にとる。このとき、

$lim_{a \to + 0} \frac{f (- s a) + t a}{a} = t < 0$

より、ある $0 < a < \min {δ, ε}$ が存在し、 $f (- s a) + t a < 0$ である。よって、

$(D + (s a, t a)) \cap U_{δ - a} = {(x, y) \in U_{δ - a} | y < f (x - s a) + t a} ∌ (0, 0)$

であるから、 $S^{1} ∖ \overset{―}{H (n)} \subseteq S^{1} ∖ {Fix}_{D} (0) ∴ {Fix}_{D} (0) \subseteq \overset{―}{H (n)}$

次に原点付近で $D$ が線分である、すなわち $f (x) = 0 ((x, f (x)) \in U_{δ})$ である場合、 $\overset{―}{H (n)} ∖ H (n) = {(\pm 1, 0)}$ の点が原点によって固定されないことを見よう。 $ε > 0$ を任意にとる。 $0 < a < min {δ, ε}$ なる $a$ をとれば、

$(D + (\pm a, 0)) \cap U_{δ - a} = {(x, y) \in U_{δ - a} | y < f (x \mp a)} = {(x, y) \in U_{δ - a} | y < 0} ∌ (0, 0)$
となるので、固定されない。

大まかに言って、 $x$ の近傍で $\partial D$ が凸（内側に曲がっている）とき ${Fix}_{D} (x) = H (n_{x})$ となり、凹（外側に曲がっている）とき ${Fix}_{D} (x) = \overset{―}{H (n_{x})}$ になります。

多角形の場合

まずは $D$ が多角形である場合を考えましょう。以降、

$[n] := {1, 2, 3, \dots, n}$

とします。突然ですが、次のような定義をします。

円周上の点の集合 $A = {a_{1}, a_{2}, \dots, a_{n}} \subset S^{1}$ が $D \subseteq S^{1}$ を覆うとは、
$D \subset ⋃_{i = 1}^{n} H (a_{i})$
を満たすことである。これは次のように言い換えることもできる。
任意の $x \in D$ に対して、ある $i \in [n]$ が存在して、 $a_{i} \cdot x > 0$ が成り立つ。
また、 $x \in S^{1}$ に対して、 $A$ が ${x}$ を覆うことを単に $A$ が $x$ を覆うという。
$A = {a_{1}, a_{2}, \dots, a_{n}} \subset S^{1}$ が $D \subseteq S^{1}$ を効果的に覆うとは、 $A$ が $D$ を覆い、 $A$ のどの真部分集合も $D$ を覆わないことである。

$A$ が $D \subseteq S^{1}$ を覆うとき、その部分集合 $B \subset A$ で $D$ を効果的に覆うものが存在する。

$A$ の元の個数 $n$ についての数学的帰納法で示す。 $D$ を覆うことができる最小の点の個数を $n_{0}$ とする。

$n = n_{0}$ のとき、

$A$ が $D$ を覆うならば、効果的である。実際、これが効果的でないとすると、この真部分集合で $D$ を覆うものがあるが、これは $n_{0}$ が $D$ を覆うことができる最小の点の個数であることに矛盾する。

$n > n_{0}$ のとき、

$A$ が $D$ を効果的に覆う場合は明らか。そうでないとき、真部分集合 $A^{'} ⊊ A$ で $D$ を覆うものがあるが、この元の個数は $n$ より小さいから、帰納法の仮定により $D$ を効果的に覆う部分集合 $B \subseteq A^{'}$ がとれる。

円周上の $n$ 点集合 $A = {a_{1}, a_{2}, \dots, a_{n}} \subset S^{1}$ は、この順で反時計回りに並んでおり、 $S^{1}$ を覆うとする。このとき、次が成り立つ。

ある $i_{1}, i_{2}, i_{3}, i_{4} \in [n]$ が存在して、 ${a_{i_{1}}, a_{i_{2}}, a_{i_{3}}, a_{i_{4}}}$ が $S^{1}$ を覆う。
$a_{1}, a_{2}, \dots, a_{n}$ はこの条件に加え、次の例外を満たさないとする。
$n = 4$ かつ $a_{1} = - a_{3}, a_{2} = - a_{4}$
このとき、ある $i_{1}, i_{2}, i_{3} \in [n]$ が存在して、 ${a_{i_{1}}, a_{i_{2}}, a_{i_{3}}}$ が $S^{1}$ を覆う。

ここで何がしたいか分かった人はすごいです。とりあえず証明します。

$A$ の部分集合 $B = {b_{1}, b_{2}, \dots, b_{k}}$ であって、 $S^{1}$ を効果的に覆うものをとる。 $b_{1}, b_{2}, \dots, b_{k}$ は相異なり、この順で反時計周りに並んでいるものとする。 $k \leq 4$ であることを示せば十分である。便宜上 $b_{0} := b_{k}, b_{k + 1} := b_{1}$ とし、 $i \in [k]$ に対して、 $b_{i}$ と $b_{i + 1}$ のなす角を $θ_{i}$ とする。便宜上 $θ_{0} := θ_{k}$ としよう。まず、円周 $S^{1}$ が $b_{1}, b_{2}, \dots, b_{k}$ によって分割されているので、
$θ_{1} + θ_{2} + \dots + θ_{k} = 2 π$
である。また、任意の $i \in [k]$ に対して、 $θ_{i - 1} + θ_{i} \geq π$ である。実際、 $θ_{i - 1} + θ_{i} < π$ であるとすると、
$H (b_{i}) \subset H (b_{i - 1}) \cup H (b_{i + 1})$
となって、 $B ∖ {b_{i}}$ が $S^{1}$ を覆うので、 $B$ が $S^{1}$ を効果的に覆うことに矛盾する。
したがって、 $θ_{i - 1} + θ_{i} \geq π$ を $i = 1, 2, \dots, k$ について足すと、
$4 π = 2 (θ_{1} + θ_{2} + \dots + θ_{k}) \geq k π$
なので、 $k \leq 4$ を得る。
(1)の不等式の等号成立条件を考えると、 $k = 4$ かつ $θ_{1} + θ_{2} = θ_{2} + θ_{3} = θ_{3} + θ_{4} = θ_{4} + θ_{1} = π$ 、すなわち、
$k = 4$ かつ $b_{1} = - b_{3}, b_{2} = - b_{4}$
である。すなわちこれ以外の場合なら $3$ 点で覆える。よって $A = B$ の場合は例外に含まれるので、 $A ⊋ B$ の場合のみ考えればよい。この場合も、 $A ∖ B$ の元 $c$ をとり、 $c$ が孤 $b_{i} b_{i + 1}$ 上にあるものとすれば、 $B^{'} := (B ∖ {b_{i}, b_{i + 1}}) \cup {c}$ とすれば $B^{'}$ が $S^{1}$ を覆う。

さて、凸多角形の固定に話を戻しましょう。

任意の多角形は $4$ 点で固定できる。また、平行四辺形を除けば $3$ 点で固定できる。

多角形の各辺の外向き法線ベクトルを、反時計周りに $a_{1}, a_{2}, \dots, a_{n}$ とする。また、各辺の中点を $x_{1}, x_{2}, \dots, x_{n}$ とする。当然すべての辺に釘を刺せば固定できるので、

$⋃_{i = 1}^{n} H (a_{i}) = ⋃_{i = 1}^{n} {Fix}_{D} (x_{i}) = S^{1}$

である。よって補題より、ある $i_{1}, i_{2}, i_{3}, i_{4} \in [n]$ が存在して、

$⋃_{k = 1}^{4} H (a_{i_{k}}) = S^{1}$

である。よって、

$⋃_{k = 1}^{4} {Fix}_{D} (a_{i_{k}}) = S^{1}$

である。よって、 $D$ は $4$ 点で固定できる。また、 $n = 4$ かつ $a_{1} = - a_{3}, a_{2} = - a_{4}$ 、すなわち $D$ が平行四辺形であるという例外を除いて、 $D$ は $3$ 点で固定できる。

一般の領域の場合

$D$ は有界領域で、その境界 $\partial D$ が区分的になめらか単純閉曲線であるとする。 $D$ は $4$ 点で固定でき、平行四辺形でなければ $3$ 点で固定できる。

まず、 $\partial D$ 上の点からなる有限集合 $V$ を、次を満たすようにとる。

$\partial D$ のなめらかではない点はすべて $V$ に含まれる。
$V$ は少なくとも $3$ つ以上の点からなる。
$V$ の点を $\partial D$ に現れる順に結んだ折れ線は多角形をなす(すなわち自己交差がない)。 $V$ はその多角形の頂点となる。
$D$ が平行四辺形でないとき、 $V$ の点を結んだ多角形も平行四辺形ではない。

$V$ の点を結んだ多角形（の内側の領域）を $D^{'}$ とする。

D^{'}

が辺上の

k

点で固定できる

⟹

D

が

k

点で固定できる

を示せばよい。 $D^{'}$ を固定する辺上の点を $x_{1}^{'}, x_{2}^{'}, \dots, x_{k}^{'}$ とし、 $x_{i}^{'}$ は辺 $u_{i} v_{i}$ 上にあるとする( $u_{i}, v_{i} \in V$ )。また、点 $x_{i}^{'}$ での $\partial D^{'}$ の外向き単位法線ベクトルを $n_{i}$ とする。曲線 $\partial D$ は $2$ 点 $u_{i}, v_{i}$ の間で滑らかであるから、コーシーの平均値の定理より、ある $x_{i} \in \partial D$ が存在して、そこでの接線が辺 $u_{i} v_{i}$ と平行になる。 $x_{i}$ での単位法線ベクトルは $n_{i}$ に等しいので、

$⋃_{i = 1}^{k} {Fix}_{D} (x_{i}) \supseteq ⋃_{i = 1}^{k} H (n_{i}) = ⋃_{i = 1}^{k} {Fix}_{D^{'}} (x_{i}^{'}) = S^{1}$

であるから、示された。

平均値の定理を使うところがポイントです。

一般化を考えてみる

ここからは、高次元の場合を考えたり、固定の定義を変えてみたりするとどうなるか見ていきます。

3次元の場合

まずはこの問題を $d$ 次元に拡張してみます。 $X$ が $D$ を固定することを次のように定義しましょう。

$D, X \subset R^{d}$ とする。 $D$ は空でない領域(連結な開集合)であるとする。 $X$ が $D$ を固定するとは、次の二つの条件を満たすことである。

$D \cap X = \emptyset$
ある $ε > 0$ が存在して、任意の $a \in R^{d}$ に対して、 $0 < | a | < ε$ ならば $(D + a) \cap X \neq \emptyset$

$D$ を固定する $n$ 点集合が存在するとき、 $D$ は $n$ 点で固定できるという。

$3$ 次元の場合すらまだ答えが出ていませんが、次のように予想しています。

任意の(3次元)凸多面体は $6$ 点で固定できる。

この問題はある程度 $2$ 次元の場合の手法が適用でき、次が成り立つことと同値になります。

$A = {a_{1}, a_{2}, \dots, a_{n}} \subset S^{2}$ が $S^{2}$ を覆うならば、ある $i_{1}, i_{2}, \dots, i_{6} \in [n]$ が存在して、 ${a_{i_{1}}, a_{i_{2}}, \dots, a_{i_{6}}}$ が $S^{2}$ を覆う。

ただし $A = {a_{1}, a_{2}, \dots, a_{n}} \subset S^{2}$ が $S^{2}$ を覆うとは、「任意の $x \in S^{2}$ に対して、ある $i \in [n]$ が存在して、 $a_{i} \cdot x > 0$ が成り立つ」ことです。なお、 $S^{2} := {x \in R^{3} | | x | = 1}$ です。

※ 追記(2025/1/11): 友人との協力もありこの予想は解決しました。機会があれば別の記事に載せようと思います。

もっといろんな移動を許そうよ

お気づきの方もいるかもしれませんが、定義1の「固定する」の定義は微妙に弱いです。定義1では、曲線をある方向に「真っ直ぐ移動させる」ことができないことを固定の定義としていましたが、曲がって動かすことも考えられます。

$D, X \subset R^{d}$ とする。 $D$ は空でない領域(連結な開集合)であるとする。 $X$ が $D$ を強い意味で固定するとは、次の二つの条件を満たすことである。

$D \cap X = \emptyset$
ある $ε > 0$ が存在して、どんな滑らかな単射曲線 $γ : [0, s] \to R^{d}$ に対しても、 $γ (0) = 0$ かつ $| γ (t) | < ε (0 \leq t \leq s)$ ならば、任意の $t \in (0, s]$ に対して $(D + γ (t)) \cap X \neq \emptyset$

$D$ は有界領域で、その境界 $\partial D$ が区分的になめらか単純閉曲線であるとする。 $D$ は $4$ 点で強い意味で固定でき、平行四辺形でなければ $3$ 点で強い意味で固定できる。

回転を許す場合

ほかにも、回転を許した移動も考えられます。

$r_{θ} = \begin{array}{r} (\begin{array}{cc} \cos θ & - \sin θ \\ \sin θ & \cos θ \end{array}) \end{array}$
とします。

$D, X \subset R^{2}$ とする。 $D$ は空でない領域(連結な開集合)であるとする。 $X$ が $D$ を回転を含めて固定するとは、次の二つの条件を満たすことである。

$D \cap X = \emptyset$

ある $ε > 0$ が存在して、どんな単射 $C^{1}$ 級写像 $γ : [0, s] \to R^{2} \times R; γ (t) = (x (t), y (t), θ (t))$ に対しても、 $γ (0) = 0$ かつ $| γ (t) | < ε (0 \leq t \leq s)$ ならば、任意の $t \in (0, s]$ に対して $r_{θ} (D + (x (t), y (t))) \cap X \neq \emptyset$