九九の答えが36種類であることの証明
まず、九九に現れる式に使われる数字の組み合わせの数を数えます。
計算式を m * n
とすると mは1~9
、 nは1~9
です。
そうすると、 mとnが異なるときに使われる数字の組み合わせ は、1~9から2つの数字を選ぶ組み合わせなので
9C2 = (9 * 8) / (2 * 1) = 36 通り …… ①
となります。
また、 mとnが等しいときの組み合わせ は、1*1
、2*2
……9*9
となりますので
9 通り …… ②
となります。
①と②より、式に使われる数字の組み合わせの数 は
36 + 9 = 45 通り …… ③
となります。
ここから、 計算結果が重複するもの を取り除いて行きます。 計算結果が重複するものは、例えば
4 * 9 = 36 6 * 6 = 36
のようなもののことです。
ここで、 1から9までの数字を素因数分解 してみましょう。
1 2 = 2 3 = 3 4 = 2 * 2 5 = 5 6 = 2 * 3 7 = 7 8 = 2 * 2 * 2 9 = 3 * 3
このように、素数と合成数1が混ざっていることがわかります。
ここで、先程の式を見てみましょう
4 * 9 = 36 6 * 6 = 36
この式を素因数分解すると、
4 * 9 = (2 * 2) * (3 * 3) = 2 * 2 * 3 * 3 = 36 6 * 6 = (2 * 3) * (2 * 3) = 2 * 2 * 3 * 3 = 36
このように、全く同じ式になります。
九九の中にある 計算結果が重複するもの というのは、このように、 式に使っている数字の組が異なり、素因数分解した結果が等しい ものであると言えそうです。
ここで、 1から9までの数字を素因数分解 したものから、合成数だけを抜き出してみます。(9以下の合成数の一覧)
4 = 2 * 2 6 = 2 * 3 8 = 2 * 2 * 2 9 = 3 * 3
少し変形して
4 = 2 * 2 6 = 2 * 3 8 = 2 * 2 * 2 = 2 * 4 9 = 3 * 3
これらの式は、1の段の計算結果 と上記の計算式について、式に使っている数字の組が異なり、素因数分解した結果が等しい ことが明らかです。 よって、
1 * 4 と 2 * 2 1 * 6 と 2 * 3 1 * 8 と 2 * 4 1 * 9 と 3 * 3 の 4通り …… ④
を、1の段と計算結果が重複する式の数 として数え上げることができます。
では、9より大きい数ではどうでしょうか。
式に使っている数字が異なり、素因数分解した結果が等しい という定義と、 9以下の合成数の一覧 からもう一度考えてみます。
4 = 2 * 2 6 = 2 * 3 8 = 2 * 2 * 2 9 = 3 * 3
ここへ、1
と2
と3
を加えてみます。
1 = 1 2 = 2 3 = 3 4 = 2 * 2 6 = 2 * 3 8 = 2 * 2 * 2 9 = 3 * 3
順番を少し変えます。
1 = 1 2 = 2 3 = 3 4 = 2 * 2 6 = 2 * 3 9 = 3 * 3 8 = 2 * 2 * 2
上記の一覧の中にある数字から、 素因数分解した結果が等しくなるような組み合わせ を探せば良さそうです。
まず、計算して項が3つになる組み合わせは
(2 * 2) * 2 = 2^3 (2 * 2) * 3 = 2^2 * 3 (2 * 3) * 2 = 2^2 * 3 (2 * 3) * 3 = 2 * 3^2 (3 * 3) * 2 = 2 * 3^2 (3 * 3) * 3 = 3^3
です。上記の内、計算結果が重複している式の組み合わせは
2^2 * 3 → (2 * 3) * 2 と (2 * 3) * 2 2 * 3^2 → (2 * 3) * 3 と (3 * 3) * 2 の 2通り …… ⑤
です。次に、計算して項が4つになる組み合わせは
(2 * 2) * (2 * 2) = 2^4 (2 * 2) * (2 * 3) = 2^3 * 3 (2 * 2) * (3 * 3) = 2^2 * 3^2 (2 * 3) * (3 * 3) = 2 * 3^3 (2 * 3) * (2 * 3) = 2^2 * 3^2 (3 * 3) * (3 * 3) = 3^4 (2 * 2 * 2) * 1 = 2^3 (2 * 2 * 2) * 2 = 2^4 (2 * 2 * 2) * 3 = 2^3 * 3
です。上記の内、計算結果が重複している式の組み合わせは
2^4 → (2 * 2) * (2 * 2) と (2 * 2 * 2) * 2 2^3 * 3 → (2 * 2) * (2 * 3) と (2 * 2 * 2) * 3 2^2 * 3^2 → (2 * 2) * (3 * 3) と (2 * 3) * (2 * 3) の 3通り …… ⑥
です。
ここまでに算出してきた ③④⑤⑥ についておさらいすると
- ③ → 式に使われる数字の組み合わせの数 = 45通り
- ④ → 1の段と計算結果が重複する式の数 = 4通り
- ⑤ → 9より大きい数で、計算結果が重複する式の数(項が3つ) = 2通り
- ⑥ → 9より大きい数で、計算結果が重複する式の数(項が4つ) = 3通り
です。これらの数を使うと、以下のように式に使われる数字の組み合わせの数から計算結果が重複する式の数を取り除いた組み合わせは
式に使われる数字の組み合わせの数 - 計算結果が重複する式の数
45 - (4 + 2 + 3) = 36 通り
となります。
したがって、九九の答えとなる計算結果の数字は36種類であると言えます。
※もっとスマートな証明を誰か……
おまけ
ここまでの思考の流れ
掛け算の九九のパターン?
— くんすとのーと (@kunst1080) 2017年4月12日
9C2なので
echo 9\*8/2 | bc#シェル芸
あれ??おかしくね???
— くんすとのーと (@kunst1080) 2017年4月12日
1 * 4 = 4
— くんすとのーと (@kunst1080) 2017年4月12日
2 * 2 = 4
mnで、mが1~9、nが1~9なんだよな……
— くんすとのーと (@kunst1080) 2017年4月12日
mとnが*異なるとき*の組み合わせは36通りだけれど、mnとm'n'が同じな組み合わせもある。
— くんすとのーと (@kunst1080) 2017年4月12日
式のパターンだけで言えば、 9C2 + 9 で45通りか…
— くんすとのーと (@kunst1080) 2017年4月12日
九九の中の、計算結果が重複する数の一覧
— くんすとのーと (@kunst1080) 2017年4月12日
echo {1..9}\*{1..9}\;|bc|sort -n | uniq -c#シェル芸
n = m のときは1
— くんすとのーと (@kunst1080) 2017年4月12日
n != m のときは2以上
1~9の数字を2つ取って掛け合わせた時の値の組み合わせは・・・
— くんすとのーと (@kunst1080) 2017年4月12日
ほう…… pic.twitter.com/1WRRHhzlq2
— くんすとのーと (@kunst1080) 2017年4月12日
規則性が見えそうで見えない・・・
— くんすとのーと (@kunst1080) 2017年4月12日
3回出てくるっていうことは、n==mの部分集合なんだよな…
— くんすとのーと (@kunst1080) 2017年4月12日
んで4回出てくるのはn==mの部分集合ではない
— くんすとのーと (@kunst1080) 2017年4月12日
n==mでないものはコンビネーションの関係で必ず2n回出てくるはずなので…
— くんすとのーと (@kunst1080) 2017年4月12日
重複の最大値は4…why
— くんすとのーと (@kunst1080) 2017年4月12日
4ってことは同じ結果の式が2回出てくる
— くんすとのーと (@kunst1080) 2017年4月12日
81以下の素数と、9以下の素数をn倍して81以下になる数字種類の合計は81-36 = 45
— くんすとのーと (@kunst1080) 2017年4月12日
あと1
— くんすとのーと (@kunst1080) 2017年4月12日
10~81の中の素数と、それをn倍して81以下になる数の種類が45?
— くんすとのーと (@kunst1080) 2017年4月12日
10以上81以下の素数の一覧 pic.twitter.com/TsGB5O51fC
— くんすとのーと (@kunst1080) 2017年4月12日
ここから起こすのは難しそう
— くんすとのーと (@kunst1080) 2017年4月12日
九九の答えは全て1~9のn倍
— くんすとのーと (@kunst1080) 2017年4月12日
ではない
— くんすとのーと (@kunst1080) 2017年4月12日
3回登場するのは、計算結果が10以下になる累乗数と、その累乗数で81以下のもの
— くんすとのーと (@kunst1080) 2017年4月12日
素因数分解すると、こうなる。 pic.twitter.com/lQ5T7tRjKC
— くんすとのーと (@kunst1080) 2017年4月12日
ちなみに4回出てくるやつはこんな感じ pic.twitter.com/VNJta10BtL
— くんすとのーと (@kunst1080) 2017年4月12日
眠れなくなりそうなので風呂入ろ……
— くんすとのーと (@kunst1080) 2017年4月12日
だれか証明して><
答えが一致するっていうことは、素因数分解の結果が一致するということ…
— くんすとのーと (@kunst1080) 2017年4月12日
1~9の数字を素因数分解すると
— くんすとのーと (@kunst1080) 2017年4月12日
1:
2: 2
3: 3
4: 2 2
5: 5
6: 2 3
7: 7
8: 2 2 2
9: 3 3
これらの組み合わせを数えればよさそう
— くんすとのーと (@kunst1080) 2017年4月12日
もうちょいで証明できそうな感じだけど寝るしかない
— くんすとのーと (@kunst1080) 2017年4月12日
やばい九九のせいで今日何もしてない
— くんすとのーと (@kunst1080) 2017年4月12日
10C2の45から2, 3, 4(2*2), 6(2*3), 8(2*2*2), 9(3*3)使って重複をカットすればOK、っていうところまできた。
— くんすとのーと (@kunst1080) 2017年4月12日