東進数学コンクール２０１３年１２月５日発表問題 - c21coterie @ ウィキ

http://www.toshin.com/concours/
東進数学コンクール２０１３年１２月５日に答えが公開される問題です。

問題

30個の島と150本の橋があり、島と島の間は一本の橋で結ばれているか、結ばれていないかのいずれかである。また、どの島からどの島へも橋を 何本か伝って渡
ることができる。
15個の島に赤の旗が立っており、残りの15個の島には青の旗が立っている。
この状態からスタートして、以下の動作で旗の色を変える。
①30個の島の中からランダムに1つ島を選び、それをXとする。
②島Xと橋で結ばれている島の中からランダムに一つ選び、それをYとする。
③Xの旗の色とYの旗の色が異なる場合、Yの旗の色をXの旗の色と同じものに変える。
この動作を全ての島の旗の色が同じになるまで繰り返し行う。このとき全ての島の旗の色が赤になる確率は橋の配置により異なるが、その最大値を求めよ。

私なりの解法

堀江伸一こと私の解法。

この問題、数式で解くらしいのですが数式を思いつかなったのでシミュレーションで近似解を求めてみました。
橋の配置は
青島はすべての青島と接続、15*14/２＝１０５本。
赤島は赤島～青島へ３本ずつ青島へ橋を伸ばし４５本。
青島は赤島へ３本ずつ橋がつながる。

精度の高いシミュレーション的にはこれをマルコフ過程としてとらえ、行列演算が安定解に収束するまで分布を計算すればよいのですが。
そこまでこったコードを書くのもめんどくさいし２＾３０の状態数の管理を効率よく描くのもめんどいです。
単純に1０万回勝負させて約85.6％という近似解を得ました。
コードや発送に記述ミスがなければこの辺が答えです。
答えの公開が楽しみですね。

• 2013/11/21

コードに記述ミスがあったことが判明。
記述ミス修正。
その結果計算の精度が下がったようで２０万回の勝負に増加させる。
85.8％近辺に答えがあることが判明。

• 2013/11/24

コードの数字を一か所書き間違えてるのを発見。
修正した結果85.05%近辺に答えがありそうだと判明。

2０万回勝負させるコード。
MT.hヘッダについてはこちらを参照のこと。
http://www.sat.t.u-tokyo.ac.jp/~omi/random_variables_generation.html
http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/CODES/mt19937ar.c

#include <iostream.h>
#include <stdio.h>
#include <time.h>
#include "MT.h"
const int Red=1;
const int Blue=0;
double RedVictory=0;
double BlueVictory=0;


void calc(){
	int island[2][15],BRCount[2]={15,15};
	unsigned long isLandTypeX,isLandTypeY,x,y,temp;
	for(int i=0;i<15;i++){
		island[Blue][i]=Blue;
		island[Red][i]=Red;
	}
	for(int i=0;i<10000;i++){
		isLandTypeX=genrand_int32()%2;
		x=genrand_int32()%15;
		int XColor,YColor;
		if(isLandTypeX==Blue){
			//初期青島がXになった
			temp=genrand_int32()%17;
 			if(temp<3){
				//初期赤島がYになった
				y=(15-temp+x)%15;
				isLandTypeY=Red;
			}else{
				//初期青島がYになった
				y=(temp-3)%14;
				if(x<=y)y=(y+1)%15;
				isLandTypeY=Blue;
			}
		}else{
			//初期赤島がXになった
			//Yが青島になる
			isLandTypeY=Blue;
			y=(genrand_int32()%3+x)%15;
		}
		//旗の色替え処理
		XColor=island[(int)isLandTypeX][(int)x];
 		YColor=island[(int)isLandTypeY][(int)y];
		BRCount[(int)XColor]++;
		BRCount[(int)YColor]--;
		island[(int)isLandTypeY][(int)y]=XColor;
		
		if(BRCount[Blue]==0||BRCount[Red]==0)break;
	}
	
	if(BRCount[Red]==0){
 		BlueVictory+=1;
	}else if(BRCount[Blue]==0){
		RedVictory+=1;
	}
}

int main(){
	int i;
 	unsigned long a;
	init_genrand((unsigned)time(NULL));
 	for(int i=0;i<200000;i++){
		calc();
	}
	double all=RedVictory+BlueVictory;
	std::cout<<RedVictory<<" "<<BlueVictory<<" "<<RedVictory/all;
}