20枚神経衰弱ゲーム数→
10G=1,
11G=330,
12G=38940,
13G=1940708,
14G=38250520,
15G=235449500,
16G=310432606,
17G=67020602,
18G=1594846,
19G=1022,
という仮説。
— MTAK (@lmtak) June 19, 2015
こんな感じで計算させてみました。
package calc; import java.util.HashSet; public class PairCards { private int finalPairs = 0; private long[] games = new long[0]; private PairCards(int pairs) { this.finalPairs = pairs; this.games = new long[pairs * 2]; } public static void main(String[] args) { int pairs = 10; if (args != null && args.length > 0) { try { pairs = Integer.parseInt(args[0]); } catch (NumberFormatException nfe) { // NOP } } new PairCards(pairs).start(); } private void start() { long startMillis = System.currentTimeMillis(); generatePatterns(new char[0], 0); long endMillis = System.currentTimeMillis(); // result long elapsed = endMillis - startMillis; System.out.println("elapsed: " + elapsed + " (ms)"); for (int i = finalPairs; i < finalPairs * 2; i++) { System.out.println(i + " turns : " + games[i]); } } private void generatePatterns(char[] parents, int pairs) { int currentPairs = pairs + 1; char[] cards = new char[parents.length + 2]; char newCard = (char)('a' + currentPairs - 1); int inserts = currentPairs * 2 - 1; cards[0] = newCard; cards[1] = newCard; for (int i = 2; i < cards.length; i++) { cards[i] = parents[i - 2]; } for (int j = 0; j < inserts; j++) { if (j > 0) { // swap char x = cards[j]; cards[j] = cards[j + 1]; cards[j + 1] = x; } if (currentPairs >= this.finalPairs) { play(cards); } else { generatePatterns(cards, currentPairs); } } } private void play(char[] cards) { HashSet<Character> appeared = new HashSet<Character>(); int turns = 0; int cidx = 0; while (cidx < cards.length) { // 1st-card Character first = (Character)cards[cidx++]; if (appeared.contains(first)) { // got pair. turns++; continue; } else { // memory this-card appeared.add(first); } // 2nd-card Character second = (Character)cards[cidx++]; if (first == second) { // LUCKY!! got pair. turns++; } else if (appeared.contains(second)) { // will get pair in next turn. turns += 2; } else { // memory this-card appeared.add(second); turns++; } } games[turns]++; } }
実行結果はこんな感じで出力されました。6分かかってない。
elapsed: 348735 (ms)
10 turns : 1
11 turns : 330
12 turns : 38940
13 turns : 1940708
14 turns : 38250520
15 turns : 235449500
16 turns : 310432606
17 turns : 67020602
18 turns : 1594846
19 turns : 1022
解説とか
すべての順列で試すと計算量が爆発する(カード20枚の場合は、20! = 243 2902 0081 7664 0000)ので、すべての組み合わせ(カード20枚の場合は、19×17×15×……×3×1 = 6 5472 9075)で計算させます。
まずは2枚の場合
当然1ターンで終了です。このとき、カードが「A」と「a」であった場合、順列だと「Aa」「aA」の2通りありますが、いずれも1ターンで終了するため、この2枚を同一視して「AA」とみなしても確率は2/2 = 1/1 と同じ結果になります。
つぎに4枚の場合
カードが「A」、「a」、「B」、「b」の場合、順列だと 4! = 24 通りになります。すべて書き出すと、
- AaBb : 2ターン
- aABb : 2ターン
- AabB : 2ターン
- aAbB : 2ターン
- BbAa : 2ターン
- bBAa : 2ターン
- BbaA : 2ターン
- bBaA : 2ターン
- ABab : 3ターン
- aBAb : 3ターン
- AbaB : 3ターン
- abAB : 3ターン
- BAba : 3ターン
- bABa : 3ターン
- BabA : 3ターン
- baBA : 3ターン
- ABba : 3ターン
- aBbA : 3ターン
- AbBa : 3ターン
- abBA : 3ターン
- BAab : 3ターン
- bAaB : 3ターン
- BaAb : 3ターン
- baAB : 3ターン
2ターンは8通り、3ターンは16通りですので、確率だと2ターン = 8/24 = 1/3、いっぽう3ターン = 16/24 = 2/3となります。
組み合わせだと「AABB」「ABAB」「ABBA」の3通りに集約できます。このとき、「AABB」は2ターンで終了、「ABAB」は3ターンで終了、 「ABBA」も3ターンで終了です。確率で見ると、2ターン = 1/3、いっぽう3ターン = 2/3で、順列でも組み合わせでも確率は同じ値になります。
組み合わせの数え上げについて
以下のような手順でもれなく数え上げることが出来ます。
2枚から4枚のときは、「ZZ」に対して2枚の「Y」を差し込みます。差し込むときは、「◎●Z●Z●」のように考えて、「◎」に1枚目の「Y」を固定で配置し、「●」のいずれかに2枚目の「Y」を配置します。
4枚から6枚のときも同様に、「YYZZ」「YZYZ」「YZZY」に2枚の「X」を差し込みます。最初の「YYZZ」に対しては、「XXYYZZ」「XYXYZZ」「XYYXZZ」「XYYZXZ」「XYYZZX」の5通りが考えられ、残りの「YZYZ」「YZZY」にも同様に5通りずつの差し込み方が考えられます。
このアルゴリズムで、指定のペア数に対する数え上げが出来ます。Javaソースでは、generatePatterns(char[], int)
メソッドが再帰呼出しで実装されています。
ターン数の数え上げについて
ツイート再掲。
さて、問題の20パネル神経衰弱のそこそこ手際がよさそうな手順考えてみたから再掲しとくよ。最善かと言われると自信ないけど参考にしてみてくださいな。 pic.twitter.com/5Gk7QnntzH
— 0x1CED-ネイチャー絶対許さねえマン (@num89th) June 17, 2015
上記のJavaソースでは、
play(char[])
メソッドにて実装されています。既に出てきたカードを覚えておくためのSet<Character>
を生成し、#contains(Character)
で既出かどうかの判定をします。
1枚目をめくり、Set
に含まれていれば、そのペアを取って1ターン終了。ターン終了なので、次にめくるのはまた1枚目です。
1枚目に含まれていなければ、Set
に覚えさせます。
2枚目をめくり、1枚目と同じカードならペアを取って1ターン終了です。ラッキーですね。
1枚目とは違うカードで、Set
に含まれていれば、次のターンでそのペアを取ります。よって2ターンかかります。
1枚目とは違うカードで、Set
に含まれていなければ、Set
に覚えさせて、1ターン終了です。