Bàn về bài 5 – Olympic toán quốc tế 2008

Từ khi rẽ hướng từ Toán sang Tin, tôi ko còn tập giải đề cuộc thi này, toàn quan tâm chuyện bên lề, nếu có giải thì cũng chỉ “cưỡi ngựa xem hoa” bài Tổ hợp.

Olympic Toán quốc tế năm nay được tổ chức tại thủ đô Madrid – Tây Ban Nha. Đoàn Việt Nam có thành tích rất cao, cả 7 thành viên đều đoạt huy chương, trong đó nổi bật là Hoàng Đức Ý đến từ Lam Sơn (Thanh Hóa) có điểm số cao nhất với tấm huy chương vàng. Sau 7 năm vắng bóng, Lam Sơn có sự trở lại đầy ấn tượng. Bản thân tôi ko lạ gì cái tên Hoàng Đức Ý, vài năm gần đây đọc báo Toán học Tuổi trẻ thấy đăng tên Ý ầm ầm.

Trở lại chủ đề chính, quả thực bài 5, bài tổ hợp năm nay khá thú vị:

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.

Một dạng quen thuộc: bài toán về những chiếc bóng đèn có 2 trạng thái: on / off. So với bài toán cùng dạng tôi phải giải trong game Tomb Raider, xem ra bài này còn dễ hơn. Suy nghĩ những bài kiểu như thế luôn luôn sướng, chả cần nháp nhiếc gì, cứ nằm khểnh trên giường tự do bay bổng, chỉ cần một ý tường là xong. Cái cách ra đề bắt tính N/M cũng đã gợi ý cách giải, phản ứng đầu tiên của tôi là: với mỗi dãy thuộc loại 1, hãy tìm cách sinh ra từ nó P dãy thuộc loại 2, chứng minh các bộ P dãy đó ko giao nhau, vậy thì kết quả N/M = P.

Thật vậy, xét bất kì dãy D gồm k phần tử thuộc loại 1: x[1], x[2], …, x[k] dĩ nhiên 1 <= x[i] <= n, D ko thiếu số tự nhiên nào từ 1 đến n và số lần xuất hiện của mỗi số tự nhiên đó là lẻ. Xét bất kì số tự nhiên t từ 1 đến n, giả sử t xuất hiện trong D tại các vị trí từ trái qua phải là i[1] < i[2] < … < i[z] thì z lẻ, z >= 1. Xét tất cả các tập con chẵn phần tử của i[1], i[2], …, i[z] (kể cả tập rỗng), với mỗi tập con đó, thay các số hạng trong D tại các vị trí đó bằng (t + n), thì sinh ra được 1 dãy E thuộc loại 2. Số tập con nói trên là 2^(z-1) và hiển nhiên ko có 2 dãy E giống nhau. Cho t chạy hết từ 1 đến n, tương ứng được z[1], z[2], …, z[n], ta có tổng số tập con, cũng là tổng số dãy E sinh ra được từ D là:

2^(z[1]-1) * 2^(z[2]-1) * … * 2^(z[n]-1) = 2^(z[1] + z[2] + … + z[n] – n) = 2^(k-n)

Vậy N/M = 2^(k-n)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s