« Koki,(コウキ)の初CM、大塚製薬「ボディメンテ」海外挑戦/駅編&10km走 | トップページ | 「性格悪い人限定飲み会」、実際は性格フツーの人たちか♪ »

数学甲子園2018本選Math Battle(マスバトル)、問題と解き方3(第7問、白黒タイル)

☆追記:さらに続編記事もアップした。

2018本選、解き方4(問題8~12))

 

 

   ☆   ☆   ☆

2018マスバトルの記事を12問分

アップした後、ずいぶん時間が経って

しまった。理由は色々あるが、一番

大きいのは、順番的に次に解くべき

問題7に苦戦してたのだ。

 

181030a

 

たまたま先日、オセロの世界選手権

が話題になったから、オセロのアプリ

で弱いAIに圧勝して遊んでたけど、

この白黒タイル問題には敗北寸前。

 

 

   ☆    ☆    ☆

行列か数列の理論の応用だろうけど

思いつかないから、2の9乗=512

通りをシラミつぶしにチェックするしか

ないか・・と思って書き並べ始めたら、

ようやく解けた。

 

やはり、具体的に手を動かして試行

錯誤することが大切。ただし、それだけ

だと、「出来る」ことの証明は可能でも、

「出来ない」ことの証明にはならない。

だから結局、論理が必要となる。

 

本来なら今回は問題7~12の記事

を書く所だけど、既にかなりの時間を

費やしたので、今日は問題7の解説

だけにしよう。今回も、スマホ向けに

1行の字数を少なくしてある。

 

ちなみに、既にアップ済みの今年の

数学甲子園記事3本は次の通り。

 

 数学甲子園2018予選、

   正答率の低い3つの問題

 

 数学甲子園2018本選Math

 Battle(マスバトル)、問題と

 解き方1(英語の問題)  

 

 数学甲子園2018(マスバトル)、

 問題と解き方2(問題1~6)

 

   ☆    ☆    ☆

第7問

白と黒のタイルを用いて、3×3の

ボードをつくります。1つの行または

列の3つのタイルの色をすべて変化

(黒ならば白、白ならば黒に変換)

させる操作を行います。

 

この操作を繰り返すことで、すべての

タイルを白にすることができるタイル

の配置の総数を求めなさい。ただし、

回転・裏返しによる配置の同一視は

行わないものとします。

 

 

解答

行の変換や列の変換は、2回行うと

元に戻って、0回行うのと同じになる。

よって、各行、各列の変換は0回か

1回だけ行うと考えてよい。

 

また、すべて白にできる配置とは、

逆に、すべて白の配置から変換

可能な配置でもある。

 

以下、白いタイルを数字の0、黒い

タイルを数字の1で表すことにする。

すべて白の配置なら、以下の通り。

 

 0 0 0

 0 0 0

 0 0 0

 

この状態から、例えば「1行目に

1回、2行目に1回、3行目に0回、

1列目に0回、2列目に1回、

3列目に0回」だけ操作を行うと、

操作の順番に関わらず、次の

ただ1通りの配置になる。

 

 1 0 1

 1 0 1

 0 1 0

 

同様に考えて、一般に、3行3列

に対する変換の回数の組合せに

対して、タイルの配置が1通り対応。

 

ただし、1対1とは限らないので、

それぞれの行や列への変形が

0回か1回かを考えて、

2×2×2×2×2×2=64通り

の配置を書いてみる。

 

行・列すべて0回から始めて、行・列

すべて1回まで。既に書いたものと

重複した場合、色を付けて区別。

 

(注. スマホやタブレットの場合、

数字に自動でリンクが付いてしまい、

色が消えてしまうので悪しからず。)

 

000 111 000 000 100

000 000 111 000 100

000 000 000 111 100

 

010 001 011 101 110 

010 001 100 010 001

010 001 100 010 001

 

100 010 001 100 010 

011 101 110 100 010

100 010 001 011 101

 

001 111 111 000 110 

001 111 000 111 110

110 000 111 111 110

 

101 011 011 101 110

101 011 011 101 110

101 011 100 010 001

 

011 101 110 100 010

100 010 001 011 101

011 101 110 011 101

 

001 001 110 110 010  

110 110 001 110 101

110 110 110 001 101

 

101 101 100 011 011 

010 101 011 100 011

101 010 011 011 100

 

001 010 100 001 010 

001 010 100 110 101 

110 101 011 001 010

 

100 110 101 011 111 

011 001 010 100 111 

100 001 010 100 111

 

111 011 101 110 000

111 011 101 110 111

111 011 101 110 111

 

111 111 001 010 001

000 111 001 010 001

111 000 001 010 001

 

000 000 000 000

000 111 000 000

111 000 111 000

後半ほぼ全て、32通りが重複。

 

例えば、行2つと列1つに1回変換

した9通りは、列1つと行2つに1回

変換した9通りと一致する。また、

行2つと列2つに1回変換した9通り

なら、行1つと列1つに1回変換した

9通りと一致。

 

一般に、行nコと列mコに1回変換

した配置全体は、行3-nコと列

3-mコに1回変換した配置全体と

一致する(n,m=0,1,2,3)。

 

∴ (求める配置の総数)

 =64-32

 =64/2

 =32(通り) ・・・答

 

 

感想

オセロの変化の多さにつられて難しく

考え過ぎた。行列の行や列の基本

変形として単純に考えるべきだった。

 

最初は64通りが答かと思ったけど、

念のために書き並べると大量の重複

が判明。書き並べるだけでも1度ミス。

 

結局、(2の6乗)÷2が答になるけど、

キレイな理由は今のところ不明。行列

の成分の添字とクロネッカーのデルタ

δi j を使うような気がする程度。

 

なお、問題文をよく読むと、最初から

すべて白の場合も含めるのが正解

のはず。疲れた切ったところで、今日

はこの辺で。。☆彡

 

 

 

cf.数学甲子園2017予選、

   全20問の問題、解き方、感想

  同・本選Math Battle、

    問題と解き方(abema動画)

  同・問題と解き方2

  同・問題と解き方3

 

 2016本選1st Stage、全問題

 16予選、全20問の解き方、感想

 16(Abemaライブ)、前半感想

 2015準々決勝、全問コメント

 15予選、全20問の解き方、感想

 14準々決勝、全問コメ&問題10

 13予選ポイント、問題15解説

 12、予選問題&3日ぶりのラン

 数学選手権にチャレンジ (11)

 

         (計 2464字)

|

« Koki,(コウキ)の初CM、大塚製薬「ボディメンテ」海外挑戦/駅編&10km走 | トップページ | 「性格悪い人限定飲み会」、実際は性格フツーの人たちか♪ »

「ゲーム」カテゴリの記事

数学」カテゴリの記事

コメント

解答、力作ですね。私も最初は2^3x2^3=64通りと思いました。全て二回(ixj=jxi)数えていると解るまでは、しばらくかかりました。。

投稿: gauss | 2018年11月 5日 (月) 02時52分

> gauss さん
  
こんばんは。毎度どうもです。
力作というか、力づくというか♪  
高校時代から、このくらいの場合分けなら
しらみつぶし戦略でやってました。
まあでも、頑張って数百通りくらいまで。
     
で、重複するのがちょっと分かりにくいですよね。
今回は答が与えられてないから、念のために自分で
チェックしましたが、答があったらすぐ見てたかも。
3×3以上の行列や3次元以上の図形は苦手です shine

投稿: テンメイ | 2018年11月 6日 (火) 00時35分

コメントを書く



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




« Koki,(コウキ)の初CM、大塚製薬「ボディメンテ」海外挑戦/駅編&10km走 | トップページ | 「性格悪い人限定飲み会」、実際は性格フツーの人たちか♪ »