部屋割論法の理解・整数集合の性質(2)を紹介します。
性質(2)
部屋割論法の理解・整数集合の性質(2)を紹介します。
性質(2)
部屋割論法の理解・整数集合の性質(1)・考察を示します。
考察
部屋割論法の理解・整数集合の性質(1)の解答例を示します。
性質(1)の解
選んだn+1個の数をx(1)<x(2)<・・・<x(n+1)とする。
各x(i)について、nで割って得られる余りをr(i)とすると、
x(i) = nq(i) + r(i) (q(i)=0または1または2 , 0≦r(i)≦n-1 )
が成り立つ。
そこで、部屋割論法(n個の余り0,1,2,・・・,n-1がn個の部屋に対応し、
n+1個の余りr(1),r(2),・・・,r(n+1)がn+1人の客に対応する)により、
r(i) = r(j)(i<j)
となるものがあることがわかる。すなわち、
x(i) = nq(i) + r(i),
x(j) = nq(j) + r(j)
x(i) - x(j) に着目する。
x(j) - x(i) = n(q(j) - q(i)) + (r(j) - r(i))
= n(q(j) - q(i))
1 ≦ x(j) - x(i) ≦2n-1 より、q(j) - q(i)は、0、1のいずれかになる。
q(j) - q(i) = 0 とすると、 x(j) = x(i) となり矛盾。
したがって、q(j) - q(i) = 1 を得る。
すなわち、x(j) - x(i) = n が成り立つ。以上より、命題が証明された。
部屋割論法の理解・整数集合の性質(1)を紹介します。
性質(1)
部屋割論法の理解・四隅同色問題(2)の解答例を示します。
問題(2)の解
部屋割論法の理解・四隅同色問題(2)を紹介します。
問題(2)
部屋割論法の理解・四隅同色問題(1)の解答例を示します。
問題(1)の解