Bipartite graph

Một đồ thị $G$ được gọi là hai phần (hay lưỡng phân) nếu $V(G)$ có thể phân hoạch thành hai tập con $X$ và $Y$ , sao cho mỗi phần tử của $E(G)$ có một đầu mút trong $X$ và đầu mút còn lại trong $Y$ . Khi đó $X$ và $Y$ được gọi là các phần của đồ thị lưỡng phân. Ta ký hiệu đồ thị lưỡng phân với hai phần $X$ và $Y$ bởi $G[X,Y]$ . Nếu trong $G[X,Y]$ , mọi đỉnh thuộc $X$ được nối với mọi đỉnh của $Y$ thì $G[X,Y]$ được gọi là đồ thị lưỡng phân đầy đủ.

Ví dụ 1. Gọi $X$ và $Y$ lần lượt là tập các cầu thủ bóng đá và tập các câu lạc bộ trong một thành phố. Khi đó ta có đồ thị lưỡng phân $G[X,Y]$ , ở đây $x\in X$ được nối với $y\in Y$ khi và chỉ khi $x$ đã từng chơi cho $y$ .

Ví dụ 2 (Bài toán tối ưu trong đường sắt). Giả sử ta có một lịch trình các chuyến tàu cùng các điểm dừng của chúng, và cần tìm một tập hợp các ga tàu càng nhỏ càng tốt sao cho mọi chuyến tàu ghé thăm ít nhất một trong các ga đã chọn. Bài toán này có thể được mô hình hóa như một bài toán trên đồ thị lưỡng phân có các phần là tập các chuyến tàu và tập các ga tàu, mỗi chuyến tàu nối với ga mà nó sẽ dừng.

Bây giờ chúng tôi sẽ giới thiệu một số kết quả cơ bản về đồ thị hai phần.

Định lý 1. Cho đồ thị lưỡng phân $G[X,Y]$ không có đỉnh cô lập và thỏa mãn $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ). Khi đó $\mid X\mid \leq \mid Y\mid$ . Đẳng thức xảy ra khi và chỉ khi $\deg (x)= \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ).

Chứng minh. Vì $G$ không có đỉnh cô lập nên với mỗi $(x,y)\in X\times Y$ , ta có

$\displaystyle \sum_{y^{\prime}\in N(x)}\frac{1}{\deg (x)}=\sum_{x^{\prime}\in N(y)}\frac{1}{\deg (y)}=1.$

Suy ra

$\displaystyle \mid X\mid =\sum_{x\in X}\sum_{y\in N(x)}\frac{1}{\deg (x)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg x},$

và

$\displaystyle \mid Y\mid =\sum_{y\in Y}\sum_{x\in N(y)}\frac{1}{\deg (y)}=\sum_{\substack{(x,y)\in X\times Y\\ xy\in E(G)}}\frac{1}{\deg y}.$

Kết hợp với giả thiết $\deg (x)\geq \deg (y)$ với mọi $xy\in E(G)$ ( $x\in X$ và $y\in Y$ ) ta có những điều cần chứng minh. $\Box$

Định lý 2. Một đồ thị là lưỡng phân khi và chỉ khi nó không chứa chu trình độ dài lẻ.

Chứng minh. Nếu một đồ thị là lưỡng phân thì dọc theo một chu trình của nó, các đỉnh thuộc hai phần sẽ xuất hiện luân phiên. Vì thế, mỗi chu trình trong đồ thị lưỡng phân phải có độ dài là số chẵn. Bây giờ xét một đồ thị $G$ không chứa chu trình với độ dài là số lẻ. Ta chỉ cần xét tình huống $G$ là một đồ thị liên thông.

Gọi $T$ là một cây bao trùm trong $G$ (nó tồn tại theo [1]), và chọn một đỉnh $r$ làm gốc của cây này. Gọi $C$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn, và $L$ là tập tất cả các đỉnh mà đường đi trong $T$ nối $r$ với nó có độ dài chẵn. Khi đó $V(G)$ được phân hoạch thành hai phần $C$ và $L$ .

Ta sẽ chứng minh $G$ là đồ thị lưỡng phân với các phần là $L$ và $C$ . Xét hai đỉnh kề nhau $x$ và $y$ của $G$ . Nếu $xy\in T$ thì độ dài của $rTx$ và độ dài của $rTy$ khác tính chẵn-lẻ, do đó trong hai đỉnh $x$ , $y$ có một đỉnh thuộc $C$ và đỉnh còn lại thuộc $L$ . Nếu $xy\not \in T$ , từ giả thiết ta thấy chu trình $xTy\cup xy$ có độ dài chẵn. Theo phần chứng minh trước thì mỗi cạnh khác $xy$ thuộc chu trình này có các đầu mút thuộc hai phần khác nhau của phân hoạch, suy ra $x$ và $y$ thuộc hai phần khác nhau của phân hoạch. $\Box$

Tài liệu tham khảo

[1] https://nttuan.org/2024/08/02/tree/

Discrete random variables

Ta thường không quan tâm đến thí nghiệm mà chỉ quan tâm đến một số hệ quả từ thí nghiệm đó. Chẳng hạn, những tay cờ bạc chỉ quan tâm đến số tiền họ được hay mất, không quan tâm mấy đến trò chơi. Nhiều hệ quả từ thí nghiệm có thể được biểu diễn bằng một hàm trên không gian mẫu của thí nghiệm.

Định nghĩa 1. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ . Một biến ngẫu nhiên là một hàm $X:\Omega\to\mathbb{R}$ sao cho với mỗi $x\in\mathbb{R}$ , $\{\omega\in\Omega\mid X(\omega)\leq x\}\in\mathcal{F}.$

Một biến ngẫu nhiên được gọi là rời rạc nếu nó chỉ nhận giá trị trong một tập hợp đếm được.

Không khó khăn lắm để thấy rằng nếu $X$ và $Y$ là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc) thì $X+Y$ , $XY$ , và $\alpha X$ ( $\alpha\in\mathbb{R}$ ) cũng là các biến ngẫu nhiên (biến ngẫu nhiên rời rạc).

Định nghĩa 2. Cho một không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến ngẫu nhiên $X:\Omega\to\mathbb{R}$ . Hàm phân bố của biến ngẫu nhiên $X$ là hàm $F_X:\mathbb{R}\to [0;1]$ xác định bởi

$F_X(x)=\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\}),\quad\forall x\in\mathbb{R}.$

Để cho gọn, ta viết sự kiện $\{\omega\in\Omega\mid X(\omega)\leq x\}$ bởi $\{ X\leq x\}$ . Khi đó xác suất $\mathbb{P}(\{\omega\in\Omega\mid X(\omega)\leq x\})$ sẽ được viết là $\mathbb{P}( X\leq x)$ .

Ví dụ 1. Tung một đồng xu hai lần. Không gian mẫu của phép thử là $\Omega =\{NN,SS,SN,NS\}$ . Xét biến ngẫu nhiên $X$ , số mặt ngửa, xác định bởi

$X(NN)=2, X(SS)=0, X(SN)=1, X(NS)=1.$

Hàm phân bố của $F_X:\mathbb{R}\to [0;1]$ của $X$ xác định bởi

$F_X(x)=\begin{cases}0,\quad x<0\\ 1/4,\quad 0\leq x<1\\ 3/4,\quad 1\leq x<2\\ 1,\quad x\geq 2.\end{cases}$

Ví dụ 2. Xét không gian xác suất $(\Omega,\mathcal{F},\mathbb{P})$ và một biến cố $A$ . Hàm chỉ báo của $A$ là hàm $I_A: \Omega\to \mathbb{R}$ xác định bởi

$I_A(\omega)=\begin{cases}1,\quad \omega\in A\\ 0,\quad \omega\not\in A.\end{cases}$

Ta thấy $I_A$ là một biến ngẫu nhiên rời rạc với hàm phân bố $F:\mathbb{R}\to [0;1]$ xác định bởi

$F(x)=\begin{cases}0,\quad x<0\\ 1-\mathbb{P}(A),\quad 0\leq x<1\\ 1,\quad x\geq 1. \end{cases}$

Nếu $\{A_i\}_{i\in I}$ là một họ các biến cố đôi một rời nhau sao cho $\displaystyle A\subset \bigcup_{i\in I} A_i$ thì

$I_A(\omega)=\sum_{i\in I}I_{A\cap A_i}(\omega),\quad \forall \omega\in \Omega.$ $\Box$

Định lý 1. Hàm phân bố $F_X$ của biến ngẫu nhiên $X$ có các tính chất sau

(a) với mỗi số thực $x_1$ và $x_2$ , nếu $x_1<x_2$ thì $F_X(x_1)\leq F_X(x_2)$ .

(b) $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ và $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ .

(c) $F_X$ liên tục phải tại mọi điểm.

Chứng minh. Xét hai số thực $x_1$ và $x_2$ với $x_1<x_2$ . Biến cố $\{X\leq x_2\}$ là hợp của hai biến cố rời nhau $\{X\leq x_1\}$ và $\{x_1<X\leq x_2\}$ nên

$F_X(x_2)=\mathbb{P}(X\leq x_2)=\mathbb{P}(X\leq x_1)+\mathbb{P}(x_1<X\leq x_2)\geq \mathbb{P}(X\leq x_1)=F_X(x_1).$

Ta có $\{X\leq n\}_{n\geq 1}$ là một dãy tăng các sự kiện có hợp bằng $\Omega$ , theo định lý 1 trong [1], ta có

$1=\mathbb{P}(\Omega)=\mathbb{P}\left(\bigcup_{n=1}^{+\infty}\{X\leq n\}\right)=\lim_{n\to +\infty}\mathbb{P}(X\leq n),$

kết hợp với tính đơn điệu của $F_X$ ta được $\displaystyle \lim_{x\to +\infty}F_X(x)=1$ . Tính chất $\displaystyle \lim_{x\to -\infty}F_X(x)=0$ được chứng minh theo cách tương tự.

Bây giờ xét một số thực $x_0$ . Ta thấy $\{x_0<X\leq x_0+\frac{1}{n}\}_{n\geq 1}$ là một dãy giảm các sự kiện có giao bằng rỗng, theo định lý 2 trong [1], ta có

$0=\mathbb{P}\left(\bigcap_{n=1}^{+\infty}\left\{x_0<X\leq x_0+\frac{1}{n}\right\}\right)=\lim_{n\to +\infty}\left(F_X\left(x_0+\frac{1}{n}\right)-F_X(x_0)\right),$

kết hợp với tính đơn điệu của $F_X$ ta có $F_X$ liên tục phải tại $x_0$ . $\Box$

Continue reading →

IMO Shortlist 2022: Number theory

N1. Một số nguyên dương được gọi là số Na Uy nếu nó có ba ước dương phân biệt có tổng bằng $2022$ . Xác định số Na Uy nhỏ nhất.

N2. Tìm tất cả các số nguyên dương $n>2$ sao cho

$\displaystyle n! \mid \prod_{ p<q\le n,\quad p,q\in\mathbb{P}} (p+q).$

N3. Cho $a > 1$ là một số nguyên dương và $d > 1$ là một số nguyên dương nguyên tố cùng nhau với $a$ . Đặt $x_1=1$ và với $k\geq 1$ , $x_{k+1} = x_k + d$ nếu không chia hết $x_k$ , $=x_k/a$ nếu $a$ chia hết $x_k$ . Tìm, theo $a$ và $d$ , số nguyên dương $n$ lớn nhất mà tồn tại chỉ số $k$ sao cho $x_k$ chia hết cho $a^n$ .

N4. Tìm tất cả các bộ ba số nguyên dương $(a,b,p)$ sao cho $p$ là số nguyên tố và $a^p=b!+p.$

(IMO2022/5)

N5. Đối với mỗi $i\in [9]$ và $T\in\mathbb{N}^*$ , ký hiệu $d_i(T)$ là số lần chữ số $i$ xuất hiện khi tất cả các bội của $1829$ trong $[T]$ được viết ra theo cơ số $10$ . Chứng minh rằng có vô số $T\in\mathbb{N}^*$ sao cho có đúng hai giá trị phân biệt trong các số $d_1(T)$ , $d_2(T)$ , $\dots$ , $d_9(T)$ .

N6. Cho $Q$ là một tập hợp không nhất thiết hữu hạn các số nguyên tố. Đối với một số nguyên dương $n$ , xét phân tích ra thừa số nguyên tố của nó: gọi $p(n)$ là tổng của tất cả các số mũ và $q(n)$ là tổng của các số mũ tương ứng với các số nguyên tố trong $Q$ . Số nguyên dương $n$ được gọi là đặc biệt nếu $p(n)+p(n+1)$ và $q(n)+q(n+1)$ đều là số nguyên chẵn. Chứng minh rằng tồn tại một hằng số $c>0$ không phụ thuộc $Q$ sao cho với mọi số nguyên dương $N>100$ , số các số nguyên đặc biệt trong $[N]$ ít nhất là $cN$ .

N7. Gọi $k$ là một số nguyên dương và $S$ là một tập hữu hạn các số nguyên tố lẻ. Chứng minh rằng có nhiều nhất một cách (sai khác phép quay và đối xứng) để đặt các phần tử của $S$ xung quanh một đường tròn sao cho tích của hai số cạnh nhau bất kỳ có dạng $x^2+x+k$ với một số nguyên dương $x$ .

(IMO2022/3)

N8. Chứng minh rằng với mỗi số nguyên dương $n$ , số $5^n-3^n$ không chia hết cho số $2^n+65$ .

—

Các phần khác đã được đăng ở

Đại số: https://nttuan.org/2024/05/06/isl2022-algebra/

Hình học: https://nttuan.org/2023/09/08/isl2022-geometry/

Tổ hợp: https://nttuan.org/2023/09/29/isl2022-combinatorics/

Bản pdf của IMO SL từ 2014 đến 2021: https://nttuan.org/2023/07/02/isl/

Sau khi sửa một vài chỗ, bản pdf của IMO SL 2022 sẽ được đăng trong link trên.

Đề thi Olympic Toán nữ sinh Châu Âu 2024 (EGMO 2024)

Vào mùa thu năm 2009, trường Cao đẳng Murray Edwards, Cambridge đã tiếp cận Quỹ Toán học Vương quốc Anh với lời đề nghị làm điều gì đó để hỗ trợ việc trau dồi toán học cho các học sinh nữ. Một tình nguyện viên của UKMT (UK Maths Trust), Vicky Neale, đã gia nhập trường với tư cách là Giám đốc Nghiên cứu toán học vào đầu năm đó và trường đã tìm cách hỗ trợ các hoạt động của cô.

Đồng thời, UKMT đang lên kế hoạch cử một đội tham dự Olympic Toán nữ sinh Trung Quốc (CGMO) vào tháng 8 năm 2010.

Trong kỳ nghỉ Giáng sinh năm 2009, Geoff Smith đã có ý tưởng tổ chức một cuộc thi Olympic Toán học dành cho học sinh nữ châu Âu, có thể sử dụng trường Cao đẳng Murray Edwards làm địa điểm khai mạc. Mục đích là mang đến cho nhiều cô gái trải nghiệm tương tự như CGMO.

Vào ngày 29 tháng 12 năm 2009, Geoff đã chuyển ý tưởng của mình tới ủy ban Olympic Toán học Anh, ủy ban đã quyết định ủng hộ đề xuất này.

Tại IMO 2010 ở Kazakhstan, một cuộc họp sơ bộ đã được tổ chức để xác định liệu quốc tế có quan tâm đến việc tổ chức EGMO hay không. Không có gì ngạc nhiên khi một số quốc gia (nơi không có truyền thống giáo dục riêng cho nữ sinh) tỏ ra thận trọng khi tham gia, nhưng rõ ràng có đủ sự quan tâm để tiến hành sự kiện khai mạc.

Sự tham gia của Vương quốc Anh tại CGMO, đội do Ceri Fiddes và Alison Zhu phụ trách, đã thành công rực rỡ. Cả Ceri và Alison đều trở lại với quyết tâm tạo ra một sự kiện ở châu Âu. Ceri Fiddes sẽ trở thành Giám đốc Cuộc thi EGMO đầu tiên và Alison sẽ dẫn dắt đội Vương quốc Anh tại EGMO đầu tiên.

Thông báo công khai đầu tiên và ra mắt chính thức của EGMO được thực hiện vào ngày 8 tháng 3 năm 2011, nhân kỷ niệm 100 năm Ngày Quốc tế Phụ nữ.

Hỗ trợ tài chính đã được huy động từ nhiều nguồn khác nhau và nhóm của Ceri đã tham gia lập kế hoạch chi tiết cho EGMO 2012.

Tinh thần đã được nâng cao đáng kể vào tháng 5 năm 2011 khi Charles Leytem thông báo rằng Luxembourg sẽ đăng cai EGMO 2013.

Tương tự IMO, các học sinh sẽ thi trong 2 ngày, mỗi ngày làm 3 bài toán trong 4 tiếng rưỡi. Có thể thấy rằng nhiều bài toán trong đề thi EGMO không khó bằng các bài toán trong đề thi IMO.

egmo2024-day1 Download

egmo2024-day2 Download

Nguồn: https://www.egmo.org/

International Mathematics Tournament of the Towns, Spring 2024

Kỳ thi Toán quốc tế giữa các thành phố là một kỳ thi học sinh giỏi môn Toán có quy mô quốc tế được tổ chức lần đầu tiên tại Nga vào năm 1980. Cho đến nay, mỗi năm, kỳ thi được tổ chức tại hơn 100 thành phố ở hơn 25 quốc gia trên toàn thế giới. Điều đặc biệt của kỳ thi là học sinh được làm bài tại thành phố của mình, do đó giảm thiểu tối đa các chi phí phát sinh. Bài làm của các thí sinh sẽ được Ban tổ chức tại địa phương chấm và gửi kết quả về Ban tổ chức Trung ương tại Nga. Mỗi năm, có hơn 1000 thí sinh đạt tiêu chuẩn được cấp Bằng chứng nhận từ Viện Hàn lâm Khoa học Nga (Russian Academy of Sciences).

Nhằm thúc đẩy phong trào dạy và học Toán theo xu hướng hội nhập quốc tế, năm 2015, kỳ thi ITOT được tổ chức lần đầu tiên tại Việt Nam do Trung tâm Nghiên cứu và Ứng dụng Khoa học Giáo dục, Trường Đại học Giáo dục, Đại học Quốc gia Hà Nội làm đại diện chính thức của kỳ thi tại Việt Nam.

Từ năm 2024, Công ty TNHH Giáo dục VSO là đơn vị đại diện chính thức phối hợp với Viện Hàn lâm Khoa học Nga để tổ chức các kỳ thi ITOT tại Việt Nam. Kỳ thi được tổ chức hằng năm, mỗi năm hai vòng vào mùa thu (khoảng tháng mười) và mùa xuân (khoảng tháng ba). Học sinh có thể tham gia vào một trong hai hoặc cả hai vòng, tùy theo điều kiện địa phương.

1. Mục đích của kỳ thi

Kỳ thi Toán quốc tế giữa các thành phố giúp cho học sinh có cơ hội tham gia một kỳ thi chuẩn quốc tế. Mục đích chính của kỳ thi là góp phần nâng cao chất lượng dạy và học toán, đồng thời phát hiện và bồi dưỡng các học sinh có năng khiếu. Bên cạnh đó, kỳ thi còn cung cấp cho giáo viên và những người tổ chức địa phương một nguồn tài liệu chất lượng cao.

2. Cơ quan tổ chức:

Công ty TNHH Giáo dục VSO

Đơn vị triển khai: Vietnam Math Circle

3. Thời gian, địa điểm tổ chức kỳ thi ITOT45 mùa xuân

– Thời gian: Ngày thi cấp độ O: 23/03/2024

Ngày thi cấp độ A: 24/03/2024

– Địa điểm: Trường Tiểu học, THCS và THPT Thực nghiệm Khoa học Giáo dục, 50 P. Liễu Giai, Cống Vị, Ba Đình, Hà Nội

4. Đối tượng dự thi

– Cấp THCS: Học sinh khối lớp 7, 8 và 9;

– Cấp THPT: Học sinh khối lớp 10, 11 và 12.

5. Hình thức thi

Thí sinh thi tập trung tại điểm thi. Thông tin về các phòng thi và danh sách học sinh sẽ được ban tổ chức công bố trên website trước ngày 22/03/2024.

Nguồn: https://www.mathcircle.edu.vn/ITOTSpring2024