数学好きの塗り絵 - 偽計数学妨害罪

こんにちは、108Hassiumです。

突然ですが、皆さん塗り絵はお好きでしょうか？

私は、昔は嫌いでした。

選色センスがどうのこうのとかいう以前に、そもそも色を均一に、はみ出さずに塗ることができません。

ところが、文明の利器【PC】の登場により、状況は一変します。

Windows paintに代表される大抵のペイントソフトには、「塗りつぶし」という機能があります。

その名の通り指定範囲を塗りつぶす機能で、まさに均一に色を塗るために存在する機能です。

この機能により、こんなに複雑な図形でも美しく塗り分けられるようになりました。

何？

おそらく多くの人が「いきなり何を見せられてるんだ」って感じになったと思うので説明します。

「東京オリンピックエンブレム盗作騒動」って覚えてますか？

覚えてない人や知らない人のために説明すると、2020年の東京オリンピックの公式エンブレム案に盗作疑惑が浮上し撤回された、という騒動です。

その疑惑のエンブレムについて、「3×3に分割した正方形を使うのはよくある基本的なデザイン手法である」といった感じの情報を目にしました。

それを見て私はこんなことを考えました。

「3×3の格子点を全部結んだらどうなるんだろう？」

ようするに、こういう事です。

「格子点」はマス目の角のことで、それら全てを斜めに結んでみたということです。

これが完成したとき、私は思いました。

というわけで塗り分けました。

どうやら6×6は、奇数個の領域が集まる点があるため、2色での塗分けは不可能なようです。

延長

ここで終わってしまうのは面白くないので、抵抗を試みます。

先程のものは「n×nの格子点の内の2つを結ぶ線分をすべて重ねた図形」なので、奇数本の線分と繋がるような格子点がある場合には塗り分け不可能となってしまうのでした。

そこで、今度は「n×nの格子点の内の2つを通る直線をすべて重ねた図形」を考えてみましょう。

要するに、

これが、

こうなります。(枠の外は無視します)

こうすることで、格子点には常に偶数本の線が集まるようになるので、必ず2色で塗り分けられるようになるはずです。

というわけで、

塗りました。

そして、

冒頭のデカい画像は、7×7でした。

疑問

ここまで読んだ人の中にはいろいろと疑問に思っている人もいると思いますが、そういう話をする前にいくつかの単語を定義します。

まず、「m×nの格子点の内の2つを結ぶ線分をすべて重ねた図形」を「m,n総格子図形」、「m×nの格子点の内の2つを通る直線をすべて重ねた図形」を「m,n延長総格子図形」と命名します。

オリンピックエンブレム案の話から思い付いたやつは「3,3総格子図形」で、その前に出てきたデカいやつが「7,7延長総格子図形」です。

というわけで、ここから私が抱いた疑問をぶちまけていきたいと思います。(全部未解決です)

線、何本あるの？

めっちゃたくさんありますが、どのくらいあるのか気になりました。

といっても実際に数えるのは面倒臭すぎるので、大まかな数を計算してみます。

まず、m×nの格子の格子点の数は $(m+1)(n+1)$ です。

全ての線分は格子点を結んでいるので、「 $(m+1)(n+1)$ 個の点から2個の点を選ぶときの選び方の数( $={}_{(m+1)(n+1)}C_2$ )」よりは少ないはずです。

${}_{(m+1)(n+1)}C_2=\frac{(mn+m+n+1)(mn+m+n)}{2}=\frac{m^2n^2+2m^2n+2mn^2+3mn+m^2+n^2+m+n}{2}$

どうやらmを固定したときは2次式、m=n(正方形)だと4次式で上から抑えられるようです。

てっきり指数関数的に増えるものだと思っていたので、思ってたよりは少ないですね。

m,n総格子図形が2色で塗り分けられるm,nの条件は？

6,6総格子図形は塗り分け不可能だったわけですが、他の組み合わせはどうなるのでしょうか。

調査結果がこちらです。

◯

めちゃくちゃ×が多いです。

ちなみにどうやって調べたかというと、

こういうものを作って、

白い点を長方形の格子点(辺上のものは除く)に合わせ、

長方形と重なった点の数を数え、

・奇数だったら不可能
・全部偶数だったら可能

と判定します。

判定原理の説明は面倒なので省きます。

3色でも塗り分けられない総格子図形ってあるの？

「四色定理」ってご存知ですか？
ja.wikipedia.org

簡単に説明すると「平面図形は4色で塗り分けられる」という定理です。

四色定理が成り立つという事は、総格子図形は4色使えば塗り分けられることになります。

しかし実際に試してみると、3色だけで塗り分けられそうな気がしてきます。

奇数領域の格子点を繋ぐように第3の色を塗って、残りを2色で塗ればいいように思えます。

4色フルに使わないといけないパターンはあるのでしょうか。

7角以上の多角形って出てくるの？

3,3総格子図形は3角形と4角形で構成されていますが、4,4総格子図形には5角形があります。

そして、5,5総格子図形をよ～く観察すると、6角形が含まれています。

※分割されていないもののみを扱います

では、7角以上の多角形は出てくるのでしょうか？

根拠はないですが、私は「いくらでも角数の多い多角形が出現する」と予想しています。

自動化

色
塗
る
の
面
倒
臭
ぇ
～

すみません、突然本音が出てしまいました。

文明の力により自動塗りつぶしが可能になったものの、それでも面倒臭すぎます。

何とかして自動化できないでしょうか？

できました。

グラフ描画ソフト「Desmos」により、2,2(延長)総格子図形の自動彩色に成功しました。

これには以下の2つの定理を利用しています。

$f(x,y)g(x,y)=0$ のグラフは、 $f(x,y)=0$ のグラフと $g(x,y)=0$ のグラフを重ねたものになる

$f(x,y)g(x,y)≥0$ のグラフは、 $f(x,y)g(x,y)=0$ のグラフを2色に塗り分けたものになる

例えば $f(x,y)=x^2+y^2-4$ 、 $g(x,y)=xy+1$ とすると、

こうなります。

延長総格子図形を描くには直線の式を掛けまくればいいので、2,2延長総格子図形を表す式は　xy(x-1)(y-1)(x-2)(y-2)(y-x)(y-x+1)(y-x-1)(y+x-1)(y+x-2)(y+x-3)(y-2x)(y-2x+2)(y+2x-2)(y+2x-4)(2y-x)(2y-x-2)(2y+x-2)(2y+x-4)≥0　になりました。

さて、やり方が分かったので次は4,4を描いてみましょう。

約3時間にわたる試行錯誤の結果、4,4延長総格子図形を表す式　x(x-1)(x-2)(x-3)(x-4)y(y-1)(y-2)(y-3)(y-4)(y-x)(y-x+1)(y-x+2)(y-x+3)(y-x-1)(y-x-2)(y-x-3)(y+x-1)(y+x-2)(y+x-3)(y+x-4)(y+x-5)(y+x-6)(y+x-7)(y-2x)(y-2x+1)(y-2x+2)(y-2x+3)(y-2x+4)(y-2x+5)(y-2x+6)(y-2x-1)(y-2x-2)(y+2x-2)(y+2x-3)(y+2x-4)(y+2x-5)(y+2x-6)(y+2x-7)(y+2x-8)(y+2x-9)(y+2x-10)(2y-x)(2y-x+1)(2y-x+2)(2y-x-1)(2y-x-2)(2y-x-3)(2y-x-4)(2y-x-5)(2y-x-6)(2y+x-2)(2y+x-3)(2y+x-4)(2y+x-5)(2y+x-6)(2y+x-7)(2y+x-8)(2y+x-9)(2y+x-10)(y-3x)(y-3x-1)(y-3x+2)(y-3x+3)(y-3x+5)(y-3x+6)(y-3x+8)(y-3x+9)(y+3x-3)(y+3x-4)(y+3x-6)(y+3x-7)(y+3x-9)(y+3x-10)(y+3x-12)(y+3x-13)(3y-x)(3y-x+1)(3y-x-2)(3y-x-3)(3y-x-5)(3y-x-6)(3y-x-8)(3y-x-9)(3y+x-3)(3y+x-4)(3y+x-6)(3y+x-7)(3y+x-9)(3y+x-10)(3y+x-12)(3y+x-13)(y-4x)(y-4x+4)(y-4x+8)(y-4x+12)(y+4x-4)(y+4x-8)(y+4x-12)(y+4x-16)(4y-x)(4y-x-4)(4y-x-8)(4y-x-12)(4y+x-4)(4y+x-8)(4y+x-12)(4y+x-16)(2y-3x)(2y-3x-2)(2y-3x+1)(2y-3x+3)(2y-3x+4)(2y-3x+6)(2y+3x-6)(2y+3x-8)(2y+3x-9)(2y+3x-11)(2y+3x-12)(2y+3x-14)(3y-2x)(3y-2x+2)(3y-2x-1)(3y-2x-3)(3y-2x-4)(3y-2x-6)(3y+2x-6)(3y+2x-8)(3y+2x-9)(3y+2x-11)(3y+2x-12)(3y+2x-14)(3y-4x)(3y-4x+4)(3y+4x-12)(3y+4x-16)(4y-3x)(4y-3x-4)(4y+3x-12)(4y+3x-16)≥0　を求めることができました。

ペイントで手動で線を引いて色を塗るよりも時間がかかったような気がしますが、あとはこの式をDesmosに渡せば一瞬で、