7706：1〜nからm個の和がmの倍数に2通り以上取れる…n>2...

問題7706・・・http://ddincrement.blog.shinobi.jp/amoo_o/6 より 引用 Orz〜

1〜nの数字を一つずつ使い、下記条件を満たす数列a[1],…,a[n]を作る。

条件：「1≦m≦nについて、a[1]＋…＋a[m] はa[m]で割り切れる。」

2＜nのとき、条件を満たす並べ方が少なくとも2つ以上あることを示せ。

（amoO_O様）

解答

・わたしの…

1,2,3,…,m…1〜mの和は…(1+m)m/2 

なので…mが奇数ならmの倍数

n-m,n-(m-1),n-(m-2),…,n-1…の和=m*(2n-m-1)/2

なので…mが奇数ならmの倍数

たとえば…

1〜10のとき…

m=7 なら…

1+2+3+4+5+6+7=7*8/2=7*4

3+4+5+6+7+8+9=7*12/2=7*6

mが偶数のとき、たとえば…n=m=4 のとき…

1+2+3+4=10で4の倍数にゃならないですね…?

↑

嘘でしたぁ…^^;

↓

・鍵コメH様からのもの Orz〜

3個の場合は213,312、4個の場合は4231,3142と作ることができます

nが奇数の場合は(n-1)個まで並べて最後にnをつければいいので
nが偶数個の時に2通り作れれば良いことになります

1〜2nまでの数を並べる場合
n+1 1 n+2 2 ･･･ n+k k ･･･ 2n n
2n-1 1 2 2+(n-1) 3 3+(n-1) ･･･ k k+(n-1) ･･･ n-1 2(n-1) 2n n
といった並べ方なら証明しやすいと思います

*題意の意味が了解できました☆…グラッチェ〜m(_ _)m〜

けっきょく...

n(n+1)/2=整数 で考えれば…
n=2m-1 なら…最後にn or m or 1
n=2m なら…最後にm or 1…(2m+1>n なので無理…)
でOKとわかりますのでしたのね ^^♪

[スモークマン]

＞2:06amの鍵コメHさまへ ^^
題意を十分理解できていませんでしたぁ ^^;
数字を並べて、その最後の数字で和が割り切れる並べ方が二通り以上を言えばよかったんですね Orz〜
最後が1の場合が１通り…
偶数の場合は…1,2,3,…,nとn+1,n+2,…,n+n
が同数なので、どちらもnの倍数だから…a[2n]=n にしておけばいくらでもあるってわけでしたのね ^^
たとえば…
6個なら…234561, 124563
8個なら…2345671, 12356784

n(n+1)/2=整数 で考えれば…
n=2m-1 なら…最後にn or m or 1
n=2m なら…最後にm or 1…(2m+1>n なので無理…)
でOKとわかりますのでしたぁ♪

紹介させていただきまっす〜m(_ _)m〜v