Thư viện bài, chủ đề ‘Combinatorics’

Đề thi toán quốc tế 2008

Ngô Quang Hưng | 01 tháng 08, 2008 | Bản để in Bản để in

Như mọi khi, tôi quan tâm đến bài tổ hợp trong đề năm nay:

Let n and k be positive integers with k ≥ n and k−n an even number. Let 2n lamps labelled 1, 2, . . . , 2n be given, each of which can be either on or off. Initially all the lamps are off. We consider sequences of steps: at each step one of the lamps is switched (from on to off or from off to on).

Let N be the number of such sequences consisting of k steps and resulting in the state where lamps 1 through n are all on, and lamps n + 1 through 2n are all off.

Let M be the number of such sequences consisting of k steps, resulting in the state where lamps 1 through n are all on, and lamps n + 1 through 2n are all off, but where none of the lamps n + 1 through 2n is ever switched on.

Determine the ratio N/M.

Bài này dễ một cách đáng ngạc nhiên so với bài tổ hợp năm ngoái. Bản thân câu hỏi đã gợi ý hướng suy nghĩ: tính N/M có nghĩa là ta nên xét tương quan giữa các chuỗi on/off loại 1 và các chuỗi on/off loại 2. Nôm na, N - tổng số các chuỗi loại 1 - là tổng số các chuỗi có k phần tử thuộc tập {1, 2, …, 2n} sao cho mỗi phần tử trong {1, …, n} xuất hiện một số lẻ lần, và mỗi phần tử trong {n+1, …, 2n} xuất hiện một số chẵn lần. Còn M - tổng số chuỗi loại 2 - là tổng số các chuỗi giống như loại 1 nhưng các phần tử trong {n+1, …, 2n} không xuất hiện lần nào.

Phản ứng đầu tiên của tôi là: lấy một chuỗi loại 2 và xây dựng từ đó một số X chuỗi loại 1. Nếu mỗi chuỗi loại 2 tương ứng với chính xác X chuỗi loại 1 (one-to-many mapping), và các bộ X phần tử này không giao nhau, và mỗi phần tử loại 1 đều nằm trong một bộ X chuỗi nào đó, thì ta kết luận N/M = X. Phần còn lại để cho các bạn đọc. [Cần một fact đơn giản sau: cho một tập S kích thước y, tổng số tập con của S với lực lượng chẵn là 2 lũy thừa (y-1).]

Bài này rất có tinh thần “định trị một đại lượng bằng hai cách“. Do tập các chuỗi loại 2 là tập con của tập các chuỗi loại 1, cũng có thể hiểu rằng ta phân hoạch tập các chuỗi loại 1 ra làm các tập con có kích thước X, sao cho mỗi tập có chính xác một chuỗi loại 2. Cách hiểu thứ hai này tuy có vẻ dễ dàng hơn trong ngữ cảnh của bài toán này, nhưng tôi không thích nó vì nó không “tổng quát” bằng. Nếu cách xây dựng như trên không thỏa mãn điều kiện “không giao nhau” (disjointness) thì ta phải xây dựng một “many-to-one map” ngược lại từ loại 1 vào loại 2 rồi tính tỉ lệ.

Chủ đề: Combinatorics | Bình luận (1) »

Một bài toán đồ thị

Ngô Quang Hưng | 09 tháng 01, 2008 | Bản để in Bản để in

Một người bạn gửi cho bài toán sau đây. Tôi vừa tìm được lời giải rất gọn.

Cho n là một số nguyên lẻ lớn hơn 2. Mỗi cạnh của complete graph K_n được gán một cân nặng khác nhau. Chứng minh rằng có một walk chiều dài n trên graph K_n này với các cạnh có chiều dài tăng dần (strictly increasing!).

Chủ đề: Combinatorics | Bình luận (4) »

Định trị một đại lượng bằng hai cách [5]

Ngô Quang Hưng | 22 tháng 12, 2007 | Bản để in Bản để in

Lần này ta chứng minh một định lý kinh điển của đại số: định lý Cayley-Hamilton. Mặc dù có thể phát biểu tổng quát hơn, ta chỉ phát biểu nó cho các trường số thực và phức.

Định lý Cayley-Hamilton: Gọi A là một ma trận vuông thực hoặc phức. Gọi p(x) = \det(xI-A) là đa thức đặc trưng của A. Ta có p(A) = 0.

Ví dụ:

A = \begin{bmatrix} 2 & 3\\ 1 & 4\end{bmatrix}

Thì đa thức p(x), tức là định thức của ma trận (xI-A) là
p(x) = \det \begin{bmatrix} x-2 & -3\\ -1 & x-4\end{bmatrix} = (x-2)(x-4)-3 = x^2-6x+5

Thay x bằng ma trận A trong p(x), dễ dàng xác minh được rằng
p(A) = A^2 - 6A + 5 = \begin{bmatrix} 2 & 3\\ 1 & 4\end{bmatrix}^2 - 6\begin{bmatrix} 2 & 3\\ 1 & 4\end{bmatrix} + 5\begin{bmatrix} 1 & 0\\ 0 & 1\end{bmatrix} = \begin{bmatrix} 0 & 0\\ 0 & 0\end{bmatrix}

Tuyệt nhỉ! Chứng minh kiểu đại số hoặc kiểu hình topo của định lý này có thể tìm ở nhiều nơi, bao gồm cái Wikipedia entry tôi liên kết ở trên, hoặc là tìm bên Planet Math, hoặc google ra cả đống. Còn chứng minh bằng định trị hai cách tôi sẽ trình bày dưới đây thì khó tìm hơn. Đây là chứng minh của Straubing hồi 1983.
Đọc tiếp toàn bài »

Chủ đề: Combinatorics | Bình luận (4) »

Đề thi toán quốc tế 2007

Ngô Quang Hưng | 27 tháng 07, 2007 | Bản để in Bản để in

Anh Nghị mới gửi cho tôi đề thi toán quốc tế 2007 ở Hà Nội dạng pdf. Chưa biết kết quả thế nào. Theo thông lệ, mỗi năm tôi cũng xem đề và giải các bài mình thích. Tôi rất ngại hình học, còn phương trình hàm thì nhàm, cho nên đa số chỉ giải bất đẳng thức và toán tổ hợp. Đề năm nay có bài số 1 và số 3 nhìn hấp dẫn, đặc biệt là bài số 3:

In a mathematical competition some competitors are friends. Friendship is always mutual. Call a group of competitors a clique if each two of them are friends. (In particular, any group of fewer than two competitiors is a clique.) The number of members of a clique is called its size.

Given that, in this competition, the largest size of a clique is even, prove that the competitors can be arranged into two rooms such that the largest size of a clique contained in one room is the same as the largest size of a clique contained in the other room.

Bài này rất Khoa Học Máy Tính, lời giải khá đơn giản, mang tính thuật toán. Gợi ý: bỏ hết competitors vào một buồng, gọi là buồng bên trái. Sau đó chọn theo một tiêu chuẩn nhất định một competitor và chuyển sang buồng bên phải. Quá trình này sẽ từ từ làm max-clique của buồng trái giảm dần và của buồng phải tăng dần. Đến lúc gần xong thì có thể phải chuyển ngược lại một chút!

Chủ đề: Combinatorics | Bình luận (7) »

Định trị một đại lượng bằng hai cách [4]

Ngô Quang Hưng | 27 tháng 06, 2007 | Bản để in Bản để in

Lần này ta xét một số chứng minh kinh điển về các số vô tỉ và các số siêu việt (transcendental numbers).

Ví dụ 7: khoảng 500 năm trước công nguyên, Hippasus khám phá ra số vô tỉ đầu tiên, \sqrt{2}, với chứng minh chặt chẽ. (Theo truyền thuyết thì chứng minh này đem lại cho ông những điều không hay ho gì.) Chứng minh của Hippasus trình bày trong các sách giáo khoa cấp 2 thường dùng phương pháp infinite descent kiểu Fermat. Ta trình bay một chứng minh khác dùng phương pháp định trị một đại lượng bằng 2 cách.

Giả sử \sqrt{2} = a/b là một số hữu tỉ, nghĩa là a^2 = 2b^2 = c là một số nguyên dương nào đó. Khi phân tích c ra thừa số nguyên tố, vì c = a^2 các thừa số nguyên tố của c đều có số mũ chẵn, trong khi đó vì c = 2b^2 thừa số 2 sẽ có số mũ lẻ. Vô lý!

(Đại lượng ta định trị là số mũ của 2 trong phân tích thừa số của c.)

Ví dụ 8: Euler chứng minh rằng e là số vô tỉ dùng phương pháp định trị 2 cách như sau. Giả sử e=a/b là hữu tỉ. Theo khai triển Taylor ta có:

\frac{a}{b} = \sum_{k=0}^\infty \frac{1}{k!}

Nhân hai vế với (b+1)! thì vế trái là một số nguyên, trong khi đó vế phải bằng
(b+1)!\left(\sum_{k=0}^{b+1} \frac{1}{k!}\right) + (b+1)!\left(\sum_{k=b+2}^\infty \frac{1}{k!}\right)

Dễ thấy rằng (b+1)!\left(\sum_{k=0}^{b+1} \frac{1}{k!}\right) là một số nguyên, trong khi đó (b+1)!\left(\sum_{k=b+2}^\infty \frac{1}{k!}\right) là một số thực trong khoảng (0,1). Vô lý!

Ý tưởng chính: Một cách trực quan hơn, ta có thể hiểu chứng minh này như sau. Nếu a/b là một số hữu tỉ, và m là một số nguyên bất kỳ, thì giá trị m(a/b) hoặc là bằng với một số nguyên hoặc là cách số nguyên gần nhất ít nhất 1/b. Trong khi đó, khi nhân e=a/b với m=n! với n càng lớn thì m(a/b) càng tiến đến gần một số nguyên với khoảng cách nhỏ tùy ý. Ý tưởng tương tự ý này sẽ được dùng để chứng minh một số là số siêu việt như trong ví dụ sau đây. (Dĩ nhiên là ta vẫn dùng phương pháp định trị một đại lượng bằng hai cách.)

Ví dụ 9: một số đại số (algebraic number) là một nghiệm (thực hoặc phức) của một đa thức khác 0 hệ số hữu tỉ nào đó, nghĩa là nghiệm của a_0 + a_1x + \dots + a_nx^n = 0 trong đó a_i là các số hữu tỉ và a_n \neq 0. Bậc của một số đại số là bậc của đa thức tối giản (và monic) mà số đại số đó là nghiệm. Như vậy, số hữu tỉ chẳng qua là số đại số bậc nhất!

Ngược lại, số siêu việt là các số không phải số đại số. Lịch sử các số siêu việt cũng hay, bao gồm các đóng góp của Lindemann (sư phụ của Hilbert), Hermite (sư phụ của Poincaré), và cả một bài toán Hilbert (đã có lời giải).

Hermite chứng minh rằng e là số siêu việt, dùng phương pháp định trị hai cách. Hilbert đơn giản hóa chứng minh này một chút. Chứng minh của Hilbert là chứng minh đa số sách vở dùng hiện nay. Ta cũng sẽ dùng ý tưởng đã nêu trên. Giả sử e là số đại số. Không mất tính tổng quát ta giả sử có các số nguyên a_0, a_1, \dots, a_n với a_n \neq 0 thỏa mãn

f(e) := a_0 + a_1e + \dots + a_ne^n = 0

Ta sẽ tìm một số nguyên dương m sao cho mf(e) \neq 0, dẫn đến điều vô lý. Cụ thể hơn, ta sẽ chứng minh mf(e) = S_1 + S_2, trong đó S_1 là một số nguyên khác 0, còn |S_2| < 1. Từ ý tưởng của Hermite, Hilbert đặt
g(x) = x^q \left[(x-1)(x-2)\dots (x-n)\right]^{q+1}e^{-x}

m = \int_0^\infty \frac{1}{q!} g(x) dx

Trong đó q là một số nguyên dương sẽ xác định sau. Đến đây thì S_1, S_2 được xác định như sau
mf(e) = \sum_{k=0}^n a_ke^k \int_0^\infty \frac{1}{q!} g(x) dx = S_1 + S_2

trong đó
S_1 = \sum_{k=0}^n a_k \int_k^\infty \frac{1}{q!} g(x)e^k dx

S_2 = \sum_{k=1}^n a_k \int_0^k \frac{1}{q!} g(x)e^k dx

Ta phải chứng minh hai điều sau đây.

  • Điều 1 S_1 là môt số nguyên khác 0.

    Trước hết. Với k=1, \dots, n, đổi biến y = x-k ta có

    \int_k^\infty \frac{1}{q!} g(x)e^k dx = \int_0^\infty \frac{(y+k)^q \left[(y+k-1)\cdots(y+k-k)\cdots\right]^{q+1}e^{-y}}{q!} dy

    Với \alpha là số nguyên dương bất kỳ, hàm Gamma cho ta biết
    \int_0^\infty y^{\alpha} e^{-y}dy = \alpha!

    Vì thế \int_k^\infty \frac{1}{q!} g(x)e^k dx chia hết cho (q+1) với k=1, \dots, n. Như vậy
    S_1 \equiv a_0((-1)^nn!)^{q+1} \pmod{q+1}

    Dùng định lý Fermat nhỏ, dễ thấy rằng nếu ta chọn q+1 là một số nguyên tố lớn hơn a_0 và n! thì S_1 \not\equiv 0 \pmod{q+1}, vì thế S_1 là số nguyên khác 0.

  • Điều 2 |S_2| < 1.

    Trị tuyệt đối của mỗi số hạng trong tổng S_2 có dạng \frac{|\int_0^k a_kg(x)e^k dx|}{q!}. Tử số tiến đến vô cùng chậm hơn mẫu số rất nhiều, vì thế với q đủ lớn mỗi số hạng này rất bé, và vì thế tổng của chúng nhỏ hơn 1.

Bài tập 2: chứng minh rằng \pi là số siêu việt. (Gợi ý: dùng đẳng thức Euler e^{i \pi} + 1 = 0)

Chủ đề: Combinatorics | Bình luận »

Định trị một đại lượng bằng hai cách [3]

Ngô Quang Hưng | 16 tháng 04, 2006 | Bản để in Bản để in

Ví dụ 6: Tiếp theo bài 1 và bài 2, lần này ta xét vài kết quả liên quan đến hệ số Gauss (Gaussian coefficients, còn gọi là q-binomial coefficients vì nó là q-analog của binomial coefficients).

Xét không gian vector V = \mathbb{F}_q^n, là không gian hữu hạn n chiều trên trường \mathbb{F}_q (q là lũy thừa của một số nguyên tố). Ta sẽ trả lời hai câu hỏi sau đây:

  1. Cho 0 \leq m \leq n. Có bao nhiêu không gian con m chiều trong V?
  2. Cho 0 \leq k \leq m \leq n. Gọi W là một không gian con k chiều của V. Có bao nhiêu không gian con m chiều của V chứa W?

Xét câu hỏi thứ nhất trước. Gọi x là tổng số các bộ thứ tự (v_1, \dots, v_m) của m vectors độc lập tuyến tính của của V. Ta định trị x bằng hai cách:

  • Cách 1: có tất cả q^n-1 cách chọn v_1, sau đó có thể chọn v_2 bằng q^n-q cách, vân vân. Nói chung, có q^n-q^{i-1} cách chọn v_i để hình thành bộ thứ tự (v_1, \dots, v_m). Như vậy,
    x = (q^n-1)(q^n-q)\dots(q^n-q^{m-1})
  • Cách 2: gọi g(n,m) là số không gian con m chiều trong V. Xét một không gian con m chiều W bất kỳ. Gọi y là tổng số bộ thứ tự (v_1, \dots, v_m) của m vectors độc lập tuyến tính của của W. (Các vectors này là một hệ cơ sở của W.) Tương tự như trong cách 1, ta biết
    y = (q^m-1)(q^m-q)\dots(q^m-q^{m-1})

    Dễ thấy rằng x=y \cdot g(n,m).

Do đó, qua hai cách định trị này ta kết luận

g(n,m) = \frac{x}{y} = \frac{(q^n-1)(q^n-q)\dots(q^n-q^{m-1})}{(q^m-1)(q^m-q)\dots(q^m-q^{m-1})}.

Trong ngôn ngữ của q-series, ta thường ký hiệu (q)_k = (1-q)\dots(1-q^k), và viết lại các hệ số Gauss như sau:
g(n,m) := \genfrac{[}{]}{0pt}{}{n}{m}_q = \frac{(q)_n}{(q)_m (q)_{n-m}}

Bài tập 1: trả lời câu hỏi số hai bằng phương pháp định trị hai cách. (Gợi ý: định trị tổng số các bộ thứ tự (v_1, \dots, v_{m-k}) sao cho chúng độc lập tuyến tính và các v_i đều không nằm trong W. Câu trả lời sẽ là \genfrac{[}{]}{0pt}{}{n-k}{m-k}_q.) Qua bài tập này, ta có thể thấy sự tương đồng giữa hệ số Gauss và hệ số binomial.

Chủ đề: Combinatorics | Bình luận (1) »

Định trị một đại lượng bằng hai cách [2]

Ngô Quang Hưng | 12 tháng 04, 2006 | Bản để in Bản để in

Tiếp theo bài trước, lần này ta xét một ví dụ kinh điển.

Ví dụ 5. Euler là bậc thầy của kỹ thuật định trị hai cách (và là bậc thầy của ti tỉ thứ khác). Năm ông 24 tuổi (1731), Euler là người đầu tiên trong lịch sử toán học tìm được biểu thức tính \zeta(2), mà thời đó gọi là bài toán Basel. Số là Jakob Bernoulli rất bức xúc vì mãi không tìm ra giới hạn của tổng

\zeta(2) = 1 + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \dots

mặc dù Jakob biết rõ là nó có giới hạn. Từ thành phố Basel, Jakob viết trong quyển Tractatus de Seriebus Infinitis:

If anyone finds and communicates to us that which thus far has eluded our efforts, great will be our gratitude.

Chứng minh của Euler đại khái như sau. (Ở đây ta thay đổi một chút cho phù hợp với tính chặt chẽ của toán học hiện đại, nhưng tinh thần của chứng minh của Euler hoàn toàn không bị làm méo đi.) Ta khai triển biểu thức \sin(x)/x bằng hai cách:

  1. Dùng khai triển Taylor, dễ thấy
    \frac{\sin(x)}{x} = 1 - \frac{x^2}{3!} + \frac{x^4}{5!} - \frac{x^6}{7!} + \dots
  2. Dùng biến đổi Fourier, “dễ” chứng minh được rằng (ta quay lại với biến đổi Fourier vào dịp khác, vì kỹ thuật này tuyệt đối hữu dụng)
    \frac{\sin(x)}{x} = \left(1 - \frac{x^2}{\pi^2}\right)\left(1 - \frac{x^2}{2^2\pi^2}\right)\left(1 - \frac{x^2}{3^2\pi^2}\right)\dots

Hệ số của x^2 ở biểu thức 1 là - \frac{1}{3!}, còn hệ số của x^2 ở biểu thức 2 là - \frac{1}{\pi^2} \zeta(2). Nên \zeta(2) = \pi^2/6. Ta định trị hệ số của x^2 bằng hai cách để chứng minh một trong những công thức đẹp nhất trong toán học:

\zeta(2) = 1 + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + \dots = \frac{\pi^2}{6}

Robin Chapman có ghi lại một đống cách chứng minh điều này. Về Euler, tôi giới thiệu quyển “Euler, the master of us all” của Will Dunham. Các hàm zeta bậc cao hơn (và chẵn) cũng có thể tính cụ thể được dùng phương pháp định trị bằng hai cách.

Chủ đề: Combinatorics | Bình luận (3) »

Đề tài nào hấp dẫn lời bình?

Ngô Quang Hưng | 05 tháng 04, 2006 | Bản để in Bản để in

Có vẻ như viết cái gì “technical” quá hoặc thuần túy news thì ít có lời bình, cái gì philosophical hoặc khôi hài một chút thì hấp dẫn hơn. Bằng chứng là bác Ái Việt đang tiếp tục bình hai posts cũ: “nếu phải làm lại từ đầu” và “going to higher dimensional space” :-)

Nhân nói về “going to higher dimensional space”, có bài toán sau đây minh họa chiều ngược lại: dimension cao hơn làm cho bài toán khó hơn nhiều lần (trong trường hợp này là khó hơn vô hạn - so far):

Tổng số các ma trận hoán vị là n!. (Các ma trận vuông chỉ chứa 0 và 1 sao cho mỗi hàng và mỗi cột chỉ có một số 1.) Câu hỏi đơn giản là: đếm tổng số các hình lập phương - mỗi ô chứa 0 hoặc 1 (có tất cả n^3 ô) - trong đó mỗi cột (theo cả ba chiều) chỉ chứa một số 1. (Chú ý: mỗi chiều có n^2 cột.)

Tổng quát hơn, ta có thể hỏi câu hỏi tương tự cho các chiều từ 4 trở lên. Ta chưa trả lời được các câu hỏi này! (Không có công thức tính.)

Tổng số hình lập phương như trên bằng với tổng số hình vuông Latin với n symbols. Câu hỏi từ 4 chiều trở lên thì liên quan đến orthogonal arrays, có ứng dụng trực tiếp trong coding theory, đặc biệt là trong thiết kế các ma trận Hadamard, dùng cho thiết kế các chip-sequences của CDMA (orthogonal codes dùng cho wireless transmission - ví dụ như cellphones).

Chủ đề: Combinatorics | Bình luận (2) »

Định trị một đại lượng bằng hai cách [1]

Ngô Quang Hưng | 31 tháng 03, 2006 | Bản để in Bản để in

Một trong những ý tưởng sâu sắc nhất tôi học được trong Toán học là “định trị một đại lượng bằng hai cách“. Ta có thể dùng ý tưởng này để

  • chứng minh rất nhiều các đẳng thức toán học
  • tìm công thức (gọn) tính một biểu thức toán học
  • chứng minh rất nhiều các bất đẳng thức toán học

Trong loạt bài này tôi ghi lại một số ví dụ minh họa ý tưởng này. Trong các ví dụ sau đây, ta dùng ký hiệu

[n] = \{1, \dots, n\}

Ví dụ 1: xét đẳng thức

\sum_{i=0}^n \binom{n}{i} = 2^n

Vế trái rõ là đếm tổng số các tập con của [n] (đếm theo i là kích thước tập con). Mỗi tập con tương ứng 1-1 với một vector trong \mathbb{F}_2^n, các phần tử của tập con tương ứng với thành phần bằng 1 trong vector. Có tổng cộng 2^n vectors như vậy.

Ví dụ 2: đẳng thức sau đây thường được gọi là đẳng thức Vandermonde (Vandermonde’s convolution formula), là trường hợp đặc biệt của đẳng thức Chu-Vandermonde trong lý thuyết chuỗi siêu hình học (hypergeometric series):

\sum_{i=0}^k \binom{n}{k-i} \binom{m}{i} = \binom{m+n}{k}

Vế phải là tổng số các tập con kích thước k của tập [m+n]. Ta có thể chọn một tập kích thước k bằng cách chọn i phần tử từ [m] và k-i phần tử từ [m+n]-[m]. Đó là đại lượng mà vế trái tính.

Ví dụ 3: với các số nguyên dương i \leq j \leq n, định nghĩa ma trận W_{ij} như sau. Các hàng của W_{ij} được đánh số bằng các tập con kích thước i của [n], các cột tương ứng với các tập con kích thước j. Và,

(W_{ij})_{X,Y} = \begin{cases} 1 & X \subseteq Y \\ 0 & X \not\subseteq Y \end{cases}

Ta sẽ chứng minh rằng A = W_{ij}^TW_{ij} là matrận positive semi-definite, và là positive definite nếu i=j. (Dĩ nhiên, B^TB luôn positive semi-definite vì v^TB^TBv = |Bv|^2, nhưng ta chứng minh bằng cách hơi khác.) Trước hết, với X,Y là các tập con kích thước j của [n], ta có
a_{X,Y} = \binom{|X \cap Y|}{i}

Với vector v \neq 0 bất kỳ (trong không gian thực \binom{n}{j} chiều), ta có
v^TAv = \sum_X \sum_Y \binom{|X \cap Y|}{i} v_Xv_Y

Đến đây, ta sẽ dùng ý tưởng “định trị một đại lượng theo hai cách”. Trong tổng trên, số lần xuất hiện của mỗi cặp v_Xv_Y bằng với tổng số tập con I kích thước i trong phần giao của X và Y. Như vậy, ta có thể viết lại cái tổng trên bằng cách nhóm các số hạng theo I:
v^TAv = \sum_{I : |I| = i} \sum_{X \supseteq I} \sum_{Y \supseteq I} v_Xv_Y

Đến đây thì ta xong vì
v^TAv = \sum_{I : |I| = i} \left( \sum_{X \supseteq I} v_X \right)^2 \geq 0

Ví dụ trên xuất hiện trong các chứng minh dùng đại số tuyến tính của định lý Ray-Chaudhuri–Wilson trong lý thuyết thiết kế (Design Theory).

Ví dụ 4: khi nhắc đến ý tưởng “định trị bằng hai cách”, không thể nào không nhắc đến định lý Erdos-Ko-Rado lừng danh và chứng minh của Katona. Định lý Erdos-Ko-Rado phát biểu như sau:

Gọi \mathcal{A} là một bộ các tập con kích thước k của [n] (n \geq 2k) thỏa mãn điều kiện rằng hai thành viên bất kỳ của \mathcal{A} đều giao nhau. Ta có, |\mathcal{A}| \leq \binom{n-1}{k-1}

Chứng minh. Gọi \mathcal{C} là tập tất cả các cách xếp các số 1, \dots, n trên một đường tròn (cyclic order). Có tất cả (n-1)! cách. Ta sẽ định trị đại lượng s sau đây bằng hai cách: tổng số các cặp (A, C) trong đó A \in \mathcal{A}, C \in \mathcal{C}, và các phần tử của A nằm liên tục trên một cung của C.

  • Cách một: với mỗi A \in \mathcal{A}, có tất cả k!(n-k)! đường tròn C chứa A liên tục trên một cung. Do đó, s = |\mathcal{A}| k! (n-k)!
  • Cách hai: với mỗi đường tròn C, có nhiều nhất là k thành viên của \mathcal{A} là cung của đường tròn, do từng cặp trong chúng phải giao nhau. Vì thế, s \leq (n-1)!k

Ta suy ra kết quả |\mathcal{A}| \leq \binom{n-1}{k-1} từ hai cách định trị s như trên. Đẳng thức có thể đạt được bằng cách chọn \mathcal{A} là bộ tất cả các tập con chứa phần tử 1. Ví dụ này cho thấy ta có thể dùng ý tưởng “định trị hai cách” để chứng minh bất đẳng thức.

Chủ đề: Combinatorics | Bình luận »