Blog Khoa Học Máy Tính

Bổ đề Sauer

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

Bài học máy qua góc nhìn của lý thuyết tính toán số 4 có chứng minh bổ đề Sauer (bổ đề 5.2) bằng quy nạp. Tuy nhiên, một chứng minh bằng quy nạp không hay lắm vì nó “giấu” trực quan của chứng minh. Trong bài này, chúng ta sẽ chứng minh bổ đề Sauer bằng một kỹ thuật rất phổ biến trong extremal combinatorics gọi là kỹ thuật shifting. Xem các tham khảo sau đây để biết thêm về kỹ thuật shifting:

[1] P. Frankl: The shifting technique in extremal set theory, in Surveys in Combinatorics 1987 (C Whitehead, ed.), London Math. Soc. Lecture Note Series 123, Cambridge University Press (1987), 81–110.

[2] B. Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability. Cambridge University Press 1986.

Rất nhiều định lý cổ điển như định lý Erdos-Ko-Rado (đã chứng minh trên blog này bằng kỹ thuật định trị hai cách) hay định lý Kruskal-Katona đều chứng minh được bằng kỹ thuật shifting. Kỹ thuật này cũng được ứng dụng gần đây trong nhánh phân tích các hàm Boolean. Nhánh này liên hệ mật thiết đến computational learning theory, coding theory, approximation algorithms, và complexity theory: toàn là các đề tài trung tâm của theoretical CS hiện nay.

Ta sẽ phát biểu lại bổ đề Sauer. Gọi $\mathcal H$ là một lớp các hàm số từ $\Omega$ vào $\{0,1\}$ . Có thể hiểu $\mathcal H$ là một bộ các tập con của $\Omega$ . Chú ý rằng cả $\mathcal H$ lẫn $\Omega$ đều có thể vô hạn (thậm chí không đếm được). Với một tập con hữu hạn $S \subseteq \Omega$ , định nghĩa projection của $\mathcal H$ lên như sau: $\Pi_{\mathcal H}(S) = \{ h \cap S \ | \ h \in \mathcal H\}$ . Trong ngữ cảnh “học máy” thì projection của lớp giả thuyết $\mathcal H$ lên một tập hữu hạn các mẫu là bộ tất cả các cách mà các giả thuyết này phân lớp các mẫu này.

Một tập bị băm nát bởi $\mathcal H$ nếu $\Pi_{\mathcal H}(S)$ chính là tập tất cả các tập con của . VC-dimension của $\mathcal H$ là kích thước lớn nhất của một tập con của $\Omega$ bị băm nát bởi $\mathcal H$ . Nếu $\mathcal H$ băm nát một tập con có kích thước lớn tùy ý thì VC-dimension của $\mathcal H$ là vô hạn.

Bổ đề Sauer:

Giả sử $\mathcal H$ có VC-dimension hữu hạn, bằng . Xét một tập con bất kỳ của $\Omega$ . Ta có,

$|\Pi_{\mathcal H}(S)| \leq \sum_{i=0}^d \binom m i$

Chứng minh. Đặt $\mathcal F = \Pi_{\mathcal H}(S)$ . Dĩ nhiên $\mathcal F$ là hữu hạn, và là một bộ các tập con của . Không mất tính tổng quát, ta có thể giả sử m>d . Do $\mathcal H$ không băm nát bất kỳ tập con nào có kích thước $\geq d+1$ , dễ thấy rằng $\mathcal F$ cũng không băm nát bất kỳ tập con nào của với kích thước $\geq d+1$ . Ta sẽ dùng tính chất này để chặn trên $|\mathcal F|$ .

Chúng ta sẽ “xê dịch” (shift) $\mathcal F$ từ từ để thành một bộ $\mathcal G$ các tập con mới của thỏa mãn các điều kiện sau đây:

$|\mathcal G| = |\mathcal F|$
Nếu $A \subset S$ bị băm nát bởi $\mathcal G$ thì cũng bị băm nát bởi $\mathcal F$ .
$\mathcal G$ là một ideal của Boolean lattice trên , nghĩa là nếu $G\in \mathcal G$ thì tất cả các tập con của đều là thành viên của $\mathcal G$ .

Giả sử ta tìm được $\mathcal G$ thỏa mãn các điều kiện trên, thì một tập con của bị $\mathcal G$ băm nát nếu và chỉ nếu $A \in \mathcal G$ . Nhưng $\mathcal G$ không băm nát bất kỳ tập con nào có kích thước $\geq d+1$ . Do đó, tất cả các thành viên của $\mathcal G$ đều có kích thước $\leq d$ . Vì thế $|\mathcal G| \leq \sum_{i=0}^d \binom m i$ .

Đến đây, ta mô tả phép “dịch chuyển” $\mathcal F$ thành $\mathcal G$ thỏa mãn các điều kiện 1, 2, 3 ở trên bằng một thuật toán. Giả sử $S = \{1, 2, \dots, m\}$ .

1. For ( to ) do
2.    Foreach () do
3.        If ( and ), then
4.            Replace  by 
5.        Endif
6.    Endfor
7. Endfor
8. Repeat 1–7 until  no longer changes. Call this final collection

Với mỗi vòng lặp 1–7, nếu bộ $\mathcal F$ không đổi thì thuật toán kết thúc, còn nếu có đổi thì một thành viên nào đó của $\mathcal F$ bị giảm kích thước. Kích thước của các thành viên của $\mathcal F$ không thể giảm mãi (mà $\mathcal F$ vẫn thay đổi), do đó thuật toán sẽ kết thúc.

Bây giờ ta chứng minh rằng $\mathcal G$ thỏa mãn ba điều kiện 1, 2, và 3 ở trên.

Điều kiện 1 đã rõ ràng, vì ta chỉ biến thành $F \setminus \{i\}$ khi $F \setminus \{i\} \notin \mathcal F$
Ta chứng minh rằng tính chất này bất biến sau mỗi lần ta thực hiện vòng lặp 2–6 với một phần tử bất kỳ trong thuật toán trên. Giả sử $\mathcal F$ là bộ tập hợp trước khi vòng lặp này được thực hiện, và $\mathcal F'$ là bộ tập hợp sau khi vòng lặp này được thực hiện.
Giả sử $A\subseteq S$ bị băm nát bởi $\mathcal F'$ . Nếu $i \notin A$ thì dĩ nhiên đã bị băm nát trước thay đổi. Do đó, có thể giả sử $i \in A$ .

Xét một tập con $R\subseteq A$ nào đó. Ta cần chứng minh rằng $R = A \cap F$ với $F \in \mathcal F$ . Do bị băm nát sau vòng lặp, $R = A \cap F'$ với $F' \in \mathcal F'$ . Nếu $i \in R$ thì cũng thuộc $\mathcal F$ . Bây giờ xét trường hợp $i \notin R$ . Tồn tại $T\in \mathal F'$ sao cho $T \cap A = R \cup \{i\}$ . Rõ ràng là cũng thuộc $\mathcal F$ . Nhưng “còn sống sót” sau vòng lặp chứng tỏ là $T \setminus \{i\} \in \mathcal F$ , và do đó $R = A \cap (T \setminus \{i\})$ .
Tính chất này đã rõ.

Chủ đề: Combinatorics & Trí tuệ nhân tạo | Bình luận »

Đại bàng con

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

Năm ngoái kỷ niệm CMT10 bằng Улыбка, năm nay kỷ niệm CMT10 bằng Орлёнок.

Орлёнок, орлёнок, взлети выше солнца
И степи с высот огляди.
Навеки умолкли весёлые хлопцы,
В живых я остался один.

Орлёнок, орлёнок, блесни опереньем,
Собою затми белый свет.
Не хочется думать о смерти, поверь мне,
В шестнадцать мальчишеских лет.

Орлёнок, орлёнок, гремучей гранатой
От сопки врагов отмело.
Меня называли орлёнком в отряде,
Враги называли орлом.

Орлёнок, орлёнок, мой верный товарищ,
Ты видишь, что я уцелел.
Лети на станицу, родимой расскажешь,
Как сына вели на расстрел.

Орлёнок, орлёнок, товарищ крылатый,
Ковыльные степи в огне.
На помощь спешат комсомольцы-орлята
И жизнь возвратится ко мне.

Орлёнок, орлёнок, идут эшелоны,
Победа борьбой решена.
У власти орлиной орлят миллионы,
И нами гордится страна.

Lời Nga copy lại từ Marxists.org. Lời Việt bắt đầu bằng: “bay lên đón mặt trời đại bàng con hãy vút cao qua núi đồi, hãy lướt tới bao chân mây …”

Chủ đề: Âm Nhạc | Bình luận (4) »

Tại sao Obama thắng?

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

Đối với dân máy tính thì câu trả lời đã rõ ràng qua cuộc phỏng vấn sau đây ở Google:

Chủ đề: Vui - Giải Trí | Bình luận (1) »

Vượt định kiến bằng Lăng Ba Vi Bộ

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

Mục lục.

1. Hội xu ngửa
2. Từ ngữ dùng để phỉ báng, xưa và nay
3. Đập đầu vào tường mãi, một trong hai thứ sẽ vỡ
4. Đồng hồ nguyên tử ở bệnh viện phụ sản
5. Bọn cướp biển và hiện tượng ấm toàn cầu
6. Shakespeare và một triệu con khỉ
7. Khi những con giun đất hiển linh
8. Vượt định kiến bằng Lăng Ba Vi Bộ
9. Được làm vua, thua làm … chú thích

Hội xu ngửa.
Tương truyền rằng, nhà vua ở một vương quốc vĩ đại nọ rất yêu khoa học. Tên miền của vương quốc này là NN. Ông ta muốn tìm hiểu cơ động học của tiền xu vào những đêm nguyệt thực, vì đây là những đêm thiên địa dung hòa, vũ trụ tiết lộ bí mật của nó. Cứ mỗi lần nguyệt thực, ông yêu cầu mỗi người dân thảy một đồng xu xem nó sấp hay ngửa. Sau một thời gian, dân chúng cũng nhiễm tinh thần yêu chân lý của nhà vua, và họ đưa ra những mô hình dự đoán sấp ngửa. Ngưu tầm ngưu, mã tầm mã, mô hình tầm mô hình.

Hiệp hội mười đồng xu ngửa ra đời trong hoàn cảnh ấy. Mô hình dự đoán của hiệp hội này rất đơn giản: các đồng xu thảy trong một đêm nguyệt thực luôn ra mặt ngửa. Vương quốc nọ có khoảng 100 triệu dân. Hiệp hội mười đồng xu ngửa có trên dưới 100 nghìn thành viên. Họ có cả một website tên là “xungửa.còm” rất đông khách vãng lai. Tất cả các đồng xu thảy bởi 100 nghìn thành viên này trong 10 lần nguyệt thực gần đây nhất đều cho ra mặt ngửa, vị chi là 1 triệu đồng xu ngửa. Các trải nghiệm của họ hoàn toàn nhất quán với mô hình. Họ lý luận rằng xác suất mà cả một triệu đồng xu đều ngửa là một phần 2 lũy thừa một triệu. Mà 2 mũ 130 thôi đã nhiều hơn tổng số nguyên tử trên toàn vũ trụ rồi. Do đó lý thuyết của họ không thể nào sai!

Trời sinh cả Du lẫn Lượng. Song song với họ, còn có hiệp hội mười đồng xu úp, rồi điều tra census thường niên của nhà vua cho thấy còn có cả hiệp hội hiệp hội năm ngửa, năm sấp, hiệp hội sấp ngửa năm lần, hiệp hội sấp sấp ngửa ngửa sấp hai lần, và cỡ chừng 1019 hiệp hội khác. Các hiệp hội này tranh cãi nhau chí tử, sắp sửa bạo loạn đến nơi.

Ông vua nọ rất buồn, cố gắng đứng ra hòa giải. Phụng thiên thừa mệnh, hoàng đế chiếu rằng: đến 7 đêm nguyệt thực kế tiếp, tự thân vua sẽ thảy đồng xu, và hiệp hội nào đoán đúng cả 7 đồng xu sẽ là kẻ chiến thắng, hội trưởng sẽ được phong chức quốc sư, tiền tài quyền lực không bút nào tả xiết, kể cả các tay bút sừng sỏ nhất của Minh Biện (nghĩa là không sừng sỏ gì lắm). Nguyệt thực thì mỗi năm có từ 0 đến 3 lần, phải chờ đến 5 năm sau kết quả mới được công bố. Kết quả là: còn đến cả chục hiệp hội đoán đúng cả 7 đồng xu! Ông vua thấy thế buồn quá ngã vật ra chết lăn quay cù quày, ôm xuống tuyền tài cái mộng giải thích cơ động học đồng xu. Mặc dù chẳng hội nào chiếm được chức thái sư, kể từ ngày đó, các hiệp hội này danh tiếng nổi như cồn, trở thành các trường phái nghiên cứu môn cơ động học đồng xu đêm nguyệt thực mà hiện nay có rất nhiều môn đệ tử trên toàn thế giới.

Từ ngữ dùng để phỉ báng, xưa và nay.

Đó là chuyện xưa. Ngày nay, ở một quốc gia khác với tên miền VN, cũng có nhiều môn phái lớn. Chỉ hơi khác là các mặt đồng xu ở quốc gia này được in nhiều thứ hơn là sấp/ngửa:

Đồng xu	Ngửa	Sấp
1	Mũi tẹt	Mũi tẹt hơn
2	Làm cho Tuổi Trẻ	Làm cho Thanh Niên
3	Thi Đại Học được ≥ 13.5 điểm (vừa đậu!)	Thi Đại Học được < 13.5 điểm
4	Sinh ra trong gia đình khá giả	Sinh ra trong gia đình nghèo
5	Bố mẹ cho genes tốt	Bố mẹ không cho genes tốt
6	Sinh bên này vĩ tuyến 17	Sinh bên kia vĩ tuyến 17
7	Cao trên 1 mét 45	Cao dưới 1 mét 45
8	Vòng ngực trên 72cm	Vòng ngực dưới 72cm
9	Cha mẹ đặt tên là Lê Văn Kiểm	Cha mẹ đặt tên là Tăng Minh Phụng
10	…	…

Và hiệp hội mười xu ngửa trong quốc gia này có tên rất lạ là hiệp hội èo lít. Những người còn nhớ văn hóa vương quốc NN cổ xưa không thể hiểu được tại sao mười xu ngửa trong quốc gia VN lại được gọi là èo lít, chắc là cần thương hiệu mới vì sợ vi phạm tác quyền. Nhưng khác nhau chỉ về tên gọi, còn hiện tượng thì vẫn như ở NN: các hiệp hội vào In Tờ Lét phỉ nhau chí tử. Thậm chí thành viên các hiệp hội còn dùng những từ như “ngu”, “dốt”, “cộng sản”, “chống cộng Bolsa”, “hèn”, “đểu”, vân vân, để gọi nhau.

Hồi xưa ở vương quốc NN người ta hay chửi nhau: “mày là cái đồ sấp ngửa ngửa sấp sấp”.

Đập đầu vào tường mãi, một trong hai thứ sẽ vỡ.
Trong vương quốc VH, xu ngửa = nhà xuất bản nhận in bản thảo, xu sấp = nhà xuất bản từ chối in bản thảo.

Năm 1995, một phụ nữ người Anh nộp bản thảo của mình và nhận được 12 đồng xu sấp liên tục. Thay vì gia nhập hội một tá xu sấp, bà ta thử thêm xu mười ba và lần này là xu ngửa từ nhà xuất bản Bloomsbury. Đồng xu ngửa này cũng xém nữa là sấp nếu không nhờ một cô bé 8 tuổi tên Alice Newton, con gái của giám đốc Bloomsbury, đã đọc chương một và đòi bố cho xem chương hai. Tuy nhận in, một biên tập viên của Bloomsbury gợi ý rằng phụ nữ nọ nên đi tìm việc khác vì viết sách trẻ em rất ít tiền. Người phụ nữ đó tên là Joanne Rowling. Bản thảo đánh trên máy đánh chữ có tựa đề “Harry Potter và hòn đá của Triết Gia”. Đồng xu ngửa số 13 biến Rowling thành người đầu tiên trong lịch sử thế giới trở thành tỉ phú tiền đô nhờ viết sách, và là người giàu thứ 1062 trên thế giới, theo tạp chí Forbes.

Chỉ trong phạm vi sách trẻ em, bản thảo quyển And to Think That I Saw It on Mulberry Street nhận được khoảng 27, 28 đồng xu sấp. Đó là bản thảo đầu tay của Theodor Seuss Geisel, được biết nhiều hơn qua cái tên Dr. Seuss. Phần còn lại là lịch sử. Trong top 100 các sách thiếu nhi bán chạy nhất mọi thời đại, 16 quyển là của Dr. Seuss. Ông viết khoảng 60 sách thiếu nhi, bán được cỡ 220 triệu bản.

Thế nhỡ những người như Rowling và Dr. Seuss gia nhập hội mười xu sấp hơi sớm một chút thì sao?

Một tác giả Mỹ đã nhận toàn xu sấp, và tự tử chết. Mẹ ông ta đem một bản thảo đến nhà văn Walker Percy và Percy giúp đem in. Bản thảo nọ là quyển A Confederacy of Dunces. Tác giả đã chết tên là John Kennedy Toole. Năm 1981, tiểu thuyết này được có mỗi … giải Pulitzer.

Trong thế giới điện ảnh (ĐA), xu ngửa = phim có lời nhiều, xu sấp = phim lời ít. Các hội sấp ngửa tương tự như thế giới VH nhiều không kể xiết. Xem thêm A Drunkard’s Walk có nhiều ví dụ.
Các bệnh viện phụ sản có đồng hồ nguyên tử
Chiêm tinh học là một giáo phái xu ngửa có truyền thống vài nghìn năm. Các tín đồ tin rằng giờ/ngày/tháng/năm sinh và vị trí trăng sao có thể dùng để đoán vận mệnh, tính cách cá nhân và các sự kiện xã hội. Không ít nghiên cứu khoa học đã cho thấy chiêm tinh học đoán chính xác bằng với … đoán bừa, ví dụ xem mấy bài này trên tờ Nature và các tham khảo từ đó:

Shawn Carlson. “A double-blind test of astrology“. Nature, 318, 419 - 425 (05 December 1985).
John Maddox, Defending Science Against Anti-Science, Nature, 368:185, 1994.

Hoặc gần đây hơn, các nhà khoa học đã ghi lại hành trình cá nhân của 2000 người sinh trong khoảng vài phút của nhau, hồi đầu tháng 3 năm 1958, mà theo chiêm tinh học thì họ sẽ có “số phận” tương tự. Họ đánh giá khoảng 100 đặc điểm, bao gồm chỉ số IQ, nghề nghiệp, sức khỏe tinh thần, khả năng nghệ thuật, toán học, khoa học, thể thao, khả năng đọc, viết, vân vân. Đây là tất cả các đặc điểm mà chiêm tinh học khẳng định có thể “đoán” dùng hồ sơ khai sinh. Kết quả là Chiêm Tinh Học hoàn toàn sai (uniformly negative).

Tín đồ chiêm tinh học cãi: “cách nhau vài phút là làm số phận khác nhau lắm rồi“. Thế nhưng nếu bạn đi xem chiêm tinh gia đoán số phận thì họ sẽ vui lòng lấy dữ liệu ngày giờ sinh rất không chính xác mà bạn đưa ra. Bạn có bao giờ đi một cái bệnh viện phụ sản mà ở đó có đồng hồ nguyên tử, hay đồng hồ caesium chưa? Mà đồng hồ nguyên tử cũng chỉ đúng đến 1 phần 10 mũ 10 giây thôi.

Vả lại, kể cả khi có đồng hồ nguyên tử thì tính giờ sinh từ lúc nào nhỉ? Ông bố đứng bên cạnh cầm đồng hồ (nguyên tử) quả lắc, nhăm nhăm thấy bà mụ vừa lấy con mình ra là … bấm ngay à? Nếu thò cái đầu ra thì có gọi là “ra đời” chưa? Nếu phải ra ngoài hẳn thì mới tính vào giờ sinh thì những đứa bé chết trong các ca sinh khó khăn là không có “số mệnh” à? Còn những đứa bé phải mổ thì tính giờ sinh thế nào?

Lý luận như trên của tín đồ chiêm tinh thuộc về vương quốc tất cả các đồng xu hai mặt đều ngửa. Đoán kiểu nào cũng đúng, bằng chứng ngược kiểu gì cũng sai. Trong vương quốc này, hiệu ứng Forer được thấy ở khắp nơi. Năm 1948, nhà tâm lý học Bertram R. Forer đưa cho sinh viên của ông một bộ câu hỏi xác định cá tính (personality test). Sau khi các sinh viên trả lời bộ câu hỏi xong, thì mỗi sinh viên nhận được một bản “đánh giá cá tính” dựa trên các câu trả lời của bản thân sinh viên họ. Mỗi sinh viên sẽ chấm điểm bản đánh giá cá tính của bản thân mình xem đúng hay sai, điểm từ 0 (hoàn toàn sai) đến 5 (hoàn toàn đúng). Các bản đánh giá cá tinh này được các sinh viên cho điểm trung bình 4.26: rất ấn tượng!

Chỉ có một vấn đề nhỏ: Ferer đã phát cho tất cả các sinh viên cùng một bản đánh giá cá tính mà ông chép lại từ các horoscopes. Bản đánh giá cá tính này có nội dung như sau:

You have a need for other people to like and admire you, and yet you tend to be critical of yourself. While you have some personality weaknesses you are generally able to compensate for them. You have considerable unused capacity that you have not turned to your advantage. Disciplined and self-controlled on the outside, you tend to be worrisome and insecure on the inside. At times you have serious doubts as to whether you have made the right decision or done the right thing. You prefer a certain amount of change and variety and become dissatisfied when hemmed in by restrictions and limitations. You also pride yourself as an independent thinker; and do not accept others’ statements without satisfactory proof. But you have found it unwise to be too frank in revealing yourself to others. At times you are extroverted, affable, and sociable, while at other times you are introverted, wary, and reserved. Some of your aspirations tend to be rather unrealistic.

Các chiêm tinh gia là các nhà tâm lý đại tài, nhưng khả năng dự đoán tương lai của họ thì bằng với khả năng bệnh viên phụ sản Từ Dũ có đồng hồ nguyên tử trên từng giường đẻ.

Vài chục năm trước, một người Tây Ban Nha trúng sổ số độc đắc. Chuỗi số độc đắc kết thúc bằng con số 48. Rất tự hào về “thành tựu” của mình, ông ta tiết lộ bí mật: “tôi nằm mơ thấy số 7 trong 7 đêm liền, mà 7 lần 7 là 48, do đó tôi tìm mua các số kết thúc bằng 48, nhờ đó trúng độc đắc”. Ông này có thể bầu làm vua của vương quốc các đồng xu 2 mặt ngửa. Xem

Stanley Meisler, Spain lottery — Not even war stops it. Los Angeles Times, Dec 30, 1977.
Bọn cướp biển và hiện tượng ấm toàn cầu

Năm 2005, ban giáo dục tiểu ban Kansas đòi dạy Intelligent Design — một thông điệp tôn giáo giả danh khoa học — trong các trường phổ thông. Để minh họa cho tính nhố nhăng của lý luận của ban giáo dục, Bobby Henderson đã làm một cái chart so sánh tổng số cướp biển và nhiệt độ toàn cầu (xem ảnh), và sau đó thành lập đại giáo phái Quỷ Mì Ý Bay có đến vài chục triệu tín đồ (để chế diễu ban giáo dục nọ). Chúng ta sẽ bàn về giáo phái Quỷ Mì Ý Bay trong một dịp khác, điều ta cần là cái chart giảm cướp biển thì tăng nhiệt độ toàn cầu ở trên.

Một giáo phái xu ngửa có rất nhiều tín đồ có tên là Objectivism. Giáo chủ là Ayn Rand, với Alan Greenspan là một (cựu) giáo dân. Sau vụ khủng hoảng tài chính lần này, Greenspan thừa nhận:

“I made a mistake in presuming that the self-interests of organizations, specifically banks and others, were such as that they were best capable of protecting their own shareholders and their equity in the firms.”

Greenspan, 82, who relinquished leadership of the Fed just two years ago, said the collapse of the sub-prime mortgage industry — and the vast, mostly hidden trade in derivative financial instruments it spawned — exposed a “flaw” in his categorical reliance on free markets.

Khoan xét đến việc Objectivism là đúng hay sai (tín đồ của họ bảo vệ tới cùng, cho rằng Greeenspan không phải là free marketeer thật sự), trong riêng thế giới của Greenspan thì năm nay cướp biển không giảm mà quả đất vẫn ấm lên.
Shakespeare và một triệu con khỉ
Định lý vô hạn các con khỉ đại khái nói rằng, cho thật nhiều các con khỉ gõ lung tung vào các bàn phím, thì với xác suất cực gần với 1, chúng sẽ gõ được Hamlet của Shakespeare. Ta có thể chứng minh điều này bằng lý thuyết xác suất không khó khăn gì.

Trong một hội nghị năm 1996, Robert Wilensky nói:

Chúng ta từng nghe bảo rằng một triệu con khỉ ngồi ở một triệu bàn phím có thể gõ toàn bộ các tuyệt tác của Shakespeare. Bây giờ, may nhờ có Internet, ta biết rằng điều này không đúng sự thật.

Con khỉ đang gõ bài này thấy rất nhột.

Các nhà nghiên cứu tại trường đại học Plymouth ở Anh đã thí nghiệm hồi năm 2003: bỏ một máy tính vào chuồng khỉ ở vườn thú Paignton ở Tây Nam nước Anh. Bọn khỉ lấy đá đập tán loạn vào máy tính; sau đó thì tiểu tiện, đại tiện vào bàn phím, cuối cùng mới gõ một đống chữ S, và vài chữ A, J, L, M, cho ra 5 trang sản phẩm. Mike Phillips, một trong số các nhà nghiên cứu này, nói: “rõ ràng tiếng Anh không phải tiếng mẹ đẻ của khỉ“.

Gạt đùa bỡn sang một bên. Định lý khỉ thật sự nói rằng, bất kỳ cái gì — nếu tồn tại — thì dù hiếm hoi đến mấy mà có đủ người tìm thì tìm vẫn ra. Thậm chí không cần một “chiến lược” tìm kiếm gì cả. Các con khỉ chỉ gõ loạn cào cào lên thôi. Bỏ một cây kim lên bãi cát. Một người vốc 10 nắm cát bất kỳ thì khả năng tìm ra kim trong đó là không tưởng. Nhưng nếu có một triệu người, mỗi người vốc 10 nắm cát bất kỳ, thì nhiều khả năng là tìm được kim. Khi độ hiếm hoi giảm xuống (đến không hiếm hoi) thì tổng số khỉ cần thiết sẽ giảm xuống. Nếu một nửa bãi cát có kim thì chỉ cần một gã vốc một nắm cát là đủ.

Nếu một gã nào đó trong một triệu gã tìm kim bãi cát ở trên mà tìm được kim thì không phải hắn có công năng đặc dị gì. Con khỉ gõ được Hamlet thì vẫn là con khỉ. Điểm này được Taleb lập đi lập lại trong hai quyển Fooled by Randomness và Black Swan. Chỉ cần sự ngẫu nhiên, một vài mutual funds sẽ có những thời điểm lời khủng khiếp, một vài cá nhân sẽ có những thành công vượt bực (Bill Miller của Legg Mason Capital Management chẳng hạn).

Những hội sấp ngửa “sống sót” trong vương quốc NN là hoàn toàn ngẫu nhiên, có thể chứng minh được bằng lý thuyết xác suất. Điểm này tương tự như công ty đoán giá xì tốc, inc trong bài điểm sách Thiên Nga Đen phần 1, và kiểu logical fallacy như bác Khoa đã viết trong bài điểm sách Halo Effect.
Khi những con giun đất hiển linh

đủ thứ lý thuyết lăng nhăng

thấy thích thú về bức ảnh … rồi thôi

Trong một mớ hỗn mang rộng lớn, bao giờ cũng có các góc nhỏ có một trật tự nào đó. Hiện tượng này xuất hiện rất nhiều trong phương pháp xác suất, theo nghĩa của Paul Erdos, khi ta chứng minh rằng trong một không gian mẫu đủ lớn thì các local patterns sẽ tồn tại. Nhìn mãi lên mây sẽ thấy một số đám mây trông giống con rồng, con chó, con … giun đất. Không hiểu tại sao đến bây giờ người ta không viết truyền thuyết về con giun đất hiển linh.

Trong mớ hỗn mang nhân quả của hiện tượng ấm toàn cầu, cái “trật tự” cướp biển giảm làm tăng nhiệt độ quả đất không dùng để kết luận ra cái gì được hết!

Vượt định kiến bằng Lăng Ba Vi Bộ
Hội viên hội xu ngửa đã có mô hình sai vì họ khái quát hóa từ một vài “mẫu” địa phương. Nhiều định kiến xuất phát từ cùng một lỗi như thế. Ai đó gặp vài anh Việt Kiều rồi kết luận Việt Kiều ở Mỹ làm nails đánh bài. Người khác gặp vài anh du học sinh rồi kết luận du học sinh Việt Nam ở bẩn và không biết xem bóng bầu dục. Thử tưởng tượng Rowling kết luận, sau 12 lần bị từ chối, rằng Harry Potter sẽ không bao giờ được nhận xuất bản.

Những đồng xu trong vương quốc NN được ném độc lập với nhau. Trong cuộc sống chúng ta thường gặp các đồng xu xâu lại với nhau thành chuỗi bằng một sợi dây vô hình nào đó. Người Bắc có nhiều bạn bè người Bắc, Người Nam có nhiều bạn bè người Nam, họ giúp nhau thắt chặt những định kiến vùng miền. Kết quả của đồng xu kế tiếp “correlate” chặt chẽ với đồng xu trước. Gia đình ba mẹ tin vào chiêm tinh học sẽ tiêm nhiễm cho con niềm tin này. Đồng xu của em bé vừa ra đời đã có mặt nặng mặt nhẹ.

Giả sử ta có một ly nước chanh, có đường ở dưới nhưng chưa khuấy lên, thì không thể nếm nước trên bề mặt (cho dù nếm cả ngụm) để kết luận là ly nước không có đường. Đầu tiên phải khuấy nó lên. Tiếc rằng, trên thực tế thì không thể “khuấy” Việt Kiều không làm nail và Việt Kiều làm nail rồi mới làm bạn ngẫu nhiên với họ. Nhưng điều có thể làm là nếm ly nước ở nhiều chỗ: bên phải một cái, dưới đáy một cái, bên trái một cái, v.v. Phương pháp này trong lý thuyết xác suất gọi là phương pháp Monte Carlo. Nhưng làm bạn với Việt Kiều Cali, New York, Chicago, Ithaca, v.v. một cách ngẫu nhiên như thế cũng rất khó vì giới hạn Vật Lý. Có thể phần nào giải quyết tình trạng này bằng Markov Chain Monte Carlo, gọi nôm na là Lăng Ba Vi Bộ.
Được làm vua, thua làm … chú thích
Một phần không nhỏ những gì diễn ra trong cuộc sống và xã hội là kết quả của sự ngẫu nhiên (NN). Trong một miền hỗn mang to lớn, nếu nhìn vào một góc nhỏ nào đó ta có thể tìm được một trật tự nhất định. Trật tự đó chẳng có ý nghĩa gì ghê gớm.

Không thể đánh giá con người hay sự vật/việc chỉ dùng kết quả thành bại được. Sẽ là một lỗi logic cơ bản nếu bài này kết luận rằng tất cả thành bại đều do ngẫu nhiên (vì các loại ví dụ kể trên chỉ là một số đồng tiền ngửa ủng hộ luận điểm này!!!). Dĩ nhiên tài năng có ảnh hưởng đến kết quả, nhưng con người có xu hướng đánh giá thấp vai trò của sự ngẫu nhiên.

Sẽ có ít định kiến hơn nếu chúng ta hiểu ý nghĩa của xác suất, không bước trên lối mòn định sẵn mà cần “Lăng Ba Vi Bộ” tìm Thiên Nga Đen.

Nếu thi thoảng có gặp nhiều xu sấp, thì không nên gia nhập hội xu sấp ngay. Đây là lý do tại sao những người kiên trì thường thành công, thiên tài có thể “tu luyện” được. Ngược lại, Einstein cảnh báo rằng: “định nghĩa của sự điên rồ là làm một thứ lập đi lập lại mà mong đợi kết quả khác nhau“.

Cuối cùng: thế nhỡ đâu tất cả những gì nhân loại chứng kiến/đo đạc được cho đến nay đều là xu ngửa thì sao? Nhỡ đâu ba định luật Newton và sự tiến hóa sinh vật cũng là xu ngửa. Đây là vấn đề qui nạp (induction) của David Hume, vượt quá khuôn khổ bài viết. Rất hy vọng có thể quay lại đề tài này trong một bài viết tới.

Chủ đề: Giới thiệu sách & Xác suất & thống kê | Bình luận (7) »

Busy busy busy

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

Năm nay hơi tham, ở trong nhiều TPC quá. (Hình như năm sau cũng vậy.) Đành khất các bạn nhiều câu hỏi chưa trả lời kịp.

Tôi đọc các bài báo tồi nhiều đến nỗi muốn bệnh luôn.

Cái môi trường “nghiên cứu” trong đa phần các đại học trên thế giới hiện nay tạo incentives cho nhiều nghiên cứu dỏm quá (kể cả của tôi). Phí thời gian của tất cả mọi người. Dù biết là cũng chỉ vì chén cơm nhưng vẫn chán!

Chủ đề: Chưa phân loại | Bình luận (2) »

Loại DoS Mới

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

Theo Tin

SEPTEMBER 30, 2008 | 2:45 PM — Things are a-brewin’ in Sweden. Sweden is not just home of the infamous bikini team, it is also the home of Outpost 24, an equally sexy software-as-a-service network scanning service, and the employer of my friend Robert E. Lee and his colleague Jack C. Louis. These guys are the inventors of UnicornScan, a user-land TCP stack turned into a port scanner. Never heard of it? Use Nmap exclusively? Well if you run Linux, I suggest checking it out, especially if missed ports in your portscan is inexcusable. But I digress.

Robert and Jack are smart dudes. I’ve known them for years, and they’ve always been one step ahead of the game. A couple of years ago, Jack found some anomalies in which machines would stop working in some very specific circumstances while being scanned. A few experiments, tons of reading through documentation, and one mysteriously named tool called “sockstress” later, and the two are now touting a nearly universal denial-of-service (DOS) attack that can be performed on almost any normal broadband Internet connection — in just a few seconds.

How bad is it? Well, in an interview — fast-forward five minutes in to hear it in English), the two were asked if they could take out a data center. While they’ve never tried, it appears to be a totally plausible attack. Worse yet, unlike most DOS attacks, the machines often do not come back online once the attack is over. The victim system just doesn’t respond any more. Great, huh?

…

Chủ đề: Bảo mật và mật mã học | Bình luận »

Trắng trợn

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

Trang a còng có phải thuộc báo Người Lao Động, “tiếng nói của liên đoàn lao động TPHCM” không nhỉ?

Ai đó đăng lại bài của tôi ở trang a còng, không hỏi han gì hết.

Đây không phải là lần đầu tiên và chắc không phải lần cuối cùng tôi … được đạo văn.

Chủ đề: Vui - Giải Trí | Bình luận (7) »

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

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

Hôm qua một phần bài giảng lớp randomized algorithms đẫn đến chứng minh đẳng thức sau đây:

$\sum_{j=1}^m j \binom{2m}{m+j} = m\binom{2m-1}{m-1}$

Có thể chứng minh đẳng thức này bằng cách viết lại vế trái thành

$\frac 1 2 \sum_{j=1}^m 2j \binom{2m}{m+j} = \frac 1 2 \sum_{j=1}^m \left( (m+j) \binom{2m}{m+j} - (m-j)\binom{2m}{m-j}\right)$

Sau đó, chú ý rằng $k\binom{n}{k} = n \binom{n-1}{k-1}$ , ta khai triển tiếp thành:

$m \sum_{j=1}^m \binom{2m-1}{m+j-1} - m \sum_{j=1}^{m-1} \binom{2m-1}{m-j-1} = m\binom{2m-1}{m-1}$

Đẳng thức cuối cùng có được là do $\binom{2m-1}{m+j-1} = \binom{2m-1}{m-j}$ . Có cách nào chứng mình đẳng thức đầu tiên nhanh gọn và trực quan hơn không?

Xét tập $S = \{1,\dots,2m\}$ . Vế phải $m\binom{2m-1}{m-1}$ đếm tổng số cách chọn một tập con gồm số từ , sao cho trong có một số thuộc $\{m+1,\dots,2m\}$ tô màu xanh và m-1 số còn lại tô màu đỏ. Một tập như vậy có thể được chọn bằng cách chọn một tập con kích thước $j\geq 1$ từ $\{m+1,\dots,2m\}$ trước, tô một phần tử màu xanh, phần còn lại đỏ, và chọn một tập con kích thước m-j từ $\{1,\dots,m\}$ . Như thế ta chứng minh được một đẳng thức … khác:

$\sum_{j=1}^m j\binom{m}{j} \binom{m}{m-j} = m\binom{2m-1}{m-1}$

Chuyện này khá thường xảy ra khi làm nghiên cứu và giảng dạy. Các “khám phá” nho nhỏ như vậy là các bài tập về nhà tốt. Đẳng thức trên, sau khi viết lại một chút, dễ thấy là trường hợp đặc biệt của đẳng thức Chu-Vandermonde mà ta đã đề cập trong phần 1 chuỗi bài này.

Hừm, quay lại với đẳng thức đầu tiên. Làm thế nào để “phiên dịch” vế trái? Trước hết, ta viết lại đẳng thức để vế phải có diễn dịch “sạch” hơn.

$\sum_{j=1}^m 2j \binom{2m}{m+j} = 2m\binom{2m-1}{m}$

Vế phải đếm tổng số tập hợp $T\subset S$ gồm m+1 phần tử trong đó có một phần tử được tô màu đỏ. Vế trái đếm tổng số các tấp hợp $R\subseteq S$ thỏa mãn: (a) $|R| \geq m+1$ , và (b) một trong số 2(|R|-m) phần tử lớn nhất của được tô màu đỏ.

Tôi tìm được một song ánh (bijection) từ bộ các tập vào bộ các tập , nhưng song ánh này hơi phức tạp. Cũng có thể dùng nguyên lý involution của Garcia-Milne, nhưng như vậy song ánh cũng không được trực tiếp.

Lạ thật, một đẳng thức đơn giản như vậy mà tôi không tìm được một song ánh đơn giản. Bạn có tìm được không?

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

Nhân ma trận, DFT, và lý thuyết biểu diễn nhóm (5)

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

Tiếp theo các bài trước, bài này nói về DFT trên các nhóm Abel. Ta đã biết rằng các phép biểu diễn tối giản trên một nhóm Abel bất kỳ đều là các phép biểu diễn 1 chiều. Tổng số các (isomorphism classes của) các phép biểu diễn một chiều này bằng với tổng số conjugacy classes của nhóm, nghĩa là bằng với tổng số phần tử trong nhóm vì đây là nhóm Abel.

Để cho dễ hiểu, hãy xét trường hợp đơn giản khi $G = \mathbb Z_n$ . (Nhớ rằng mỗi nhóm Abel hữu hạn đều isomorphic với tổng trực tiếp của một mớ cyclic groups dạng $\mathbb Z_m$ .) Trong trường hợp này, một hàm số $\chi: G \to \mathbb C$ là một character của nếu nó là một phép đồng cấu từ vào $\mathbb C^\times$ , nghĩa là nó thỏa mãn

$\chi(a+b) = \chi(a) + \chi(b), \ \forall a, b \in G = \mathbb Z_n$

Từ đó, dễ thấy rằng $\chi(0) = 1$ và $\chi(1)$ là một nth root of unity. Các giá trị khác thỏa $\chi(k) = (\chi(1))^k$ . Đặt $\omega = e^{2\pi i/n}$ . Với mỗi phần tử $a \in \mathbb Z_n$ , nếu ta đặt $\chi_a(1) = \omega^a$ thì tập hợp bộ $\chi_a$ này chính là tập hợp characters của . Viết ra cụ thể hơn:

$\chi_a = \begin{bmatrix} 1\\ \omega^a\\ \vdots \\ \omega^{(n-1)a} \end{bmatrix}, \ \ a = 0, 1, \dots, n-1$

Bộ các characters này một hệ cơ sở trực chuẩn của $\mathbb C^n$ nếu ta dùng inner-product

$\langle \chi, \chi' \rangle = \frac 1 n \sum_{b \in \mathbb Z_n} \chi(b)^* \chi'(b)$

Như đã nói sơ lược trong bài 2 về DFT, xét một hàm (nghĩa là vector) $\mathbf f: \mathbb Z_n \to \mathbb C$ bất kỳ; biểu diễn $\mathbf f$ dùng hệ cơ sở trực chuẩn trên:

$\mathbf f = \hat f_0 \chi_0 + \hat f_1 \chi_1 + \dots + \hat f_{n-1} \chi_{n-1}$

thì $\mathbf{\hat f} = DFT^{-1}(\mathbf f)$ . Đây chính là cái định nghĩa DFT thường thấy trong sách giáo khoa. Như vậy, DFT thường dùng trong xử lý tín hiệu số là một trường hợp đặc biệt của DFT trên nhóm $\mathbb Z_n$ .

Trường hợp một nhóm Abel bất kỳ thì như thế nào?

Một nhóm Abel bất kỳ đề có thể viết dưới dạng $G \cong \mathbb Z_{m_1} \oplus \cdots \mathbb \oplus Z_{m_k}$ . Hơn nữa, nếu $G \cong H_1 \oplus H_2$ và $\phi_1, \phi_2$ là hai characters của H_1, H_2 thì hàm $\chi: G \to \mathbb C$ định nghĩa bởi $\chi(h_1,h_2) = \phi_1(h_1)\phi_2(h_2)$ là một character của . Ngược lại, bất kỳ character nào của cũng có thể viết được dưới dạng “tích” của hai characters của H_1,H_2 . Tổng quát hơn, nếu $G \cong \mathbb Z_{m_1} \oplus \cdots \mathbb \oplus Z_{m_k}$ thì mọi character của đều là “tích” (nói đúng hơn là “tổng trực tiếp”) của các characters của $\mathbb Z_{m_i}, 1\leq i \leq k$ .

Nhờ đó, ta có thể viết cụ thể ra bộ characters của nhóm $G \cong \mathbb Z_{m_1} \oplus \cdots \mathbb \oplus Z_{m_k}$ như sau: mỗi character $\chi_{\mathbf a}$ sẽ được đánh chỉ số bởi một thành viên $\mathbf a \in \mathbb Z_{m_1} \times \cdots \mathbb \times Z_{m_k}$ . Nhớ rằng $\mathbf a$ là một vector. Character này được định nghĩa như sau:

$\chi_{\mathbf a}(\mathbf b) = \omega_{m_1}^{a_1b_1}\cdots \omega_{m_k}^{a_kb_k}$

Bộ characters này là một hệ cơ sở trực chuẩn của không gian $\mathbb C^{G}$ . Từ đó ta dễ dàng viết lại DFT của một hàm $\mathbf f: G \to \mathbb C$ bất kỳ, cùng với DFT nghịch đảo và các đẳng thức Parseval, Plancharel.

Chủ đề: Thuật Toán | Bình luận (6) »

Mars and Venus

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

The following story is fairly well-known.

This assignment was actually turned in by two English students:

Rebecca and Gary
English 44A
SMU
Creative Writing
Prof Miller
In-class Assignment for Wednesday

The Assignment: Today we will experiment with a new form called the tandem story. The process is simple. Each person will pair off with the person sitting to his or her immediate right. One of you will then write the first paragraph of a short story. The partner will read the first paragraph and then add another paragraph to the story. The first person will then add a third paragraph, and so on back and forth. Remember to reread what has been written each time in order to keep the story coherent. The story is over when both agree a conclusion has been reached.

The Submission:

At first, Laurie couldn’t decide which kind of tea she wanted. The camomile, which used to be her favorite for lazy evenings at home, now reminded her too much of Carl, who once said, in happier times, that he liked camomile. But she felt she must now, at all costs, keep her mind off Carl. His possessiveness was suffocating, and if she thought about him too much her asthma started acting up again. So camomile was out of the question.

Meanwhile, Advance Sergeant Carl Harris, leader of the attack squadron now in orbit over Skylon 4, had more important things to think about than the neuroses of an air-headed asthmatic bimbo named Laurie with whom he had spent one sweaty night over a year ago. “A.S. Harris to Geostation 17,” he said into his transgalactic communicator. “Polar orbit established. No sign of resistance so far…” But before he could sign off a bluish particle beam flashed out of nowhere and blasted a hole through his ship’s cargo bay. The jolt from the direct hit sent him flying out of his seat and across the cockpit.

He bumped his head and died almost immediately, but not before he felt one last pang of regret for psychically brutalizing the one woman who had ever had feelings for him. Soon afterwards, Earth stopped its pointless hostilities towards the peaceful farmers of Skylon 4. “Congress Passes Law Permanently Abolishing War and Space Travel.” Laurie read in her newspaper one morning. The news simultaneously excited her and bored her. She stared out the window, dreaming of her youth — when the days had passed unhurriedly and carefree, with no newspapers to read, no television to distract her from her sense of innocent wonder at all the beautiful things around her. “Why must one lose one’s innocence to become a woman?” she pondered wistfully.

Little did she know, but she has less than 10 seconds to live. Thousands of miles above the city, the Anu’udrian mothership launched the first of its lithium fusion missiles. The dim-witted wimpy peaceniks who pushed the Unilateral Aerospace Disarmament Treaty through Congress had left Earth a defenseless target for the hostile alien empires who were determined to destroy the human race. Within two hours after the passage of the treaty the Anu’udrian ships were on course for Earth, carrying enough firepower to pulverize the entire planet. With no one to stop them they swiftly initiated their diabolical plan. The lithium fusion missile entered the atmosphere unimpeded. The President, in his top- secret mobile submarine headquarters on the ocean floor off the coast of Guam, felt the inconceivably massive explosion which vaporized Laurie and 85 million other Americans. The President slammed his fist on the conference table. “We can’t allow this! I’m going to veto that treaty! Let’s blow’em out of the sky!”

This is absurd. I refuse to continue this mockery of literature. My writing partner is a violent, chauvinistic, semi-literate adolescent.

Yeah? Well, you’re a self-centered tedious neurotic whose attempts at writing are the literary equivalent of Valium.

You total $*&.

Stupid %&#$!.

Chủ đề: Vui - Giải Trí | Bình luận »

Thư học trò

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

Như mọi năm, đến gần thời gian mà các sinh viên chuẩn bị nộp đơn vào grad school tôi nhận được khá nhiều emails từ các prospective students từ nhiều nơi trên thế giới. (Nhiều nơi = TQ và Ấn.) Hôm nay mới nhận được một thư khá dài dòng, kể thành tích nghiên cứu MPLS, traffic engineering đủ loại, xong rồi kết luận, và tôi trích nguyên văn

I hope we can keep touching

Email còn gửi kèm ảnh, một chú … húi cua đeo kính cận.

Chủ đề: Dành cho du học sinh & Vui - Giải Trí | Bình luận (3) »

Tin Thở Dài

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

Thứ nhất, có qui định mới về hoạt động cứu trợ từ thiện ở VN

TT - Hình ảnh đoàn cứu trợ của các đơn vị, cơ quan báo chí, doanh nghiệp đến trực tiếp vùng thiên tai, hỏa hoạn, sự cố lớn giúp đỡ người dân bị nạn từ nay sẽ không còn. Trước nhiều ý kiến băn khoăn khác nhau về việc này, bà Hà Thị Liên - ủy viên ban thường trực Mặt trận Tổ quốc VN - giải thích:

- Tuần tới chúng tôi sẽ họp với các tổ chức liên quan về việc thành lập các ban cứu trợ, thảo luận việc triển khai nghị định 64 và thông tư 72 về công tác cứu trợ. Còn quỹ cứu trợ hiện có ở các cơ quan báo chí và các cơ quan khác sắp tới, theo tôi, nên chuyển hết về tài khoản của ban cứu trợ trung ương.

…

Xem toàn bài trên TTOnline

Thứ hai, một tin không liên quan

TT - Chiều muộn, Alejandra và Georg - đôi vợ chồng người Mexico - đi lượm rác dọc bờ biển Nha Trang. Họ đến đây du lịch và rất thích bãi biển tuyệt đẹp với làn nước trong xanh, song họ nói biển sẽ đẹp hơn nhiều nếu không có rác. Thế là vợ xách bao, chồng cặm cụi lượm từng que kem, túi nilông, hộp xốp… vương vãi trên bờ biển.

Cảm kích trước thiện chí của hai người bạn nước ngoài, chị Tú đi dạo gần đó dù đang mang thai khá lớn cũng vui vẻ nhập cuộc. Cả ba người cùng đi lượm đến lúc rác đầy bao mới thôi.

Chủ đề: Tin tức đó đây | Bình luận (3) »

Jason Lezak

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

Một cuộc đua tiếp sức 4×100 mét sải kỳ tuyệt! Đầy kịch tính, must-see TV. Xem phân tích kỹ thuật ở đây. Trong khoảng 20 mét cuối, Jason Lezak còn thua Alain Bernard nửa thân người, để rồi gần như bay trên mặt nước về đích trước đội Pháp 0.08 giây. Điều kỳ diệu là Jason đã 32 tuổi, và có đến 5 đội trong trận chung kết này phá kỷ lục thế giới cũ, và đội về nhất bơi nhanh hơn kỷ lục cũ gần 4 giây. (Trong những kỳ thi như thế này, 1 giây đã là infinity.)

Chủ đề: Tin tức đó đây | Bình luận (2) »

So sánh

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

Tìm cụm tử “Cuil vs Google” qua cuil
Tìm cụm từ “Cuil vs Google” qua google

Chủ đề: Vui - Giải Trí | Bình luận (1) »

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

Ngô Quang Hưng | 01 tháng 08, 2008 | 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) »

Trang sau »