Inoueianさんの出題を元にした「オセロ問題」まとめ
-
- いいね！0
Satoru Inoue
@Inoueian
惜しいアイディア：それは、コインが表を向いているますに対応する数字を全部足して、64で割った余りを取る事（つまりmod 64の足し算）。こうして出てくる答えは0から63の整数なので、64種類に盤面の状態が分類出来ます。
2012-01-29 11:21:24
Satoru Inoue
@Inoueian
惜しいアイディア：ます1つ1つに番号をふるのは、だいたい誰でも考えるアイディアじゃないでしょうか。ちょっと数学寄りの人なら、ここで盤面の状態を64種類に分類する方法も思い付きます。
2012-01-29 11:19:19
Satoru Inoue
@Inoueian
惜しいアイディア：与えられた配置はコインが全部裏向きで、もし1番のますが指定されていたとすれば、1番のコインをひっくり返せば相棒は指定されたますが1番だったとすぐに分かります。他の配置でも計算はもうちょっと大変ですが出来る…と思うと間違いなんですね。
2012-01-29 11:23:44
Satoru Inoue
@Inoueian
惜しいアイディア：もし、最初の配置が、1番のコインだけ表を向いていて、他は全部裏だったとします。そして、敵は2番のますを指定してきました。そうすると、どのコインをひっくり返しても、あなたは相棒に2番のますが指定されたと伝えることが出来ません。試してみてください。
2012-01-29 11:26:22解答編
Satoru Inoue
@Inoueian
まずこのヒントは、途中まで合ってるのね。 https://t.co/qF9OFoRj https://t.co/xawAIEHT https://t.co/c3sad4pK https://t.co/aDf79ReW
2012-01-29 19:19:27
Satoru Inoue
@Inoueian
チェスボードのます1つ1つに、0から63までの数字を振るのは良いアイディア。でもここでまず、2進法に変え無いといけない。2の6乗は64なので、000000から111111までの2進法の数字がますに1つずつ対応する事になる。
2012-01-29 19:21:27
Satoru Inoue
@Inoueian
コインが表になっているますの数字を足していくのも正しい。でも、ここで大事なのは、桁の繰り上げをしない事。（他にも色々捉え方のある操作。1の桁、2の桁、4の桁…それぞれで、表の出てるますの数字を排他的論理和で組み合わせる、という表現も出来る。）
2012-01-29 19:24:34
Satoru Inoue
@Inoueian
これだけじゃなんだか分かんないと思うので、ヒントに出した例で。数字の1に対応するマスだけ表を向いていて、相手が指定したマスは2に対応するのだったとします。ひっくり返す前の状態を見せると、相棒は1のマスが指定されたのだと思うことになります。
2012-01-29 19:27:20
Satoru Inoue
@Inoueian
ひっくり返す前の状態は、2進法で000001。ひっくり返した後に持っていきたい状態は、2進法で000010。そのままだと、1の桁と2の桁が間違ってます。こういう時は、000011（10進法だと3）に対応するマスのコインをひっくり返せば正しい状態に持っていけます。
2012-01-29 19:28:55
Satoru Inoue
@Inoueian
ひっくり返す前の状態と、ひっくり返した後に持っていきたい状態を比べて、一致してる桁は0、違ってる桁が1になる数字に対応するマスのコインをひっくり返せばOK。どのマスが指定されても大丈夫。
2012-01-29 19:30:56別解編
僕が最初に思いついた方法です。
ここから二進法でシンプルに答えられることに気づきました。
まず盤面をURLのように6通りに色分けします。
twitpic.com/8f1ysb
（画像がタイトルに表示されないようリンクは貼りません）
出題者が黒を奇数枚おいていたとします。
一枚ひっくり返すと黒は偶数枚になり，色分けすると遇数+遇数か奇数+奇数になります。そこでパートナーとは「遇+遇のときには灰色の領域に奇+奇のときには白色の領域に正解のマスがある」と約束しておけば常に一枚ひっくり返すだけで正解を示すことができます。
出題者が黒を偶数枚おいたときには偶+奇と奇+偶の場合分けで同様の約束をすればよいです。
群論編
がっくん
@perpQ
昨日の問題の答えを140字に押し込んでみます。 RT @wkaname: 【問題】 続） さて，どのような 「事前打ち合わせ」 をしておいて，「どのコマを 1 枚だけ選んで裏返せ」 ば，パートナーに正解マスを当てさせることが出来るか？
2012-02-03 12:22:08
がっくん
@perpQ
a)マスに0から63まで番号を振り2進数に直すb）各位ごとに黒オセロのマスをXORゲートで合計し新たな2進数を指定するc）出題者の指定したマスの番号の2進数とbで求めた2進数の各位をbと同様に足し，対応するマスを裏返すd)パートナーはbの方法で指定されたマスを知ることができる．
2012-02-03 13:35:36この方法はInoueianさんの模範解答と同じでした。ちょっと意外。
がっくん
@perpQ
諸用で遅くなりましたｗ 最初に考えたのはもっと小学生でも分かる方法でしたが140字にするとこうなるかな．行列（群）で表現するともうちょっと意味は分かりやすくなりそうだけど，ツイッターじゃむりです．
2012-02-03 13:39:00
がっくん
@perpQ
a)マスに0から63まで番号を振り2進数に直し各位の数字をa_iとおくb）各マスに6x6の行列A_ij=δ_ij(-1)^a_iを対応させるc)黒オセロのマスの行列を掛け算するd）出題者の指定したマスの行列とbで求めた行列を掛け，対応するマスを裏返すd)パートナーはbの方法で（略
2012-02-03 13:51:11補足すると行列はすべて対角成分が1か-1の対角行列で2^6=64通りになります。
Satoru Inoue
@Inoueian
@fromPerpSpace どうでしょうね。これじゃない表現で不可能だとは即証明出来ませんが、もし出来たとしても適用するのが無茶苦茶大変そうというのは分かりますw
2012-02-03 14:30:05