ますぱら

代数とか、パズルとか、素数大富豪とか

パズルと不定方程式 ~立体編~

気づいたら6月になってました。前回の記事が5月7日だったので、ほぼ一か月ぶりの更新です。書きたいテーマはいくつもあるのでもっと書かなきゃなあと思います。

 

 

今日のテーマはこれです。現在、神保町のみらい研究所に置かせてもらっているパズルです。

 

f:id:K-Miura:20170604222310j:plain

 

二種類のピース、合計10個を箱に詰めるのが目的。ピース構成は以下のとおりです。

 

f:id:K-Miura:20170604183448j:plain

 

大きい方(以下「ピースA」と呼ぶ)が6単位分、小さい方(以下「ピースB」と呼ぶ)は4単位分のピースで、箱(一合升)は4×4×3=48単位分の直方体です。

 

6×4+4×6=48

 

なので、体積としてはぴったり。そしてなんと驚くことに、このパズルの解は対称なものを除くとただ一通りなのです(コンピュータで確かめました*1)。

 

でも、もしかすると、ピースAとピースBのそれぞれの個数を変えれば、この二種類で一合升をぴったり埋める方法が他にもあるかもしれない。今回は不定方程式を使って、この問題を考えていきます。

 

 

ピースAをa個、ピースBをb個使って一合升を埋めるとすると、

 

6a+4b=48

 

という等式が成立していなければなりません(今は「二種類のピースを使う」ということなので、a,bはともに正の整数とします)。

この不定方程式の解(a,b)は一通りではないですが、実はある工夫をすると、もっと強い条件を表す方程式を立てることができます。

 

f:id:K-Miura:20170604183534j:plain

 

この図は、各ピースと4×4×3の箱を、隣接する単位立方体が異なる色になるように青と緑で色付けした様子を表しています。一つの形に対して二つの塗り方がありますが、直方体については回転によって同じものだと分かります。

ここで、それぞれの形における青と緑の数を数えてみます。

まず、直方体の箱については当然、青と緑は24個ずつ。ピースAについても、(塗り方は二種類ありますがどちらも)青と緑が3個ずつです。しかしピースBは、「青1個と緑3個」または「青3個と緑1個」になっている。これが重要です。

 

塗り方の違うピースを別物と考えて、改めて

 

f:id:K-Miura:20170604183629j:plain

 

と呼ぶことにしましょう。すると、「AとBの二種類で一合升を埋める」という問題は「A_1,A_2,B_1,B_2を使って色が合うようにCを作る」という問題に置き換えられます。ただし、後者については「A_1とA_2は少なくとも一方は使う」「B_1とB_2は少なくとも一方は使う」という条件付きです。

 

使われるA_1,A_2,B_1,B_2の個数をそれぞれa_1,a_2,b_1,b_2とおくと、青の立方体の個数について

 

3(a_1+a_2)+b_1+3b_2=24\,\,\,\,\,\,\,\,\,\,\,\,(1)

 

という式が立ち、さらに緑の立方体の個数について

 

3(a_1+a_2)+3b_1+b_2=24\,\,\,\,\,\,\,\,\,\,\,\,(2)

 

が成り立つはず。ここでa_1,a_2は非負整数で少なくとも一方は正、b_1,b_2も非負整数で少なくとも一方は正です。この不定方程式を解いてみます。

 

 

まず、(1)からb_13の倍数であること、そして2式の差からb_1=b_2であることがわかるので、

 

b_1=b_2=3k

 

と書けます(kは正整数)。これを(1)に代入して両辺を3で割ると

 

(a_1+a_2)+4k=8 

 

が得られ、a_1+a_2,kは正なのでa_1+a_2=4,k=1(すなわちb_1=b_2=3)となります。つまり結局

 

(ピースAの個数)=a_1+a_2=4

(ピースBの個数)=b_1+b_2=6

 

が個数の組み合わせとしては唯一で、この二種類で一合升をぴったり埋める方法は他にはないことがわかりました。

 

 

なお、式(1)と式(2)を足し合わせると

 

6(a_1+a_2)+4(b_1+b_2)=48

 

となり、これは最初の不定方程式

 

6a+4b=48

 

と同じものです。なので(1),(2)式は、最初の式を「色分けによって精密化した」ものだと考えられます。この色分けの方法は平面だと市松模様と呼ばれる塗り方なので、今回のような議論は「市松理論」と呼ばれることもあるようです。岩澤理論みたいでかっこいいですね!

 

 

それでは今日はこの辺で。

*1:BurrToolsというソフトを使っています

人力素数判定をしよう!

みなさんこんにちは。倍数判定の時間です。

素数大富豪をしているとき、あるいは街中で見つけた自然数素数かどうか気になったとき。私たちが日常生活を送るうえで、倍数判定力(素数判定力)を問われる局面は多々あると思います。今日は私がそのような場面でどのように考え、どのように素数と出会っているかを紹介するため、倍数判定法の記事を書きます。


与えられた自然数nが素数かどうかを人力で判定するとき、√n以下の素数で割ってみる「試し割り」以外に有用な方法はほとんどないでしょう。「素数pで割れるかどうか」は「素数pの倍数かどうか」と同じことなので、実際には素数の倍数判定が重要になってくるわけです。小さい素数から順に、倍数判定法を見ていきましょう。


2,3,5の倍数判定 ~一の位チェック&桁和チェック~

一の位が偶数なら元の数も偶数であり、一の位が5か0なら5の倍数です。また各桁の和が3の倍数なら元の数も3の倍数です。

例:5123874は2の倍数。83025は5の倍数。また5+1+2+3+8+7+4=30と8+3+0+2+5=18は3で割れるので、この二数は3の倍数でもある。

〈追記〉
要は、一の位が1,3,7,9のいずれかでないと2か5で割れてしまいます。
また、3の倍数判定については「桁和が3で割れるか否か」をチェックできればいいので、
・3の倍数の部分が見えたら消す
・等差数列をなす三整数は消す
を使うと早いです。たとえば458881479は、先頭の45と末尾の9を消すと888と147という二つの等差数列が残るので3の倍数です。

7,11,13の倍数判定 ~1001チェック→91&交代和チェック~

7*11*13=1001なので、判定したい自然数nから1001の倍数を引いても、「7の倍数かどうか」「11の倍数かどうか」「13の倍数かどうか」の性質は変わりません。さらにここから7と13の倍数判定については、7*13=91の倍数を引いていって確かめることができます。また、nの偶数桁の和と奇数桁の和との差を計算して11で割れるかどうか確かめれば、nが11の倍数かどうかを確かめたことになります(証明は略)。

例:3157から1001*3=3003を引くと154であり、154から91を引くと63である。63は7では割れて13では割れない。また154の偶数桁は5のみで奇数桁の和は1+4=5であり、5-5=0は11の倍数。よって3157は7と11の倍数であり13の倍数ではない。

7*11*13が1001であることには数の神秘を感じずにはいられません。なお、91を使った倍数判定は今年1月にtsujimotter氏により見出されました。

tsujimotter.hatenablog.com

ここまでは、素数大富豪プレーヤーをはじめとする多くの方がご存知の手法かと思います。本題はここからです。

〈追記〉
特に6桁の数を判定したい場合、「上3桁と下3桁の差を計算する」ことが「1001の倍数を引く」操作になっているので、上3桁と下3桁が近い数のときは1001チェックはとても早く終わります。例えば108109は上下の差が1なので7,11,13では割れません。
108のような2,8で終わる3桁の3の倍数の下に一つ違いの数を付けると13以下の素因数を持たない整数となり、素数の期待が高まります。その中で
・102101,102103
・108107,108109
・192191,192193
・312311,312313
・342341,342343
・522521,522523
・612611,612613
・822821,822823
・882881,882883
は双子素数です。闘会議をきっかけに調べてみました。

twitter.com


17以上の倍数判定① ~3p法~

これは私が17以上の倍数判定をする際に最もよく使っている方法です。簡単に言うと「自然数nに素数pまたはその三倍(3p)を足すか引くかして一の位を0にする」方法で、以下の事実に基づいています。

  • 一の位が1,3,7,9のいずれかである自然数nおよび7以上の素数pに対して、n+p,n-p,n+3p,n-3pのどれか一つが10の倍数になる。

つまり、pや3pを使えば一の位を0にできるのです。一の位の0は取って考えてよい(7以上の素数pについて、「10で割る」という操作は「pの倍数かどうか」には影響しない)ので、これで桁数を一つ減らせたことになります。
そして、桁を減らした後の数が2や5で割れるなら、一の位が1,3,7,9になるまで割りましょう。そうすれば再び3p法を適用できます。

例:1121から17*3=51を引くと1070であり、0を取った107は素数なので17で割れない。しかし1121に19を足すと1140であり、0を取った114は2で割ると57である。これは19*3である。よって1121は17の倍数ではないが19の倍数である。

17以上の倍数判定② ~概数法~

これは、判定したい自然数nの上3桁くらいを見てpの倍数が思い浮かんだときに有効な方法です。3p法に比べると自明なやり方ですが、うまく使い分けるとスピードが上がります。3p法が「下の位から攻める」のに対して、概数法は「上の位から攻める」方法です。

例:1021は4桁の数だが、上3桁を見ると102であり、102は17の倍数である。よって1020が17の倍数であり、1を加えた1021は17の倍数ではない。



さて、紹介する倍数判定法は以上ですが、最後にここまでの内容を踏まえて、1187が素数であることを確かめる手順の一例を解説します。

  • 1187の一の位は7なので、2,5では割れない。また桁和は1+1+8+7=17なので3の倍数でもない。(一の位チェック&桁和チェック)
  • 1187から1001を引くと186であり、186から91を2回引くと4が残る。当然4は7や13では割れない。また186の偶数桁和は8、奇数桁和は1+6=7であり、8-7=1は11で割れない。(1001チェック→91&交代和チェック)
  • 1187から17を引くと1170であり、0を取った117から再び17を引くと100なので17では割れない。また1187から19*3=57を引くと1130であり、0を取った113は素数なので19で割れない。(3p法)
  • 115は23の倍数、116は29の倍数である。1187-1150=37は23で割れず、1187-1160=27は29で割れない。(概数法)
  • 1187に31*3=93を足すと1280であり、これは見るからに2,5以外の素因数を持たず31で割れない。(3p法)

37^2>35^2=1225>1187なので、ここまでで1187が素数だと分かったことになります。



なお、17以上の素数の倍数判定については、29など簡明な方法が見つかっているものもあります。

tsujimotter.hatenablog.com

これらを併用できればより効率よく素数判定を進められるかもしれません。


それでは今日はこの辺で。

素数体操のコツとトレーニング

みなさんこんにちは。素数大富豪効果もあり、最近素数がブームですね。テレビのニュースでも毎日のように素数を見かけます。

この流れに乗ってメディアに取り上げられてもおかしくない素数コンテンツとして、鯵坂もっちょさんによって提唱された素数体操」があります。

※知らない方は以下のリンクを参照してください

togetter.com


素数になるところの四股を曲げるこの体操はなかなか難易度の高いものです。
私は先日、トランポリンのある施設で素数体操を踊ってきました。

twitter.com


バランスを保つのが難しい!

素数の出現タイミングが不規則なためですね。
でもせっかくなのでもっと上手に踊れるようになりたい。なので今回私は、素数の性質と人間の動きの観点から、素数体操のコツを探っていきたいと思います。


さて、素数体操の特徴を考えるために、素数の性質(分布)と素数体操との関係を見ていきます。素数は不規則に現れるとはいえ、素数体操において重要な一桁目(一の位)については比較的わかりやすい特徴があります。以降、単に「①素数」と書いて、一桁目が1である素数を表します(③素数、⑦素数、⑨素数についても同様)。

 

素数体操の特徴その1:同じ側の手足を同時に曲げることが多い】

 
もっちょさんも指摘しているように、右手右足を曲げる「①,⑦素数」、左手左足を曲げる「③,⑨素数」は頻繁に現れます。歩いているときのように手足の動きが逆の方がバランスを取りやすいのですが、「①,⑨素数」や「③,⑦素数」は少ない。素数体操が我々に与える最初の試練です。

motcho.hateblo.jp

※この記事での「右」、「左」の呼び方は曲げるべき四股の右、左とは反対になります

 

手足の同じ側を同時に曲げる際のポイントは、体幹をしっかり引き締めることです。腹筋、そして背筋で伸ばしているほうの手足をしっかり支え、もう一方の手足を素早く曲げる。体の軸がぶれないように注意しましょう。

  

素数体操の特徴その2:四股はどこも、いつまでも使い続ける】


1,3,7,9は10と互いに素なので、ディリクレの算術級数定理*1より①,③,⑦,⑨素数がそれぞれ無限個あることがわかります。 
つまり途中から使わなくなる部位はありません。体幹を鍛えたあとは両手両足をまんべんなく強化しましょう。


素数体操の特徴その3:左手と右足は曲げる機会がやや多い】

 

「チェビシェフの偏り」というものをご存知でしょうか。

integers.hatenablog.com

 

算術級数素数定理*2より、①,③,⑦,⑨素数の割合は漸近的には25%です。しかしせきゅーんさんのブログに詳しく記述があるように、③,⑦素数は①,⑨素数よりやや多く現れます。つまり素数体操では、右手や左足よりも左手や右足を曲げる機会のほうが多くなりやすいのです。もし体幹と両手両足のすべてを鍛え終えたのなら、念のため左手と右足を+ \alphaで鍛えておくことをお勧めします。

…とはいえ、仮に1万まで素数体操を踊ったとしても素数の個数はそれぞれ

素数:306個
素数:310個
素数:308個
素数:303個

なので、ほとんど違いはないですね。10万、100万まで踊りたい上級者のための追加トレーニングといえるでしょう。

※100万までを1ポーズ1秒で踊ると約27時間47分かかります(MATH POWERには収まる)。

 

 

最後に、普通の地面で踊る場合とトランポリンの場合とに分けて、補足を書きます。


(ⅰ)普通の地面の場合
両足を曲げるときにしゃがむことになるので、スクワットで足を重点的に強化しましょう。なお、両足を曲げるのは⑦素数と⑨素数が双子素数として現れる時なので、

素数体操でしゃがむ機会は無限回あるか?」

は双子素数予想よりも強い未解決問題です。

 

(ⅱ)トランポリンの場合
場外に出ないように真上に跳び続けるのはとても難しいので、「次なんだっけ?」などと考えている暇はありません。またトランポリンは競技としては一演技で10個の技を行うので(私は上の動画では11回跳んでしまっている)、例えば『規定演技:800台』などと決めて素数体操に対応した10個のアクロバットを競うスポーツも面白そうです(四つ子素数なら抱え込み宙返り、素数砂漠なら伸身宙返り、その他未定)。

 

 

素数体操には素数の性質がいろいろ表れていることがわかりました。特に上記のせきゅーんさんの記事にはまだまだ素数体操のヒントがありそうです(記事の本題はむしろ特徴1「同じ側の手足を同時に曲げることが多い」に深く関係している)。そして何より、素数を覚えるために考案された素数体操が、素数の性質を体感する手段となっていることが大変面白いですね。

 

素数大富豪世界一の次は、素数体操世界一を目指します。それでは今日はこの辺で。

パズルと不定方程式 〜平面編〜

みなさんこんにちは。新年度いかがお過ごしでしょうか。年度が変わったときによく使う言葉に「新生活」というのがありますが、私にとっての新生活はまさにこのブログを始めた生活です。

 

最初の内容として書こうと思った記事はいくつかあるのですが、私が4月から入会したパズル懇話会の例会がちょうど一昨日あったので、今日はそこで発表したパズルを数学的に解説します。

 

f:id:K-Miura:20170417225752j:plain

 

こちらがその「台形パズル」です。最小単位を1としたときのピースの寸法は

f:id:K-Miura:20170417153405j:plain

こうなっています。ルートが登場するととたんに数学感が出ます(笑)

図のように、相似比1:\sqrt2の二つの長方形を同じ形で切り分けてできた6枚のピースで、一つの長方形を作るのが目的です。

 

 

ところで、平面のパズルと聞いたとき、もしかすると多くの方はジグソーパズルを思い浮かべるかもしれませんね。ジグソーパズルも形としては長方形を作るのが目的なので台形パズルと似ています。でも、この台形パズルのような「シルエットパズル」と呼ばれるタイプのパズルは、ジグソーパズルとは解き味が全然違うのです。

 

ジグソーパズルは、たとえば四隅のパーツを見つけた後、その隣に何がくるかは絵やピースの形から判断できます。四隅を決めて、辺のピースをつないでいき、中を埋める。少し言葉は悪いですが、そうやって時間の問題でジグソーパズルは完成します。

 

一方のシルエットパズルは、目的が「長方形を作る」だったとしても、まずどれを隅に置くべきかわからない。そして隅のピースを決めたとしても、その隣に何をどの向きで置くべきかわからない。場合の数が膨大で、試行錯誤だけでは解けないことが多いと思います。

 

 

そんなときに使うのが代数です。

 

 

たとえば、この台形パズルを解こうとして、図のようにまず一番大きなピースを左下の隅に置いたとします。

f:id:K-Miura:20170417230338j:plain

この次に、今置いたピースの相似形のピースを右隣に、このように置くと…

f:id:K-Miura:20170417225234j:plain

実はこれ、この時点で「詰み」なのです。パズルに慣れている方はもうお気づきでしょうか?

なぜこれではダメなのか。順を追って説明します。

 

 

まず、この6ピースを全て使って図形を作るということは、面積は必ず24になります。

f:id:K-Miura:20170417230919j:plain

今は長方形を作りたいので、縦と横の長さをそれぞれx,yとおくと

 

xy=24

 

です。縦の長さは横の長さ以下、すなわちx\leqq yとしておきましょう。

ここで問題となるのが、xyとしてどんな数を考えるかということ。もし整数だけを考えるのなら24の約数を考えればよく、「\mathbb{Z}上での因数分解」をすることになりますが、今は違います。

 

そう、\sqrt2がいるのです。

 

\sqrt2の整数倍の長さの辺を使えるので、今は\mathbb{Z} \left[\sqrt2 \right] 上での因数分解を考えるべきなのです。

 

まさに代数学。パズルを理詰めで考えようとしたときに数学が出てくるととても楽しいですね(個人の見解)。

 

さて、\mathbb{Z} \left[\sqrt2 \right] 上での因数分解をするために、改めて

 

x=a+b\sqrt2\,\,,\,\,y=c+d\sqrt2\,\,\,(a,b,c,d \in \mathbb{Z})

 

とおいて、方程式

 

(a+b\sqrt2)(c+d\sqrt2)=24

 

を考えます。しかし困ったことに、\mathbb{Z}上での因数分解と違って、この方程式には無数の解があるのです(ペル方程式に関する知識を用いて証明できます)。

 

それらの無数の解について議論するほうが数学的には有意義かもしれませんが、今はパズルに専念しましょう。何をするのかというと…

 

a,b,c,d\,はすべて非負整数

 

として考えます。今回の6つのピースには確かに\sqrt2が登場しますが、辺の長さを足し合わせて作れる長さは、「非負整数と\sqrt2の非負整数倍との和」に限られます。-1-\sqrt2は作れないのです。

 

改めて問題を書くと、

 

(a+b\sqrt2)(c+d\sqrt2)=24\,\,\,(a,b,c,d\,は非負整数)

 

変形すると

 

(ac+2bd)+(ad+bc)\sqrt2=24\,\,\,(a,b,c,d\,は非負整数)

 

このようになります。もしここでad+bc\neq 0だとすると\sqrt2の無理性に反するので

 

ad+bc=0

 

です(1\sqrt2\mathbb{Q}上一次独立と言っても良い)。

 

a,b,c,d \, は非負整数」という条件が効いてきます。結局

 

ad=bc=0

 

となります。

a=b=0\,のときは\,x=0\,\,c=d=0のときは\,y=0\,となり不適ですので、あり得るのは

 

  • a=c=0\,\,\,(このとき\,x=b\sqrt2\,,\,y=d\sqrt2\,,\,bd=12\,)
  • b=d=0\,\,\,(このとき\,x=a\,,\,y=c\,,\,ac=24\,)

 

の2パターンですね。

 

これでようやく、前述の置き方がダメな理由を説明できます。すなわち、

長方形の一辺の長さとして1\sqrt2の両方が登場するはずがない

のです。6ピース全部を考えると、

f:id:K-Miura:20170417153416j:plain

この図の赤の辺と青の辺を並べてはいけないことになります。

f:id:K-Miura:20170417225245j:plain

 なお、一番大きなピースはどの向きで置いても幅が2\sqrt2以上なので、最終的に以下の4通りまで絞れます。

 

(x,y)=(2\sqrt2,6\sqrt2)\,,\,(3,8)\,,\,(4,6)\,,\,(3\sqrt2,4\sqrt2)

 

この中で二つ、実際に長方形を作れる比率が存在します。

みなさんぜひ、厚紙などで作って遊んでみてください。また私は火曜日のみらいけん数学デーに毎回このパズルを持って行っているので、そのときに声をかけていただけると中の人が喜びます。

 

 

数学を使ってパズルを考えるのは本当に面白いです。実は一昨日私が発表したパズルはもう一つあるので、それについてもいずれ記事にしたいと思っています。

 

それでは今日はこの辺で。みなさん新生活を楽しんでください!

ブログを始めたp個の理由(p=2)

初めまして、みうらです。代数とパズルと素数大富豪が好きな院生です。

もっとも、この最初の記事を見てくださっている方の多くは、数学のイベントでお会いしたことのある数学仲間かもしれませんね。

私は今日初めてブログを書いているのですが、ブログを始めた理由は主に二つ。今回は私がブログを始めたきっかけと、今後書いていきたいと思っていることについて、簡単に記しておこうと思います。

 

 

2016年10月5日。私の学生生活に転換点があるとしたら間違いなくこの日です。

MATH POWERという数学のイベントで、素数大富豪大会が行われたこと。その決勝戦で私の出した1021が素数だったこと。これがすべての始まりでした。

私は素数の力を借りて、数学のイベントを楽しむ機会を得ました。そして今日までの半年間で、こうやってブログを書こうと思うまでになりました。界隈のみなさんには本当に感謝しています。

 

さて、私がブログを書こうと思った理由ですが、簡単に言うと

  • 考えることが好きだから

  • 数学を楽しみたいから

の二つになるでしょうか。

 

まず、考えることが好きなのは、私が数学を専門として学んでいるからなのかもしれません。数学という学問には考えたくなるテーマが本当にたくさんあります。そして、数学的な背景を持つパズルを考えたり作ったりするのも大変面白い。常に何かを考えていたい私にとって、数学やパズルはとてもありがたい対象になっているのです。

でも、数学そのものを考えることだけでなく、一見数学とは関係の少なそうなことを数学的に考えるのも非常に楽しいです。数学の世界とは違う世界(パラレルワールド?)の出来事だとか、数学とは反対側(パラ)の存在だと思っていたことを、数学的に考えることができたとき。そのエキサイティングさも数学の醍醐味だと思っています。そういう経緯でブログの名前を「ますぱら」にしました。マスハラじゃないよ。

 

もう一つの理由「数学を楽しみたい」については、まだちょっとふわっとした感覚です。

この半年間で知り合うことのできた数学界隈の多くの方はブログを書いており、数学の話題でもそうでなくても、日常のいろいろなことを面白くしようというエネルギーにあふれています。私も今回ブログを持つことを通じて、自ら日常を面白くしたい。数学的に楽しめる空間を作りたい。そう考えています。自分だけではなく界隈の方と一緒に楽しむ数学を生み出す基盤にしたいという意味で、数学を楽しむブログを書いていきたいです。

 

 

最初だからか、どうしても文章が堅苦しくなってしまいました。でも文章ばかりの記事は今日くらいでしょう。

このブログではこれから、代数(特に素数とか)の話、パズルの話、素数大富豪の話などを書いていく予定です。まだ不確定要素も多いですが、少しずつ軌道に乗せていきたいと思います。

素数が被ってる?大事なことなのでp回言っただけですよ。

 

それでは、今日の記事はこれくらいにします。内容的には次回が1つ目の記事といったところでしょうか。そすうるとこれは0番目の記事ですね。0は自然数派の方の気持ちがわかったかもしれません。 

誤字ってる?大事なことなのでp+1回言っただけですよ。