次: 必要条件・十分条件 上: 例で考える 前: 例で考える

02滋賀医大

各頂点から2本ずつ枝分かれした樹形図の各頂点に，上から下へ左から右へと図のように番号をつけ 番号 i をつけた頂点を頂点 i と呼ぶ．

(1)

頂点 i のすぐ下の段にあって頂点 i と結ばれている頂点の番号は 2i と 2i+1 であることを示せ．

(2)

第 n 段までのすべての頂点に1つずつ石を置いて，各石を1段ずつ 枝に沿って上に動かし，頂点1に達すれば「上がり」として外に取り出す． 全ての石を取り出すのに要する操作の総数 S_n を求めよ．ただし，1つの 石を1段上に動かすこと，または頂点1にある石を外に取り出すことを1つの 操作とする． たとえば， $S_1=1,\ S_2=5,\ S_3=17$ である．また，1つの頂点には2つ 以上の石は置けないものとする．

(3)

自然数 $k,\ n\ (k<n)$ に対して，次のような条件を満たす自然数の対 $(i,\ j)\ (i<j)$ の個数を $k,\ n$ で表せ．

$$\begin{array}{ll} 条件\ :&頂点iと頂点jは第n段にあり，それぞぎ.. ...段ずつ交互に上に動かすと，第k段ではじめて出会う． \end{array}$$