数学徘徊記

自由な数学ブログ。

ある長方形の問題の8通りの解答

定理

ある長方形\(R\)が, 少なくとも1つの辺の長さが整数であるような有限個の長方形に分割されているとする. このとき\(R\)も少なくとも1つの辺の長さが整数である. f:id:yootaamath:20181217115506p:plain

記事の概要

好きな証明 Advent Calendar 2018 の18日目の記事です.
adventar.org
上の定理に8通りの異なる証明を与えます.
この記事はFourteen Proofs of a Result About Tiling a Rectangle を参考にしました. この論文では14もの証明や, その一般化について紹介しています(まだ読み切れていません…).

定義

長方形においてを横の長さ, 高さを縦の長さとする. 長方形\(R\)の部分となっている長方形をタイル, そのうち幅が整数のものを\(H\)タイル(horizontal), 高さが整数のものを\(V\)タイル(vertical)とする. また長方形\(R\)が標準の位置にあるとは, 各辺が軸に平行であり, 左下の頂点が\(xy\)座標の原点にあることをいう. 長方形の頂点をということにする(グラフの頂点と区別するため).
また, 少なくとも1つの辺の長さが整数であるような長方形をキチン長方形ということとする(数学セミナー2018年10月号の時枝正先生の連載記事「試験のゆめ・数理のうつつ/多変数微積分:渦巻く場,秘法εε=δδ-δδ」より, この表現を借りました).
\([x]\)で\(x\)を超えない最大の整数を表す.
\(xy\)平面上の格子点とは, \(x\)座標と\(y\)座標がともに整数であるような点のことを言う.

証明

(1) 二重積分

\(xy\)平面上の, 各辺が軸に平行である長方形\(T\)について, 頂点の座標が\((a,c),(b,c),(a,d),(b,d)\)であるとする.
すると
\[\begin{eqnarray}
\iint_T e^{2\pi i(x+y)}dxdy&=&\int^d_c\int^b_a e^{2\pi i(x+y)}dxdy \\
&=&-\frac{1}{4\pi^2}(e^{2\pi ib}-e^{2\pi ia})(e^{2\pi id}-e^{2\pi ic})
\end{eqnarray}\]より,
\[\begin{eqnarray}
\iint_T e^{2\pi i(x+y)}dxdy=0&\Leftrightarrow& b-a, d-cの少なくとも1つが整数\\
&\Leftrightarrow& Tがキチン長方形
\end{eqnarray}\]
である.
仮定より各タイルにおいてこの積分の値は0であるため、\(R\)全体でもこの積分の値は0. よって\(R\)がキチン長方形であることが示された. ■

これは定理の発見者オリジナルの証明だそうです.
どこから積分が出てくるんだ…? という気持ちになりますが, こう考えると自然です.
たとえば, 「8×8のチェス盤の右上と左下のマスを切り取る. これを1×2のドミノで埋め尽くせるか?」という有名問題がありますが, これはチェス盤を黒と白の市松模様で埋め尽くすことで, できないことが証明できます. ここで黒を1, 白を0と考えてみましょう. するとチェス盤の色塗りは\(\mathbb{R}^2\)から\(\mathbb{R}\)への関数とみなせます. そして「どうドミノを置いても黒を1つ覆う」は「どのドミノの区間積分しても1」と言い換えられます. この場合は1×2のドミノですが, 今回の定理の場合はキチン長方形です. 長方形の辺の長さは任意の正の実数になるので連続的です. この場合にもできるように考えると, 三角関数を使って連続的な色分けをすることが思い浮かぶかもしれません. 私は思い浮かびませんでした.
この場合は連続的な「色塗り」でしたが, 実は普通に市松模様でもできます(次証明).

(2) 市松模様

\(R\)を標準の位置に置く. \(xy\)平面を\(\frac 12 \times \frac 12\)のマス目で埋め尽くし, 黒と白で市松模様に塗る. このとき, 各辺が軸に平行な任意の長方形において,
キチン長方形⇒長方形上の黒と白の面積が等しい
特にそれが原点を頂点に持つならば
キチン長方形⇔長方形上の黒と白の面積が等しい
であるので定理が成り立つ. ■

これを見るとやはり「市松模様スゲー!」と思います.

(3) 市松模様2

\(R\)を標準の位置に置く. \(xy\)平面を\(\frac 12 \times \frac 12\)のマス目で埋め尽くし, 黒と白で市松模様に塗る.
ここで, 長方形の辺となる線分をずらして新しい長方形分割\(R'\)を作ることを考える.
タイルの辺で\(x\)軸に平行なものにおいて, それが直線\(y=a\)上にあるとき
・もし\(a\)が整数なら動かさない.
・そうでない場合, それを直線\(y=[a]+\frac 12\)上に動かす.
タイルの辺で\(y\)軸に平行なものにおいても同様に動かす. この操作においてあるタイルは潰されるかもしれないがそれは本質ではない(面積0のタイルと考える). この操作を行っても, 各タイルはキチン長方形である.
\(R'\)がキチン長方形であることが示されれば元の定理も証明される.
市松模様に戻ると, \(R'\)の各タイルは同じ数の黒い正方形と白い正方形を持つので, \(R'\)も同じ数の黒い正方形と白い正方形を持つからキチン長方形であることが示された. ■

タイルの辺を動かすという発想です. 動かすことでタイルの辺の取りえる値が離散的になりかなり扱いやすくなりました. このように, タイルの辺を動かす発想は今後もいくつか出てきます.

(4) 多項式

\(R\)を標準の位置に置き, (4)と同様に\(R'\)を作る. (4)に似たような方法で辺をずらすことを考える.
タイルの辺で\(x\)軸に平行なものにおいて, それが直線\(y=a\)上にあるとき

  • もし\(a\)が整数なら動かさない.
  • そうでない場合, それを直線\(y=a+t\)上に動かす.

タイルの辺で\(y\)軸に平行なものにおいても同様に動かす.
このとき\(t\)を\(0\leq t \leq \varepsilon \)の範囲で動かすと, \(\varepsilon\)が十分小さいときは\(t\)をどのように動かしても長方形がつぶれて消えることはない.
このときにそれぞれのタイルの面積がどのように変化するかを考える. \(t\)を動かしても, 長さが整数であるようなタイルの辺の長さは変化しないので, どのタイルも面積の変化は1次関数的である. よって\(R\)の面積の変化も一次関数的であり, \(R\)もキチン長方形である. ■

これは個人的にかなり好きです. これを見てから元の定理を見たとき, 自明に思えてしまいました. これは多次元にも容易に一般化できます.

(5) 素数

\(R\)を標準の位置に置く.
素数\(p\)に対し, \(R\)を原点中心に\(p\)倍に拡大する. これを\(R'\)とする.
次に\(R'\)のタイルの各辺について, それが直線\(x=a\)上にある場合はそれを\(x=[a]\)上にずらす. 直線\(y=a\)上にある場合はそれを\(y=[a]\)上にずらす. これを\(R''\)とする.
このとき\(R\)の各タイルはキチン長方形なので, \(R''\)の各タイルは少なくとも1つの辺の長さが\(p\)の倍数である. よってこれらの面積は\(p\)の倍数であり, したがって, \(R''\)の面積も\(p\)の倍数である. すると\(R''\)の少なくとも1つの辺の長さは\(p\)の倍数であり, すなわち\(R\)の少なくとも1つの辺の長さはもっとも近い整数との差が\(1/p\)未満である. 素数は無数にあることから, \(R\)のどちらかの辺は無数の\(p\)についてもっとも近い整数との差が\(1/p\)未満であるため, \(R\)はキチン長方形である. ■

市松模様に若干似ています. 素数がこんなところでも出てくるとは….

(6) オイラーパス

f:id:yootaamath:20181217115640p:plain
グラフ\(\Gamma\)を次のように定める(図参照):

  • 平面上の点であって, あるタイルの角となるもの全体を頂点とする.
  • 各タイルにおいて, \(H\)タイルでは横に, \(V\)タイルでは縦に頂点同士を辺で結ぶ.

ただし, 多重辺を許すものとする.
このとき, \(R\)の角を除くすべての\(\Gamma\)の頂点の次数は2または4である(その頂点に集まる長方形は2または4個であるため).
また\(R\)の角において次数は1である.
したがって, ある角から別の角へのパスが存在し, そのパスのすべての辺が水平・垂直方向に整数の長さであるから, \(R\)がキチン長方形であることが示された. ■

今までとかなり趣向が違う感じです. 今までは整数がとびとびの値しかとらないことを本質に使っている感じでしたが, 今回はそうではありません. 整数が加減法で閉じていることを本質に使っています. これを一般化することで\(R\)の部分加群についても似たようなことを示すことができるそうです.

(7) 二部グラフ

f:id:yootaamath:20181217115713p:plain
\(S\)を\(xy\)平面の格子点であってあるタイルの角となるもの全体の集合とする.
\(T\)をタイル全体の集合とする.
\(R\)を標準の位置に置き, 二部グラフ\(\Gamma'\)を次のように定める(図参照):

  • 頂点の集合は\(S\cup T\)である.
  • \(s\in S\)と\(t\in T\)は, \(s\)が\(t\)の角となるときに辺で結ばれている.

各タイルにおける仮定より, \(T\)の元の次数は偶数(0,2,4)である. また\(R\)の角とならない\(S\)の元の次数も偶数(2,4)である.
しかし原点においては次数が奇数(1)である.
よってグラフの次数の総和が偶数であることから, 原点以外に次数が奇数となる頂点が存在する. これは\(R\)の角にしかなりえないので, \(R\)はキチン長方形である. ■

(6)に似ています. 多重辺がなく, グラフについての簡単なことしか使わないのでこちらのほうが好きです.

(8) 数学的帰納法

f:id:yootaamath:20181217115733p:plain
\(H\)タイルの幅, \(V\)タイルの高さはともに1であるとしてよい(タイルを分割することができるので). このときの\(H\)タイルの個数で数学的帰納法を用いる.
もし\(H\)タイルが存在しない場合は自明である(レンガが積みあがっている感じ).
\(H\)タイルが存在すると仮定し, そのうちの1つを\(T_0\)とおく. このとき, もし\(T_0\)の上に接している\(H\)タイルがある場合は, そのうちの1つを\(T_1\)とおく. ない場合は, 図のようにして\(T_1\)タイルを作る.
f:id:yootaamath:20181217115743p:plain
このとき\(V\)タイルは\(V\)タイルのままであるので影響はない. \(T_2,T_3,\dots,T_m\)タイルにおいても同様に上に上に\(R\)の一番上までとっていく. 逆に, \(T_{-1},T_{-2},T_{-3},\dots,T_{-n}\)においても\(T_0\)から下に下に\(R\)の一番下までとっていく.
すると, \(R\)の下から上まで結ぶ\(H\)タイルの列\[T_{-n},\dots,T_{-1},T_0,T_1,\dots,T_m\]を構成できた. ここでそのタイルの列を抜き取り, 残った部分をガチャンと合わせることで, \(H\)タイルが少ない場合へと帰着できる.
よって数学的帰納法より示された. ■

ガチャンと合わせるのが気持ちよくて好きです.

まとめ

というわけで8種類の証明を紹介しました. お疲れ様でした.
全然別の角度からの証明方法があり, 非常に面白いと思っています. それがこれらの証明が好きな理由です.
自力で新しい証明をつくってみようと思ったのですが無理でした…

初等的解法の存在する角度の問題

日曜数学 Advent Calendar 2018 の11日目の記事です。
adventar.org

はじめに

これは名大の日本数学コンクール論文賞に応募したものです。
11月24日の名古屋大学の数理ウェーブで発表した内容です。

論文内容

数理ウェーブでの発表に用いたスライドです。
www.dropbox.com
論文よりもこちらのほうがまとまっているので。。。

概要

https://www.gensu.co.jp/saito/challenge/pdf/3circumcenter_d20180609.pdf
上の論文をもとに作成しました。

上の論文において、整角四角形の問題を、各線分の長さの等しい折れ線の問題に置き換えることで解いています。

ここで私は、その折れ線を代数的な考察をしやすくするために言い換えました。
具体的には、折れ線を第\(n\)次巡回群\(G=\{1,g,g^2,\dots,g^{n-1}\}\)の群環\(\mathbb{Q}[G]\)の要素とみなし、環準同型\(f:\mathbb{Q}[G]\rightarrow \mathbb{C}\)を\(g\mapsto \exp(2\pi i/n)\)と定めました。
(いきなり折れ線を複素数で入れ替えると折れ線の形の情報が失われてしまうと考えました。また失われた情報(みたいなやつ)が本質だと考えました。)
(今思うと\(\mathbb{Q}[x]/(x^n-1)\)としたほうがわかりやすかったような…実質同じですが)
そして折れ線の始点と終点を結ぶ直線の実数軸となす角度を求める問題は、\(\textbf{g}\in \mathbb{Q}[G]\)が与えられたときに\(f(\textbf{g})\)の偏角を求める問題と言い換えられます。
これはさすがに答えが有理数\(q\)を用いて\(2\pi q\)と表せる場合でないと初等的に解けないので、「\(\textbf{g}\in \mathbb{Q}[G]\)と整数\(k\)が与えられたときに\(f(\textbf{g})\)の偏角が\(2\pi k/n\)であることを示せ」という問題にします。これは\(\ker f\)の構造がわかるとうれしい問題で、実は\(\ker f\)が正多角形の組み合わせで表せるもの全体になっていることが言えてしまうため、その折れ線の問題が初等的に解けることが示されます。
(論文発表後に気づきましたが、arlie_reさんのブログにその証明とほとんど同じことが書いてありました。)
また、四角形の問題に限らず、\(n\)角形における角度の問題は、それがある基準を満たす(角度のわかる三角形を組み合わせて作図できる)ならば折れ線の問題に帰着できることを示しました。

生存報告 & 論文公開

最近忙しくて…ごめんなさい。

数学について

数オリの夏季セミに参加してきました。ホモロジーの初歩について勉強しました。
蛇の補題むっちゃすごい!!という感じです。
数学甲子園の本選が近いので頑張ります。

競プロについて

青coderになりました。黄色を目標に頑張ります。
あとPCK予選も近いので頑張ります。

付録(というかこれがメイン)

せっかくなので4年生のときに作成した論文を公開します。
(学校で論集の作成があって、そのときに作ったもの)
多項式についての考察です。
www.dropbox.com

水色になるまでにやったこと

AtCoder水色になれました。(id: dama_math)
(競プロ界隈、色が変わったら記事にする文化があるらしいので記事にしました)
f:id:yootaamath:20180527082016p:plain

やったこと

ちょうどひと月半前に競プロを始めました
C++の基本事項を学びました
多少のデータ構造を学びました
多少グラフを実装できるようになりました
400点を多少解けるようになりました

今後の目標

とりあえず蟻本を読み進めて夏休みの終わりまでに青色になります

生存報告

ブログを最近全然更新していないので、生存報告です。

数オリのほうは日本代表になれませんでした。
まあ来年もあるので、次回は日本代表になれるよう頑張ります。

最近は競プロと代数的整数論をやってます。
競プロは4月11日に始めたばかりなので何もわからない状態ですが頑張っていきたいと思います。
代数的整数論は雪江整数論1でやっています。楽しいので6月中には読み終えたいです。
できたら代数的整数論のメモ・自分の考察的なやつをブログに載せたい…

ネタがあったらぼちぼち更新していきます。

2018APMO受験記

APMO(アジア太平洋数学オリンピック)受験してきました~

APMOとは?

APMO(アジア太平洋数学オリンピック)は、その名の通りアジアと環太平洋地域の国々が参加する数学オリンピックです。
試験の形式は4時間5問で、JMOと同じですね。
国際大会なわけですが海外に行けるわけではなく、試験は国内の会場で受け、その成績を主催国でまとめるという形になっています。
日本では、過去JMO入賞者(高3も含む)のみが試験資格を持つ形です。

問題ごとの感想

1

簡単でした。15分くらいで解けました。図を書くのがやや大変な気がしますが、書いてしまえばもう解けたようなものですね。
共通接線を引く→いろいろそれに乗っていることが分かる→構図→外心 みたいな感じ。

2

実はこれは一番後に解けた問題です。不等式が苦手なので…
\(x\)の周辺でおおむね値が決まる&それ以外はほぼ影響しない ということを証明すればいい感じですね。
けっこうガバガバ評価でいけます(僕は\(>\frac{5}{2}\)の証明を答案に書いた)。最小値はいくらなんでしょうね?

3

グラフについての基本的な知識があれば\(n\)が偶数であることがすぐにわかります。あとは構成ゲー。6個でできたパーツと8個でできたパーツをぐるっとつなげてやる感じで構成しました。最初は全然なさそう…と思っていましたが、ほとんどの偶数でできるというのが分かるとおおおって思いました。割と好きです。

4

まあ「やればできる」問題ですね。構成ゲーに近いところもある気がします。そんなに面白くなかったです。

5

見た目はきれいそうですが、全然わかりませんでした…
ぬさんによると、線形代数で解けるようです。

結果

35点中28点でした。たまたま自分に合った問題が出たおかげですかね。

2018JMO受験記

予選

予選はうまくいったんじゃないでしょうか。
第28回(2018年)JMO予選の問題

問題ごとに感想

問題1

算数パズルみたいで面白いですね。

問題2

1つ1つ数えていけば解けますね。はい。

問題3

まあ長さを変数にして連立方程式を解けばいいんでしょ
→解けない。焦る。
→面積を考えてみたら解かなくてもいいことがわかってわろた

問題4

まあやるだけですね。

問題5

簡単だけど面白い

問題6

まず図を正しくかけてるか何度も確認
→答えが想像以上に汚くなってかなり心配になった

問題7

ぱっと見難しそうだなーってとばしてたけど、よく考えたらそんなに難しくないじゃん

問題8

すこし妥協が必要な問題ですね

問題9

幾何は得意だからなーって思ってやってみて、割と苦戦した

問題10

見た目ヤバいし、10番目だし難しいんだろうなーって思って最後に手を付けた
解けなくてもいいやって思った
→意外とわかることがあって面白い!!

問題11・12

時間もないし、あきらめた

全体の感想

後輩と10問答えが同じで安心。
解いてて楽しかったですね。特に10番とか。
(実際10点だった)

本選

第28回(2018年)JMO本選の問題

時系列順

試験開始
→問題をざっくり見る。
→幾何が2しかないじゃん、つらい
→1番、\(\gcd(a^2b^2+3, a^2+b^2+2)\)とか謎でしかない
→しかも「最後に残った数が平方数でない」ってヤバい
→3番、見た目が気持ち悪い
→4番、マス目に数字を書いてく問題か、苦手だなあ
→5番はしーらね
→2番を考える
→緊張して手が震えて図がうまくかけない
→お菓子を食って緊張をほぐす
→簡単じゃん、つらい(ここまで20分)
→1番に手を付ける
→\(\gcd(a^2b^2+3, a^2+b^2+2)\)をいろいろ計算してみる
→3の倍数ばっかりだなー
→閃く!! 3の倍数の個数の偶奇が変わらない!!
→やったぜ。(ここまで40分)3か4のどちらかを完答したい。
→3番と4番、交互に少しずつ考えながらやっていく
→全然進展しない(ここまで2時間30分)
→頭を冷やすために1番と2番の解答を書く
→3番、周期の約数を考える
→むっちゃいろいろわかる!
→解けた!! やった!!
→4番に移る
→全然わかんねえな、3番の解答を書くか
→4番に戻る
→お!? 解けた!! やった!!
→時間ないし急いで解答かこう
→(書きながら)…あれ?この解答嘘じゃね?
→まあしょうがない、このステップの後を書けば部分点もらえるか
→そのあとのステップも嘘じゃん、つら(残り10分)
→修正できそうにないな、解答の見直しをしよ

問題ごとの感想

問題1

3の倍数の個数に注目すればすぐ解けますが、気づかなければ全然進まないような問題かと思います。
1番級にしては難しいのではないでしょうか。

問題2

幾何の問題に慣れていたのですぐ解けましたが、Twitter上では「難しい」という意見もまあまあありました。

問題3

なかなか見ないタイプの問題で、大変だったと思います。
周期の約数を見るという発想ができるかどうか。
ただ部分点は取りやすい問題だったと思います。

問題4

わかりません

問題5

わかりません、ただ部分点は稼げたかもしれないので、後悔しています。

結果

(18/2/21 追記) 銅賞でした!! やったぜ。