平成２８年３月１３日

[流れ星]

　　　　　第331回数学的な応募解答

　　　　　　＜解答募集期間：２月14日〜3月13日＞

［部屋割り論法］

　「・・・の中には少なくともひとつの・・・が存在する」という形の命題を証明するのに有効なのが部屋割り論法と呼ばれる証明方法です。

その論法は「ｎ＋１人をｎ室の部屋に入れたとき、少なくとも一つの部屋は2人以上の人が入ることになる」という当たり前の事実である。

　ここで、

問題１：２ｎ個の整数がある。それらの数をｎ個ずつの２組に分けるとき、どう分けても、各組の数の和Ｓ_１、Ｓ_２の差はｎより小さいとする。

このとき、これらの２ｎ個の数のうち、少なくともｎ＋１個は相等しいことを証明せよ。

問題２：ｎを自然数とする。1から２ｎまでの自然数の中からどのように（ｎ＋１）個の自然数を選んでも、その中に一方が他方を割り切るような２つの数の組が存在することを示せ。（1993　大阪教育大学入試問題）

NO1「uchinyan」 02/16 13時49分　受信 更新 3/13

問題１：

2n 個の整数を小さい順に a(1), a(2), ..., a(2n) とします。ただし等しいものがあってもいいとします。

これを，a(1), ..., a(n) と a(n+1), ..., a(2n) に分けて，前者の和を S1，後者の和を S2，とすれば，

S2 - S1 が 2n 個の整数を二つに分けたときのそれぞれの和の差の最大なので，条件は，

S2 - S1 = (a(n+1) - a(1)) + ... + (a(n+i) - a(i)) + ... + (a(2n) - a(n)) < n，

ここで，和の各項のいずれもが 0 でない場合は，それぞれが 1 以上なので，

S2 - S1 >= n となって条件を満たしません。そこで，少なくとも一つは 0 です。

そこで，a(n+i) - a(i) = 0，i は 1 〜 n のいずれか，とすると，a(i) の定義より，

a(i) = a(i+1) = ... = a(n) = a(n+1) = ... = a(n+i-1) = a(n+i)，

がいえ，少なくとも (n+i) - i + 1 = n+1 個が等しいことになります。

問題２：

1 〜 2n から n+1 個を選ぶときに，それぞれの a に対して，

2a, 4a, 8a, 16a, ... のうち，1 〜 2n に存在し一つでも選んだ n+1 個にあれば命題は成立し，

a/2, a/4, a/8, a/16, ... のうち，1 〜 2n に存在し一つでも選んだ n+1 個にあれば命題は成立します。

そこで，命題が成立しないような反例を作るためには，a を一つ選ぶごとにこれらをすべて除くことになります。

ところが，a は奇数か，偶数の場合には 2 で割っていくといつかは奇数になり，得られる奇数はすべて異なるので，

取り得る a の個数は 1 〜 2n の奇数の個数と同じで n 個までです。

そこで，n+1 個を選ぶには，少なくとも 1 個は既に選んだものを 2 で何回か掛けた又は割ったものになります。

つまり，一方が他方を割り切る二つの数が必ず存在します。

以上のことより，題意は証明されました。

(例)

ちょっと分かりづらいかも知れないので n = 8 の例を示します。

「：」の，左が選んだ数，右が残っている数，です。

例えば，

：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

---> 16：3 5 6 7 9 10 11 12 13 14 15

---> 15 16：3 5 6 7 9 10 11 12 13 14

---> 14 15 16：3 5 6 9 10 11 12 13

---> 13 14 15 16：3 5 6 9 10 11 12

---> 12 13 14 15 16：5 9 10 11

---> 11 12 13 14 15 16：5 9 10

---> 10 11 12 13 14 15 16：9

---> 9 10 11 12 13 14 15 16：

ここまでなので 8 個しか選べず，

8 + 1 = 9 個目を取るには倍数／約数の関係にある除いたものを取るしかありません。

他の例，

：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

---> 1：3 5 6 7 9 10 11 12 13 14 15

---> 1 3：5 7 9 10 11 13 14 15

---> 1 3 5：7 9 11 13 14 15

---> 1 3 5 7：9 11 13 15

---> 1 3 5 7 9：11 13 15

---> 1 3 5 7 9 11：13 15

---> 1 3 5 7 9 11 13：15

---> 1 3 5 7 9 11 13 15：

この場合も同様で，9 個目を取るには倍数／約数の関係にある除いたものを取るしかありません。

ただし，この例では選んだ 8 個の中で既に倍数／約数の関係にあるものがあります。

しかし，証明すべき命題は 9 個を選ぶことが前提なので，8 個の中のことはまた別の話です。

もう一つの例，

：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

---> 16：3 5 6 7 9 10 11 12 13 14 15

---> 15 16：3 5 6 7 9 10 11 12 13 14

---> 5 15 16：3 6 7 9 11 12 13 14

---> 5 12 15 16：7 9 11 13 14

---> 5 7 12 15 16：9 11 13

---> 5 7 11 12 15 16：9 13

---> 5 7 9 11 12 15 16：13

---> 5 7 9 11 12 13 15 16：

この取り方はかなりランダムですが，これも同様です。

なお，実は，数学的帰納法での考え方に沿ったものです。

15, 16 の両方が選ばれる以外は，n-1 = 8 - 1 = 7 の帰納法の仮定により明らかなので，

15, 16 の両方が選ばれる場合がポイントになります。

(感想)で述べたようにこれがうまくいきませんでした。

(感想)

うーむ，今回は参った，苦労しました，試験だったら完全にアウトですね。

問題１：は，しばし考えたものの，広義の単調増加列に思い至った後は比較的容易に解けました。

もっとも，最初の証明はもっとややこしかったのですが，見直して大分スッキリしました。

問題２：は，最初は数学的帰納法で比較的容易にできるだろう，と思ったのですが，

かなりいい線までいった，一時はできたと思った，ものの，すぐに論理的な抜けが見つかり，

どうしてもそれを詰め切れませんでした。ちょっとのことのように思うのですが，

今もこの方向ではうまくいっていません。仕方がないので視点を変えたらあっさり。

もっとも，最初は(例)の２番目で述べたことで混乱しましたが，別の話と気付いて何とか。

論理的に大丈夫だろうと思いますが，どうかな。

NO2「スモークマン」 02/16 22時20分　受信

「スモークマン」 02/18 22時21分　受信

「スモークマン」 02/24 20時10分　受信 更新 3/13

問題１：２ｎ個の整数がある。それらの数をｎ個ずつの２組に分けるとき、どう分けても、各組の数の和Ｓ_１、Ｓ_２の差はｎより小さいとする。このとき、これらの２ｎ個の数のうち、少なくともｎ＋１個は相等しいことを証明せよ。

回答

m(1)<=m(2)<=…<=m(2n)

{m(2n)-m(2n-1)}+{m(2n-2)-m(2n-3)}+…+{m(2)-m(1)}<n

左辺はnペアあり、各ペアは0以上…

so…少なくとも1ペアは0である…それをm(k+1)=m(k)とするとき、

別のペアにしたら…その他のペアはかわらないので…m(k+1) or m(k) と等しいペアが少なくとも一つあることになる。

この操作はどのペアと取り替えてもどちらかは少なくとも0になる…so…少なくとも最初の1ペア(２個)+n-1ペア(n-1個)が等しいということ=少なくとも(2+n-1=n+1)個は等しいことが言える。

回答

m(1)<=m(2)<=…<=m(2n)

{m(2n)-m(2n-1)}+{m(2n-2)-m(2n-3)}+…+{m(2)-m(1)}<n

左辺はnペアあり、各ペアは0以上…

so…少なくとも1ペアは0である…それをm(k+1)=m(k)とするとき、

別のペアにしたら…その他のペアはかわらないので…m(k+1) or m(k) と等しいペアが少なくとも一つあることになる。

＜水の流れ＞　２ｎ個の数のうち、少なくともｎ＋１個は相等しいとは言えないです。

　あくまでも等しいペアが1組で2個しかないのです。

回答

＊えっと...その等しい１ペアの数を他の(n-1)ペアのいずれかの数と入れ替えることを考えます。大小は決まります。

入れ替えてない部分は変わってないので、再び、最初と同じことが言え、

少なくとも、入れ替えた２個のペアのどちらかが0になります。

次はその等しい組を残りの(n-2)ペアのいずれかの数と入れ替えます。

入れ替えてない部分は変わらないので、やはり入れ替えた２ペアのいずれかが0になります。

これを繰り返すと...入れ替えられるペアの数は-1ずつ減って行き…差が0のペアは+1ずつ増えて行きます=等しい数が１個ずつ増えて行きます。最初から(n-1)ペア入れ替えたらお仕舞なので...等しい数は+(n-1)個、最初の等しい１ペアの数が2個あるので…

合計=2+(n-1)=n+1個の数は等しくなることが言えると思うのですが…^^;…?

「スモークマン」 02/26 23時45分　受信 更新 3/13

問題２：ｎを自然数とする。1から２ｎまでの自然数の中からどのように（ｎ＋１）個の自然数を選んでも、その中に一方が他方を割り切るような２つの数の組が存在することを示せ。

（1993　大阪教育大学入試問題）

回答

n+1〜2n のn個は…

明らかにn=1のときは、1,2 から2個取り出すと題意を満たしている。

n>=2 のときは…

1<2n/(n+1)=m<2, 0<(n+k)/(n+k+1)<1

なので…

これらのn個同士は互いに割り切れない…

残りのm=2〜n から任意の1個mを選ぶとき、2m>=n+1なら題意を満たしており、

n/2^2<=m<=n/2 なら…n+1<=2^2*m<=2n

n/2^3<=m<=n/2^2 なら…n+1<=2^3*m<=2n

以下その繰り返しで…m=2〜nは...

n/2^k<=m<=n/2^(k-1) に含まれるので…n+1<=2^k*m<=2n

という、n+1<=2^k*m<=2n が存在するから、題意は満たされる。

NO3「早起きのおじさん」 02/21 16時43分　受信 更新 3/13

問題1

2n個の数を｛ｋ₁,ｋ₂,･･･,ｋ_n,ｋ_n+1,･･･,ｋ_2n｝とします。

また、ｋ₁≧ｋ₂≧･･･≧ｋ_n≧･･･≧ｋ_n+1≧･･･≧ｋ_2nの大小とします。

●その1の考え

和S₁とS₂の差が最も大きいのは、

S₁＝ｋ₁+ｋ₂+･･･+ｋ_n、S₂＝ｋ_n+1+･･･+ｋ_2n

のときです。

S₁−S₂＝(ｋ₁+ｋ₂+･･･+ｋ_n)−(ｋ_n+1+･･･+ｋ_2n)

＝(ｋ₁−ｋ_n+1)+( ｋ₂−ｋ_n+2)+･･･+(ｋ_n−ｋ_2n)≦n−1

ここで、(　)はn個あります。

どの(　)も差が正とすると、差がn以上になってしまいます。

つまり、aをある整数として、ｋ₁＝･･･＝ｋ_n＝a+1で、ｋ_n+1＝･･･＝ｋ_2n＝aのような場合です。

少なくてもどこかの(　)は0でないと、不等式は成立しません。

i番目の(　)が0とすると(つまりk_i＝k_n+i)、i番目からn+i番目のn+1個の数が等しくなります。

ｋ₁≧･･･≧k_i＝･･･＝ｋ_n＝ｋ_n+1＝･･･＝k_n+i≧･･･≧ｋ_2n

j番目の（　）も0とすると（i<jとします）、j番目からn+j番目のn+1個の数が等しくなります。

すると、j番目からn+i番目が重なるので、(n+j)−i+1＝n+(j−i)+1個の数が等しくなります。

このときは結局、i番目からj番目の（　）は0です。

●その2の考え

和Sをk₁を含み、残りの2n−1個の中からn−1個を選んで合計したもの、ｓを残りの和とします。

少し分かりにくいので、n＝3として、具体的にみてみます。

　Sとする場合の表

S−ｓの₅C₂個の場合を並べます。

　(k₁+k₂+k₃)−(k₄+k₅+k₆)≦2

　･･･

　(k₁+k₃+k₄)−(k₂+k₅+k₆)≦2

　･･･

　(k₁+k₄+k₅)−(k₂+k₃+k₆)≦2

　･･･

　(k₁+k₅+k₆)−(k₂+k₃+k₄)≦2

これらを辺々合計しますが、₅C₂＝₄C₁+₄C₂に注意します。

つまり、₄C₂＝₃C₁+₂C₁+₁C₁です。

　₅C₂ k₁−(₄C₂−₄C₁)(k₂+k₃+k₄+k₅+k₆)≦₅C₂×2

つまり、

最大の数は、残りの数の平均からプラス2までの範囲にあります。

　2n個の数の例

以上を踏まえて、nのときを調べます。

和Sをk₁を含み、残りの2n−1個の中からn−1個を選んで合計したもの、ｓを残りの和とします。

S−ｓの_2n−1C_n−1個の場合を並べます。

　(k₁+k₂+･･･+k_n)−(k_ｎ+1+･･･+k_2n)≦(n−1)

　･･･

(k₁+k₃+･･･+k_n+1)−(k₂+･･･+k_2n)≦(n−1)

　･･･

(k₁+k₄+･･･+k_n+2)−(k₂+･･･+k_2n)≦(n−1)

　　･･･

(k₁+k_n+2+･･･+k_2n)−(k₂+･･･+k_n+1)≦(n−1)

これらを辺々合計しますが、_2n―1C_n−1＝_2n−2C_n−2+_2n−2C_n−1に注意します。

つまり、_2n―1C_n−1＝_2n−2C_n−2+_2n−3C_n−2+･･･+_n−2C_n−2です。

　_2n−1C_n−1 k₁−(_2n−2C_n−1−_2n−2C_n−2)(k₂+･･･+k_2n)≦_2n−1C_n−1×(n−1)

ここで、

なので

最大の数は、残りの数の平均からプラス(n−1)までの範囲にあります。

このことを考えます。

イ）まず、すべての数が等しい場合、条件を満たします。（元の状態）

ロ）元の状態において、最大の数k₁に1から(n−1)まで加えても条件を満たします。

このとき、2n−1個の数は相等しいです。

ハ）Sにはn個の数があります。

元の状態において、k₁からk_n−1個の数に1ずつ加えても条件を満たします。

このとき、n+1個の数は相等しいです。

ニ）ロとハを合わせて、k_iの大小関係を損なわないようにSの数を計n−1まで増やしていきます。

このときn+1より多い数が相等しくなります。

ホ）元の状態において、最小の数k_2nから1から(n−1)まで引いても条件を満たします。

このとき、2n−1個の数は相等しいです。

ヘ）ｓにはn個の数があります。

元の状態で、k_n+2からk_2n個の数から1ずつ引いても条件を満たします。

このとき、n+1個の数は相等しいです。

ト）ホとヘを合わせて、k_iの大小関係を損なわないようにｓの数を計n−1まで減らしていきます。

このときn+1より多い数が相等しくなります。

チ）元の状態で、ｓからSの方に1ずつ条件を満たす範囲で数を移していきます。

この場合は、相等しい数は、n+1より多くなります。

リ）ニとトとチを合わせてｓからSの方に1ずつ移し、Sは1ずつ加え、ｓは1ずつ減らすこともできます。

この場合、ｓからSに1移すと、Sに加えることのできる数（ｓから減らすこののできる数）は、2減ります。

この場合にもn+1より多い数が相等しくなります。

問題2

感じをつかむため、nをいくつか変えて、一方が他方を割り切らないように数を選んでみます。

そのとき素数を重視してみます。

・n＝2のとき、｛2,3｝

・n＝3のとき、｛2,3,5｝

・n＝4のとき、｛2,3,5,7｝

ここまでは、n個の数を選ぶことができます。

しかし、

・n＝5のとき、｛2,3,5,7｝

のように、n個選ぶことができません。

そこで、次の表を参考に選ぶ方法を変えます。

倍数の表（縦の数の倍数であるときに＊をつけてある）

数をn+1から2nまでのn個にしてみます。

すると、

・n＝2のとき、｛3,4｝

・n＝3のとき、｛4,5,6｝

・n＝4のとき、｛5,6,7,8｝

・n＝5のとき、｛6,7,8,9,10｝

のようにnの値によらず、うまくいきます。

しかし、n+1個目の数は1からnの中から選ぶことになります。

すると、どう選んでもその数の倍数がn+1から2nまでの中に存在します。

NO4「浜田明巳」 02/23 13時29分　受信

「浜田明巳」 02/26 08時24分　受信 更新 3/13

問題１
　条件を満たす２ｎ個の整数を
　　ａ_１，ａ_２，ａ_３，………，ａ_２ｎ　とする．
　このとき，
　　Ｓ_１＝Σ_{１≦ｋ≦ｎ}ａ_ｋ，Ｓ_２＝Σ_{ｎ＋１≦ｋ≦２ｎ}ａ_ｋ　とすると，
　　｜Ｓ_１−Ｓ_２｜＜ｎ　である．
　２ｎ個の数
　　ａ_１−ｍ，ａ_２−ｍ，ａ_３−ｍ，………，ａ_２ｎ−ｍ
も条件を満たすことを示す．・・・（＊）
　　Σ_{１≦ｋ≦ｎ}(ａ_ｋ−ｍ)＝Ｓ_１−ｍｎ
　　Σ_{ｎ＋１≦ｋ≦２ｎ}(ａ_ｋ−ｍ)＝Ｓ_２−ｍｎ
　　∴｜(Ｓ_１−ｍｎ)−(Ｓ_２−ｍｎ)｜＝｜Ｓ_１−Ｓ_２｜＜ｎ
　故に（＊）が成り立つ．

　ｍを適当に決めて，
　　ａ_１−ｍ，ａ_２−ｍ，ａ_３−ｍ，………，ａ_２ｎ−ｍ　の値で０の個数が一番多くなるようにする．
　そして，それらの値を改めて，
　　ａ_１，ａ_２，ａ_３，………，ａ_２ｎ　とする．
　ａ_ｋのうち，正のものをｘ個，
　　　　　　　０のものをｙ個，
　　　　　　　負のものをｚ個（ｙ≧ｘ≧０，ｙ≧ｚ≧０，ｘ＋ｙ＋ｚ＝２ｎ）　とし，
　　ａ_ｋ≧ａ_ｎ＋ｋ（１≦ｋ≦ｎ）　とする．
　ｘ≧ｚとしても，一般性を失わない．
　ｙ≦ｎと仮定し，矛盾を導き出す．
　ここで，ｙ≦ｎ≦ｘ＋ｚである．
　ａ_ｋ＞０，ａ_ｎ＋ｋ＜０（１≦ｋ≦ｚ）とすると，
　　ａ_ｋ−ａ_ｎ＋ｋ≧２
　ａ_ｋ＞０，ａ_ｎ＋ｋ＝０（ｚ＋１≦ｋ≦ｘ）とすると，
　　ａ_ｋ−ａ_ｎ＋ｋ≧１
　また，
　　ａ_ｋ−ａ_ｎ＋ｋ≧０（ｘ＋１≦ｋ≦ｎ）であるから，
　　Ｓ_１−Ｓ_２＝(ａ_１−ａ_ｎ＋１)＋(ａ_２−ａ_ｎ＋２)＋(ａ_３−ａ_ｎ＋３)＋………＋(ａ_ｎ−ａ_２ｎ)
　　　　　　　≧２ｚ＋(ｘ−ｚ)＝ｘ＋ｚ≧ｎ
　これは｜Ｓ_１−Ｓ_２｜＜ｎに反する．
　　∴ｙ≧ｎ＋１
　故に題意は成立する．

問題２
　１から２ｎまでの整数から，ｎ＋１個の相異なる数ａ_１，ａ_２，ａ_３，………，ａ_ｎ＋１を選ぶ．
　　ａ_ｋ＝２^ｐ(ｋ)(２ｑ_ｋ−１)（ｋ＝１，２，３，………，ｎ＋１）
　　ｐ(ｋ)は非負整数，ｑ_ｋは正整数，１≦ｑ_ｋ≦ｎ　とすることができる．
　　２ｑ_１−１，２ｑ_２−１，２ｑ_３−１，………，２ｑ_ｎ＋１−１・・・（☆）はｎ＋１個の奇数である．
　ところが，１から２ｎまでの整数の中で，奇数はｎ個しかない．
　故に（☆）内には，重複する奇数が少なくとも１組存在する．
　それらを
　　２ｑ_ｘ−１，２ｑ_ｙ−１（１≦ｘ＜ｙ≦ｎ，２ｑ_ｘ−１＝２ｑ_ｙ−１）とする．
　ａ_ｘ＝２^ｐ(ｘ)(２ｑ_ｘ−１)≠ａ_ｙ＝２^ｐ(ｙ)(２ｑ_ｙ−１)であるから，ａ_ｘ，ａ_ｙは約数，被約数の関係にある．
　故に題意は成立する．

NO5「にいばりZ12」 02/23 23時50分　受信 更新 3/13

問題１：２ｎ個の整数がある。それらの数をｎ個ずつの２組に分けるとき、どう分けても、各組の数の和Ｓ１、Ｓ２の差はｎより小さいとする。

このとき、これらの２ｎ個の数のうち、少なくともｎ＋１個は相等しいことを証明せよ。

条件を整理します

2n個の整数の集合をHとしをの要素をa _i(_i=1→2ｎ)、a _i≦a _i+1とします

Hをn個づつ2組に分けた集合H1、H2の和の小さい方をS1大きい方をS2とします

S1を構成するの集合をH1でその要素をa _i(_i=1→ｎ) 、S2を構成するの集合をH2でその要素をa _i(_i=n+1→2n)　

このように並べ替えると分割されるS1とS2の差は最大となり「どう分けても」の条件の最も厳しい状態となります。

S1=Σ_i=1→na_i

S2=Σ_i=n+1→2na_i

S1-S2≦0<nなので

S2- S1を考えます　　　

S2- S1=(Σ_i=1→na_i -Σ_i=n+1→2na_i)<n

H1とH2の要素のうち、相等しい要素がｎ+1個より小さい(n個以下)と仮定すると

相等しくない要素はn-1個より大きく(n個以上)なります

相等しくない要素をH2から1個H1から1個取り出すとその差は

H2の要素はH1の要素より大きいので

a_n+j- a_n-k≧1（n≧j≧1、n-1≧k≧0）

S2- S1≧1×n=n＞n-1

「S2と S1の差はn-1より大きい」

２ｎ個の整数がある。それらの数をｎ個ずつの２組に分けるとき

「相等しい要素がｎ+1個より小さい」ならば「S2と S1の差はn-1より大きい」

この対偶命題は

「S2と S1の差はnより小さい」ならば「相等しい要素がｎ+1個以上」

上記後段「相等しい要素がｎ+1個以上」は、「少なくともｎ＋１個は相等しい」と同値

よって

２ｎ個の整数がある。それらの数をｎ個ずつのS2と S1の２組に分けるとき、どう分けても

「S2と S1の差はnより小さい」ならば「少なくともｎ＋１個は相等しい」が言えます

・・・・・・・・回答

「にいばりZ12」 03/01 01時13分　受信 更新 3/13

問題２：ｎを自然数とする。1から２ｎまでの自然数の中からどのように（ｎ＋１）個の自然数を選んでも、その中に一方が他方を割り切るような２つの数の組が存在することを示せ。（1993　大阪教育大学入試問題）

・1から2nまでの数には奇数と偶数が同数(n個)含まれ、2nは偶数・・・・�@

・1から2nの自然数の集合をHとします

・Hからn+1個の要素を取り出した集合をAとします。

・Aの中のに一方が他方を割り切るような二組の数が無いようなAを探しこのような集合をBとします。

・Aに1を含む場合、1はすべての自然数を割り切ります（なので、Bはその要素に1を含むことはできません）。・・・�A

・Aに2を含む場合すべての偶数を割り切ります。

集合Hは偶奇同数で各々n個存在します

　したがって2をその要素に含むBは2以外の偶数はその要素に含まずまた、上記より1を含みません。

　Hの要素の総数2nから2以外の偶数の数（ｎ-1）を引き要素1の1個を引くと

　2n-(n-1)-1=nとなりAがn+1個と言う条件を満たしません（なので、Bはその要素に2を含むことはできません）。・・・�B

即ち、Bは3から2nまでの数(2n-2)個の内から互いに割り切れないn+1個の数の組み合わせとなります。

　

3≦nを考えます

Hを3からn、n+1から2n個の2組に分けた集合H1、H2とします

H1の要素は3からnの自然数、H2の要素はn+1から2nの自然数（H1の個数はn-2・H2の個数はn)

H2には一方が他方を割り切るような二つの数の組は存在しません。

∵2n/( n+1)<2　(n>2)・・�C　　　　　　　　　　　　　　　　　　　　　　　　　

Aの中のに一方が他方を割り切るような二組の数が無いようなAを探しこのような集合をBとします。

今Aの要素が1個のみH1に属し残りの要素はすべてH2に属するようなAを考えます。

この1個のみH1に属する要素をa1としこの要素がH2の要素の約数でなければ�AよりBが空集合でなくなります。

a1を場合分けします

(n+1)/2≦ a1≦n・・・・・・・・・・n+1≦2a1≦2n→a1がH2に2倍数を持つ領域

(n+1)/3≦ a1< (n+1)/2・・・・・・・n+1≦3a1< 3(n+1)/2≦2n→a1がH2に3倍数を持つ領域

(n+1)/4≦a1< (n+1)/3・・・・・・・n+1≦4a1< 4(n+1)/3≦2n→ a1がH2に4倍数を持つ領域

・

・

・

(n+1)/n≦ a1< (n+1)/(n-1)・・・・・・・n+1≦na1< n(n+1)/(n-1)≦2n →a1がH2にn倍数を持つ領域

一方H2に属する要素は、素数か合成数のいずれかです。

�A�Bより3≦ a1≦nなのでH2に属する合成数の要素はその約数にH1に2つ以上の素因数を持ちます。

即ち、H1の要素はすべてH2の要素の約数でありよってa1をどのように選んでもBは空集合となります。

そこで、a1の倍数でH2に属する要素の代わりにH1からAの要素を選ぶと、その倍数がやはり2つ以上H2に属し且つ素因数分解の一意性からa1の倍数と異なる倍数がH2に存在することになります。

よってこの操作を繰り返してもBの空集合は変わりません。

従ってBは常に空集合であり、1から２ｎまでの自然数の中からどのように（ｎ＋１）個の自然数を選んでも、その中に一方が他方を割り切るような２つの数の組が存在する・・・・回答

「部屋割り論法」と言う言い回しも記憶にありますが、「鳩ノ巣原理」で覚えていました。

　今回の問題の本解は、もっとずっとシンプルでエレガントだと思います。

NO6「アーベル」　　　　 02/28 19時33分　受信 更新 3/13

問題１：２ｎ個の整数がある。それらの数をｎ個ずつの２組に分けるとき、どう分けても、各組の数の和Ｓ_１、Ｓ_２の差はｎより小さいとする。

このとき、これらの２ｎ個の数のうち、少なくともｎ＋１個は相等しいことを証明せよ。

背理法で証明する。

相等しいものはn個以下であると仮定する

2n個を小さい順に並べて、最初のn個をa(i)　後半のn個をb(i)とする

a(i)よりb(i)までの個数はn+1だから仮定より任意のiでb(i)-a(i)>=1

よってΣb(i)-Σa(i)>=nとなり矛盾

問題２：ｎを自然数とする。1から２ｎまでの自然数の中からどのように（ｎ＋１）個の自然数を選んでも、その中に一方が他方を割り切るような２つの数の組が存在することを示せ。（1993　大阪教育大学入試問題）

問題１に結び付けられず、本質から外れる気がするけれど

強引に帰納法で証明しました

n=1のときは明らか

簡単のためn=9　のときを仮定して10のときに成立することを示す

仮定　1〜18から10個の数を選べば　割り切る2数がある

これに19、20を付け加え、11個を選ぶ。

選ぶ11個が1〜18にあれば仮定からOK

19、20のどちらか一方のみを含まれる場合

1〜18から10個選ぶので、この場合も仮定からOKだから

19、20の両方が選ばれた場合のみ考えればよい

このとき1〜18から9個選ぶけれど、20/2=10が含まれていれば問題ないので

10が含まれない場合のみ考えればよい。

もし18までに選ぶ9個の中に割り切る2数があれば問題ないから

このような2数が全く無いと仮定する。このとき10を加えてみると

帰納法の仮定より、10個の中には割り切る2数が存在する。

10を加えて、“はじめて”存在するのだから、1〜18に10の倍数か

10の約数があることになる。10*2>18　だから倍数はなく、

10の約数があることになる。この約数は当然20の約数になっている。

一般のn=k　でも同じだから帰納法は成立する。

「アーベル」　　　　 02/29 22時23分　受信 更新 3/13

問題２：ｎを自然数とする。1から２ｎまでの自然数の中からどのように（ｎ＋１）個の自然数を選んでも、その中に一方が他方を割り切るような２つの数の組が存在することを示せ。（1993　大阪教育大学入試問題）

問題１には結び付けられなかったけれど、再考しました

1〜2nを偶数奇数に分ける

1,3,5,……,2n-1　Aとする。

2,4,……,2n　Bとする

Bは2でくくれるものはくくりだし2^a*k　kは奇数とする

このときkは明らかにAの中に存在する。

n+1個選ぶから、A、B両方から1個以上選ばれている。

このBから選ばれたものの奇数部分kがAから選ばれた中にあれば

割り切れるからOK。

でなければ、例えばAから5個選ばれていたら、Bからn-4個

Aで選ばれなかった奇数はn-5個で、Bから選んだn-4個

の奇数部分kはn-5種類しかない

よって鳩ノ巣より同じkの2つがあり2^aのaが小さいか同じものが

割り切ることになる。

NO7「二度漬け白菜」 03/08 22時10分　受信 更新 3/13

[問題1]
背理法で証明する．
2n個の整数のうち，相等しいものは高々 n 個しかないと仮定する．
これら2n個の整数を小さい順に並べて，
a[1]，a[2]，a[3]，… ，a[2n] とする．
a[1]≦a[2]≦a[3]≦…≦a[2n]であり，相等しいものは高々 n 個なのであるから，
1≦k≦n なるすべて整数 k に対して，a[n+k]-a[k]≧1  --- (★)
が成り立つはずである．

S=a[1]+a[2]+…+a[n]，
T=a[n+1]+a[n+2]+…+a[2n]
とする．
与えられた条件より，T-S＜n が成り立っている．

一方，
T-S
=Σ[k=1..n](a[n+k]-a[k])
≧Σ[k=1..n](1)　(∵★)
=n

これは矛盾．
よって，2n個の整数のうち，少なくとも n+1 個は相等しい．

[問題2]
(証明)
任意の正の奇数 k に対して，無限集合 S[k] を次で定める．

S[k]={k*2^p | p = 0，1，2,… }．

2*n 以下の任意の正整数は M*2^r (rは0以上の整数．Mは奇数であって，1≦M≦2*n-1)
という形にかける．
つまり，2*n 以下の任意の正整数は，n個の集合 S[1]，S[3]，S[5]，… ，S[2*n-1]
のいずれかに属する．

いま，1 から 2*n までの自然数の中から勝手に（n+1）個の自然数を選ぶとする．
部屋割り論法により，ある奇数 m (1≦m≦2*n-1)が存在して，
勝手に選んだ(n+1)個のうちの少なくとも2つの数 a, b (a＜b) が S[m] に属する．
このとき，a=m*2^r，b=m*2^t (r，tは0以上の整数で，r＜t)
とかけるので，a が b を割り切る．
よって，1 から 2*n までの自然数の中からどのように(n+1)個の自然数を選んでも，
その中に一方が他方を割り切るような2つの数の組が存在する。(証明終)

---------------------------------------------------------------------

[問題2]に関して：
以下のサイトに同じ趣旨の問題がありました．

Mathematical Excalibur
https://www.math.ust.hk/excalibur/

Vol.1 No.1 というファイルの最初の頁の，Example 2. がまさにそれです．
https://www.math.ust.hk/excalibur/v1_n1.pdf

＜水の流れ：　このサイトの発見には驚きと感謝の念で一杯です。ありがとうございます。大学入試問題作成者はこのサイトを参考にしたのでしょうか。＞