$n$を自然数とする．右図のように，同じ大きさの正方形のマスが$2^n$個描かれた透明なシート$K_n$を使って次のゲームを行う．まず，$1$から$2^n$までの自然数の中から無作為に一つ選ぶ試行を$2$回行い，$1$回目に選ばれた自然数を$x_1$，$2$回目に選ばれた自然数を$x_2$とする（$x_1=x_2$となることもある）．このとき，$K_n$の左から$x_1$個目のマスに$\bigcirc$を記入し，左から$x_2$個目のマスに$\times$を記入する．次に，このシートを中央の線（左右のマスの数が等しくなるような縦の線）で折り畳むという操作を繰り返し行い，$\bigcirc$が書かれたマスと$\times$が書かれたマスが重なったときゲームを終了する．ゲームが$k$回の操作で終了したとき，得点を$k$とする．例えば，$n=3$，$x_1=2$，$x_2=6$のとき右図のようになり，得点は$2$となる．ただし，$\bigcirc$，$\times$が始めから同じマスにある場合は得点を$0$とする．以上のゲームにおいて$k$点を得る確率を$p(n,\ k)$とする．このとき，次の問いに答えよ．
(1) $p(n,\ 1)$を求めよ．また，$n \geqq 2$のとき，$p(n,\ 2)$を求めよ．
(2) $2 \leqq k \leqq n$のとき，$p(n,\ k)$を$p(n-1,\ k-1)$を用いて表せ．
(3) $1 \leqq k \leqq n$のとき，$p(n,\ k)$を求めよ．