ぷらこのきろく

メモとかテストとか備忘録とか

算数の問題

ちゃんと書ける日記がここしかないのでここで。
せっかくだからてふとか使ってみよう。

ツイッターみてたらこんな問題が流れてきた。
https://twitter.com/nekonyannyan821/status/915572712596168704

で、仕事帰りの電車の中で解こうとがんばってた。。

すべてのi (1 \leq i \leq n) で i番目のカードの数字がi \\
つまり 1,2,...n とカードの数字が並んだ場合は条件を満たす。これを基準に考える。\\
んで、nのカードのどこかのカードを入れ替えたn-1通りは、条件を満たす。\\
1からn-1までのカードで、任意の2枚を入れ替えた場合、\\
小さい数字のカードは条件を満たさなくなるが、\\
そのカードとnのカードを入れ替えたらまた条件を満たす。\\
というわけで_n C _2 = \frac{n(n-1)}2\\
任意の3枚以上を入れ替えたらきっと条件を満たすのは無理っぽいから\\
全部足して\frac{n(n+1)}2\\
が答えなんじゃなかろうか。

てなことを考えてたんだけど、
問題流した人がヒントというか答え出してて
1が入るのは2通り、そのいずれにも2が入るのが2とおり、・・・
って言ってた。
なんでだーって悩んでたら
3枚以上の入れ替えでも
1,2,3,4→2,3,1,4と1つずつくるっとずらすように入れ替えて、最後に一番小さな1と4を入れ替えたら
条件満たすやん、と、家かえってお風呂に入ってから思い立ったしまった。
もちろん3以上でも成り立つ。
で、条件満たすために入れ替えるのが「1つずつくるっとずらす」だけだとしたら
 1 + (n-1) + _n C _2 + _n C _3 + ... _n C _{n-1} \\
2項定理とかで 2^{n-1}通りじゃないか。
これはヒントと合致する。
ただ、入れ替えの条件が他ではダメだということを証明してないからなんか気持ち悪い。


で、なんかくやしい。もっと方法ないか。

 n = 2のとき 2通り\\
n = k のときa _k通りと仮定したとき、n = k+1のとき増える場合は\\
  1,2,...nの順に並ぶ場合の最後に{n+1}のカードを加えた場合の1通り\\
  上の場合に、{n+1}のカードと任意のカード1枚を入れ替えた場合、n通り\\
  1,2,...nの順に並んでいないカードの最後に{n+1}のカードを加え、 \\
  n番目のカードと{n+1}番目のカードを入れ替える場合、a _k - 1通り\\
だから・・・いやちょっとまて

1~nを並べたときに、条件に合わないiが一つだけある場合
をカウントせんといかんのじゃないか。

あまりに力押しで疲れてきた。うーんやっぱりあの2通りが何個分のがいちばんスマートだよなぁ。。
とりあえず今日は疲れたので寝る。