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 →

Vietnam TST 2023/6

Trong bài này tôi giới thiệu một lời giải của bài 6 trong đề thi chọn đội tuyển IMO 2023. Đây là lời giải của tác giả bài toán, không phải lời giải của tôi. Nếu có chỗ sai trong lời giải dưới đây thì đó là lỗi của tôi.

Với mỗi số nguyên dương $m$ , ký hiệu $[m]$ là tập gồm $m$ số nguyên dương đầu tiên.

Bài toán (Vietnam TST 2023/6). Cho số nguyên $n>2$ . Xác định số $k_n$ lớn nhất sao cho với mỗi họ $k_n$ tập con có $3$ phần tử của $[n]$ , luôn tô màu được các phần tử của $[n]$ bởi hai màu để không có tập con nào trong họ có ba phần tử cùng màu.

Lời giải. Với $n=3$ và $n=4$ thì $k_n=C_n^3$ , bởi vì ta có thể tô $2$ phần tử của $[n]$ xanh và $n-2 \leq 2$ phần tử còn lại màu đỏ và không có tập con ba phần tử cùng màu nào cả.

Với $n \geq 5$ thì $k_n \leq 9$ , bởi vì với $10$ tập con có $3$ phần tử của $[5]$ thì với mọi cách tô màu các phần tử $[5]$ bởi $2$ màu luôn có $3$ phần tử cùng màu. Với $n=5$ thì $k_5=9$ , vì với $9$ tập con $3$ phần tử tùy ý luôn có $1$ tập con $3$ phần tử không được chọn, ta có thể tô màu $3$ phần tử này màu xanh và $2$ phần tử còn lại màu đỏ, cách tô màu này thỏa mãn bài toán. Với $n=6$ , ta cũng có $k_6=9$ , vì ta có thể chia $20$ tập con $3$ phần tử của $[6]$ thành $10$ cặp, mỗi cặp là $2$ tập con bù nhau. Với $9$ tập con $3$ phần tử tùy ý của $[6]$ , luôn có $1$ cặp $(A, B)$ mà $A,$ $B$ không được chọn, ta tô $3$ phần tử của $A$ xanh, $3$ phần tử của $B$ đỏ và cách tô màu này thỏa mãn bài toán.

Mệnh đề 1. Với $n\geq 7$ thì $k_n \leq 6$ .

Chứng minh. Tồn tại $7$ tập con có $3$ phần tử của $[7]$ đôi một chung nhau không quá $1$ phần tử. Thật vậy, biểu diễn $1$ , $2, \ldots$ , $7$ là $7$ đỉnh một $7-$ giác đều. Chọn $B_1=\{1,2,4\}$ và $B_i$ là ảnh của $B_1$ quanh tâm đa giác với góc $\frac{2 \pi}{7} \times(i-1)$ . Rõ ràng các $B_i$ (như một tam giác) đôi một không có cạnh chung.

Giả sử tô màu được các phần tử của $[7]$ bởi $2$ màu sao cho không có $B_i$ nào có các phần tử cùng màu. Khi đó mỗi $B_i$ có đúng $2$ cạnh mà $2$ đỉnh của chúng khác màu. Suy ra ta có một đồ thị lưỡng phân $G[X,Y]$ , với $X$ là tập các phần tử xanh và $Y$ là tập các phần tử đỏ, có $14$ cạnh. Điều này không thể xảy ra vì $\mid X\mid +\mid Y\mid =7$ . $\Box$

Mệnh đề 2. Với $n \geq 5$ thì $k_n \geq 6$ .

Chứng minh. Ta chứng minh bằng qui nạp theo $n$ . Theo phần trình bày ở trên thì mệnh đề đúng với $n=5$ và $n=6$ . Với $n \geq 7$ , ta xét một họ gồm $6$ tập con có $3$ phần tử của $[n]$ . Tồn tại hai phần tử $a$ và $b$ của $[n]$ sao cho chúng không cùng thuộc một tập của họ này, vì $C_7^2=21>6 \times C_3^2=18$ . Bỏ $a$ , $b$ và thêm $c$ vào $[n]$ , ta có một cách tô màu thỏa mãn bài toán theo giả thiết quy nạp. Bỏ $c$ và cho lại $a, b$ về tập $[n]$ , sau đó tô màu $a$ và $b$ bởi màu của $c$ , ta có cách tô màu thỏa mãn bài toán. $\Box$

Từ mệnh đề 1 và mệnh đề 2, ta có $k_n=6$ khi $n \geq 7$ . $\Box$

IMO2022SL/G7: Euler line

Trong bài này chúng tôi sẽ giới thiệu một số lời giải của bài toán G7 trong cuốn IMO 2022: Shortlisted Problems.

IMO2022SL/G7. Hai tam giác $ABC, A^{\prime}B^{\prime}C^{\prime}$ có cùng trực tâm $H$ và cùng đường tròn ngoại tiếp có tâm $O$ . Gọi $PQR$ là tam giác tạo bởi $AA^{\prime}$ , $BB^{\prime}$ và $CC^{\prime}$ , chứng minh rằng tâm đường tròn ngoại tiếp của tam giác $PQR$ nằm trên $OH$ .

Erdos–Ginzburg–Ziv theorem

Định lí Erdos–Ginzburg–Ziv. Cho số nguyên dương $n.$ Khi đó trong mỗi $2n-1$ số nguyên, tồn tại $n$ số có tổng chia hết cho $n.$

Chứng minh. Trước tiên ta thấy khẳng định đúng với $n=1,$ và nếu khẳng định đúng với $x>1$ và $y>1$ thì nó cũng đúng với $xy.$ Thật vậy, giả sử $a_1,a_2,\ldots,a_{2xy-1}$ là các số nguyên bất kỳ. Trước tiên, vì $2xy-1>2y-1$ nên trong các số đã cho ta có thể chọn $y$ số $a_{1j}$ sao cho $\displaystyle a_{11}+a_{12}+\cdots +a_{1y}\equiv 0\pmod{y},$ sau bước này ta còn $2xy-1-y=(2x-1)y-1>2y-1$ số. Trong $(2x-1)y-1$ số đó ta chọn $y$ số $a_{2j}$ sao cho

$a_{21}+a_{22}+\cdots+a_{2y}\equiv 0\pmod{y},$ sau bước này ta còn $(2x-2)y-1$ số. Tiếp tục làm như vậy cuối cùng ta được $(2x-1)y$ số $a_{ij}$ thỏa mãn

$a_{i1}+a_{i2}+\cdots+a_{iy}\equiv 0\pmod{y},\quad \forall i=\overline{1,2x-1}.$ Vì khẳng định đúng với $n=x$ nên trong $2x-1$ số nguyên $\displaystyle\frac{1}{y}(a_{i1}+a_{i2}+\cdots+a_{iy}),$ tồn tại $x$ số, chẳng hạn $\displaystyle\frac{1}{y}(a_{i1}+a_{i2}+\cdots+a_{iy})$ với $i=1,$ $2,\ldots,$ $x$ , có tổng chia hết cho $x.$ Khi đó $xy$ số $a_{ij}$ với $(i,j)\in [x]\times [y]$ có tổng chia hết cho $xy,$ suy ra khẳng định đúng với $xy.$

Vậy ta chỉ cần chứng minh nó đúng với các số nguyên tố. Giả sử $n=p$ là một số nguyên tố và $a_0,$ $a_1,\ldots,$ $a_{2p-2}$ là các số nguyên bất kỳ. Ta cần chỉ ra có $p$ số trong các số đã cho có tổng chia hết cho $p.$ Với mỗi số nguyên $\alpha,$ ký hiệu $(\alpha)_p$ là số dư khi chia $\alpha$ cho $p.$ Không mất tính tổng quát, giả sử $\{(a_i)_p\}$ là một dãy không giảm. Nếu tồn tại $i\in [p-1]$ sao cho $(a_i)_p=(a_{i+p-1})_p$ thì

$(a_i)_p=(a_{i+1})_p=\cdots =(a_{i+p-1})_p\Rightarrow \sum_{j=i}^{i+p-1}a_j\equiv 0\pmod{p},$ nếu không, xét $p-1$ tập $A_i=\{a_i,a_{i+p-1}\}$ và dùng hệ quả trong [1] ta có