部屋割論法の理解・整数集合の性質（２）

　部屋割論法の理解・整数集合の性質（２）を紹介します。

性質（２）

部屋割論法の理解・整数集合の性質（１）・考察

　部屋割論法の理解・整数集合の性質（１）・考察を示します。

考察

部屋割論法の理解・整数集合の性質（１）の解

　部屋割論法の理解・整数集合の性質（１）の解答例を示します。

性質（１）の解

　選んだ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、１のいずれかになる。

q(j) - q(i) = 0 とすると、 x(j) = x(i) となり矛盾。

したがって、q(j) - q(i) = 1　を得る。

すなわち、x(j) - x(i) = n　が成り立つ。以上より、命題が証明された。

部屋割論法の理解・整数集合の性質（１）

　部屋割論法の理解・整数集合の性質（１）を紹介します。

性質（１）

部屋割論法の理解・四隅同色問題（２）の解

　部屋割論法の理解・四隅同色問題（２）の解答例を示します。

問題（２）の解

部屋割論法の理解・四隅同色問題（２）

　部屋割論法の理解・四隅同色問題（２）を紹介します。

問題（２）

部屋割論法の理解・四隅同色問題（１）の解

　部屋割論法の理解・四隅同色問題（１）の解答例を示します。

問題（１）の解