Chào mọi người. Mình là thành viên mới.
Cảm nhận của mình về những đề của kì thi này thì, có vẻ họ sẽ đánh giá thí sinh thông qua cách tiếp cận cũng như phạm vi hiểu biết về các kết quả liên quan đến bài toán, chứ không đặt thang điểm rồi chấm như thông thường. Vì với thời gian 1 tiếng như anh Bằng nói, mình nghĩ giải quyết triệt để 1 bài đã là khó chứ chưa nói đến việc trình bày.
Sau khi xem qua vài đề thì nhìn chung, một đề thi sẽ bao gồm tầm 3 đến 5 bài toán lớn, mỗi bài toán về một kết quả thuộc một môn học nào đó, tập trung vào đại số tuyến tính, giải tích (phần nhiều là về lí thuyết chứ không có bài tập tính toán), toán rời rạc, .v.v... Mỗi bài toán này sẽ được chia ra thành các bài con, thí sinh sẽ giải quyết các bài toán con gợi ý cho kết quả chính.
Sau đây là vài bình luận về đề 2016 anh Bằng đã đề xuất. Đề có ba bài toán lớn: một là giải tích, hai là toán rời rạc, ba là đại số tuyến tính và liên quan đến các vấn đề về ma trận ngẫu nhiên.
Bài 1
Phần 1 nhắc đến các vấn đề của giải tích thực liên quan đến chuỗi lũy thừa tương ứng của một chuỗi số. Phần này đưa ra tính chất nếu một chuỗi lũy thừa có bán kính hội tụ là 1 thì hội tụ đều trên [0,1), đồng thời cần thêm một điều kiện nào đó để có thể thác triển tính hội tụ đều lên đoạn [0,1], khi đó ta có thể ''lấy giới hạn từng thành phần của chuỗi'', cụ thể ở đây là cho $x \to 1^{-}$.
Phần 2 nói rằng mọi thứ sẽ rất sai nếu ta bỏ qua tính hội tụ đều khi lấy giới hạn từng thành phần . Ví dụ như sau: Lấy $a_n=(-1)^n$, và thu được một "đẳng thức" $1-1+1-1+\ldots = \dfrac{1}{2}$.
Phần 3, 4, 5 nêu ra một vài điều kiện đủ để việc lấy giới hạn trên vẫn đúng. Mình không thạo phần này nên xin phép bỏ qua.
Bài 2
Bài 2 chủ yếu nói đến điều kiện Hall và định lý Hall trong toán rời rạc. Định lý Hall phát biểu rằng đối với một đồ thị G hai phe hữu hạn (finite bipartite graph), thỏa mãn điều kiện Hall là một điều kiện cần và đủ để trên G tồn tại một ghép cặp hoàn hảo (perfect matching). Chú ý rằng điều kiện Hall có một phát biểu tương đương bằng ngôn ngữ tập hợp, tuy nhiên cá nhân mình thích phát biểu bằng ngôn ngữ đồ thị hơn vì nó tính trực quan hình học.
https://en.wikipedia...arriage_theorem
Ngoài ra, lí do họ phải gọi riêng điều kiện và định lý ra vì nói chung, định lý Hall không đúng cho trường hợp vô hạn.
Phần 1, 2 là phát biểu của định lý Hall. Trong link wiki trên có chứng minh của định lý, ngoài ra có thể tham khảo trong hầu hết các sách về lý thuyết đồ thị.
Phần 3, 4, 5 là các ứng dụng của định lý Hall trong các bài toán cụ thể. Mình nghĩ nếu có background tốt khi học toán olympic thời phổ thông thì sẽ có lợi thế trong phần này.
Bài 3
Đây là bài khó nhất của đề (chắc vì thế nên xếp cuối cùng). Mình sẽ trình bày cụ thể về bài này.
Bài toán trình bày một kết quả về xác suất để một đồ thị $n \times n$ có hệ số là $1$ hoặc $-1$ có định thức bằng $0$ (tức suy biến), cụ thể là nếu $n$ tiến ra vô cùng thì xác suất trên tiến về $0$.
Ta sử dụng luôn các kí hiệu trong bài.
Phần 1. Xét ma trận $M \cdot M^T$. Các kết quả quen thuộc chỉ ra đây là một ma trận đối xứng, nửa xác định dương. Như vậy, các giá trị riêng $\lambda_i$ của $M \cdot M^T$ đều không âm.
Nhận xét, do các hệ số của ma trận $M$ đều là $1$ hoặc $-1$ nên đường chéo chính của $M \cdot M^T$ sẽ gồm toàn số $n$. Chú ý các giá trị riêng có tổng là trace của ma trận và tích là định thức của ma trận
$\sum \lambda_i = n^2$ và $\prod \lambda_i = \det (M \cdot M^T)$
Từ đó
$\det(M)^2= \det(M \cdot M^T) = \prod \lambda_i \le \frac{1}{n^n}(\sum \lambda_i = n^2)^n = n^n$
Suy ra kết quả phần 1.
Phần 2.
Ta biểu diễn định thức bằng tổng của $n!$ thành phần, sau đó chú ý khai triển
$(\sum a_i)^2= \sum a^2_i + 2\sum_{i \neq j}a_ia_j$
Các $a_ia_j$ tương ứng của các $\det(M)^2$ (khi viết dưới dạng tổng $n!$ thành phần) khi lấy tổng (theo M) sẽ triệt tiêu nhau (do đổi dấu), để lại các $a^2_i$. Chú ý mỗi ma trận $M$, đại lượng này có tổng là $n!$, và do có $2^{n^2}$ ma trận $M$, nên có kết quả là $2^{n^2}n!$.
Phần 3.
Suy ra từ việc một ma trận suy biến thì các vector cột của nó sẽ phụ thuộc tuyến tính, tương đương với việc có một vector cột có thể biểu thị tuyến tính bởi các vector cột trước nó. Dấu $\le$ là do một ma trận có thể bị "đếm lặp" ở vế phải.
Phần 4.
Nếu viết lại số $2^{-(n-i+1)}$ bởi $\frac{2^{i-1}}{2^n}$ thì sẽ thấy ngay cách giải quyết. Ta đặt các vector cột $M_1,\ldots,M_{i-1}$ thành một ma trận $n \times (i-1)$. Theo một kết quả của đại số tuyến tính thì với một ma trận, hạng của các vector cột sẽ bằng hạng của vector hàng (và khi đó định nghĩa hạng của ma trận). Như vậy hạng của $n$ vector hàng của ma trận này sẽ không quá $i-1$.
Như vậy, một số vector hàng đầu tiên của ma trận trên là một hệ độc lập tuyến tính cực đại của tập các vector hàng, và do $M_i$ được biểu thị tuyến tính bởi các $M_1,\ldots,M_{i-1}$, nên các hệ số từ hàng $i$ trở xuống của $M_i$ sẽ phụ thuộc vào các hệ số từ hàng $1$ đến $i-1$. Cụ thể, nếu chọn trước các hệ số từ hàng $1$ đến $i-1$ của $M$, sẽ có không quá $1$ vector $M$ thỏa mãn.
Từ đó suy ra kết luận.
Phần 5.
Đây là định lý Sperner.
https://en.wikipedia...erner's_theorem
Có nhiều cách chứng minh của nó, hay gặp nhất là sử dụng bất đẳng thức Lubell-Yamamoto-Meshalkin đối với chain và antichain của một partially ordered set.
https://en.wikipedia...lkin_inequality
Ngoài ra, cá nhân mình khá thích chứng minh khác mình gặp ở thời phổ thông, vẫn còn giữ link, mọi người tham khảo.
http://real.mtak.hu/.../1/paper_91.pdf
Phần 6.
Xét $A = \{(\xi_1,\ldots,\xi_k) \in \{-1,1\}^k ~ | ~ \sum a_i\epsilon_i = 0 \}$ (là tập cho trong phần này).
Ta sẽ chứng minh $|A| \le \binom {k}{\lfloor\frac{k}{2}\rfloor}$ nhờ kết quả phần 5.
Có thể giả sử $a_i >0$. Đặt $S$ là tổng các $a_i$. Khi đó có một tương ứng 1-1 giữa các bộ $(\xi_i)$ thuộc $A$ và các tập con $I$ của $\{1,\ldots,k\}$ thỏa mãn $\sum_{i \in I} a_i = S/2$. Hai tập con $I$ như vậy sẽ không chứa nhau do các $a_i>0$, từ đó áp dụng phần 5 để suy ra đánh giá trên.
Sau đó sử dụng công thức xấp xỉ Stirling cho giai thừa để suy ra phần 6.
Chú ý ở đây với $k\le n$, ta thu được đánh giá $|A| \le 2^kk^{-1/2} \le 2^nn^{-1/2}$.
Phần 7.
Ước lượng các $\mathbb{P}(M_i \in V_i)$.
Thấy ngay đánh giá của phần 4 là chưa đủ, vì khi lấy tổng, thu được một đại lượng không đi về $0$. Chú ý đánh giá của phần 4 sẽ là tốt nếu i "không quá lớn". Các $i$ lớn mình sẽ sử dụng đánh giá ở phần 6 để xử lí.
Xét một vector $\alpha$ khác không thuộc phần bù trực giao của $V_i$, tức $\alpha$ trực giao với $M_1, \ldots, M_{i-1}$. Giả sử $\alpha$ có $k$ hệ số khác $0$ với $k>0$. Như vậy, $M$ sẽ phụ thuộc vào cách chọn các hệ số ở $k$ vị trí tương ứng với $k$ vị trí các hệ số khác $0$ của $\alpha$. Vậy
$\mathbb{P}(M_i \in V_i) \le \frac{2^nn^{-1/2}}{2^n} = n^{-1/2}$
Đánh giá này là tốt nếu số lượng $i$ ta sử dụng đánh giá này là đủ nhỏ.
Cụ thể, với $f(n)=\lfloor n^{1/4} \rfloor$
$\sum \mathbb{P}(M_i \in V_i) = \sum_{i=1}^{n-f(n)} + \sum_{n-f(n)+1}^{n} \le \sum_{i=1}^{n-f(n)} \frac{2^{i-1}}{2^n} + \sum_{n-f(n)+1}^{n} n^{-1/2} \le \frac{2^{n-f(n)}-1}{2^n} + f(n)n^{-1/2} \xrightarrow[]{~ n \to \infty~} 0$
Từ đó suy ra kết quả bài toán.
Nhận xét.
Mình không chắc chắn với giải của phần 7, trong lập luận có thể có thiếu sót.
Phần 1 https://en.wikipedia...rd's_inequality
Bài 3 https://math.stackex...x-is-invertible
Bài viết đã được chỉnh sửa nội dung bởi tvhoang: 22-01-2020 - 15:55