[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

同じ形のポリオミノを正方形に斜めに入れるパズルについて

同じ形のポリオミノを正方形の枠に入れるパズルを制作した。

このパズルは枠に対して縦横には入らず、ピースが斜めにしか入らない。

過去にも、斜めにしか入らないパズルとしてSixes And Sevens - designed by Goh Pit Khiam *1などが発表されている。

このパズルについて解説しよう。

※日本パズル協会主催の第５回パズルオーディション*2に応募したが結果は落選だった。（答えは最後に）

例題

斜めに入るとはどういうことかを説明するため、以下の例題を見てほしい。8 x 8 の正方形にサイズ10のポリオミノ（デコミノ）を4つ入れる。

答えは以下である。\(1:3:\sqrt{10}\)の三角形の傾きで、一辺が\(7.906 \approx 25 / \sqrt{10}\) の正方形に接するように入る。枠と平行に縦横には入らない。

例題のパズルの解の一意性について、少なくともポリオミノを構成する正方形が格子に沿って入るパターンに関しては上記の解しかないことをプログラムにより確認している。

まず正方形の格子の取り方について解説しよう。

 

格子の取り方

例題の8 x 8の正方形を傾けたときに有効な格子の取り方は27パターン存在する*3 。これは正方形に入るようなフリーポリオミノの中で、他のフリーポリオミノに真に含まれない（極大となっているもの）の数である。フリーポリオミノとは回転鏡像を同一視するポリオミノである。ここからは「有効な格子」と「極大のポリオミノ」をほぼ同じ意味で使う。

5x5の正方形には、3つ有効な格子の取り方が存在する


そのような極大のポリオミノの数が有限であることはすぐに分かるが、列挙するにはどうすればよいか？

実は正方形を格子に対して傾けて、平行移動して見つける方法が知られている*4。

まず傾きについてであるが、tanが有理数となるケースを考えれば十分である。以下に証明する。

逆に、ポリオミノが与えられたときに、それを含む最小の正方形を見つけることを考える。最小の正方形にポリオミノがちょうどはまるときに、ポリオミノのいくつかの頂点が正方形の周上に存在することになる。このとき正方形のある辺（もしくはその延長線）にポリオミノの頂点（もしくは格子点）が複数存在することを示す。以下、正方形の周上に存在する頂点の個数で場合分けをする。

a) 5個以上の場合

正方形の辺が4つであるので、鳩ノ巣論法より、ある辺に２つ以上頂点が存在する。

b) 0個の場合

正方形を少し縮小でき最小性に反する。

c) 1個の場合

図のように、頂点が存在する辺の垂直外向きに少し正方形を移動すれば、正方形の周上の頂点は0個になる。よって最小性に反する。

d) 2個の場合

隣り合う辺に頂点が乗る場合、それぞれの辺で1個の場合と同じように移動すれば、0個に減る。

向かい合う辺に頂点が乗る場合、図のように一方の頂点で固定し、正方形を少し回転すると1個に減る。（回転の向きは頂点の場所による）

どちらも最小性に反する。

e) 3個の場合

隣り合う3つの辺に1つずつ頂点が存在するとしてよい。3つのうちの真ん中の辺に対し垂直外向きに正方形を少し移動すると、2個に減らせる。よって最小性に反する。

f) 4個の場合

正方形の4辺に1つずつ頂点が存在するとしてよい。図のように\(A,B,C,D\)と順番に名前を付ける。さら直線\(AC\)と\(BD\)の交点を\(P\)とし、\(\angle APD = \theta\)とする。ここで図のように\(DB\)に\(A\)からおろした垂線が、\(C\)が乗る正方形の辺（もしくはその延長線）と交わる点を\(C'\)とする。この時\(C'\)は格子点となる。\(\theta\)が90°でない場合は\(C\neq C'\)となり、\(C, C'\)の2つの格子点が同じ辺（もしくはその延長線）に乗る。

\(\theta\)が90°の場合、\(P\)を中心に少し回転させると、\(A,B,C,D\)はすべて正方形内部に移動し、最小性に反する。（回転の向きは\(AC, BD\)の傾きによる）

 

以上より、最小の正方形の傾きが有理数であることが証明された。（細かい証明は省いてある）

さらに先述の場合分け f) 4個の場合では、格子点\(C, C'\)間の距離は正方形の一辺の長さの2倍を超えない、さらに言うと2倍未満であることがわかる。他の場合も正方形のある一辺に2つのポリオミノの頂点が乗る。よって、辺、そしてその延長線にのる格子点間の距離は正方形の一辺の長さの2倍未満である。

以上の結果より、有効な格子を調べるための正方形の傾きについて、正方形の一辺の長さ\(n\)に従い有限の範囲で列挙できる。具体的には、\(a^2 + b^2 < 4n^2\)を満たす互いに素な正整数\(a\geq b\)について、\((0,0), (a,b)\)を通る傾きの辺を持つ場合を考えればよい。

次に平行移動について考える。図の実線のようにまず正方形の一辺が乗る線（横線と呼ぶ）を決める。これは格子点を通るとしてよく、先ほどのように\((0,0), (a,b)\)を通ると仮定する。さらにその一辺に隣り合う一辺が乗る線（縦線）を決める。縦線も格子点を通るものとしてよい。この縦線の取り方は\(a^2 + b^2\) 通りある。図では\(1:2:\sqrt{5}\)の傾きの横線に対し、\(1/\sqrt{5}\)の間隔で並んだ\(1^2 + 2^2=5\) 通りの縦線の取り方を点線で示している。横線と縦線が決まればあとは一辺の大きさを指定すれば正方形が確定する。

 

 

以上より、有効な格子の候補となる正方形の傾きと位置を有限個に絞ることができた。あとは内部に含まれる格子のセル（小さい正方形）を判定すれば正方形に含まれるポリオミノが得られる。それにはセルの4頂点すべてが正方形の内部に含まれるかを判定すればよい。
※判定は点と直線の距離の式の比較により行えるが、プログラムで行う場合の留意点として、浮動小数点数での比較を行うと、ちょうどぴったり重なる場合などに判定を間違うケースが想定される。式を二乗してうまく変形すると、整数同士の判定に帰着し回避できる。

なお、生成されるポリオミノはすべてが極大ではないため、他のポリオミノに含まれるものは除く必要がある。（今回私は愚直に1セルずつ、回転鏡像を含めて包含関係を確認したが、もう少しうまいやり方がある気がする）

有効な格子の列挙は、正方形の一辺の長さnがあたえられたときにスナップショット的に行うことも可能であるが、nが実数の範囲として与えられていても、その進行を列挙できる。傾きを決めて縦線を取った後に、縦線上の一辺と向かい合う一辺（の乗る線）を決める際にも格子点を通るとしてよいので、縦線の間隔が一定だったことを思い出すと、nが与えられなくても調査が必要な正方形の大きさも列挙可能であることがわかる。

パズルを自動で解くにはソルバーが必要になる。そのアルゴリズムを紹介しよう。

ソルバーは盤面（先ほど列挙した有効な格子）とポリオミノのピースが与えられたときに、最大何個入るのか、そしてその入り方を見つける。盤面もまた、前述の通りポリオミノとなる。

パズルを解く頻出アルゴリズムとして「バックトラッキング」という枝刈付き深さ優先探索がある。数独や８クイーン問題を解く際にも使われるが、今回も使える。流れとしては、とりあえずピースを置けるだけ置いて、行き詰ったら、盤面上で最後に置かれた１ピースを除いてやり直す、という作業の繰り返しである。

さらに問題がExact Coverに帰着できるときに、双方向リストを使ってバックトラッキングを効率よく実装できる。これはDancing Link *5として知られており、今回の問題もこちらを応用できる。実際、Knuthの論文でも同一ポリオミノでのタイリングが取り上げられている。

Exact Coverとは集合\(X\)とその部分集合の属\(S\)が与えられたときに、\(S\)のいくつかの元を取ってきて、\(X\)の元がちょうど重複なく１回ずつどれかの元に含まれるという風にできるか、という問題である。ポリオミノのタイリングの場合は、盤面のセル１つ１つが\(X\)の要素となり、\(S\)はポリオミノ１ピースの置き方（セルの占め方）に相当する。ピースの置き方は回転鏡像、平行移動により列挙できる。

今回のパズルの留意点として、盤面がすべてポリオミノにより埋め尽くされるわけではなく、空白も存在する可能性がある。つまり厳密にはExact Coverではない。

しかしDancing Linkの実装を、空白も選択肢として取りうるように少し変えれば対応できる。実装としては、空白を選択する場合はその列のみカバーすればよい。（カバーとはDancing Linkの用語である。詳しい説明は原論文へ）

また、盤面の面積が\(A\)の時に、サイズnのポリオミノを\(i\)個入れると、盤面に空白は\(A-ni\)個存在することになるが、それより多く空白を作ってしまうとポリオミノが\(i\)個入ることはない。空白を選択した回数をカウントしておけば、空白の数の上限を超えた場合は枝刈りでき、探索回数（再帰呼出数）を減らせる。

Dancing LinkのColumnの選び方は原論文でもいくつか提唱されているが、本件では、選択肢の数が最小になるように選ぶことで、かなり再帰呼出数を減らせることを確認している。

ソルバーは以上である。盤面については前述の方法で列挙できるので、総当たりでソルバーを走らせれば解が見つかる。

 

また本件の派生として思いついたが、Exact Coverをもう少し拡張してもDancing Linkを応用して解けるだろう。Exact Coverのステートメントの「ちょうど1回ずつ含まれる」の部分に範囲を持たせて、「要素\(k\)が\(a_k\) ~ \(b_k\)個含まれる」と変え、さらに判定問題ではなく、全体の個数のMaxを求めるという問題に変える。今回のソルバーは\(\forall{k}: a_k=0, b_k=1\)の場合に相当する。

\(a_k, b_k\)が一般の場合は、要素\(k\)のColumn Headerに\(a_k, b_k\)を持たせて、Rowを選ぶたびに、カバーの代わりにRowで選ばれた要素\(j\)の\(a_j, b_j\)を減らしていく（戻すときは増やす）。\(b_j=0\)となったときにはColumn \(j\)のカバーを行う。

 

パズルの作り方

さきほどのソルバーはパズルを作る際にも利用できる。

微妙な違いとして、パズルを解く際は、何個ポリオミノが入るかあらかじめ分かっているが、作る際は分からない。それについては、何個入るかの目標値を0から初めて、解が見つかれば適宜インクリメントしていくことで、空白による枝狩りを利用しながらが、最大で入る個数を効率よく探すことができる。

あとはピースとなるポリオミノが列挙できれば、総当たりでパズルを探すことができる。ポリオミノの列挙に関しては多くの先行研究があるのでそちらに譲る*6 *7。

 

斜めにしか入らないものに限らず、解が一意になるパズルや、対称なパズル、解くのが難しいパズルなど、さまざま作ることができる。パズルの難易度はDancing Linkの再帰呼出数を目安とできるだろう。

 

パズルの答え

ご自由にお使いください。

 

*1:Sixes And Sevens Puzzle

*2:第５回パズルオーディション 作品募集 – 一般社団法人 日本パズル

*3:A339848 - OEIS

*4:SamN.docx - Google ドキュメント ロシア語を翻訳して理解した

*5:Donald E. Knuth. "Dancing Links". https://arxiv.org/pdf/cs/0011047

*6:Redelmeier, D. Hugh (1981). "Counting polyominoes: yet another attack". Discrete Mathematics. 36 (2): 191–203

*7:A000105 - OEIS

円周上にランダムにとった点を頂点とする多角形の性質について

半径1の円周上に一様ランダムに、独立に、３つの点をとり，それらを頂点とする三角形の面積は，平均で\frac{3}{2\pi} = 0.47746...となることが知られている。
Circle Triangle Picking -- from Wolfram MathWorld

直感的には円全体の面積{\pi}=3.1415...に比べると小さく感じる。ちなみに面積最大は正三角形の時で:\frac{3\sqrt{3}}{4} = 1.2990... である。

 

点の数が一般の場合について考えてみよう。n\geq 3 個の点を、半径1の円周上にランダムにばらまく。点の集合をPとし、Pに対する凸包（釘に輪ゴムをかけたようなもの）として得られる多角形が今回考える対象である。重複がなければ、円周上に頂点を持つn角形となる。この多角形の性質を調べてみる。

中心角について

まず、隣り合う点同士が見込む中心角\thetaの分布を求めよう。

点をランダムに１つずつ順番に配置していくことを考える。

最初に決定する点をAとし、Aで円を切って反時計回りに開き、1次元の線分にする。そして、残りの点は１つずつ順番にこの線分に一様ランダムに配置する。配置がおわったら、最終的に長さの比を変えないように線分の端と端をくっつけて円周にもどし、Aが元の位置にくるように回転させれば、件の分布を再現できる。

つまり、円に点をn個ばらまくのは、回転を無視すれば、線分に点をn-1個ばらまくのと同じなのである。回転不変の量に関してはこの考え方が使える。

ここからは線分が[0,1]として考える。

k番目に打たれた点BがAの右隣に来る確率を考える。Bの位置をxとすると、残りn-2個の点は[x,1]にのる必要がある。Bが固定されていた場合、この確率は(1-x)^{n-2}である。このとき、円に戻したときに弧ABが見込む中心角は\theta=2\pi xである。

円をAで切って作った線分。赤点はp\in P\setminus\{A,B\}

Bが何番目に配置された点かについて、n-1通りあることに注意して、Bの位置xを動かして積分すれば中心角の累積分布P[\angle AOB\leq\theta]が求まる。

\begin{align}
P[\angle AOB \leq \theta] &= (n-1)\int_0^r (1-x)^{n-2} dx \\
&= 1 - (1-r)^{n-1}
\end{align}

なお、\frac{\theta}{2\pi} = rとした。

中心角の確率密度関数はf(\theta)=\frac{dP[\angle AOB  \leq \theta]}{d\theta} = \frac{1}{2\pi}(n-1)(1-r)^{n-2}となる。

１つの中心角\thetaの分布が求まった。複数の中心角の同時分布はどうだろう。

ある点から順に反時計回りにp_1,p_2, p_3,...,p_nとし、 \angle p_kOp_{k+1}を \theta_kとする。このとき(\theta_1, \theta_2, ..., \theta_{m\leq n-1}) の同時累積分布を求めると以下になる。(最後の角は自由度がないので除く。)

\begin{align}
P&[\forall k_{,1\leq k \leq m}  (\angle p_kOp_{k+1} \leq \theta_k) ]\\
&=\dfrac{(n-1)!}{(n-{m}-1)!}\int_0^{r_1}\int_0^{r_2}...\int_0^{r_m} (1-x_1-x_2-...-x_m)^{n-{m}-1}dx_1dx_2 ...dx_m\\
&=\sum_{a\in \{0,1\}^{m}}(-1)^{\sum_{i=1}^m{a_i}} (1 - \sum_{i=1}^m a_ir_i)^{n-1}
\end{align}

なお、\frac{\theta_i}{2\pi} = r_iとした。　

最後の式は帰納法で証明できる。特にm=n-1の時に同時累積分布は(n-1)!\prod_{i=1}^{n-1} r_iとなるが、式を満たしている。

m=n-1の時、中心角の同時確率密度関数はf(\theta_1, \theta_2, ... ,\theta_{n-1})=\frac{\partial P[\forall k_{,1\leq k \leq m}  (\angle p_kOp_{k+1} \leq \theta_k) ]}{\partial \theta_1\partial \theta_2...\partial \theta_{n-1}} = \dfrac{1}{(2\pi)^{n-1}}(n-1)!とあらわされ、一様分布となる。

拘束条件0\leq\theta_k, \sum_k \theta_k \leq 2\piを考えると、これはn-1次元三角錐の内部での一様分布と考えられる。

面積について

面積の期待値を先ほどの中心角の分布から求めてみる。

円周上の隣り合う２つの頂点からなる三角形について考える。具体的には\triangle Op_1p_2,\triangle Op_2p_3,...,\triangle Op_np_1 のn個の三角形である。これらで対象の多角形の面積を表してみよう。

多角形の内部に円の中心が含まれる場合、多角形の面積はn個の三角形の総和になる。中心が含まれない場合、中心は多角形のある辺\overline{p_kp_{k+1}}（あるいは\overline{p_np_1}）とそれに対応する弧に囲まれている。この時、多角形の面積は\triangle Op_kp_{k+1}以外のn-1個の三角形の総和から\triangle Op_kp_{k+1}を引いたものとなる。

図1：円の中心が多角形に含まれる場合（左図）と含まれない場合（右図）

各三角形は長さ1の等辺を持つ二等辺三角形であり、等辺に挟まれた角が\thetaの時、面積は \sin(\frac{\theta}{2})\cos(\frac{\theta}{2})=\frac{\sin(\theta)}{2}となる。

先ほど分布を求めた中心角は\thetaが\piを超えることがあった。その場合、上記の面積が負になるが、ちょうど中心が含まれない場合の引き算をする三角形の面積に対応するので都合がよい。

\thetaの分布に沿って積分することで、三角形１つ当たりの多角形への面積寄与が求まる。

\begin{align}
E[\triangle Op_lp_{l+1}] &= \int_0^{2\pi} \dfrac{1}{2\pi}(n-1)\left(1-\frac{\theta}{2\pi}\right)^{n-2} \frac{\sin(\theta)}{2}d\theta\\
&=-\dfrac{n-1}{2(2\pi)^{n-1}}\int_0^{2\pi} \theta^{n-2} \sin(\theta)\\
\end{align}

最後の変換は2\pi - \theta=\phiという変数変換を施すことで得られる。対称性と期待値の線形性より、これをn倍すると多角形の面積の期待値となる。

積分は \int x^{n}\sin(x) dxの形であり、これは部分積分を繰り返し適用することで肩の nが減るので解くことができる。すべて展開すると以下の形となる。
integration - Computing the indefinite integral $\int x^n \sin x\,dx$ - Mathematics Stack Exchange

\begin{align}
 \int x^{n}\sin(x) dx = \cos(x) &\sum_{k=0}^{\lfloor n/2\rfloor} (-1)^{k+1}x^{n-2k}\dfrac{n!}{(n-2k)!}\\
&+\sin(x) \sum_{k=0}^{\lfloor (n-1)/2\rfloor} (-1)^{k}x^{n-2k-1}\dfrac{n!}{(n-2k-1)!}
\end{align}

代入して解くと、多くの項が0になり、最終的に多角形の面積の期待値は以下となる。

\begin{align}
E[S] &= n E[\triangle Op_lp_{l+1}]\\
&=\dfrac{1}{4\pi} \sum_{k=0}^{\lfloor (n-3)/2\rfloor} \left(\dfrac{-1}{4\pi^2} \right)^{k}\dfrac{n!}{(n-2k-2)!} \\
\end{align}

n=3,4,5の時、それぞれ面積の期待値は\frac{3}{2\pi},\frac{3}{\pi},\frac{5}{\pi}-\frac{120}{16\pi^3}となる。またn\rightarrow\inftyで多角形は円となるので、E[S]は\piに収束する。

なお、総和は交代和となっているが、nが大きくなると各項の絶対値が無限に大きくなる。

周長について

周長、つまり多角形の辺の総和についても、同様に求められる。辺の長さは |\overline{p_lp_{l+1}}| = 2\sin(\frac{\theta}{2})であるので、 \overline{p_lp_{l+1}}の周長に対する寄与の期待値を求めると以下となる。

\begin{align}
E[|\overline{p_lp_{l+1}}|] &= \int_0^{2\pi} \dfrac{1}{2\pi}(n-1)\left(1-\frac{\theta}{2\pi}\right)^{n-2} 2\sin(\frac{\theta}{2})d\theta\\
&=\dfrac{2(n-1)}{\pi^{n-1}}\int_0^{\pi} \theta^{n-2}\sin(\theta)   d\theta   \\
\end{align}
変形の過程で\frac{\theta}{2}=\phiと\pi-\phi=\xi と変数変換を２回行った。

さきほどと同様の積分形であり、n倍して展開することで周長Lの期待値を得る。

\begin{align}
E[L] &= n E[ |\overline{p_lp_{l+1}}|]\\
&=  \begin{cases}
    \dfrac{2}{\pi} \sum_{k=0}^{\lfloor (n-2)/2\rfloor} \left(\dfrac{-1}{\pi^2} \right)^{k}\dfrac{n!}{(n-2k-2)!}      & \text{if $n$ is odd,} \\
    \dfrac{2}{\pi} \left( \left(\dfrac{-1}{\pi^2} \right)^{\frac{n-2}{2}}n!+\sum_{k=0}^{\lfloor (n-2)/2\rfloor} \left(\dfrac{-1}{\pi^2} \right)^{k}\dfrac{n!}{(n-2k-2)!}   \right)  & \text{if $n$ is even.}
  \end{cases}
\end{align}

場合分けが必要な理由は、式に0^0が含まれているからである。(面積の時はうまくキャンセルしあった。）
n=3,4,5の時、それぞれ周長の期待値は\frac{12}{\pi},\frac{24}{\pi}-\frac{ 96}{\pi^3},\frac{40}{\pi}-\frac{240}{\pi^3}となる。\frac{1}{n}倍すると一辺の平均の長さとなる。またn=2では\frac{8}{\pi}となるが、これは２点間の距離の平均の2倍の長さ（往来分）である。また面積の場合と同様にn\rightarrow\inftyで、E[L]は円周と同じ2\piに収束する。

円の中心が多角形の内部に含まれるか

図1を思い返して、円の中心が多角形に含まれる場合と含まれない場合があった。これらがどれぐらいの確率で起こるかを見てみる。1992年のPutnamで球に内接する四面体が球の中心を含む確率についての問題が出題されており、エレガントな解法が3Blue1BrownのYoutubeで紹介されている。
https://kskedlaya.org/putnam-archive/1992.pdf
The hardest problem on the hardest test - YouTube

考え方の肝は１点を固定し、それ以外の点のランダムな選び方を１クッション工夫することである。具体的には球の中心を通る直線をランダムに選び、さらに球と直線の交点（２つある）から半分ずつの確率で１つ選ぶという方法にする。実際これでランダムに点を選べる。

この時、１点が固定され直線を決定した時点で、中心が四面体に入る二択の選び方が一意に決まるため、直線3本分の二択なので、中心が四面体に入る確率は\frac{1}{2^3}=\frac{1}{8}となる。この確率は直線の選び方によらず常に一定なので、これが求める答えとなる。

本件も似た考え方でアプローチできる。図のように点Aを固定して、n -1本の円の中心Oを通る直線をランダムに取る。円と直線の交点（2n -2個ある）にAの対蹠点から円周に沿ってq_1,q_2,..., q_{2n-2}と名前を付ける。

さらにn -1個の交点のペアから１つずつ選ぶことを考える。この時Aと選ばれた交点で作られる多角形が円の中心を含まないような選び方は(q_k,q_{k+1},...,q_{k+n-2})のパターンしかない。（\because \triangle Aq_lq_{l+m} (m\geq n) は鋭角三角形となり中心を含む。）

そのようなパターンはn個存在する。よって直線を決定した後に、交点からn -1個を選んだ時に多角形が円の中心を含まない確率は\frac{n}{2^{n-1}}となる。この確率は直線の選び方によらず常に一定なので、これが求める答えとなる。多角形が円の中心を含む確率は余事象より1-\frac{n}{2^{n-1}}となる。

なお、これは中心角の同時分布で求めたn-1次元三角錐を辺の中点で切頂したものの体積比となっている。

追記

さらに拡張して、円周上ではなく、原点周りで点対称な確率分布に従ってプロットされる点に関しても同様の議論ができ、選ばれた点が張る多角形が原点を含む確率は上記と一致する（と思われる）。なお、確率分布が直線上に集中していると、その限りではないのである程度散らばっている必要がある。

内角について

多角形のある頂点の内角の期待値は、正n角形の場合と同じ\frac{n-2}{n}\piである。そうでなければ、足し合わせた時に内角の和が(n-2)\piとならない。

内角が鋭角になる確率はどうだろう？実はこの問題もPutnamで出ている。
https://kskedlaya.org/putnam-archive/2005.pdf
https://kskedlaya.org/putnam-archive/2005s.pdf

実は先ほどとほとんど同様のセットアップで証明できる。

先ほどの考え方で、今度はAが左端にあるとする。(図参照。添え字がこちらのほうが便利）この時Aの内角が鋭角になる頂点の選び方は(q_k,q_{k+1},...,q_{k+n-2})形のnパターンしかない。先ほどと同じである。同様の議論により、ある頂点の内角が鋭角になる確率は\frac{n}{2^{n-1}}である。鋭角の頂点数の期待値は、その頂点数倍の\frac{n^2}{2^{n-1}}である。

qの添え字は変えず、Aを左側に移動した

また、n\geq 4の場合、円に内接する多角形の鋭角の個数は高々2個であり、2個ある場合は鋭角は隣り合っていることが知られている。これは鋭角を円周角と見込む弧の長さが円周の半分未満であることによる。

ここで鋭角がちょうど2個あるケースについてみてみる。先ほど同様の考え方で、Aともう一つ鋭角がある場合を考える。これも実は直線の配置に依存せず、以下の4パターンとなる。

(q_1,q_{2},...,q_{n-1})\rightarrow A \text{ and }q_{n-1} \text{ are acute}

(q_2,q_{3},...,q_{n})\rightarrow A \text{ and } q_{n} \text{ are acute}

(q_{n-1},q_{n},...,q_{2n-3})\rightarrow A \text{ and } q_{n-1} \text{ are acute}

(q_{n},q_{n+1},...,q_{2n-2})\rightarrow A \text{ and } q_{n} \text{ are acute}

つまり先ほどAを鋭角にするnパターンのうち、上記を除いたn-4パターンが多角形の頂点のうちAのみが鋭角になるパターンとなる。その確率は\frac{n-4}{2^{n-1}}となる。これを頂点数倍すると期待値\frac{n(n-4)}{2^{n-1}}となるが、鋭角の数1で割ると、そのまま多角形がちょうど１つ鋭角を持つ確率となる。

同様の議論により多角形がちょうど２つ鋭角を持つ確率は\frac{n}{2^{n-2}}となる。（期待値を鋭角の数2で割る。）

 

もう少し一般に、ある頂点Aの内角\thetaの分布を考えよう。中心角の時に考えた線分を持ってくる。

赤点はp\in P\setminus\{A,B\}

ここで架空の点B'をAの右隣の点Bから\frac{2\theta}{2\pi}（=rとおく）だけ離れたところにあるとしたときに、これは円に戻したときに、円周角\angle BAB'がちょうど\thetaとなる点である。
このとき、円に戻したときにAの内角が\theta以下となるのは、残りのn-2個の点が全て\overline{BB'}に乗る場合に限る。ただし、B'がA'の右側にはみ出す場合は、残りの点が全て\overline{BA'}に乗る場合に限る。

あとはBの選び方がn-1通りあることに注意して、Bを動かして積分すれば内角の累積分布P[\angle A\leq\theta]が求まる。

\begin{align}
P[\angle A \leq \theta] &= (n-1)\left(\int_0^{1-r} r^{n-2} dx +  \int_{1-r}^1 (1-x)^{n-2} dx\right)\\
&= (n-1)\left[r^{n-2}x\right]_0^{1-r} +(n-1)\left[\dfrac{-(1-x)^{n-1}}{n-1}\right]_{1-r}^1\\
&= (n-1)(1-r)r^{n-2} + r^{n-1}
\end{align}

確率密度関数は\frac{dP[\angle A \leq \theta]}{d\theta} = \frac{1}{\pi}(n-1)(n-2)r^{n-3}(1-r)となる。