パズルは面白い

パズルが好きで毎日やっているわけですが、自分の軌跡を残しておきたいと、ふと思いました。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

Online Sudoku 2006

大会参加に応募してきました。

予選   2006/9/18~22 各日50名、計250名通過
準々決勝 2006/10/1 50名通過
準決勝  2006/10/8 ?名通過
決勝   2006/10/15
というスケジュールで、決勝はロンドンに行かなきゃならないので、仮にそこまで通っても参加は無理だけど、とりあえず力試しで準決勝通過・決勝辞退を目指します。

開催の時間帯が明かされていないので、予選(2時間のOnlineSudokuの上位50名通過)を受けられるかもあやしいけど。

さて、Hardの問題集めのほうは、1000盤面で272種類です。このペースで300問までいくのだろうか? ここ150盤面で3種類しか増えていないし。
度数を集計してみるとこんな感じ。
1回 :23問
2回 :53問
3回 :66問
4回 :47問
5回 :39問
6回 :27問
7回 :10問
8回 :6問
9回 :0問
10回 :1問
スポンサーサイト
  1. 2006/09/10(日) 22:59:16|
  2. パズル・問題・イベント
  3. | トラックバック:1
  4. | コメント:10

コメント

度数分布から,全部で何問かわかったりしませんか?
  1. 2006/09/11(月) 10:49:23 |
  2. URL |
  3. <Melvy> #jRSFIvM.
  4. [ 編集]

オンライン数独はやったことないのでどんな人が集まっているのかわからないのですが、タロタロさんなら十分チャンス有り・・と、捉えていいのですよね。頑張ってください~♪^^
  1. 2006/09/12(火) 00:36:15 |
  2. URL |
  3. 都道 #IfpOg5qo
  4. [ 編集]

きっとわかるんでしょうけど、精度良く求めるには標本数が絶対的に足りない、ような気もしますね。
私の数学力は高校程度でピタッと止まっているので、あとはセミプロの方々に教えを乞いたいな。
  1. 2006/09/12(火) 00:47:55 |
  2. URL |
  3. タロタロ #-
  4. [ 編集]

これはやはり私がやるんでしょうか (笑).
考えてみましたが,どうもうまくいかないので識者の方の意見を待ちたいところです.
以下に考えたことを述べます.

尤度関数の考え方を使うと,
「盤面が全部で n 種類あるとするとき,タロタロさんの観測した事象が起きる確率を求めることができる.
この確率が最も高い n が,最も 『それらしい』 n である」
となります.
では,この確率を求めてみましょう.

各盤面は各回独立に 1/n の確率で発生すると考えられるので,タロタロさんの観測した盤面列が発生する確率は (1/n)^1000 となります.
n は少なくとも 272 以上であることがわかっているので,この範囲でこの確率を最大化するのは n = 272 です.
つまり,もう観測されていない盤面などない,ということになります.

ですが,これは 1000 回でなくても,観測した分布がどうであっても言えることなので,何かがおかしいような気がしているのです.
数百種のものを 1000 回観測したところで,まだ見ていないものがある方が自然に思えますし.

…と書いていたら,もう一つの算定法を思いつきました.あとでこちらも書きますね.
  1. 2006/09/12(火) 02:52:51 |
  2. URL |
  3. <Melvy> #jRSFIvM.
  4. [ 編集]

では,もう一つの算定法について.
n 種類が等確率で出現するとき,全部をコンプリートするのにかかる回数は
1 + n/(n-1) + n/(n-2) + … + n/2 + n
となります.
この式の i 項目は,i-1 種類が集まっているとき i 種類目を集めるのにかかる回数の期待値ですから,これを第 272 項目まで足して 1000 に近い値になる n を推定値とみなすことができます.

この算定法によると (さすがに電卓とかではきついのでコンピュータを使いました),n = 279 のときにもっとも 1000 に近い値になります.あと 7 種類ですね.
ちなみに同じように計算していくと,この 7 種をコンプリートするには平均であと 723 回かかります.
そんな中途半端な種類数のわけはないですが.

300 種類とすると,272 種を集めるのに平均 707 回かかり,そこからすべてを集めるのにはさらに 1178 回を要します.

なお,この算定の信頼性については読者の宿題とします (笑).
  1. 2006/09/12(火) 03:35:05 |
  2. URL |
  3. <Melvy> #jRSFIvM.
  4. [ 編集]

問題がN種類あるとしたとき、
ある問題が1000回中1度も現れない確率をP(N)とすると
1000回中1度も現れない問題の個数の期待値はN*P(N)なので
これがN-272となるようなNを求めれば良いように思います。

P(N)=((N-1)/N)^1000で、これはe^(-1000/N)と近似でき、
これから上の式を満たすNを求めるとN=280となりますね。
  1. 2006/09/12(火) 12:41:47 |
  2. URL |
  3. 稲葉直貴 #k.P5BJgI
  4. [ 編集]

<Melvy>さん、稲葉さん、ありがとうございます。
どうやら279~280らしいことがわかりました。
あとは体力・気力の問題ですね。
頑張れるかなぁ。
  1. 2006/09/12(火) 23:33:43 |
  2. URL |
  3. タロタロ #-
  4. [ 編集]

いえ、そこまで精度良く求めるには標本数が絶対的に足りてない、という意見に賛成です。
  1. 2006/09/13(水) 02:09:55 |
  2. URL |
  3. 稲葉直貴 #k.P5BJgI
  4. [ 編集]

最近、OnlineSudokuはじめてみました。(事情がありいつもと違うIDnameです。)
tarotaroさんに話しかけられたもののあまりうまく会話できず
(PCの調子がおかしかったとも言う(^^ゞ)、4人→3人に
部屋を移動する時も間違えてログアウトしてしまったり)、
失礼いたしましたm(_ _)m。

10回も出ているものもあるんですね。
これだけ繰り返し出る数が多いと、
覚えてしまうものも出てきてしまうのでは、と思うのですが
そのあたりはどんな感じなのでしょうか?
  1. 2006/09/18(月) 11:38:53 |
  2. URL |
  3. さかたん #XMidKxDI
  4. [ 編集]

さかたんさん。
今日昼間chatした日本の方は誰だろう?と思っていました。
さかたんさんだったとは! 言われてみればsakatanと似ていなくも無いですね。

前に見たような問題だと感じることはあっても、私は解き方までは覚えていません。もっとも同じ問題が続けて出たとき(何回か経験しています)は何となく覚えてましたけど。

コンテストの予選はいつの間にか9/25-29に延期になったようですね。
  1. 2006/09/18(月) 18:13:48 |
  2. URL |
  3. タロタロ #-
  4. [ 編集]

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://puzzleelzzup.blog33.fc2.com/tb.php/155-49787c72
この記事にトラックバックする(FC2ブログユーザー)

[パズル・ゲーム] Online World Sudoku Championship 2006

大会の受付が始まっていたんですね.タロタロさんのブログで知りました.申し込みました. 日程なんかはタロタロさんが書いていらっしゃるのでそちらを見ていただくとして,決勝 @ ロンドンは旅費も交通費も出してくれる,というように読めます.タダでロンドン… (妄想).
  1. 2006/09/11(月) 10:46:26 |
  2. ある大学院生 &lt;Melvy&gt; の日記~そこには なにもありません~

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。