2n個の整数がある。それらの数をn個ずつ2組に分けたとき、どう分けても各組の数の和S[1],S[2]の差はnより小さいとする。このとき、これらの2n個の数のうち少なくともn+1個は等しいことを証明せよ。
上記の問の解き方を教えてください。
|
No.44900 - 2017/07/25(Tue) 16:56:26
| ☆ Re: / IT | | | 対偶が正しいことを示します。
・2n個の整数を昇順に並べ, a[1]≦a[2]≦a[3]≦...≦a[n]≦a[n+1]≦...≦a[2n].とします。
・S[1]とS[2]の差が最大になるように, S[1]=a[1]+a[2]+a[3]+...+a[n] S[2]=a[n+1]+a[n+2]+a[n+3]+...+a[2n]とします。
・2n個の数のうちのどのn+1個を抽出しても,少なくとも一つは異なるとすると,
a[1],a[2],a[3],...a[n],a[n+1]の少なくとも一つは異なるので,a[1]+1≦a[n+1] となる.
同様に,a[2]+1≦a[n+2], a[3]+1≦a[n+3],...,a[n]+1≦a[2n]がいえる.
このとき,S[2]-S[1]≧nとなる.
・したがって、....
|
No.44901 - 2017/07/25(Tue) 17:57:14 |
| ☆ Re: / TOKO | | | No.44918 - 2017/07/26(Wed) 23:38:48 |
|