zi=z1+‥+zi、wj=y1+‥+yj とする。
zn≦wmとしてよい。
各1≦i≦nに対して
y j(i-1)＜xi≦yj(i)
をみたすj(i)がとれる。
この時各iに対し0≦y(j(i))-xi≦n-1である。
=0が成立するiがあるときには、主張は正しいから≠0とする。
このときyj(1)〜yj(n)は全て1〜n-1であるから相異なるi1、i2でyj(i1)=yj(i2)となるものがとれる。以下ry