探索とみせかけて
二分探索の良さを伝えるためのゲームだったはずなのに、データ数が小さかったせいで意外といい勝負になったゲーム。
基本ルール
１．A,Bの２人に「自然数がランダムに１つ書かれたカード」を１０枚ずつ渡す
２．それぞれ、自分の１０枚の中から「あてられたくない数」を決める
３．それぞれ、１０枚のカードを横一列に並べて伏せる
４．それぞれ、相手の「あてられたくない数」がどのカードに書かれているかを予想し選ぶ
５．それぞれ、相手に選ばれたカードを同時に表にする
６．４と５を繰り替えす
「あてられたくない数」があてられたら負け。同時に当てたら引き分け。
ここまでだともちろんただの運ゲー。
これに次のルールを追加する
追加ルール
基本ルール３の後、A,Bはそれぞれ相手に次のことを要求する
Ａの要求：Ｂのカードを、小さい順に左から並べてもらう
Ｂの要求：Ａの「あてられたくない数」が偶数なら奇数が、奇数なら偶数が書かれている相手のカードを全て表にしてもらう
このルールを採用することはゲーム開始前に知らされている。
問題
どちらが有利か。
解答は追記↓
基本ルール
１．A,Bの２人に「自然数がランダムに１つ書かれたカード」を１０枚ずつ渡す
２．それぞれ、自分の１０枚の中から「あてられたくない数」を決める
３．それぞれ、１０枚のカードを横一列に並べて伏せる
４．それぞれ、相手の「あてられたくない数」がどのカードに書かれているかを予想し選ぶ
５．それぞれ、相手に選ばれたカードを同時に表にする
６．４と５を繰り替えす
「あてられたくない数」があてられたら負け。同時に当てたら引き分け。
ここまでだともちろんただの運ゲー。
これに次のルールを追加する
追加ルール
基本ルール３の後、A,Bはそれぞれ相手に次のことを要求する
Ａの要求：Ｂのカードを、小さい順に左から並べてもらう
Ｂの要求：Ａの「あてられたくない数」が偶数なら奇数が、奇数なら偶数が書かれている相手のカードを全て表にしてもらう
このルールを採用することはゲーム開始前に知らされている。
問題
どちらが有利か。
解答は追記↓
雑記
理系な話題を。
・内接円を使った三平方の定理の証明（びっくり数学島）
数学者の人のサイト
他にもいろいろおもしろい話が書かれている。
・定義集
物理学者が面白おかしく言葉を定義したもの
例を挙げると、このへんが面白かった
・空集合
「空集合に関する陳述はすべて真」とすることで、全く矛盾の無い体系が作れることを知り、空集合に関する陳述に悩まされることがなくなった。
「UFOの動力は反重力エンジンなんです」
「世界政府が実現すれば戦争はなくなる！」
・観測の理論
「生きたネコと死んだネコの重ね合わせ状態」
スピード違反はお巡りさんに観測された瞬間にスピード違反になるのであって、観測されるまでは「スピード違反の私」と「スピード違反なんかしてない私」の重ね合わせ状態である。これは物理的には間違った説明だが、心理的には正しい説明といえる。
・実験と一致する
フォン・ノイマンはセミナーで、講演者がいかにして実験値と理論曲線を合わせたか、を熱心に説明しているのを聞いて「少なくとも同一平面上には存在する」と呟いたそうである。
・実験と良く一致する
実験値と理論値が、同一平面上にあるだけでなく、同一曲線上にもあること。次元が一つ下がっただけだから大したことではない。
・電子と正孔
互いに引かれあう電子と正孔に、いろいろと邪魔が入ってややこしくなっているのが固体物理の全てであり、論文は１編の恋愛小説なのだ。
「電子同志が引き合って起きる超伝導は、やはり妖しい世界なのか」
・内接円を使った三平方の定理の証明（びっくり数学島）
数学者の人のサイト
他にもいろいろおもしろい話が書かれている。
・定義集
物理学者が面白おかしく言葉を定義したもの
例を挙げると、このへんが面白かった
・空集合
「空集合に関する陳述はすべて真」とすることで、全く矛盾の無い体系が作れることを知り、空集合に関する陳述に悩まされることがなくなった。
「UFOの動力は反重力エンジンなんです」
「世界政府が実現すれば戦争はなくなる！」
・観測の理論
「生きたネコと死んだネコの重ね合わせ状態」
スピード違反はお巡りさんに観測された瞬間にスピード違反になるのであって、観測されるまでは「スピード違反の私」と「スピード違反なんかしてない私」の重ね合わせ状態である。これは物理的には間違った説明だが、心理的には正しい説明といえる。
・実験と一致する
フォン・ノイマンはセミナーで、講演者がいかにして実験値と理論曲線を合わせたか、を熱心に説明しているのを聞いて「少なくとも同一平面上には存在する」と呟いたそうである。
・実験と良く一致する
実験値と理論値が、同一平面上にあるだけでなく、同一曲線上にもあること。次元が一つ下がっただけだから大したことではない。
・電子と正孔
互いに引かれあう電子と正孔に、いろいろと邪魔が入ってややこしくなっているのが固体物理の全てであり、論文は１編の恋愛小説なのだ。
「電子同志が引き合って起きる超伝導は、やはり妖しい世界なのか」
虫食い算関連まとめ
１０月７日
・『世界最大の虫食い算』を読んで
・同じ方針でより大きな虫食い算
（実際には、更に「上へ」伸ばすことができるので、もう少し桁数は増やせる）
・除数と被除数が１ケタ、２ケタで最大の完全虫食い算
（手計算による）
１０月１０日
・３ケタと古いプログラム(BASIC)
１０月１３日
・４ケタ、５ケタ、６ケタ
１０月１４日
・正しいプログラムとその根拠
２月１日
・７ケタ、８ケタと筆算形式出力プログラム
まとめ
3/7 小数第7位まで
11/29 *3 小数第27位まで
41/179 *5 小数第142位まで
1030/1087 *9 小数第528位まで
3270/3593 *26 小数第2067位まで
7300/8087 *123 小数第7054位まで
10030/35537 *274 小数第24236位まで
31010/113749 *856 小数第76952位まで※
※既約分数の分母を100万未満と仮定。
上記表の見方
例えば２行目の「11/29 *3 小数第27位まで」とは
33/87と22/58を区別するのに小数第27位まで計算が必要、という意味。
ということで、『世界最大の虫食い算』の方針では、12ケタ÷12ケタの完全虫食い算として約400万ケタ必要な物を作ったが、各ケタごとの最大虫食い算の長さが、１ケタ増える毎に約3.8倍になることを踏まえると、12ケタ÷12ケタだと2000万ケタくらいまでは作れるのかもしれない。
・『世界最大の虫食い算』を読んで
・同じ方針でより大きな虫食い算
（実際には、更に「上へ」伸ばすことができるので、もう少し桁数は増やせる）
・除数と被除数が１ケタ、２ケタで最大の完全虫食い算
（手計算による）
１０月１０日
・３ケタと古いプログラム(BASIC)
１０月１３日
・４ケタ、５ケタ、６ケタ
１０月１４日
・正しいプログラムとその根拠
２月１日
・７ケタ、８ケタと筆算形式出力プログラム
まとめ
3/7 小数第7位まで
11/29 *3 小数第27位まで
41/179 *5 小数第142位まで
1030/1087 *9 小数第528位まで
3270/3593 *26 小数第2067位まで
7300/8087 *123 小数第7054位まで
10030/35537 *274 小数第24236位まで
31010/113749 *856 小数第76952位まで※
※既約分数の分母を100万未満と仮定。
上記表の見方
例えば２行目の「11/29 *3 小数第27位まで」とは
33/87と22/58を区別するのに小数第27位まで計算が必要、という意味。
ということで、『世界最大の虫食い算』の方針では、12ケタ÷12ケタの完全虫食い算として約400万ケタ必要な物を作ったが、各ケタごとの最大虫食い算の長さが、１ケタ増える毎に約3.8倍になることを踏まえると、12ケタ÷12ケタだと2000万ケタくらいまでは作れるのかもしれない。
累乗の計算
例えばX^100は
２乗、４乗、８乗、１６乗、３２乗、６４乗、９６乗、１００乗
と、８回の乗算で求めることができる。
では一般にX^nは何回の乗算で求めることができるか？
最初は4回以内で求まるものまで、樹形図で書いて、５回で求まりそうなものは適当に考えて
0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4
をオンライン整数列大辞典で検索。
……したんだけど、これが驚くほどたくさん引っかかるんだよなー（検索結果）
しかも、違いが微妙な感じ。手計算だと、本当に８回必要なのか、それとも７回でできる可能性を見落としてるだけなのか、ちょっと怪しい気がしたので、プログラムに計算させてみようと思った。
……んだけど、全通り数え上げが難しい。
「一旦仮定して先まで進めて、その後戻ってきて別パターンを進む」っていうのは、プログラミング初心者には難しい。
ということで乱択アルゴリズムに頼ることにした。
n回目の計算で出来たものをB(n)に保存することにする。
B(0)=1、B(1)=2、B(2)=3か4
以降、B(n)は、B(0)～B(n-1)までから2つを選ぶことになるのでn(n+1)/2通り。
もちろんBの中に重複も出るけど、めんどくさいのでチェックしない。
そうして、例えばB(8)=100となったとすると、最小回数を保存するA(B(n))をチェックして、A(100)に8を入れることにする。
n=7まで調べるとすると、全てのパターンは2*6*10*15*21*28≒100万、だったので余裕を見て500万回ループ。
BASICですサーセン。
randomize
dim A(2 to 128)
dim B(0 to 7)
LET B(0)=1
LET B(1)=2
for N=1 to 5000000
LET B(2)=3
if rnd<1/2 then LET B(2)=4
for t=3 to 7
LET X=int(rnd*t)
LET Y=int(rnd*(t-X))+X
LET B(t)=B(X)+B(Y)
LET P=B(t)
if A(P)=0 or A(P)>t then LET A(P)=t
next t
next N
for t=4 to 128
print t;A(t)
next t
END
これの、0が出てこないところまで入れて再検索するとA3313がヒット。説明に「addition chain」って書いてあったので、多分あってる。
10001までの表も載ってる。ここまでは17回以下でできるそうだ。
さて、となるともう１つ疑問がわく。
「除算もありにするとどうなるか」
例えば、３１乗は乗算のみだと
２、３、６、１２、１５、３０、３１
と７回の計算が必要だが、除算を許すと
２、４、８、１６、３２、３１
と６回で可能となる。
これもプログラムで調べた。
ただし、１回進める毎に選択肢が「乗算」「除算」で２倍ずつになるので、6回目までを調べることにした。
2*6*10*15*21*2^4≒60万なので300万回ループ。
プログラムは、上記のものを、乱数でB(Y)に1か-1を掛けるように書き換える。
できたB(n)が負なら-1倍。
これで検索するとヒットしたのがA128998。説明が「addition-subtraction chain」だからこれもあってるはず。
ちなみにこのページからA229624という「除算ありだと少なくて済むようなn」の一覧があるが、6項しかなくて悲しい。
重複考慮しなければ24億通りくらいあるのに１億通りしか調べてないので、これだけだという保証はできないが、除算ありで８回以内にできるもののうちでは、上で挙げられている6つ以外に
93,94,95,124,126,127がある。（いずれも9→8）
（今度はC）
#include < stdio.h>
#include < stdlib.h>
#include < math.h>
int main(void)
{
int a[257],b[257],p[9],q[9],x,y,f;
long n;
char i;
p[0]=1;p[1]=2;q[0]=1;q[1]=2;
for(n=2;n<=256;n++){a[n]=0;b[n]=0;}
for(n=1;n<=100000000;n++){
p[2]=3+rand()%2;
q[2]=p[2];
for(i=3;i<=8;i++){
x=rand()%i;
y=rand()%(i-x)+x;
f=rand()%2*2-1;
p[i]=p[x]+p[y];
q[i]=q[x]+q[y]*f;
if(q[i]<0){q[i]*=-1;}
if(a[p[i]]==0||a[p[i]]>i){a[p[i]]=i;}
if(b[q[i]]==0||b[q[i]]>i){b[q[i]]=i;}
}
}
for(n=4;n<=256;n++){
if(a[n]!=b[n]){printf("%d %d %d\n",n,a[n],b[n]);}
}
return 0;
}
２乗、４乗、８乗、１６乗、３２乗、６４乗、９６乗、１００乗
と、８回の乗算で求めることができる。
では一般にX^nは何回の乗算で求めることができるか？
最初は4回以内で求まるものまで、樹形図で書いて、５回で求まりそうなものは適当に考えて
0,1,2,2,3,3,4,3,4,4,5,4,5,5,5,4
をオンライン整数列大辞典で検索。
……したんだけど、これが驚くほどたくさん引っかかるんだよなー（検索結果）
しかも、違いが微妙な感じ。手計算だと、本当に８回必要なのか、それとも７回でできる可能性を見落としてるだけなのか、ちょっと怪しい気がしたので、プログラムに計算させてみようと思った。
……んだけど、全通り数え上げが難しい。
「一旦仮定して先まで進めて、その後戻ってきて別パターンを進む」っていうのは、プログラミング初心者には難しい。
ということで乱択アルゴリズムに頼ることにした。
n回目の計算で出来たものをB(n)に保存することにする。
B(0)=1、B(1)=2、B(2)=3か4
以降、B(n)は、B(0)～B(n-1)までから2つを選ぶことになるのでn(n+1)/2通り。
もちろんBの中に重複も出るけど、めんどくさいのでチェックしない。
そうして、例えばB(8)=100となったとすると、最小回数を保存するA(B(n))をチェックして、A(100)に8を入れることにする。
n=7まで調べるとすると、全てのパターンは2*6*10*15*21*28≒100万、だったので余裕を見て500万回ループ。
BASICですサーセン。
randomize
dim A(2 to 128)
dim B(0 to 7)
LET B(0)=1
LET B(1)=2
for N=1 to 5000000
LET B(2)=3
if rnd<1/2 then LET B(2)=4
for t=3 to 7
LET X=int(rnd*t)
LET Y=int(rnd*(t-X))+X
LET B(t)=B(X)+B(Y)
LET P=B(t)
if A(P)=0 or A(P)>t then LET A(P)=t
next t
next N
for t=4 to 128
print t;A(t)
next t
END
これの、0が出てこないところまで入れて再検索するとA3313がヒット。説明に「addition chain」って書いてあったので、多分あってる。
10001までの表も載ってる。ここまでは17回以下でできるそうだ。
さて、となるともう１つ疑問がわく。
「除算もありにするとどうなるか」
例えば、３１乗は乗算のみだと
２、３、６、１２、１５、３０、３１
と７回の計算が必要だが、除算を許すと
２、４、８、１６、３２、３１
と６回で可能となる。
これもプログラムで調べた。
ただし、１回進める毎に選択肢が「乗算」「除算」で２倍ずつになるので、6回目までを調べることにした。
2*6*10*15*21*2^4≒60万なので300万回ループ。
プログラムは、上記のものを、乱数でB(Y)に1か-1を掛けるように書き換える。
できたB(n)が負なら-1倍。
これで検索するとヒットしたのがA128998。説明が「addition-subtraction chain」だからこれもあってるはず。
ちなみにこのページからA229624という「除算ありだと少なくて済むようなn」の一覧があるが、6項しかなくて悲しい。
重複考慮しなければ24億通りくらいあるのに１億通りしか調べてないので、これだけだという保証はできないが、除算ありで８回以内にできるもののうちでは、上で挙げられている6つ以外に
93,94,95,124,126,127がある。（いずれも9→8）
（今度はC）
#include < stdio.h>
#include < stdlib.h>
#include < math.h>
int main(void)
{
int a[257],b[257],p[9],q[9],x,y,f;
long n;
char i;
p[0]=1;p[1]=2;q[0]=1;q[1]=2;
for(n=2;n<=256;n++){a[n]=0;b[n]=0;}
for(n=1;n<=100000000;n++){
p[2]=3+rand()%2;
q[2]=p[2];
for(i=3;i<=8;i++){
x=rand()%i;
y=rand()%(i-x)+x;
f=rand()%2*2-1;
p[i]=p[x]+p[y];
q[i]=q[x]+q[y]*f;
if(q[i]<0){q[i]*=-1;}
if(a[p[i]]==0||a[p[i]]>i){a[p[i]]=i;}
if(b[q[i]]==0||b[q[i]]>i){b[q[i]]=i;}
}
}
for(n=4;n<=256;n++){
if(a[n]!=b[n]){printf("%d %d %d\n",n,a[n],b[n]);}
}
return 0;
}
