問題7163(鍵コメT様からの提示問)
2以上の自然数nが与えられたとき、
1からnまでの自然数n個を勝手に並びかえた順列
P=(p1,p2,……..,pn)に対して
a(P)=|p2-p1|+|p3-p2|+……..|pn-p(n-1)| とおくとき,
nを固定すれば,a(P)の最大値は,
nが偶数のとき,n=2mとして,最大値2m^2-1,
nが奇数のとき,n=2m+1として,最大値2m^2+2m-1です.
では,nを固定したとき,a(P)が最大となるPの個数はいくつでしょうか.
(偶数,奇数に分けて,mで表してください.)
解答
・わたしの…
・n=2m の場合…
真ん中の間隔1を飛び越した次の点(m+1番目の点)までの取り方…は…
片側に、m-1個あり、その後は、そこから残ってる最遠点同士を結んで行けば1通りに決まるので…
左右対称性から…2(m-1)=2m-2 通り
これは、元の逆順だけある...
ただし…
m+1=2…m=1のときは…2通り
・n=2m+1の場合…
同様に考えて…片側の(2m+1-3)/2=m-1個からm+2番目の点まで結んで、あとは同じように最遠点まで結んで行けば1通りに決まるので…やはり…左右対称性から…2(m-1)=2m-2 通り
これらの逆順も左右対称にあるので…4m-4通り
ただし…
m+2=3…m=1のときは…4通り
かな ?…^^
↑
じぇんじぇん駄目駄目でしたぁ…^^;
↓
・鍵コメT様からの大ヒント♪
たとえばn=5のとき,m=2,a(P)の最大値は2*2^2+2*2-1=11であり,
11を与えるPは,
3,1,5,2,4/3,2,5,1,4/3,4,1,5,2/3,5,1,4,2とその逆順(8通り)です.
また,n=6のとき,m=3,a(P)の最大値は2*3^2-1=17であり,
17を与えるPは,
3,5,1,6,2,4/3,5,2,6,1,4/3,6,1,5,2,4/3,6,2,5,1,4とその逆順(8通り)です.
ちょっとヒントが過ぎるかもしれませんが,
n=7,m=3に対しては,最大値を与えるPは48通り,
n=8,m=4に対しては,最大値を与えるPは72通り,
n=9,m=4に対しては,最大値を与えるPは576通り,
n=10,m=5に対しては,最大値を与えるPは1152通りあります.
*我考えるゆえに我あるらし…?
法則は見つけられたかも…?
n=5,m=2…2*2!*1!*2=8
n=6,m=3…(2!)^2*2=8
n=7,m=3…2*3!*2!*2=48
n=8,m=4…(3!)^2*2=72
n=9,m=4…2*4!*3!*2=576
n=10,m=5…(4!)^2*2=1152
つまり…
n=2mのとき…((m-1)!)^2*2
n=2m+1のとき…2*m!*(m-1)!*2=4*m!*(m-1)!
になりそうも...その意味付けが今一わからない…^^;
・鍵コメT様の凄い発想☆
[7160]を振り返ってみると,nを固定して,a(P)を最大にするには,
・最初の数と最後の数の差も隣り合うものに含めてループを作るとき,
(n+1)/2より小さい数(S数と名付ける)はすべて,
両隣により大きい数が置かれ,
(n+1)/2より大きい数(L数と名付ける)はすべて,
両隣により小さい数が置かれること
・最初の数と最後の数は,差が1であること
の両方が成り立てばよいことになります.
nが偶数のとき,n個の数はn/2個のS数とn/2個のL数からなり,
ループは,S数とL数を交互に並べるしかありません.
さらに,ループを切断するところは,2数の差が1でないといけないので,
その両隣(つまり,Pの初項と末項)は,n/2 と n/2+1 に限ります.
n/2が初項の場合,Pの第(奇数)項はすべてS数,第(偶数)項はすべてL数であり,
初項と末項は決まっているので,Pの作り方は(n/2-1)!*(n/2-1)!通り.
n/2が末項の場合も同様なので,最大値を与えるPは,((n/2-1)!^2)*2通り,
すなわち2*((m-1)!^2)通りです.
nが奇数のとき,n個の数は(n-1)/2個のS数と(n-1)/2個のL数,および,
どちらでもない「(n+1)/2」(M数と名付ける)からなり,
ループは,M数の隣から順に,L,S,L,S,…のように並びます.
ループを切断するところは,M数の隣しかあり得ず,
Pは初項または末項にM数が入り,その隣から順に,LSLS…またはSLSL…となって,
一番最後は,M数に隣接するS数またはL数((n-1)/2または(n+3)/2)となります.
Pの作り方は,M数が初項か末項か(2通り),その反対側の端の項はS数かL数か(2通り),
残りのS数およびL数の並べ方(m!*(m-1)!)によって決まるので,
場合の数は,2*2*m!*(m-1)!=4*m!*(m-1)!通りです.
*熟読玩味ぃ…^^;v
・友人からのもの ^^
この解答[7160]を見ればPの個数は次のようになると思います。
n=2m のとき N(P)={(m-1)!}^2
n=2m+1 のときN(P)=(m-1)!m!
要するに両端を差が少ないまん中にもってきて、それ以外は前半と後半から
交互に適当に1つずつ取ってきて、上がり下がりにすればよい。
すべて係数が1の一次式だから、1か所でk多く取れば、別のところがk
少なくなり、両端は片方にしか関与しないから、まん中にとればよい。
*それらの逆があるから…
偶数は真ん中から数えてるから…x2
奇数は真ん中が2個あるから…x2^2 倍するべきですが…
友人からの回答は早かったぁ♪
友人からこれに絡んで考えたって問題が届きました☆
アップしますね ^^