Vuhavan's Blog

Nostalgia

Tháng Năm 11, 2011

Ngẩn ngơ trên mạng, vớ được bài này

Ông A có IQ là 110, ông B có IQ là 90. Nhưng không phải lúc nào cũng đo ra được như thể. Như ta đã biết, các phép đo không bao giờ chính xác, mà phải có sai số. Ta giả sử là sai số là một biến ngẫu nhiên có kỳ vọng là 0 và phương sai là 400.

Bạn nhắm mắt chọn một trong hai ông A hay B rồi mời bác làm một IQ test (bạn không biết là bác nào đươc chọn). Kết quả là 115. Sau đó bạn cho bác đó (vẫn chưa biết là ai) làm lại một test nữa. Bạn nghĩ rằng bác sẽ được kết quả ra sao ?

Posted in Khác | 13 phản hồi »

Đố vui: Chọn bóng

Tháng Ba 1, 2011

Trong hộp có một ít bóng xanh và một bóng đỏ. Lan và Tuấn chơi trò chơi như sau. Mỗi người nhắm mắt thay nhau chọn ra một quả bóng. Ai lấy được quả bóng đỏ là thắng. Thắng được gì thì không biết.

Tuấn là một chàng vui tính đẹp trai galant, nhường ngay cho Lan chọn trước. Nhưng Lan kinh nghiêm có thừa, đề cao cảnh giác. Nàng lẩm bẩm “Trong cu cậu cũng bảnh bao hạp nhãn, kính trắng vằng vặc, nhưng mà cũng phải xét đã. Xem nào. Nếu lấy ngay được quả đỏ không nói làm gì. Nhưng nếu lấy phải quả xanh, thì khả năng sau đó anh chàng vơ được quả đỏ hiển nhiên tăng lên. Ha…đợi đấy”

Theo bạn thì khi nào Lan nên chấp nhận đề nghị của Tuấn.

Posted in Khác | 10 phản hồi »

Gee, good news….

Tháng Hai 16, 2011

http://bee.net.vn/channel/2981/201102/Vat-ly-co-hoc-cua-ta-di-truoc-thoi-dai-1789979/

Posted in Chuyen thuong ngay | 4 phản hồi »

Tản Mạn Avatar

Tháng Một 18, 2011

Toán không ra, ngồi xem (lại) Avatar.

Đúng là sản phẩm tiêu biểu cúa Holywood, hình ảnh hoành tráng, âm thanh chuẩn, diễn viên đẹp đuôi dài. Cái chủ đề hơi cũ một tý. Người cổ đại (tốt) chiến đấu chống người hiên đại (xấu) bảo vệ thiên nhiên.

Đành rằng bọn người hiện đại nhất định tham lam ăn nhiều, phá hoại môi trường. Nhưng cái trò cứ phải cũ tốt mới xấu, xem ra cũng khiên cưỡng. Trộm nghĩ, người xưa so ra phá hoại cũng chẳng kém, chỉ có điều có một dúm người nên tác động của nó không đáng kể.

Không ít kho tàng cố tích (của đủ mọi nước) thường có chuyện dũng sĩ đi vào rừng chặt một cái cây to nhất làm đồ sính lễ cưới công chúa—cưới được hay không thì còn tùy, nhưng cây cứ phải to. (Title hiện đại kiểu VNN “Ham con nhà giàu, đi làm lâm tặc”.) Một trường hợp cụ thể về phá họai có tính toán thuộc về anh Hẻrcules rất nổi tiếng (thợ săn kiêm vận động viên Olympic toàn năng.) Chàng một hôm nhận được một nhiêm vụ rất hóc là phải đi quét chuồng bò. Nói nghe đơn giản, nhưng đây là chuồng của một lão vua rất giàu, có đến hàng ngàn con bò, phân lưu cữu cả mười năm cao như thạch trận của KHổng Minh. Nghe nói con gái vua cá sấu, Hercules không thèm để ý nên lão càng ghét, bắt quét thật nhanh (không thì phải lấy người mình không yêu). Anh này bí quá, cuối cùng nảy ra một ý nghĩ thần kỳ là phá tường chuồng bò rồi tháo nước sông vào cho phân trôi hết ra sông. Hiển nhiên hành động này cần phải lên án hơn cả Vedan thái chất bẩn ra sông Thi Vải, nhưng thay vì ra tòa chẳng hiểu sao chàng Hercules lại được tính là lập một chiến công. Kể ra có bố làm to cũng sướng !

Posted in Giải trí | 8 phản hồi »

Lấy người mình yêu và định lý Birkoff

Tháng Mười Hai 4, 2010

Khi bé, bạn đi nhà trẻ. Lớn lên, bạn phải lấy vợ. Kiểu gì cũng không tránh được, trừ các vĩ nhân.

Chuyện lấy vợ ngày xưa rất đơn giản. Một ngày đẹp trời, bố khề khà nói với…mẹ “Tôi xem con Sứt con ông phó cối đầu ngõ chăm chỉ đáo để….” Thế là vài tháng sau bạn sẽ là chồng của cô Sứt, và ngày ngày đóng cối….

Chuyên bây giờ không đơn giản như thế nữa. Bạn có tự do, có quyền theo đuổi tình yêu, chắp cánh bay xa, vv. Phải lấy người mình yêu, chà !

Trớ trêu, người bạn yêu (như Angelina Jolie) thì vô số bạn khác cũng yêu. Thế mới cáu. Nhưng không sao, chuyện này các ông Tây cũng đã nghĩ tới, chẳng phải vì cô Angelina là Tây, mà ở bên Tây luật một vợ một chồng có sớm hơn ta, nên các bác ấy phải đi trước một bước, âu cũng là cực chẳng đã.

Các ông Tây giải quyết vấn đề như sau: Thay vì mỗi Angelina, mỗi ông lên một danh sách gồm các cô có thể đưa vào tầm ngắm. Danh sách này sẽ ngắn dài gầy béo tùy theo khả năng và sở thích mối người. Câu hỏi đặt ra là: Khi nào bạn có thể lấy được một
người trong danh sách của bạn mà không dẫn đến một cuộc đọ súng đọ kiếm hay đọ một cái gì với các bạn khác ?

Điều kiện cần của bài toán tương đối dễ xác định. Tưởng tượng cô Mít và cô Đào rất “hot”, và là ý trung nhân của các anh Mai, Thuổng và Xẻng. Thế là hai thục nữ nhưng những ba anh hùng, kiếu gì cũng không ổn. Nói tổng quát, nếu danh sách của $k$ chàng tổng cộng lại chỉ có $\le k-1$ nàng, thì thế nào cũng dẫn đến mâu thuẫn khó giải quyết. Vậy điều kiện cần của bài toán Lấy (một trong những) Người Mình Yêu là:

(1) Vơi mọi $k$ , danh sách của bât kỳ $k$ chàng trai nào tổng cộng lai phải có ít nhất $k$ cô gái.

Định lý Lấy Người Mình Yêu của Hall (Hall Marriage’s thẻoem) nói rằng đây cũng là điều kiện đủ.

Định lý Hall (1) là điều kiện đủ.

Đjinh lý này có thể phảt biểu dươi dạng đồ thị. Ta biểu diễn các chàng trai bằng chấm màu đỏ và các cô gái bằng chấm màu xanh. Đồ thị $G$ có các cạnh giữa chấm xanh và chấm đỏ, $A$ nối với $B$ nếu nàng $B$ ở trong danh sách của chàng $A$ . Một “perfect matching” là một tập các cạnh không dính nhau phủ hết các đỉnh đỏ.

Định lý Hall. $G$ có perfect matching khi và chỉ khi vơi mọi $k$ , với mọi tập đỏ $S$ với $k$ phần tử, số đỉnh xanh nối vởi $S$ ít nhất là $k$ .

Định lý Hall chứng minh không khó, bạn có thể thử dưới dạng bài tập. Trong phần còn lại của bài, ta sẽ dùng định lý Hall để chứng minh một trong những định lý quan trọng nhất trong đại số tuyến tính: định lý Birkoff. Để phát biếu định lý này, ta cần một khái niệm. Một ma trận $n \times n$ được gọi là doubly stochastic nếu các phần tử là số không âm và tổng mối hàng và mỗi cột là một. Nếu ta biếu diễn ma trận đưới dạng một điểm trong không gian $R^{n^2}$ thì các ma trận DS tạo thành một tập lồi; chính xác hơn, một đa diện lồi $S$ . Câu hỏi đặt ra là: tìm đỉnh của đa diện này. Câu hỏi này quan trọng, vì trong rất nhiều bài toán cực trị, giá trị cực trị được đạt được trên các đỉnh.

Birkoff tìm ra câu trả lời rất đẹp cho câu hỏi này. Một ma trận DS được gọi là “permutation matrix” nếu mỗi hàng và mỗi cột có chính xác một số một (còn lại là không). Bạn có thể dễ dàng thấy rằng mối PM tương đương với một phần tử $\sigma$ của nhóm giao hoán $S_n$ . Bạn cũng có thể dễ dàng chứng minh các PM là đỉnh của đa diện $S$ . Birkoff chứng minh rằng ngoài ra không còn đỉnh nào khác.

Định lý Birkoff. Tập PM là các đỉnh duy nhất của đa diện $S$ .

Giả sử $A$ là một ma trận với phần tử $a_{ij}$ . Với mỗi giao hoán $\sigma$ , ta gọi dãy $a_{1 \sigma (1)}, \dot, a_{n \sigma n}$ là một diagonal của $A$ . Bạn có thể dùng định lý Hall để chứng minh bổ đề sau

{ Bổ đề.} Nếu mỗi diagonal của $A$ có ít nhất một số $0$ thì $A$ có một $k \times l$ ma trận con với các phần tử đều bằng $0$ và $k+l > n$ .

Chứng minh định lý Birkoff. Giả sử $A$ là một điểm trong $S$ . Ta sẽ chứng minh $A$ có thể viết đưới dạng $\sum_{i=1}^m \lambda_i M_i$ , với $\sum_I \lambda_i=1, \lambda_i \ge 0$ và $M_i$ là PM. Ta qui nạp theo số phần tử dương của $A$ . Nếu $A$ có $n$ phần tử dương thì nó là một PM. Giả sử $A$ có $m \ge n+1$ phần tử dương. Bạn có thể dễ dàng kiểm tra là một ma trận DS không thể có một ma trận con như trong bổ đề (bài tập). Như vậy, ta có một diagonal gồm toàn số dương. Diagonal này gắn với một phép giao hoán $\sigma$ , và qua đó, một PM $P$ . Gọi $a$ là giá trị (dương) nhỏ nhất trong diagonal trên và $B: = \frac{A- aP}{1-a}.$

$B$ cũng là một DS matrix. Ngoài ra sồ phần tử dương của nó $\le m-1$ . Vậy $B$ có thể biểu diến dưới dạng $\sum_{i=1}^m \lambda_i M_i$ . Nhưng, $A = (1-a) B + aP$ . QED

Posted in Khác | 16 phản hồi »

Homework for combinatorics 1 (part 2)

Tháng Mười Hai 1, 2010

(1) Let $S$ be a set of at least $n+2$ points in $R^n$ . Prove that $S$ can be partitioned into two subsets whose convex hulls intersect.

(2) Let $C_1, \dots, C_m$ be convex sets in $R^n$ such that any $n+1$ of them intersect. Prove that all of them intersect.

(3) Let $p$ be a fixed prime. Construct a family of $\Omega (n^3)$ subsets of $\{1, \dots, n \}$ such that each has cardinality $p^3$ but any two has intersection
either 0, 1, $p$ or $p^2$ .

(4)* Let $F$ be a family of subsets of $\{1, \dots, n \}$ such that the intersection of any three is even. Prove that for all sufficiently large $n$ , $|F| \le 2^{n/2}$ .

(*) is a bonus problem, it does not count if you cannot do it, but if you can, I am willing to hear the solution.

Posted in Khác | 4 phản hồi »

Homework for Combinatorics 1

Tháng Mười Một 7, 2010

This is a homework from my Introductory course in Combinatorics at Rutgers. Some of the problems do not require any sophisticated tools, just an open mind. Enjoy !!

(1) Deduce Erdos-Ko-Rado theorem from Katona-Kruskal theorem.

(2) Prove that if $F$ and $G$ are two upsets, then $2^n |F \cap G| \ge |F||G|$ . (Recall that a upset is a collection of subsets of the group set such that if
$A \in F$ then $B \in F$ for any $A \subset B$.)

(3) Prove that in the random graph $G(2k, 1/2)$ (having $2k$ vertices and edge probability $1/2$ ), $P(maximum \,\,\, degree \le k-1) \ge 4^{-k}$ .

(4) Prove the 2-part Sperner theorem. If $X$ is partitioned into two non-empty sets $X_1$ and $X_2$ and $F$ is a family such that for any $A \subset B$ in $F$ , $A \backslash B$ is not in $X_1$ or in $X_2$ , then $|F| \le { n \choose \lfloor n/2 \rfloor }$ .

(5) Prove that $g_d (n,r) \le 2^{d-1} \lceil rd^{1/2} \rceil { n \choose \lfloor n/2 \rfloor }$ .

(6) Let $F$ be a upset. Prove that the average size of an element of $F$ is at least $n/2$ .

Posted in Khác | 9 phản hồi »

Lát sàn (Tiling)

Tháng Mười Một 4, 2010

A favorite topic of mine is linear algebra. It keeps surprising me with wonderful and useful facts. Among others, I found this gem recently:

Theorem. Let $R$ be a rectangular in the place with edge lengths $a$ and $b$ . It is clear that if $a/b$ is rational, then $R$ can be partitioned into edge parallel squares. Prove that the inverse also holds, namely that if $R$ can be partitioned into edge parallel (not necessarily equal)
squares, then $a/b$ is rational.

Sketch of proof. Assume that $R$ is partitioned into squares with sides $x_1, \dots, x_n$ in a particular way. Looking at the sides and the positions of
the squares, we can write up a system of linear equations, each of which has the form either $c_1x_1+ \dots+c_n x_n =a$ , or $c_1x_1+\dots + c_n x_n =b$
or $x_i=x_j$ . Collecting all these equations, we end up with $Ax= h$ , where $x=(x_1, \dots, x_n)$ , $A$ has integer entries, and the coordinates of $h$ are $a,b$ or $0$ .

Assume that there is a unique solution. Then each $x_i$ can be written as $\alpha_i a +\beta _i b$ , for some rational $\alpha_i, \beta_i$ (since $A$ has integer coefficients). Plugging these back to the original equations and subtracting $a$ or $b$ from the right hand side if necessary, we obtain equations of the form $p_j a + q_j b=0$ , where $p_j, q_j$ are linear combinations (with integer coefficients) of some $\alpha_i, \beta_i$ . If there is some $j$ such that $p_j, q_j \neq 0$ , then $a/b= -q_j/p_j$ is rational and we are done.

If $p_j=q_j=0$ for all $j$ , then this means that the given partition works for all $R$ , regardless the values of $a$ and $b$ . On the
other hand, by considering the areas, we have $\sum_{i=1}^n x_i^2 =ab$ . The right hand side can be rewritten as a quadratic form in
$a$ and $b$ as $(\sum_{i=1}^n \alpha_i^2)a^2 + (\sum_{i=1}^n \beta_i^2)b^2 + 2 \sum_{i=1}^n \alpha_i \beta_i ab$ . But it is
impossible that such a form equals $ab$ for all $a,b >0$ . A contradiction.

To conclude the proof, it suffices to show that there is a unique solution. We leave it as an exercise. For more about this theorem and other interesting results, I highly recommend
PROBLEMS AND THEOREMS IN LINEAR ALGEBRA by V. Prasolov.

Vuhavan's Blog

Nostalgia

Đố vui: Ai qui ai cao ?

Đố vui: Chọn bóng

Gee, good news….

Tản Mạn Avatar

Lấy người mình yêu và định lý Birkoff

Homework for combinatorics 1 (part 2)

Homework for Combinatorics 1

Lát sàn (Tiling)

Tinh thần phục vụ….

Trang

Lưu trữ

Chuyên mục

Blogroll

Meta

Follow “Vuhavan's Blog”