« ■コマ大数学科161講:Doing Math in English Part2 | トップページ | ■コマ大数学科163講:タワー »

2009年12月17日 (木)

■コマ大数学科162講:四目並べ

「囲碁」は中国から伝わったものだが、中村亨センセによると「連珠」は日本生まれかも…とのこと。囲碁から生まれた言葉も多くあり「あいつには一目置く」とか「こりゃ駄目だ」なんてのも、もともとは囲碁用語。「岡目八目」とは、自分が対局しているときより傍で見ているときのほうが大局的に判断できるという意味だが、「おかめそば」に本当に具が八目入っているかは、それぞれが判断してほしい「たけしのコマ大数学科」

問題:縦6列、横6列の計36個の格子点上に、○(白石)で四目を作らせないようにするには、●(黒石)を最小で何個置けばよいでしょうか?

【遊び方】盤面にマウスポインタをおくと、ガイドが出るので、黒石の置き場所を選びクリックする。一度置いた黒石は、もう一度クリックすると消える。並べ終えたら「Check」ボタンを押してね。

四目並べと言えば国分寺?? コマ大数学研究会が訪れた先は囲碁サロン「ホワイエ」。かなり広いフロアでゆったり囲碁を楽しむことのできる空間だ。その片隅を借りて検証開始したが、12個からなかなか減らすことができない。そこで、囲碁サロンのお客さん、囲碁のベテランに教えを乞う。四目並ばないようにするには、縦横斜めに白石が四目並ばないように、切ればいいのだからと、あっさり、黒石11個の解答。これをコマ大生の解答とした。

コマ大生の解答

四目並べ(1)

マス北野とポヌさんも、10分間の対戦時間中、ポヌさんのスカスカな解答もあったが^^; 悩んだあげく「11個じゃないの」と以下のような答え。

マス北野&ポヌさんの解答

四目並べ(2)

木村美紀、山田茜さんの東大生チームは、黒石10個という答えを出した。

東大生の解答

四目並べ(3)

四目並べ(4)

考え方としては、コマ大生の答えと同じく、横のラインに四目ならべられないようにするには、縦に6個並べればよい。同じく縦のラインに四目並べられないようにするのに、黒石が5個、合わせて11個の黒石が必要になる。ここから、さらに減らせないかと、縦の黒石を移動させると、黒石1個を節約することができた。

中村亨センセの「美しき数学の時間」

正解は「10個」。では、10個以下の解はないのだろうか。

四目並べ(5)

まずは、中央の4目(格子点)に黒石を置かない場合を考える。すると、白に四目並ばせないためには、それぞれ灰色で示した格子点のどちらかに黒石を置かなくてはならなくなる。数えると12個。

四目並べ(6)

次に、中央の4つの目に黒石を1個置いた場合。この場合でも、白石が四目並ぶことの可能性を消すには、最低でも10箇所必要(実際には黒石を11個置くことになる)。

四目並べ(7)

中央の4目に黒石を2個置いた場合。可能性は灰色の部分になり、合計10個。よって、黒石は最低10個は必要になり、これより少ない個数の解はない。

四目並べ(8)

解答例を見ると、縦横とも中央の2つのライン上に黒石があることがわかる。つまり、中央の4目に黒石を斜めに2つ置く方法は、結局、斜めのラインを消すために、無駄な黒石が必要になっちゃうわけね。

ガスコン爺の番外編

爺は、自慢じゃないが中学のとき「棋道部」に在籍していた(ホントに自慢にならない;;)。しかも、囲碁をやったのは、あとにも先にも、中学3年の1年間だけだ^^;囲碁には、いろんな定石があるが「桂馬掛かり」もそのひとつ。相手の石や、盤面の星から、将棋の「桂馬」の動く位置に打つ戦法だ。

四目並べ(9)

盤面の四隅から桂馬の位置に打つ。4つの石から桂馬の位置に新たな石を打つ。さらに新たな2つの石から桂馬の位置に打つ。すると、東大生の解答と同じになる(回転させれば^^)。

爺が言っても、なんの説得力もないけれど、これは「Nクイーン問題」が参考になる。チェスの「クイーン」は、上下左右、斜めと、将棋の「飛車」と「角車」を合わせたような動きをする。「Nクイーン問題」は、N×Nのマス目にN個のクイーンを、動きの範囲(効き筋)の外に(ダブらないように)クイーンを配置するには、どーしたらいいかという問題。

たとえば、「Nクイーン問題」で(N=4)、(N=6)の場合は、以下のようになる。

四目並べ(10)

縦横斜めが効き筋の「クイーン」を効率的に(ダブらないように)配置するには、ナイト(桂馬)の動き方に配置することが有効なことがわかる。ルールが違うので「四目並べ」とは同じとは言えないけれど、縦横斜めに連珠する石を阻止する問題と似ているところがある。

四目並べ(11)

ちょっと強引だが「Nクイーン問題」の(N=4)と(N=6)の解を重ね合わせ、「四目並べ」のルールで考えてみる(図1)。四目並んでしまう箇所があるので、東大生がしたように「1個ズラし」をする(図2)。あとは、斜めに並ぶのを阻止するため、中央の4つのマス目に2個置けば、完成する(図3)。

このような可能性を列挙する、いわば力技の「エレファント」な解法を、泥臭いと言う人がいるけれど、世の中、手っ取り早く「エレガント」に解決できる問題ばかりではない。また、「エレガント」な解法は、けっこう、泥臭い「エレファント」な試行錯誤の上に辿り着くのだと思う。重要なのは「考える力」だ。

関係ないけれど、「桂馬」つながりとゆーことで、「コマネチ大学数学科59講:オイラー」で紹介した、オイラー方陣を再掲載しておこう。

このオイラー方陣は、桂馬の動きで方陣(8×8のマス目)を埋め尽くすことができるというだけでなく、縦、横の数字を足し合わせると、すべて「260」になるのら^^;

≪参考≫

離散数学「数え上げ理論」 離散数学「数え上げ理論」

野崎昭弘/著
講談社ブルーバックス

「『おみやげの配り方』から『Nクイーン問題』まで」とあるように、身近な問題から数学的な難問まで、離散数学の「数え上げ理論」という切り口で説明を試みる。フィボナッチ数列や、カタラン数も出てくるでよ。

たけしのコマ大数学科 第5期 DVD-BOX(12月16日発売)

※Pencil Missaileは、[SPACE]キーでも発射できるよ^^;

※コマネチ大学数学科の「過去問題」はこちらから。
コマ大数学科:2008年度全講義リスト
コマネチ大学数学科:2007年度全講義リスト
コマネチ大学数学科:2006年度全講義リスト


|

« ■コマ大数学科161講:Doing Math in English Part2 | トップページ | ■コマ大数学科163講:タワー »

コメント

http://science6.2ch.net/test/read.cgi/math/1258221985/201-300
他の人からも多分忠告があると思いますが。
既に解決済み?
次回問題の日本語について。

投稿: MYON | 2009年12月19日 (土) 04時01分

本題はさて置き(笑)、チェスをやるので、ガスコンさんの番外編は大いに参考になりました。オイラー方陣は、ナイト(将棋の桂馬に相当。但し、八方へ移動可)の動かし方に大きなヒントをくれそうです。

「Nクイーン問題」だけではなく、「Nナイト問題」なんてのも出来そうですね。これを考えると、今晩は徹夜になりそうです。これが本当の「オール・ナイト!」

お後が宜しい様で・・・

投稿: アキレ・サンタ | 2009年12月20日 (日) 12時13分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/99648/32640928

この記事へのトラックバック一覧です: ■コマ大数学科162講:四目並べ:

« ■コマ大数学科161講:Doing Math in English Part2 | トップページ | ■コマ大数学科163講:タワー »