Tree

Một đồ thị không chứa chu trình được gọi là một rừng. Một rừng liên thông được gọi là một cây.

Ví dụ 1. Cho $G$ là một cây trên $n>1$ đỉnh. Chứng minh rằng $G$ có ít nhất hai lá, và nếu $v$ là một lá thì $G\setminus\{v\}$ là một cây.

Hướng dẫn. Trong các đường đi của $G$ , quan tâm đến một đường đi dài nhất. Chứng minh hai đầu của nó là lá. Chỉ ra $G\setminus\{v\}$ là một rừng liên thông. $\Box$

Định lý 1. Với một đồ thị $G$ , các khẳng định sau là tương đương:

(1) $G$ là một cây;

(2) Mỗi hai đỉnh của $G$ được nối với nhau bởi một đường đi duy nhất trong $G$ ;

(3) $G$ là đồ thị liên thông và với mỗi cạnh $e$ , đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ không phải là đồ thị liên thông;

(4) $G$ không chứa chu trình và với mỗi hai đỉnh không kề nhau $x$ và $y$ , đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình.

Chứng minh. Giả sử $G$ là một cây và $x$ , $y$ là hai đỉnh của $G$ . Vì $G$ là đồ thị liên thông nên có một đường đi nối $x$ và $y$ , ký hiệu là $\alpha$ . Nếu có một đường đi khác đường đi này nối $x$ và $y$ , ký hiệu là $\beta$ , gọi $z$ là đỉnh chung gần $x$ nhất của hai đường đi. Đường đi từ $x$ đến $z$ dọc theo $\alpha$ hợp với đường đi từ $z$ đến $x$ dọc theo $\beta$ tạo thành một chu trình, vô lý. Vậy ta đã chứng minh $(1)\Rightarrow (2)$ .

Xét một cạnh $e=xy$ của $G$ . Nếu đồ thị có được từ $G$ bằng cách bỏ đi cạnh $e$ là đồ thị liên thông, thì trong $G$ có một đường đi nối $x$ và $y$ mà không chứa $e$ . Đường đi này cùng với $e$ là hai đường đi nối $x$ và $y$ . Vậy ta đã chứng minh $(2)\Rightarrow (3)$ , vì nếu có $(2)$ thì đồ thị phải là đồ thị liên thông.

Bây giờ giả sử có $(3)$ . Trước tiên ta thấy $G$ không chứa chu trình, vì nếu không ta bỏ đi một cạnh của chu trình thì đồ thị mới vẫn liên thông, vô lý. Xét hai đỉnh không kề nhau $x$ và $y$ . Vì $G$ là đồ thị liên thông nên có đường đi nối $x$ và $y$ . Thêm cạnh $xy$ vào đường đi này ta có một chu trình trong đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ . Vậy ta có $(4)$ .

Cuối cùng, ta giả sử có $(4)$ . Xét hai đỉnh phân biệt $x$ và $y$ . Nếu $x$ và $y$ kề nhau thì có đường đi nối $x$ và $y$ , là $xy$ chẳng hạn. Nếu $x$ và $y$ không kề nhau thì đồ thị có được từ $G$ bằng cách thêm vào cạnh $xy$ chứa một chu trình. Vì $G$ không chứa chu trình nên chu trình này chứa $xy$ , bỏ $xy$ ra khỏi nó ta có đường đi trong $G$ nối $x$ và $y$ . Vậy ta có $(1)$ . $\Box$

Hệ quả. Một đồ thị liên thông trên $n$ đỉnh là một cây khi và chỉ khi nó có $n-1$ cạnh.

Chứng minh. Giả sử $G$ là một cây trên $n$ đỉnh. Vì $G$ là đồ thị liên thông nên theo định lý 1 trong [4], ta có thể đánh số các đỉnh của $G$ là $v_1$ , $v_2$ , $\ldots$ , $v_n$ sao cho $G_i:=G[v_1,v_2,\ldots,v_i]$ là đồ thị liên thông với mọi $i$ . Do $G$ là một cây nên mỗi $G_i$ là một cây. Giả sử $G_i$ có $i-1$ cạnh với mọi chỉ số $i<k$ ( $k$ là một số nguyên dương sao cho $k\leq n$ ). Vì $G_k$ là liên thông nên với mỗi $i<k$ , có đường đi trong $G_k$ nối $v_i$ và $v_k$ . Trong tất cả các đường đi như thế, xét đường đi ngắn nhất và giả sử nó nối $v_1$ và $v_k$ . Đường đi này phải có độ dài bằng $1$ , hay $v_k$ và $v_1$ kề nhau trong $G$ . Vì $G$ không có chu trình nên trong $G_{k-1}$ , chỉ có đúng một đỉnh kề với $v_k$ , suy ra $G_k$ có $k-2+1=k-1$ cạnh. Theo nguyên lý quy nạp toán học, $G=G_n$ có $n-1$ cạnh.

Ngược lại, giả sử $G$ là một đồ thị liên thông trên $n$ đỉnh và có $n-1$ cạnh. Gọi $T$ là một đồ thị con bao trùm liên thông cực tiểu của $G$ . Do tính cực tiểu, khi bỏ mỗi cạnh ra khỏi $T$ thì đồ thị thu được không liên thông, suy ra theo định lý 1 thì $T$ là một cây. Cây này có số cạnh bằng $n-1$ theo phần đầu của chứng minh, do đó $T=G$ . $\Box$

Trong một số vấn đề, việc xét một cây với gốc sẽ rất thuận tiện. Giả sử có một cây $T$ và một đỉnh cố định $r$ , gọi là gốc của cây. Với hai đỉnh $x$ và $y$ của $T$ , có đúng một đường đi nối $x$ và $y$ , ta ký hiệu nó là $xTy$ . Với $a,b\in T$ , ta viết $a\leq_T b$ (hoặc $a\leq b$ khi không sợ nhầm lẫn) nếu $a\in rTb$ . Ta thấy $\leq_T$ là một quan hệ thứ tự bộ phận trên $T$ , gọi là thứ tự cây. Khi $a<b$ ta nói $b$ nằm trên $a$ , hay $a$ nằm dưới $b$ . Theo quan hệ thứ tự này thì $r$ là phần tử nhỏ nhất của $T$ , mỗi lá là phần tử cực đại. Hai đầu mút của mỗi cạnh của $T$ là so sánh được.

Ví dụ 2. Cho số nguyên $n$ lớn hơn $1$ và một cây trên $n$ đỉnh. Các đỉnh của cây được viết các số thực $x_1$ , $x_2$ , $\ldots$ , $x_n$ . Mỗi cạnh của cây được viết tích của hai số được viết trên các đầu mút của cạnh, gọi $S$ là tổng tất cả các số này. Chứng minh rằng

$\displaystyle\sqrt{n-1}\left(x_1^2+x_2^2+\dots+x_n^2\right)\geq 2S.$

Lời giải. Giả sử tập các đỉnh của cây là $V=\{v_1, v_2, \ldots, v_n\}$ sao cho với mỗi $i$ , số được viết trên $v_i$ là $x_i$ . Với hai đỉnh kề nhau $v_i$ và $v_j$ , gọi $P(i,j)$ là tập các đỉnh của cây không nối được đến $v_i$ bởi một đường đi sau khi xóa khỏi cây cạnh $v_iv_j$ . Ta có ngay $1\leq \mid P(i,j)\mid \leq n-1$ mỗi khi $v_i$ và $v_j$ kề nhau.

Nhận xét 1. Nếu $v_i$ và $v_j$ kề nhau thì $\mid P(i,j)\mid +\mid P(j,i)\mid=n$ .

Chứng minh. Gọi $v$ là một đỉnh của cây, và xem nó là gốc. Ta có $v_i$ và $v_j$ là so sánh được theo thứ tự cây. Nếu $v_i<v_j$ thì $v\in P(j,i)$ , nếu $v_j<v_i$ thì $v\in P(i,j)$ , nhưng không thể có cả hai. Như vậy $V$ được phân hoạch thành $P(i,j)$ và $P(j,i)$ , từ đây ta có điều cần chứng minh. $\Box$

Nhận xét 2. Với mỗi $i$ ,

$\displaystyle \sum_{v_j\in N(v_i)}\mid P(i,j)\mid =n-1$ .

Chứng minh. Cố định một chỉ số $i$ . Do mỗi đỉnh đều nối đến $v_i$ bởi một đường đi duy nhất và cây không có chu trình nên các $P(i,j)$ với $v_j\in N(v_i)$ làm thành một phân hoạch của $V\setminus\{v_i\}$ , từ đây ta có điều cần chứng minh. $\Box$

Bây giờ với mỗi cạnh $v_iv_j$ , theo nhận xét 1 ta có

$\displaystyle \mid P(i,j)\mid .\mid P(j,i)\mid=\frac{n^2-(\mid P(i,j)\mid -\mid P(j,i)\mid)^2}{4}\geq n-1,$

suy ra

$\displaystyle\frac{\mid P(i,j)\mid}{\sqrt{n-1}}x_i^2+\frac{\mid P(j,i)\mid}{\sqrt{n-1}}x_j^2\geq 2\sqrt{\frac{\mid P(i,j)\mid .\mid P(j,i)\mid}{n-1}}|x_ix_j|\geq 2x_ix_j.$

Mỗi cạnh cho ta một bất đẳng thức có dạng như trên, cộng theo vế các bất đẳng thức này ta có bất đẳng thức trong đề bài. $\Box$

Tài liệu tham khảo

[1] https://nttuan.org/2009/08/13/graph01/

[2] https://nttuan.org/2023/09/01/graph02/

[3] https://nttuan.org/2024/06/04/graph03/

[4] https://nttuan.org/2024/07/01/connected-graph/

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

Vietnam Math Circle

Vietnam Math Circle là một chương trình phi lợi nhuận.

Mục tiêu của chương trình là giúp các em học sinh hiểu về bản chất của Toán học, học giỏi Toán, và ứng dụng các kiến thức Toán trong học tập và công việc hàng ngày. Cụ thể:

Chuẩn bị cho học sinh kiến thức và kĩ năng để tham gia các kỳ thi học sinh giỏi quốc gia và quốc tế.
Giới thiệu cho học sinh về một thế giới Toán học mở và giúp các em phát triển tiềm năng/khả năng của bản thân.
Giới thiệu cho học sinh về vẻ đẹp của Toán học thông qua các chủ đề cụ thể.
Giúp học sinh hiểu về các công việc liên quan đến Toán học và ứng dụng Toán học trong tương lai.

Chương trình bắt đầu nhận hồ sơ từ 06/02/2024. Hạn đăng ký là 31/03/2024.

Chúng tôi hi vọng đạt được những mục tiêu này thông qua:

Chương trình học được thiết kế và giảng dạy bởi các chuyên gia/nhà nghiên cứu/thầy cô có nhiều kinh nghiệm trong việc giảng dạy ở Việt Nam và nước ngoài.
Tạo ra một môi trường học tập vui vẻ, thân thiện, và giúp các em cảm thấy yêu thích mỗi khi được học tại Vietnam Math Circle.
Hình thức học tập bao gồm cả trực tiếp (với học sinh nội thành Hà Nội) và trực tuyến (với học sinh ngoại thành Hà Nội và các tỉnh thành khác).
Tổ chức kỳ thi đánh giá chất lượng giữa kỳ và cuối kỳ. Học sinh qua bài kiểm tra cuối kỳ sẽ được chuyển lên cấp học tiếp theo.
Những học sinh vượt khó, học giỏi trên các tỉnh thành sẽ được đăng ký xét Học bổng Vietnam Math Circle để tham gia chương trình học.
Các học sinh xuất sắc nhất của Vietnam Math Circle sẽ được tham gia trường hè với những bài giảng chuyên sâu từ các thầy trong Hội đồng chuyên môn.
Tổ chức kỳ thi học sinh giỏi Vietnam Math Circle hàng năm vào tháng 8.
Cung cấp cho học sinh những lời khuyên, định hướng học tập, cũng như những định hướng công việc trong tương lai.

Đây là một chương trình hấp dẫn. Các bạn có thể tìm hiểu thêm về chương trình này ở đường dẫn https://www.mathcircle.edu.vn/

Naive definition of probability

Phép thử ngẫu nhiên, hay phép thử, là một thí nghiệm hay một hành động mà kết quả của nó không thể biết được trước khi phép thử được thực hiện, và khả năng xảy ra của các kết quả là như nhau. Không gian mẫu của phép thử là tập hợp tất cả các kết quả có thể xảy ra khi thực hiện phép thử. Kết quả thuận lợi cho một biến cố (sự kiện) $\displaystyle E$ liên quan đến phép thử $\displaystyle T$ là kết quả của phép thử $\displaystyle T$ làm cho biến cố $\displaystyle E$ xảy ra. Trong bài này ta chỉ xét các phép thử mà không gian mẫu là một tập hợp hữu hạn.

Ví dụ 1. Tung một đồng xu, ta thấy có thể xảy ra một trong hai kết quả sấp ( $\displaystyle S$ ) hoặc ngửa ( $\displaystyle N$ ). Phép thử ngẫu nhiên ở đây là tung một đồng xu, không gian mẫu của phép thử là tập hợp $\displaystyle \Omega =\{S, N\}$ . Ta có thể để ý xem các biến cố sau có xảy ra không?

kết quả của phép thử là $\displaystyle N$ .

kết quả của phép thử không là $\displaystyle N$ .

kết quả của phép thử là $\displaystyle S$ hoặc $\displaystyle N$ .

kết quả của phép thử là $\displaystyle S$ và $\displaystyle N$ . $\Box$

Ví dụ 2. Xét phép thử ngẫu nhiên: tung một đồng xu bốn lần. Ta thấy một kết quả là $\displaystyle SNNS$ , và không gian mẫu của phép thử là tập hợp tất cả các dãy gồm $\displaystyle 4$ chữ cái thuộc $\displaystyle \{S,N\}$ . Chúng ta có thể mã hóa $\displaystyle S$ là $\displaystyle 1$ và $\displaystyle N$ là $\displaystyle 0$ , khi đó mỗi kết quả của phép thử là một dãy $\displaystyle (s_1,s_2,s_3,s_4)$ với các $\displaystyle s_j\in\{0;1\}$ và không gian mẫu của phép thử là tập tất cả các dãy như vậy.

Gọi $\displaystyle E_i$ là sự kiện lần tung thứ $\displaystyle i$ ra mặt ngửa. Tập các kết quả thuận lợi cho $\displaystyle E_1$ , cũng được ký hiệu bởi $\displaystyle E_1$ , là

$\displaystyle E_1=\{(0,s_2,s_3,s_4)\mid s_j\in \{0;1\},\quad\forall j\}.$ Đây là một tập con của không gian mẫu.

Nếu $\displaystyle A$ là biến cố ít nhất một mặt là ngửa thì tập các kết quả thuận lợi cho $\displaystyle A$ , cũng được ký hiệu bởi $\displaystyle A$ , là $\displaystyle A=E_1\cup E_2\cup E_3\cup E_4.$ Nếu $\displaystyle B$ là biến cố tất cả bốn lần tung đều hiện mặt ngửa thì tập các kết quả thuận lợi cho $\displaystyle B$ là $\displaystyle B=E_1\cap E_2\cap E_3\cap E_4.$ $\Box$

Ví dụ 3. Xét phép thử ngẫu nhiên: Chọn một quân bài từ $\displaystyle 52$ quân bài. Không gian mẫu $\displaystyle \Omega$ của phép thử là tập tất cả $\displaystyle 52$ quân bài. Ta quan tâm đến bốn biến cố sau:

$\displaystyle A$ : Quân bài là một con Át.

$\displaystyle B$ : Quân bài có màu đen.

$\displaystyle C$ : Quân bài có chất Rô.

$\displaystyle D$ : Quân bài có chất Cơ.

Như một tập hợp $\displaystyle D=$ {Át cơ, 2 cơ , 3 cơ,…, K cơ}. Ta có thể tạo ra nhiều biến cố từ bốn biến cố này.

$\displaystyle A\cap B$ là biến cố quân bài rút ra là quân Át màu đen.

$\displaystyle A\cup C$ là biến cố quân bài rút ra là quân Át hoặc có chất Rô.

$\displaystyle A\cup C\cup D$ là sự kiện quân bài rút ra là quân Át hoặc có màu đỏ. $\Box$

Định nghĩa (Định nghĩa ngây thơ của xác suất). Cho $\displaystyle A$ là một biến cố (sự kiện) của một phép thử ngẫu nhiên với không gian mẫu hữu hạn $\displaystyle \Omega$ . Khi đó xác suất của $\displaystyle A$ , hay xác suất xảy ra $\displaystyle A$ , là $\displaystyle \mathbb{P}(A)=\frac{\mid A\mid }{\mid \Omega\mid}.$

Theo định nghĩa thì $\displaystyle 0\leq \mathbb{P}(A)\leq 1$ , với mọi sự kiện $\displaystyle A$ . Dấu bằng trong bất đẳng thức thứ nhất xảy ra khi và chỉ khi $\displaystyle A=\emptyset$ , lúc này ta gọi $\displaystyle A$ là biến cố rỗng hay biến cố không thể. Dấu bằng trong bất đẳng thức thứ hai xảy ra khi và chỉ khi $\displaystyle A=\Omega$ , lúc này ta gọi $\displaystyle A$ là biến cố chắc chắn. Để tính xác suất của biến cố $\displaystyle A$ , ta cần tính số phần tử của không gian mẫu và số phần tử của $\displaystyle A$ (như một tập hợp).

Ví dụ 4. Tung hai con xúc xắc cân đối. Tính xác suất để tổng hai mặt bằng $\displaystyle 10$ .

Lời giải. Không gian mẫu $\displaystyle \Omega$ là tập tất cả các cặp $\displaystyle (a,b)$ với $\displaystyle a$ và $\displaystyle b$ thuộc $\displaystyle \{1,2,\ldots,6\}$ . Tập các kết quả thuận lợi cho biến cố tổng hai mặt bằng $\displaystyle 10$ là $\displaystyle \{(5,5),(6,4),(4,6)\}$ , suy ra xác suất cần tính bằng $\displaystyle 3/36=1/12\approx 0.0833$ . $\Box$

Ví dụ 5. Một ván bài $\displaystyle 5$ lá được chia từ một bộ bài $\displaystyle 52$ lá tiêu chuẩn, được xáo trộn kỹ lưỡng. Ván bài được gọi là cù lũ trong poker nếu nó bao gồm ba lá bài ở cấp độ nào đó và hai lá bài ở cấp độ khác, ví dụ: ba lá bài $\displaystyle 7$ và hai lá bài $\displaystyle 10$ (theo bất kỳ thứ tự nào). Xác suất để có một cù lũ bằng bao nhiêu?

Lời giải. Không gian mẫu là họ tất cả các tập con gồm $\displaystyle 5$ lá bài trong bộ bài đã cho. Ta có ngay $\displaystyle \mid \Omega \mid =C_{52}^5$ . Có $\displaystyle 13\times 12$ cách chọn lần lượt hạng của bộ ba và đôi trong một cù lũ. Sau đó, có $\displaystyle C_4^3\times C_4^2$ cách chọn lần lượt một bộ ba và một đôi trong các hạng đã chọn trước đó. Suy ra xác suất cần tính bằng $\displaystyle \frac{13\times 12\times C_4^3\times C_4^2}{C_{52}^5}=\frac{3744}{2598960}\approx 0.0014.$ $\Box$

Continue reading →