PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 158 / 左隣の文字より辞書順で後になる文字がちょうど1個となる文字列の探査

26文字のアルファベットから3個の異なった文字を取ると,長さ3の文字列を作ることができる。例えば 'abc','hat','zyx' である。
この3つの例について調べると,'abc'は左隣の文字より辞書順で後になる文字が2個ある。'hat'では左隣の文字より辞書順で後になる文字がちょうど1個であり,'zyx'では0個である。
左隣の文字より辞書順で後になる文字がちょうど1個となるような長さ3の文字列は全部で10400個ある。
n ≤ 26 個の異なるアルファベットからなる文字列について考える。p(n) を左隣の文字より辞書順で後になる文字がちょうど1個あるような長さ n の文字列の個数とする。p(n) の最大値を求めよ。

Problem 158 - PukiWiki


入試問題でたまに見るタイプの問題ですね。アルファベットのかわりに1から26までの数で考えます。

  1. 26 個の数から n 個を選ぶ。C(26, n) 通り。
  2. n 個の文字を2つのグループ A, B にわける。A か B が空集合になる場合は不可なので 2^n-2 通り。
  3. A, B の要素をそれぞれ小さい順に並べる。
  4. (Aの最小値)>(Bの最大値)となる場合は不可。n-1 通り。

まとめると

 p(n)={}_{26}\mathrm{C}_n \cdot (2^n-n-1)

これの最大値を求めます。


Mathematica らしくグラフも描いてみました。最大値は p(18) です。

f:id:variee:20170916021750p:plain