NẾU D LẺ, 2D + 1 > N THÌ D + 1M ≤ 2D + 1 − NĐỂ CHỨNG MINH ĐỊNH...

2. Nếu d lẻ, 2d + 1 > n thì

d + 1

M ≤ 2

.

2d + 1 − n

Để chứng minh định lý, ta sử dụng một số nhận xét sau:

Bổ đề 2.4. Giả sử N, M là các số nguyên dương và 0 ≤ N ≤ M thì

(

²

nếu M chẵn

N(M − N) ≤

²

nếu M lẻ.

Bổ đề 2.5. Nếu x ∈ R thì [2x] ≤ 2[x] + 1.

Bổ đề 2.6. Cho v là xâu nhị phân ∈ [0, 1]

. Khi đó d(v + w) bằng với số số 1 xuất hiện trong v + w.

Chứng minh. Bằng việc kiểm tra tất cả các khả năng của v

và w

, ta thấy

( 0 nếu v

= w

(v + w)

=

1 nếu v

6 = w

.

Do đó

d(v , w) = |{ i | v

6 = w

}|

= |{ i | (v + w)

= 1 }| .

Chứng minh định lý với d chẵn. Ta viết ma trận A =

× n, với mỗi dòng là một phần tử u + v, với

u, v ∈ C. Ta đếm số lần xuất hiện số 1 trong ma trận trên.