Đề thi toán quốc tế 2008
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ệ.

là một ma trận vuông thực hoặc phức. Gọi
là đa thức đặc trưng của
.

, tức là định thức của ma trận
là
bằng ma trận 
, 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
là một số hữu tỉ, nghĩa là
là một số nguyên dương nào đó. Khi phân tích
ra thừa số nguyên tố, vì
các thừa số nguyên tố của
thừa số 2 sẽ có số mũ lẻ. Vô lý!
là số vô tỉ dùng phương pháp định trị 2 cách như sau. Giả sử
là hữu tỉ. Theo khai triển Taylor ta có:
thì vế trái là một số nguyên, trong khi đó vế phải bằng
là một số nguyên, trong khi đó
là một số thực trong khoảng
. Vô lý!
trong đó
là các số hữu tỉ và
. Bậc của một số đại số là bậc của đa thức tối giản (và
với 
, dẫn đến điều vô lý. Cụ thể hơn, ta sẽ chứng minh
, trong đó
là một số nguyên khác 0, còn
. 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} g(x) = x^q \left[(x-1)(x-2)\dots (x-n)\right]^{q+1}e^{-x}](/blog/latexrender/pictures/89f5d4d3d674fd729078a0615119dc01.gif)

là một số nguyên dương sẽ xác định sau. Đến đây thì
được xác định như sau


, đổi biến
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 \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](/blog/latexrender/pictures/83b0c0fe014faff8e8579793b0472f7a.gif)
là số nguyên dương bất kỳ, 
chia hết cho
với 
và
thì
, vì thế
có dạng
. Tử số tiến đến vô cùng chậm hơn mẫu số rất nhiều, vì thế với
là số siêu việt. (Gợi ý: dùng đẳng thức Euler
)
, là không gian hữu hạn
chiều trên trường
(
. Có bao nhiêu không gian con
chiều trong
?
. Gọi
là một không gian con
chiều của
của
cách chọn
, sau đó có thể chọn
bằng
cách, vân vân. Nói chung, có
cách chọn
để hình thành bộ thứ tự 
là số không gian con
là tổng số bộ thứ tự 
.

, 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}} g(n,m) := \genfrac{[}{]}{0pt}{}{n}{m}_q = \frac{(q)_n}{(q)_m (q)_{n-m}}](/blog/latexrender/pictures/3b15f340fe041e30daad71aa6ffaff0f.gif)
sao cho chúng độc lập tuyến tính và các
.) 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.
, mà thời đó gọi là bài toán Basel. Số là 
bằng hai cách:

ở biểu thức 1 là
, còn hệ số của
. Nên
. Ta định trị hệ số của 
ô) - trong đó mỗi cột (theo cả ba chiều) chỉ chứa một số 1. (Chú ý: mỗi chiều có
cột.)![[n] = \{1, \dots, n\} [n] = \{1, \dots, n\}](/blog/latexrender/pictures/f7d04fd3caea4a343277ab774ce1641d.gif)

(đếm theo
là kích thước tập con). Mỗi tập con tương ứng 1-1 với một vector trong
, các phần tử của tập con tương ứng với thành phần bằng
trong vector. Có tổng cộng
vectors như vậy.

. Ta có thể chọn một tập kích thước
và
phần tử từ
. Đó là đại lượng mà vế trái tính.
, định nghĩa ma trận
như sau. Các hàng của
. Và,
là
. (Dĩ nhiên,
luôn positive semi-definite vì
, nhưng ta chứng minh bằng cách hơi khác.) Trước hết, với
là các tập con kích thước 
bất kỳ (trong không gian thực
chiều), ta có
bằng với tổng số tập con
kích thước
và
. 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 

là một bộ các tập con kích thước
) thỏa mãn điều kiện rằng hai thành viên bất kỳ của
là tập tất cả các cách xếp các số
trên một đường tròn (cyclic order). Có tất cả
cách. Ta sẽ định trị đại lượng
sau đây bằng hai cách: tổng số các cặp
trong đó
, và các phần tử của
.
, có tất cả
đường tròn