Make 10, Eight Queens, 笑わない数学者からの挑戦状 (Mathematical Goodbye), Binary Puzzle

2017-06-25 (Sun.)

Make 10

四則パズル、小町算とも.

ルール

大抵はひと桁程度の自然数が4つ与えられ、四則 (加減乗除) を補って組み合わせることで 10 を作るパズル. 私が初めて知ったバージョンでは、自然数は一列で与えられるのでその順序を変えず、 四則演算記号 +-*/ 及び括弧 () を適切に挿入することで答えが 10 になる式を作るというものだった. けど順序くらい自由に変えられるのが普通のルールらしい. ということでここでは次のようなものを "Make 10" と呼ぶことにする.

1. 与えられる数は整数
2. 数字を自由な順に一列に並べる
3. 答えが 10 になるような式を、四則演算及び括弧を挿入して作る
   • ただし演算は全て有理数の上で行う

例

• 問:
  • \(9, 9, 9, 9\)
  • 解:
    • \(\left( 9 \times 9 + 9 \right) \div 9\)
• 問:
  • \(1, 1, 5, 8\)
  • 解:
    • \(8 \div \left( 1 - 1 / 5 \right)\)

考察

「記号と括弧を挿入して式を作る」などと言っているが、ようは次のようなことである.

1. 数字の多重集合 (multiset) \(\mathcal{A}\) がある
2. \(\mathcal{A}\) のサイズが 1 より大の間、次を繰り返し行う
   1. \(\mathcal{A}\) から数を2つ取り出して \(x, y\) とする
   2. \(x, y\) から四則で出来る数 (\(x+y, x-y, y-x, xy, x/y, y/x\) のいずれか) を \(\mathcal{A}\) に追加する

そうして得た \(\mathcal{A}\) の中の唯ひとつの数が式の結果である. 例えば \(\frac{8}{1 - 1 / 5}\) という式は、次の手順で構成される.

1. \(\mathcal{A} = \{ 1,1,5,8 \}\) (初期)
2. \(\mathcal{A} = \{ 1,8, 1/5 \}\) (\(1,5\) を取り出して \(1/5\) を追加)
3. \(\mathcal{A} = \{ 8, 4/5 \}\) (\(1, 1/5\) を取り出して \(1-1/5\) を追加)
4. \(\mathcal{A} = \{ 10 \}\) (\(8, (1-1/5)\) を取り出して（ｒｙ)

こうすると、\(\mathcal{A}\) のことを１つの状態だと見做せて、「2つ取り出して演算結果を追加」という操作によって別の状態に遷移するということを考えられる. これで \(\{10\}\) という状態に辿りつけられれば、そのパスが求める式になる.

解答

• ソースコード

Eight Queens

ルール

8x8 のマスからなるチェス盤が与えられる. ここに出来るだけ多くのクイーンを置く. ただしあるクイーンで別のクイーンを取れるような位置にあってはいけない (攻撃範囲に入ってはいけない). どう配置すればよいか.

考察

行について言うと1つの行に高々1つのクイーンしか置けない. 2つ以上あったら一方のクイーンの攻撃範囲に入ってることになるので. 盤面は8x8なので8個の駒を置くことを考える.

1行あたり1つ置くことになるので、何列目に置くか、という情報の持ち方で良さそう. \(i\) 行目のクイーンを \(a_i\) 列目に置く、ということで \[a_1, a_2, \ldots a_8 ~~(1 \leq a_i \leq 8)\] と書ける.

もちろん列についても同じ列に複数のクイーンがあってはいけない. つまり \(a_i \ne a_j\) である必要がある. とすると \(a_1, a_2, \ldots a_8\) は \(1,2,\ldots,8\) の置換でよい. というわけで \(8!\) 通りだけ試せばよい (\(8! = 40320\)).

この数列 \((a_i)\) について、行及び列に関してはクイーン同士は必ず交わってないので、斜めについてだけチェックする. \(|a_i - a_j| = |i-j| ~(i \ne j)\) のとき、ちょうど斜め方向にクイーンが攻撃しあってるので、これが無いことを、8 クイーンの全てのペアについて調べれば良い.

ちなみに NxN の盤面にはいつも N 個のクイーンを置くことができる.

解答

• ソースコード

笑わない数学者からの挑戦状 (Mathematical Goodbye)

先に紹介したパズルは初出も発案者もよくわからないけれどこのパズルは小説家の森博嗣が自身の小説 ¹ の中で登場させたもの. でも私はそういった小説は読まないので、とあるサイト ² で初めてこのパズルを知った.

ルール

参考文献 ³ にあるが、ここにも要約しておくと次の通り.

1. ボールが 15 個あり、それぞれ 1 から 15 の数字が書かれている
2. これらから 5 個選び環状に並べる
3. 1 個以上の連続したボールの選び方は 21 通りあるが、それぞれのボールの和を取った時、1 のものから 21 のものまで全てが作られる
4. このようなボールの選び方及び並べ方を求めよ

考察

これこそ、\(\left(\begin{array}{c}15\\5\end{array}\right)\) 通り試しちゃえば良いだけ. 下の解答は何も考えず全通り試しているだけ.

でも敢えてより深く考察をするのなら、

• 小さな数字はボール1個の和から作るしか無い
  • \(1\) はボール \(1\) から作る
  • \(2\) はボール \(2\) から作る (ボール \(1\) は1つしかないので \(1+1\) とは出来ないので)
    • というわけで、ボール \(1, 2\) は必要
• \(4\) はボール \(4\) から作れるが、\(1+3\) でも作れる
  • ボール \(1\) は上の考察から既に必要であることがわかっている
  • というわけで、ボール \(3\) か \(4\) かのいずれか一方は少なくとも必要
• 最大の和は5つのボールの和だが、「ボールの和で 1から 21 までの数字全てを作れ」とあるので、5つの和が21に他ならない

というわけで、有り得るボールの組み合わせは次のいずれか

• \(1, 2, 3, x, (21 - (1 + 2 + 3 + x))\)
• \(1, 2, 4, x, (21 - (1 + 2 + 4 + x))\)

というわけで組み合わせ自体は100通り程度?に減らすことは出来る. けどその後、結局並び替えも考える必要がある.

解答

• ソースコード
  • 実行結果

Binary Puzzle

その名の通り BinaryPuzzle.com ⁴ というサイトで知った.

ルール

BinaryPuzzle.com ⁵ にあるが、和訳を兼ねて要約すると、

1. NxN のマス目からなる盤面に 0 または 1 を埋める
   • 少しだけ既に埋められた状態が与えられる
2. 同じ数字は高々2つまでしか縦横に並ばない
3. どの行、及び列においても、0 と 1 は同じ数だけ含まれる
   • 長さ \(N\) は偶数であることが保証されている
4. 全く同じ01の並びを持った行 (または列) が2つ以上あることはない

考察

同じ数字が3つ並ばないということから、

• 既に同じ数字が2つ並んでるならその両端は違う数字
  • .00. → 1001 (. はまだ数字が埋められていない空のマスのこと)
• 同じ数字が1マス飛ばして2つ並んでるならその間は違う数字
  • 0.0 → 010

特別に考えたのはこのくらい. 他は深さ優先探索で埋めてく.

解答

• ソースコード

参考