フィボナッチ・フリーク

数学の小ネタ集。

Fibonacci Freak

【解決編】平面上の凸図形に含まれる多角形の面積

前回の記事で,次のような問題の解答を募集しました.

問題.平面上の凸図形Xに対し,「Xに含まれるn角形の面積の最大値をXの面積で割ったもの」をM_n(X)と書く.Xを動かしたとき,M_n(X)のとりうる値の最小値は何か?

 

fibonacci-freak.hatenablog.com

 

これについてある方からTwitterでリプライをいただき,なんとこの問題は

E. Sasという数学者により1939年に解かれていた

ことが判明しました!(昔の人,すごい!)

 

そこで,今回はその証明を紹介したいと思います.簡潔な証明なのですぐに終わります.

 

定理 (E.Sas, 1939).任意の凸図形Xに対しM_n(X)\geq \dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}であり,Xが円のときに等号が成立する.

 

証明.Xに含まれる線分のうち距離が最大のものを1つとりABとする.問題の内容は相似で不変なのでABの長さが2であると仮定してよい.A=(-1,0), B=(1,0)となるように座標をとる.ABの最大性から,X-1\leq x\leq 1の範囲に入ることに注意する.

 

f:id:fibonacci_freak:20171206232657p:plain

 

\theta\in[0,\pi]に対し\{(x,y)\in X\mid x=\cos\theta\}におけるyの最大値をh(\theta)と定める.同様に\theta\in[\pi,2\pi]に対してはyの最小値をh(\theta)と定める.するとXの境界は

f(\theta):=(\cos\theta,h(\theta))

によりパラメータづけできる.このときXの面積は

\displaystyle X=\int_{\theta=0}^{2\pi}-h(\theta) dx(\theta)=\int_0^{2\pi}h(\theta)\sin\theta d\theta

となる.

ここでt\in[0,2\pi]を1つとり,t_k=t+\dfrac{2k\pi}{n}と定める.f(t), f(t_1), f(t_2),\dots,f(t_{n-1})を頂点とするn角形の面積をS(t)とすると,和積の公式より

\displaystyle \begin{align*}S(t)=\sum_{k=0}^{n-1} \dfrac{\cos t_k h(t_{k+1})-\cos t_{k+1}h(t_k)}{2}\end{align*}\\ \displaystyle =\sum_{k=0}^{n-1} \dfrac{(\cos t_{k-1} -\cos t_{k+1})h(t_k)}{2}\\ \displaystyle=\sum_{k=0}^{n-1} \sin t_k\sin\dfrac{2\pi}{n} h(t_k)

 

と表すことができる.よってtを無作為にとったときのS(t)の期待値は

\displaystyle \dfrac{1}{2\pi}\int_0^{2\pi}S(t)dt=\dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}\int_0^{2\pi}h(\theta)\sin\theta d\theta=\dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}\cdot X.

 

これはあるtが存在してS(t)\geq \dfrac{n}{2\pi}\sin\dfrac{2\pi}{n}\cdot Xとなることを示しており,主張は示された.\square

 

見事な証明とはこのことです.まるで芸術作品のような美しさを感じませんか?

【解答募集】平面上の凸図形に含まれる多角形の面積

追記:解決したので「解決編」を書きました.

fibonacci-freak.hatenablog.com

 

 

 

 

私は今(2017年12月5日現在),こんな問題を考えています.

問題.平面上の凸図形Xに対し,「Xに含まれるn角形の面積の最大値をXの面積で割ったもの」をM_n(X)と書く.Xを動かしたとき,M_n(X)のとりうる値の最小値は何か?

 

たとえばXが正六角形の場合,M_3(X)=\dfrac{1}{2}, M_4(X)=\dfrac{2}{3}等となります.nを大きくしていくとM_n(X)は1に近づくことも推測されます.

 

f:id:fibonacci_freak:20171205214206p:plain

 

今のところ自分で導けた結果は次の2つです.

命題.M_3(X)\gt\dfrac{1}{3}.

証明.凸図形Xに含まれる三角形のうち面積が最大のものを1つ取り,その頂点をA, B, Cとする.これらはXの周上にあるとしてよい.ABC180^\circ回転させた図形(以下「耳」と呼ぶ)を各辺に貼り付けると,下図のような大きな三角形が得られる.面積の最大性から,Xはこの三角形に含まれることがわかり,M_3(X)\gt\dfrac{1}{4}が従う.

 

f:id:fibonacci_freak:20171205221610p:plain

 

さらにXのうち3つの耳に含まれる部分の面積を評価する.3つの耳を平行移動して全て重ねた時,Xと交わっていた部分(図の赤い部分)全てに含まれる点があったとすると,もとの図形の中でそれらはABCと等しい面積を持つ三角形をなす.ゆえに赤い部分は境界以外では高々2つまでしか交わらないので,赤い部分の面積はABCの高々2倍であり,Xの面積はABCの高々3倍であることがわかる.よってM_3(X)\gt\dfrac{1}{3}\square

 

命題.M_4(X)\gt\dfrac{1}{2}.

証明.凸図形Xに含まれる四角形のうち面積が最大のものを1つ取り,その頂点をA, B, C, Dとする.これらはXの周上にあるとしてよい.A,Cそれぞれを通り対角線BDに平行な直線と,B,Dそれぞれを通り対角線ACに平行な直線を描くと,ABCDの2倍の面積を持つ平行四辺形が得られる.面積の最大性からXはこの平行四辺形に含まれることがわかり,M_4(X)\gt\dfrac{1}{2}が従う.\square

 

(それから一応,M_3(X)\gt\dfrac{3}{8}という評価も得られたような気になっていますが,証明が複雑なので間違っている気もしています.確証が得られたら追記します.)

 

しかし正直なことを言うと,さすがにもっと良い評価が得たい!という気持ちでいっぱいです.

そこで,ぜひ優秀な読者の皆さんにも一緒に考えてもらいたい,というわけです.

もし何か新しい結果が得られたら,Twitter(@Asuka_Tsukimi)までご連絡ください!

twitter.com

ご協力をお願いします(*^^*)(*^^*)(*^^*)(*^^*)

格子立方体の一辺の長さとWittの消去定理

格子点(座標が整数の点)を結んでできる図形は面白い問題の源泉です.今回は格子点を結んでできる立方体について考えてみましょう.まずn次元の格子立方体を厳密に定義します.

定義.n次元空間の格子点を頂点とするn次元立方体を格子立方体という.ただし立方体とは,単位区間n個の直積の直交変換による像である.

この定義はたとえば2次元なら正方形,3次元なら通常の立方体と一致します. さて,ここで次のような問題を考えます.

問題.n次元の格子立方体の一辺の長さとしてあり得る実数の集合をL(n)で表す.L(n)はどのような集合になるか?

まずは2次元の場合を考えてみましょう.三平方の定理より一辺の長さは0以上の整数a,bを用いて\sqrt{a^2+b^2}と表すことができます.逆にこのように表せる実数Dに対して一辺がDの格子正方形が存在することも自明です.よって

L(2)=\{\sqrt{a^2+b^2}\mid a,b\in \mathbb{Z}_{\geq 0}\}\setminus \{0\}

であることがわかりました.

3次元の場合は少し難しいですが,体積を考えるとうまくいきます.先ほどと同じように,三平方の定理から辺の長さDは正整数の平方根であることがわかります.一方,格子立方体の体積は辺のベクトルを並べた行列の行列式に等しく,辺のベクトルは成分が全て整数なので,体積も当然整数になります.よってD^3は整数であり,Dが正整数であることがわかりました.逆に任意の整数Dに対して一辺の長さがDの立方体が存在することは自明なので,結局

L(3)=\mathbb{Z}_{\gt 0}

であることがわかりました. 全く同じ議論から

L(2k+1)=\mathbb{Z}_{\gt 0}

もわかります.

4次元の場合はさらに面白いことが起こります.そう,4次元にはあの定理があるのです!

Lagrangeの四平方和定理.任意の正整数Dは4つの非負整数a,b,c,dによってD=a^2+b^2+c^2+d^2と表せる.

4次元立方体の一辺の長さは先ほどと同様に整数の平方根になりますが,逆に任意の正整数Dに対して一辺の長さが\sqrt{D}の立方体を構成することができます.実際,上の定理を使ってD=a^2+b^2+c^2+d^2と表すと,

v_1=\begin{pmatrix}a\\b\\c\\d \end{pmatrix}, v_2=\begin{pmatrix}b\\-a\\d\\-c \end{pmatrix}, v_3=\begin{pmatrix}c\\-d\\-a\\b \end{pmatrix}, v_4=\begin{pmatrix}d\\c\\-b\\-a \end{pmatrix}

で張られる格子立方体の一辺の長さは\sqrt{D}になります.よって

L(4)=\{\sqrt{D}\mid D\in \mathbb{Z}_{\gt 0}\}

がわかりました.上で構成した立方体の直積を考えれば,より一般に

L(4k)=\{\sqrt{D}\mid D\in \mathbb{Z}_{\gt 0}\}

であることもわかります.

 

これで残ったのはn=4k+2の場合のみとなりました.n=2の場合の正方形の直積を考えれば

L(4k+2)\supset \{\sqrt{a^2+b^2}\mid a,b\in \mathbb{Z}_{\geq 0}\}\setminus \{0\}

となります.

実はこの包含は等号になります!

証明には対称双線型形式に関するWittの消去定理を使います.

Wittの消去定理.標数0の体上の有限次元ベクトル空間V_1,V_2,V'_1,V'_2に,それぞれ対称双線型形式B_1, B_2, B'_1, B'_2が与えられているとする.V_1\oplus V_2には対称双線型形式B_1\oplus B_2が誘導され,V'_1\oplus V'_2にはB'_1\oplus B'_2が誘導される.このとき,V_1\oplus V_2\cong V'_1\oplus V'_2かつV_1\cong V'_1ならばV_2\cong V'_2である.ただし\congは等長同型,すなわち対称双線型形式を保つ線形同型が存在することを表す.

これを使うために,格子立方体を対称双線型形式の言葉に言い換えます.

定義.有理点を頂点とする立方体を有理立方体という.

実は一辺の長さがDの有理立方体を与えることは(\mathbb{Q}^n,DB)から(\mathbb{Q}^n,B)への等長同型を与えることと対応します.ここでB\mathbb{Q}^nの標準内積です.この対応はv_1,\dots,v_nで張られる有理立方体に対し,標準基底をv_1,\dots,v_nに送る線型写像を対応させることで得られます.

さて,DL(4k+2)の元とすると,格子立方体は有理立方体なので,先ほどの対応から(\mathbb{Q}^{4k+2},DB)\cong (\mathbb{Q}^{4k+2}, B)となります.一方でD\in L(4k)でもあるので,(\mathbb{Q}^{4k},DB)\cong (\mathbb{Q}^{4k}, B)となります.よってWittの消去定理より(\mathbb{Q}^2,DB)\cong (\mathbb{Q}^2, B)がわかり,これはDが有理正方形の一辺の長さであることを意味しています!

よって正整数p,q,r,sを用いてD=\sqrt{\dfrac{p^2}{q^2}+\dfrac{r^2}{s^2}}と表すことができます.両辺を二乗し分母を払うと

(qs)^2D^2=p^2+r^2

となります.ここで次の定理を使います.

Eulerの定理.正整数nが二つの平方数の和として表せるための必要十分条件は,4で割ったあまりが3である素因数の指数が全て偶数であることである.

とくにこの条件はnを平方数で割っても(もちろん割った後が整数なら)変わらないことに注意します.いまD^2三平方の定理から正整数であることがわかっているので,前の式とEulerの定理よりD^2も平方数の和として表せます.よってD\in\{\sqrt{a^2+b^2}\mid a,b\in \mathbb{Z}_{\geq 0}\}\setminus \{0\} がわかりました.

 

n=4k+2の場合に関する以上の解法は楕円曲線に関する業績で知られるN.Elkiesによるもの(MathOverflowの回答)です.こんな素朴な問題に深い整数論的現象が潜んでいるなんて,とても面白いと思いませんか!

USAMO2008第6問と有限体上の線形代数

USAMO(アメリカ数学オリンピック)の2008年大会では,第6問として次のような問題が出題されました.

ある数学の会議において,どの2人の数学者も友達かそうでないかのどちらかであるとする.参加した数学者全員は二つの大きな部屋のいずれかで夕食を食べる.数学者たちはみな,自分の友達のうち偶数人が含まれる部屋で食事をしたいとする.全員の希望を満たすように数学者を分ける方法の総数は2の冪(つまりある正整数kに対し2^k)であることを示せ.

 

これは純粋に組み合わせ論の問題ですが,実は線形代数の知識を使うと見通しよく解くことができます.

 

解答.数学者に1,2,\dots,nと番号をつける.以下,行列やベクトルは全て\mathbb{F}_2=\mathbb{Z}/2\mathbb{Z}上で考える.ijが友達であるときa_{ij}=1,そうでないときa_{ij}=0と定め,a_{ii}iの友達の総数を2で割った余りとする.これによりn\times n行列(a_{ij})が定まる.また,iを部屋Aに割り当てるときv_i=0,部屋Bに割り当てるときv_i=1とするとn次元ベクトル(v_i)が定まる.このとき,割り当て方vが数学者全員の希望を満たすことは

\[\begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n}\\ a_{21} & a_{22} & \dots & a_{2n}\\ \vdots & \vdots & \ddots & \vdots\\a_{n1} & a_{n2} & \dots & a_{nn}\end{pmatrix}\begin{pmatrix}v_1\\ v_2\\\vdots\\v_n\end{pmatrix}=\begin{pmatrix}a_{11}\\ a_{22}\\ \vdots\\a_{nn}\end{pmatrix}\]

と同値である.実際左辺の第i成分は,iが部屋Aにいるときは

(部屋Bにいるiの友達の総数) \mathrm{mod}~2

であり,iが部屋Bにいるときは

iの友達の総数)+(部屋Bにいるiの友達の総数) \mathrm{mod}~2

なので,これがa_{ii}になることはiの希望が満たされることと同値である.よって全員の希望を満たす割り当て方は存在すれば2冪であることがわかった.解の存在を示すには,拡大係数行列

\[\left(\begin{array}{cccc|c}a_{11} & a_{12} & \dots & a_{1n} & a_{11}\\a_{12} & a_{22} & \dots & a_{2n} & a_{22} \\ \vdots & \vdots & \ddots & \vdots & \vdots\\ a_{n1} & a_{n2} & \dots & a_{nn} & a_{nn}\end{array}\right)\]

のランクがもとの行列のランクに等しいことを示せば良い.行変形により第i_0行の第1列からn列までを0にできたとすると,実は同じ行のn+1列も0になる.実際,行変形としては第i_1,i_2,\dots,i_k行を第i_0行に足すという操作だけ考えればよい.このとき

\displaystyle \sum_{p=0}^ka_{i_pi_q}\equiv 0~(\mathrm{mod}~ 2)

より

\displaystyle \sum_{p,q}a_{i_pi_q}\equiv \sum_{p=0}^k a_{i_pi_p}\equiv 0~(\mathrm{mod}~ 2)

なので第n+1列も0になっている.ゆえに拡大係数行列のランクはもとの行列と等しく,解の存在が示された.\square

定規だけで円に接線を引く

平面上に円が描かれており,その周上の一点Pが指定されているとします.Pでこの円に接する直線を,定規だけを用いて作図することはできるでしょうか?

この問題には面白い解答があります.

まず円周上にP以外に4つの点をとります.これは好きなようにとって構いません.次にこれら5点を星型に結び,下図のように2本の直線を引いて,交点をQとします.すると実は直線PQが接線になっているのです!

f:id:fibonacci_freak:20171027224350p:plain

証明はパスカルの定理を用いると簡単にできます.

パスカルの定理.二次曲線上の一般の位置にに6点A,B,C,D,E,Fをとると,ABDEの交点,BCEFの交点,CDFAの交点は一直線上に並ぶ.
f:id:fibonacci_freak:20171027222909p:plain

今回の場合,接点Pを非常に近い2点P',P''に置き換えることで円周上に6点が並び,ちょうどP',P'',Qが一直線上に並ぶことが帰結されます.P',P''Pに近づく極限を考えることで,これが接線になることがわかります.

またパスカルの定理は円だけでなく一般の二次曲線に対して成り立つので,この方法は他の二次曲線にも使えることがわかります!

実際にこの方法で双曲線に接線をひいてみたものが下図です.

f:id:fibonacci_freak:20171027224429p:plain

イェイ!(*^^*)

ChompゲームとHilbertの基底定理

今回はChompというゲームに関する小ネタです.

Chompは石を使って2人で遊ぶゲームです.石をn\times mに並べます.プレイヤーは図のようにある1つの石を選んで,そこより右上にある石を全て取り去ります.これを交互に繰り返して,一番左下の石を取った方が負けです.

f:id:fibonacci_freak:20171020111249p:plain

実はChompは先手必勝であることを示すことができます(このブログで以前紹介した手法です。ぜひ考えてみてください)が,今回はその話ではなく,ゲームが有限の手数で終わるかどうかという点に着目します.

もちろんChompそのものは,有限個の石が一手ごとに減っていくわけなので,自明に有限手数で決着がつきます.

しかし,石が右と上方向に無限に続いているという設定にした「無限Chomp」を考えると話は難しくなります.果たして無限Chompは有限手数で決着がつくのでしょうか?

実は無限Chompは必ず有限の手数で終わることが証明できます.このことはもちろん初等的にも示せますが,今回は可換環論の定理であるHilbertの基底定理を使った証明を紹介したいと思います.

定理(Hilbertの基底定理).Noether環上の多項式環はNoether環である.特に\mathbb{C}[x_1,\dots,x_n]はNoether環である.

 

最も左下の石を0行目0列目として,a行目b列目にある石を(a,b)と呼び,多項式環の元x^ay^b\in \mathbb{C}[x,y]を対応させます.

f:id:fibonacci_freak:20171020112834p:plain

 

さらに盤面の状態にイデアルIを次のように対応させます.まず初めはI=(0)とし,プレイヤーが(a,b)をとったらII+(x^ay^b)に変化させます.すると常に次の関係が成り立つことがわかります:

(a,b)が盤面から取り除かれている\Leftrightarrowx^ay^b\in I.

さて,前述のように\mathbb{C}[x,y]はNoether環であり,先ほどの考察よりIは真に大きくなり続けるので,ゲームが終わらなければ矛盾します.よってゲームは有限手数で終わります!

この証明は石のマスが3次元,4次元方向にも並んで(つまり\mathbb{Z}^n_{\geq 0}上に石が並んでいる),取る時もa \in \mathbb{Z}^n_{\geq 0}を選んでa+\mathbb{Z}^n_{\geq 0}を取り去るという「高次元無限Chomp」に対しても適用できます.

ベン図とグレイ符号

領域が4個のベン図を描きたい! 

というのは誰もが一度は考えることだと思います(?)。しかし普通に描いてみると2^4=16通りすべての組み合わせができなかったり、同じ組み合わせの場所が2つできてしまったりと、なかなかうまくいきません。

f:id:fibonacci_freak:20171004115952p:plain

そこで今回は、領域がいくつのベン図であっても必ず機械的に書ける方法を紹介したいと思います!

使う数学的概念は「グレイ符号」というものです。

 

グレイ符号とは何か?

(※グレイ符号を知っている方はこの節は読み飛ばして構いません)

「符号」というのは数や文字列に対して別の数や文字列を対応させる規則のことです。ここではわかりやすく、2進列(0と1の並び)を別の2進列に変換する規則を考えます。

しかし、そもそもなぜ2進列を別の2進列に変換することなどを考えるのでしょうか。例えば実用的な話として、何かの棒の回転角度を検出するセンサーを作ることを考えてみましょう。基準となる位置から反時計回りに測った角度を\thetaとして、

0^\circ\leq \theta\lt 45^\circ\to 000,

45^\circ\leq \theta\lt 90^\circ\to 001,

90^\circ\leq \theta\lt 135^\circ\to 010,

135^\circ\leq \theta\lt 180^\circ\to 011,

というように2進表記の0,1,2,3,\dotsの順番で信号が出力されるようにするのが普通でしょう。しかし実はこのような決め方では不具合が生じる可能性が高いのです。

たとえば棒の角度がちょうど90^\circ付近で動いている時、信号は001010の間を行き来します。ここで各桁の信号が変化するタイミングが少しでもずれたら、その瞬間に000011という全く別の信号が出力される可能性があるのです。これでは安定的な信号が得られません。

そこで同じく45^\circ区切りに、次の順番で信号が出力されるようにしてみます。

000,001,011,010,110,111,101,100

こうすれば信号が乱れることはありません。なぜなら隣り合う2つの信号は1桁しか違わないからです。実は000,001,010,\dotsにそれぞれ000,001,011,\dotsを割り当てるこの規則こそが、3桁のグレイ符号と呼ばれるものです。

具体的に作り方を定義しましょう。

n桁のグレイ符号とは,、0,1の列a_1\dots a_nに対し別の列b_1\dots b_nを対応させる規則であって、次のように帰納的に定義されるものである。
1桁のグレイ符号はa_1=b_1(何もしない)。
n桁のグレイ符号は、b_1\dots b_{n-1}a_1\dots a_{n-1}に対応するn-1桁のグレイ符号で、末尾b_na_{n-1}=a_nならば0、そうでなければ1

具体的には次のようになります。

f:id:fibonacci_freak:20171004123811p:plain

隣り合う自然数の2進表記に対応する符号は1桁しか違わないことが見て取れます。これは定義からただちに証明できます。実際a_1\dots a_{n-1}が変化するのはn=a_1\cdots a_n(2進表記で自然数とみなす)が奇数から偶数になるときですが、末尾の2桁の差が変化するのはnが偶数から奇数になるときで、これらは同時に変化することがないので帰納的に示せます。

 

領域がn個のベン図の描きかた

グレイ符号がわかってしまえば、実はベン図を描くのはとても簡単です。領域1個から初めて、次のように帰納的に描いていきます。n個まで描けたとして、n+1個目の領域を描きましょう。まず今あるベン図の2^n個の部屋に2進列を割り当てるのですが、上からk桁目は「その部屋がk番目に描いた領域の内部に入っているかどうか」を見て、入っていれば1、入っていなければ0とします。たとえばn=3なら次のようになります。

f:id:fibonacci_freak:20171004122854p:plain

全ての領域に2進列を割り当てたら、自然数0,1,2,\dotsの2進表記に対応するグレイ符号の順番に線を結んで新しい領域を作ります。すると全ての部屋を1回ずつ通るので、全ての部屋が新しい領域で2分され、2^{n+1}個の部屋からなる正しいベン図が書けるのです!グレイ符号を使ったのは、線を跨ぐごとに隣りあう部屋(=1桁のみ違う部屋)にしか行くことができないから、というわけです(領域を描いている途中で「飛び地」に行かなければいけない状況は、この作り方なら発生しません。気になった方は帰納法で示してみましょう)。

最後にこうして描ける領域6個(部屋は2^6=64個)のベン図を鑑賞して終えることにしましょう。

f:id:fibonacci_freak:20171004125757p:plain

楽しい!(*^^*)

広告を非表示にする