整数の部屋割り法は大体、わかっているつもりでしたが、 下記の問題に苦戦してます。どなたか、ヒントでもいいから ご教示ください。
「2桁の整数から任意の20個を選ぶとき、この中に a+d=b+c であるような a,b,c,d (a<b<c<d) が存在することを示せ。」
部屋割り法では、どんな特性をもつ部屋(箱)を何個用意するかがキーだと思いますが、この問題に限っては、どんな特性の部屋(箱)を何個用意したら良いか、アイデアが沸いてきません。なお、この問題は総合参考書の練習問題にありましたが、答は「省略」としか書いてありませんでした。どなたか宜しくお願い致します。
|
No.53664 - 2018/09/10(Mon) 18:55:28
| ☆ Re: 整数 ― 部屋割り法 / らすかる | | | 選んだ20個の整数を小さい順にa[1]〜a[20]として 条件を満たすa,b,c,dが存在しないと仮定します。 b[n]=a[n+1]-a[n](1≦n≦19)とすると b[n]=1を満たすnは最大2個(∵3個あると条件を満たすa,b,c,dが存在する) b[n]=2を満たすnは最大2個(∵同上) b[n]=3を満たすnは最大2個(∵同上) ・・・ b[n]=9を満たすnは最大2個(∵同上) よってa[20]-a[1]=Σ[n=1〜19]b[n]>(1+2+3+4+5+6+7+8+9)×2=90>89となり矛盾。
|
No.53668 - 2018/09/10(Mon) 19:48:31 |
| ☆ Re: 整数 ― 部屋割り法 / らすかる | | | より簡潔な方法を思い付きました。
2桁の整数20個から2個選ぶ組合せは20C2=190組あるが 2整数の差は最小1、最大89の89通りしかないので 190組のうち差が等しい3組が必ず存在する。 その差が等しい3組のうち2組をうまく選べば 差が等しく同じ整数を含まない2組(p,q),(r,s) が選べるので、その選んだp,q,r,sを小さい順に a,b,c,dとすれば、問題の条件を満たす。
|
No.53669 - 2018/09/10(Mon) 20:18:16 |
| ☆ Re: 整数 ― 部屋割り法 / ばたやん | | | No.53713 - 2018/09/11(Tue) 11:42:16 |
| ☆ Re: 整数 ― 部屋割り法 / IT | | | 基本の考え方は、らすかるさんのと同じで二番煎じですが、少し違った答案です。
2桁の整数20個から2個選ぶ組合せは20C2=190組 異なる2つの2桁の整数の和は最小21,最大197なので高々177通り。 したがってa+d=b+c,a<d,b<c,(a,d)≠(b,c)…(ア)となるa,b,c,d が存在する。 (ア)よりa,b,c,d の中に互いに等しい整数はない。 a<b としても一般性を失わない。 このときa+d=b+cよりc<d である。 よって a<b<c<d となる。(ここの説明は、らすかるさんの方法の方がスッキリしているかも知れません)
|
No.53730 - 2018/09/11(Tue) 23:06:29 |
|