7枚のカードの問題(2)2018年04月20日 22時05分45秒

7枚のカードの問題
http://takamura.asablo.jp/blog/2018/04/14/8826570
を某所で話したところ、大学後輩の山根君が驚くべき解答を寄越してきた。
--
A氏が自身の3数の排他的論理和(Xaとする)を言う。
B氏は自身の3数の排他的論理和(Xbとする)を計算し、(1から7までの排他的論理和は0なので)0^Xa^Xb = Xa^Xbを計算すると、これがC氏の数(cとする)に他ならないのでこれを言う。
--
というシンプルで美しいもの。
0^Xa^Xb = cとなるのは簡単にわかるが、問題は「Xaとcのペア」から、A氏とB氏のカードが一意に特定できるケースがないかどうか、である。

例えばXa=1, c=3の場合、
A:247 B:156 (C:3)
A:256 B:147 (C:3)
の2通りがあるため、C氏はA氏とB氏のカードを一意に特定できない。
A氏,B氏に配られる全カードの組み合わせ(140通り)について確認すると、「Xaとcのペア」が同じものは、常にこのような2通り以上存在した(※)。したがってどんな場合でも、C氏はA氏とB氏のカードを一意に特定できない。

※「Xaとcのペア」が同じになるのは2通りか4通りしかなかった。
例えばA氏が1と言ってC氏が1を持っていた場合は、
A:247 B:356 (C:1)
A:256 B:347 (C:1)
A:346 B:257 (C:1)
A:357 B:246 (C:1)
の4通りになる。

7枚のカードの問題2018年04月14日 23時16分58秒

「超難問論理クイズ「幼女と7枚のカード」が難しいけど面白すぎる」
https://sist8.com/7cards
「7枚のカードそれぞれに1~7の数字が書かれており、事前に打ち合わせをしていないA,B,Cの3氏にランダムに3,3,1枚配る。
各氏は自分のカードしか見えない。
まずA氏が何か発言をする。次いでB氏が何か発言をする。但し発言は全員に聞こえる。
するとA,B氏は3人のカードが何かがわかり、C氏にはわからない。
どういう発言をしたのか。」
という問題があった。以前書いた「2人の幼女とチェス盤の部屋」よりは楽だったかも。

最初にA氏が自分の3枚に基づく発言をすることで、B氏はA,C氏のカードが何かわかってしまうことになる。

答えは「A氏自分のカードの数字の和を7で割った余り(Raとする)を言う」である。
A氏のカードが1,2,4だとすると、Ra = (1+2+4) % 7 = 0である。
A氏の持ちうるカードの組み合わせは7C3 = 35通りあるが、以下のようにRa毎に5通りになる。
Ra  A氏のカードの組み合わせ((1,2,4)を124のように書いている)
0……124,167,257,347,356
1……125,134,267,357,456
2……126,135,234,367,457
3……127,136,145,235,467
4……137,146,236,245,567
5……147,156,237,246,345
6……123,157,247,256,346

どの行を見ても、2つの数字がかぶる組み合わせはない。(もしwyzとxyzのように2つの数字がかぶれば、B氏はRaを聞いて、自分の持つカード3枚以外の4枚がwxyzであるとしかわからない。つまりRaを聞いても何も新しい情報は得られない)

例えばA氏がRa=1と言い、B氏のカードが345であったとしたら、B氏は、A氏のカードが267であるとわかる。(そしてC氏のカードは残る1だとわかる)

次にB氏の発言だが、先と同様に自分のカードの数字の和を7で割った余り(Rbとする)を言ってもよい。先ほどとA,Bの立場が逆転するだけである。ただ、既にB氏は全員のカードがわかっているので、シンプルにC氏のカードの数字(cとする)を言ってもよい。A氏は、自分とCのカード以外の3枚がB氏にあるとわかるし、Cに何か追加情報が伝わるわけではない。(ただし、3人の数字の合計は28で7で割ると余り0なので、C氏は最初にRaを聞くだけで、Rbは「Ra+Rb+cが7で割り切れる7未満の数字」とわかる。つまりB氏がRbを言ってもC氏に追加情報が伝わるわけではない。)

ここまででC氏はRaとRbおよびcがわかるわけだが、例えばRa=1,Rb=2,c=4であればA氏とB氏のカードがそれぞれ「125と367」か「267と135」か「357と126」までしか絞れない。(足すと7で割り切れないRa=1,Rb=2,c=5などはありえない)

チェス盤の「状態数」の高速演算法2018年03月24日 14時27分55秒

先日のブログ「チェス盤の問題」
http://takamura.asablo.jp/blog/2018/03/22/8808782
での未解決問題:「黒マスの総駒数の偶奇を並べた数」の高速演算法だが、次のようにすればできることに気が付いた。いわゆるreductionである。

16マスの場合を例にとり、駒配置を表す2進数をxとする。
x ^= ((x & mask1) >> 8)
x ^= ((x & mask2) >> 4)
x ^= ((x & mask3) >> 2)
x ^= ((x & mask4) >> 1)
とすれば、最下位ビットを0番目とすると8,4,2,1番目にあるビットが、1~4段目の黒マス内の1の数の偶奇(偶数:0,奇数:1)を示している。後は
((x & 256)>>5) | ((x & 16)>>2) | ((x & 4)>>1) | ((x & 2)>>1)
または
((x & 256)>>5) | ((x & 16)>>2) | ((x & 6)>>1)
としてビットを詰めれば、「黒マスの総駒数の偶奇を並べた数」が得られる。処理量はマスの数の対数に比例する。
図でマスクは最小限のビットを立てたものにしているが、黒マスを1、白マスを0と見立て、1段目から順に0xff00,0xf0f0,0xcccc,0xaaaaでも構わない。

チェス盤の問題2018年03月22日 00時01分07秒

「超難問論理クイズ「2人の幼女とチェス盤の部屋」が本当に難しすぎた」https://sist8.com/chess2you
という問題をとある筋から聞いた。問題を一言で言うと
・悪魔が8x8のチェス盤上にランダムに駒を置く。
・A氏が登場し、悪魔が伝える1から64の整数Nを聞き、チェス盤のある一マスに「駒があれば除く、駒がなければ新たに置くという操作」を一回だけ行う。
・B氏が操作後のチェス盤のみを見て、Nを当てるにはどうすればよいか。
というものである。上記リンクに答えもあるが、見ずに解いてみた。確かに難しかった。

簡単のためチェス盤が4x4の16マスで、Nを1~16の代わりに0~15の整数とする。
またチェス盤を横に1x16に展開して考える。駒がある状態を1、ない状態を0とする。
事前に任意に駒配置された状態で、相手に0か1を伝える方法としては、黒く塗った8マス内の駒総数が偶数なら0、奇数なら1、とすればよい。最初から都合よくそうなっているわけでは必ずしもないが、駒を除く(1→0)、あるいは駒を置く(0→1)ことができるので、
黒く塗った8マス内の駒総数の偶奇 と 伝える数字
の組み合わせがどうあっても、以下のように最終状態から相手が伝えたい数字を正しく判断できる。
0と0・・・任意の白マスを操作する
0と1・・・任意の黒マスを操作する
1と0・・・任意の黒マスを操作する
1と1・・・任意の白マスを操作する
上図に示すように黒塗り幅を8,4,2,1マスごとに行えば、4通りの方法で0か1かを伝えることができる。

ここで重要なのは、4通りの方法それぞれ独立に0,1を伝えることができることである。
黒塗りの幅8,4,2,1ごとに任意の指定色を持つマスは必ず一つ存在する。
例えば駒が中図のように配置されていて、N=9(二進数で1001)であれば、操作するマスは上段から順に黒、黒、白、白となる。それを満たすマスは、右から13番目の青枠で囲ったマスである。
このマスを操作(0なら1に、1なら0に変更)すると、下図のように、黒マス内の駒総数の偶奇が示す二進数がNに一致することになる。

結局、黒マスの総駒数の偶奇パリティを並べた数とNとのxorをとった数が、操作すべき駒の場所を示している(右端が0番目と数えることに注意)。

実際のチェス盤の場合は64マスなので、黒塗り幅が32,16,8,4,2,1の6通りで6ビット(0~63)を伝えればよい。

未解決問題:「黒マスの総駒数の偶奇を並べた数」の高速演算法がありそうだが、わからない。(後日記:できました→ http://takamura.asablo.jp/blog/2018/03/24/8810385 )

井上暦2018年01月30日 12時23分22秒

知り合いの井上さんという方が、一年を基本52週(364日)とし、時々53週(371日)の「閏年」をはさむ暦(井上暦と名付けよう)を考えていた。これだと「●月○日が△曜日」というのが毎年変ることもなく、便利に思える。
一年は正確には365.2422日であるので、井上暦で6年に一回閏年をはさむと(52*7*5 + 53*7)/6=365.1667日となり、少しずれる(年間誤差0.0755日)。
N年にM回閏年を入れる場合、M<N<=400の範囲で現行のグレゴリオ暦の精度(年間誤差0.0053日)よりよくなるものは119通りある。
うち最も精度が良いのはN=355,M=63(355年に63回閏年を入れるもので年間誤差は実に0.0000535日!)だが、閏年を入れるタイミングが難しい。
よさそうなのはN=45,M=8。5年に一回閏年とするが45年に一回閏年にしない、というもので、年間誤差も0.0022日しかない。周期もグレゴリオ暦の400年よりだいぶ短い。