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/

Conditional probability

Bạn đọc nên xem lại hai bài sau

[1] https://nttuan.org/2024/01/24/naive-definition-of-probability/

[2] https://nttuan.org/2024/06/02/probability-space/

—

Nhiều phát biểu về cơ hội có dạng: Nếu $B$ xảy ra thì xác suất để $A$ xảy ra là $p$ . Trong bài này ta sẽ quan tâm đến các phát biểu như vậy.

Ví dụ 1. Giả sử một lớp học có $n$ học sinh, trong đó có $n_1$ bạn giỏi toán và $n_2$ bạn nữ. Chọn ngẫu nhiên một học sinh trong lớp. Gọi $A$ là biến cố học sinh được chọn giỏi toán, và $B$ là biến cố học sinh được chọn là nữ. Khi đó theo định nghĩa ngây thơ của xác suất, $\mathbb{P}(A)=n_1/n$ và $\mathbb{P}(B)=n_2/n$ . Bây giờ ta tập trung vào nhóm các bạn học sinh nữ trong lớp. Xác suất để em được chọn trong nhóm này mà giỏi toán bằng $m/n_2$ , ở đây $m$ là số học sinh nữ trong lớp giỏi toán. Nếu kí hiệu $\mathbb{P}(A\mid B)$ là xác suất này, thì

$\displaystyle \mathbb{P}(A\mid B)=\frac{m}{n_2}=\frac{m/n}{n_2/n}=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}.$ $\Box$

Ta có định nghĩa hình thức sau

Định nghĩa 1. Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ và hai biến cố $\displaystyle A$ , $\displaystyle B$ với $\displaystyle \mathbb{P}(B)>0$ . Xác suất của $\displaystyle A$ biết $\displaystyle B$ đã xảy ra, cũng được gọi là xác suất của $\displaystyle A$ với điều kiện $\displaystyle B$ , kí hiệu $\displaystyle \mathbb{P}(A\mid B)$ , được định nghĩa bởi

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}.$

Chú ý rằng $\displaystyle\mathbb{P}(A\mid B)$ là xác suất của $\displaystyle A$ khi biết $\displaystyle B$ xảy ra, nó không phải là xác suất của biến cố $\displaystyle A\mid B$ , không có biến cố $\displaystyle A\mid B$ . Nếu $\displaystyle \mathbb{P}(A)>0$ thì $\displaystyle \mathbb{P}(A\mid A)=1$ .

Ví dụ 2. Xét phép thử ngẫu nhiên: Tung lần lượt hai con xúc xắc cân đối. Biết rằng con xúc xắc đầu hiện $\displaystyle 3$ chấm, xác suất để tổng số chấm lớn hơn $\displaystyle 6$ là bao nhiêu?

Lời giải. Không gian mẫu của phép thử là $\displaystyle \Omega=\{1,2,3,4,5,6\}^2$ . Như quy ước đối với không gian xác suất rời rạc, $\displaystyle \mathcal{F}$ là họ tất cả các tập con của $\displaystyle \Omega$ . Cuối cùng, $\displaystyle \mathbb{P}(A)=\mid A\mid / 36$ với mỗi $\displaystyle A \subset \Omega$ .

Bây giờ gọi $\displaystyle B$ là biến cố con đầu ra $\displaystyle 3$ chấm, và $\displaystyle A$ là biến cố tổng các chấm lớn hơn $\displaystyle 6$ . Khi đó

$\displaystyle B=\{(3, b): 1 \leq b \leq 6\}, \quad A=\{(a, b): a+b>6\},$ $\displaystyle \quad A \cap B=\{(3,4),(3,5),(3,6)\}.$ Suy ra

$\displaystyle \mathbb{P}(A \mid B)=\frac{\mathbb{P}(A \cap B)}{\mathbb{P}(B)}=\frac{|A \cap B|}{|B|}=\frac{3}{6}=\frac{1}{2}.$ $\Box$

Ví dụ 3. Rút ngẫu nhiên hai quân bài từ một bộ bài cho trước, mỗi lần rút một quân và không trả lại. Gọi $\displaystyle A$ là sự kiện quân bài thứ nhất mang chất cơ và $\displaystyle B$ là sự kiện quân bài thứ hai có màu đỏ. Tính $\displaystyle \mathbb{P}(A\mid B)$ và $\displaystyle \mathbb{P}(B\mid A)$ .

Lời giải. Không gian xác suất được xây dựng theo cách tự nhiên. Với không gian xác suất này, $\displaystyle \mathbb{P}(A)=1/4$ , $\displaystyle \mathbb{P}(B)=1/2$ , và $\displaystyle\mathbb{P}(A\cap B)=\frac{25}{204}.$ Từ đây ta thu được

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(A\cap B)}{\mathbb{P}(B)}=\frac{25}{102}\approx 0,25$

và

$\displaystyle\mathbb{P}(B\mid A)=\frac{\mathbb{P}(B\cap A)}{\mathbb{P}(A)}=\frac{25}{51}\approx 0,49.$ $\Box$

Từ định nghĩa của xác suất có điều kiện ta có

Định lý 1 (Công thức Bayes). Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ và hai biến cố $\displaystyle A$ , $\displaystyle B$ với $\displaystyle \mathbb{P}(A)\mathbb{P}(B)>0$ . Khi đó

$\displaystyle\mathbb{P}(A\mid B)=\frac{\mathbb{P}(B\mid A)\mathbb{P}(A)}{\mathbb{P}(B)}.$

Định lý 2 (Công thức xác suất toàn phần). Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ . Giả sử $\displaystyle A_1$ , $\displaystyle A_2$ , $\displaystyle \ldots$ , $\displaystyle A_n$ là một phân hoạch của $\displaystyle\Omega$ sao cho $\displaystyle \mathbb{P}(A_i)>0$ với mọi $\displaystyle i$ . Khi đó với mỗi biến cố $\displaystyle B$ ,

$\displaystyle\mathbb{P}(B)=\sum_{i=1}^n\mathbb{P}(B\mid A_i)\mathbb{P}(A_i).$

Công thức xác suất toàn phần cho một liên hệ giữa xác suất có điều kiện và xác suất không điều kiện. Để tính một xác suất, ta có thể dùng công thức này để chia bài toán thành các bài toán đơn giản hơn, và nó thường được sử dụng cùng với công thức Bayes.

Ví dụ 4. Có hai chiếc hộp, $\displaystyle \alpha$ và $\displaystyle \beta$ , đựng các viên bi xanh và đỏ. Hộp $\displaystyle \alpha$ chứa hai viên bi đỏ và ba viên bi xanh, hộp $\displaystyle \beta$ chứa ba viên bi đỏ và bốn viên bi xanh. Một viên bi được lấy ngẫu nhiên từ hộp $\displaystyle \alpha$ và bỏ vào hộp $\displaystyle \beta$ . Sau đó, lấy ngẫu nhiên một viên bi trong hộp $\displaystyle \beta$ và kiểm tra màu của nó. Xác suất để nó có màu xanh là bao nhiêu?

Lời giải. Không gian xác suất được mô tả theo cách tự nhiên. Gọi $\displaystyle A$ là biến cố viên bi lấy sau mang màu xanh, và $\displaystyle B$ là biến cố viên bi lấy trước mang màu xanh. Tính toán đơn giản ta được $\displaystyle \mathbb{P}(B)=3/5>0$ và $\displaystyle\mathbb{P}(\overline{B})=2/5>0$ , do đó theo công thức xác suất toàn phần, ta có

$\displaystyle\mathbb{P}(A)=\mathbb{P}(A\mid B)\mathbb{P}(B)+\mathbb{P}(A\mid \overline{B})\mathbb{P}(\overline{B}).$

Mà ta lại có $\displaystyle \mathbb{P}(A\mid B)=5/8$ và $\displaystyle \mathbb{P}(A\mid \overline{B})=1/2$ , suy ra $\displaystyle \mathbb{P}(A)=23/40= 0,575.$ $\Box$

Ví dụ 5. Có hai nhà máy sản xuất cốc, nhà máy I và nhà máy II. Biết rằng $\displaystyle 20\%$ số cốc từ nhà máy I và $\displaystyle 5\%$ từ nhà máy II bị lỗi. Mỗi tuần, I sản xuất số lượng cốc gấp đôi II. Xác suất để một chiếc cốc được chọn ngẫu nhiên trong một tuần sản xuất đạt yêu cầu là bao nhiêu? Nếu chiếc cốc được chọn bị lỗi thì khả năng nó được sản xuất bởi I là bao nhiêu?

Lời giải. Gọi $\displaystyle A$ là biến cố mà chiếc cốc được chọn là đạt yêu cầu, và gọi $\displaystyle B$ là biến cố nó được sản xuất tại $\displaystyle I$ . Khi đó

$\displaystyle\mathbb{P}(A)=\mathbb{P}(A\mid B)\mathbb{P}(B)+\mathbb{P}(A\mid \overline{B})\mathbb{P}(\overline{B})$

$=\frac{4}{5}\cdot\frac{2}{3}+\frac{19}{20}\cdot\frac{1}{3}=\frac{51}{60}\approx 0,85.$

Nếu chiếc cốc được chọn bị lỗi thì khả năng nó được sản xuất bởi I, theo công thức Bayes, là

$\displaystyle \mathbb{P}(B\mid \overline{A})=\frac{\mathbb{P}(\overline{A}\mid B)\mathbb{P}(B)}{\mathbb{P}(\overline{A})}=\frac{\frac{1}{5}\cdot \frac{2}{3}}{1-\frac{51}{60}}=\frac{8}{9}\approx 0,889.$ $\Box$

Ví dụ 6. Có một đồng xu công bằng và một đồng xu không công bằng với xác suất hiện mặt sấp khi tung là $\displaystyle 3/4$ . Chọn ngẫu nhiên một trong hai đồng xu và tung nó ba lần. Nó hiện mặt sấp cả ba lần. Tính xác suất để đồng xu được chọn là đồng xu công bằng.

Lời giải. Gọi $\displaystyle A$ là biến cố đồng xu được chọn đều hiện mặt sấp khi tung ba lần, và $\displaystyle B$ là biến cố đồng xu được chọn là đồng xu công bằng. Theo công thức Bayes và công thức xác suất toàn phần, ta có

$\displaystyle \mathbb{P}(B \mid A)=\frac{\mathbb{P}(A \mid B) \mathbb{P}(B)}{\mathbb{P}(A)}=\frac{\mathbb{P}(A \mid B) \mathbb{P}(B)}{\mathbb{P}(A \mid B) \mathbb{P}(B)+\mathbb{P}\left(A \mid \overline{B}\right) \mathbb{P}\left(\overline{B}\right)}$

$=\frac{(1 / 2)^3 \cdot 1 / 2}{(1 / 2)^3 \cdot 1 / 2+(3 / 4)^3 \cdot 1 / 2}\approx 0.23$ . $\Box$

Ví dụ 7. Xét một trò chơi trong đó một người chơi phải chọn một trong ba cánh cửa. Một trong ba cánh cửa giấu một giải thưởng có giá trị là một chiếc ô tô mới, trong khi mỗi một trong hai cánh cửa còn lại giấu một chiếc bút chì. Sau khi người chơi lựa chọn, người dẫn chương trình (biết xe ở đâu) sẽ mở một trong hai cánh cửa mà người chơi không chọn và cho biết phía sau cánh cửa đó có một cái bút chì. Vào thời điểm này, người chơi phải lựa chọn giữa hai cánh cửa còn lại. Người chơi nên giữ nguyên lựa chọn hay thay đổi?

Lời giải. Bởi vì còn hai cách cửa, một chứa ô tô và cánh còn lại chứa bút chì, nên nhiều người cho rằng chọn lại hay giữ nguyên thì khả năng là như nhau. Đây là câu trả lời sai.

Gọi $\displaystyle A_i$ là biến cố giải thưởng ô tô nằm sau cánh cửa $\displaystyle i$ . Giả sử người chơi đã chọn cánh cửa $\displaystyle 1$ . Gọi $\displaystyle B$ là sự kiện người dẫn chương trình mở ra cánh cửa số $\displaystyle 2$ có giải thưởng là cái bút chì. Theo định nghĩa của xác suất có điều kiện và công thức xác suất toàn phần,

$\displaystyle \mathbb{P}\left(A_1 \mid B\right)=\frac{\mathbb{P}\left(A_1 \cap B\right)}{\mathbb{P}(B)}=\frac{\mathbb{P}\left(B \mid A_1\right)\mathbb{P}\left(A_1\right)}{\mathbb{P}\left(B \mid A_1\right) \mathbb{P}\left(A_1\right)+\mathbb{P}\left(B \mid A_2\right) \mathbb{P}\left(A_2\right)+\mathbb{P}\left(B \mid A_3\right) \mathbb{P}\left(A_3\right)}.$

Bây giờ lập luận đơn giản cho ta $\displaystyle\mathbb{P}(A_i)=1/3$ với mọi $\displaystyle i$ , $\displaystyle \mathbb{P}\left(B \mid A_1\right)=1 / 2$ , $\displaystyle P\left(B \mid A_2\right)=0$ , và $\displaystyle \mathbb{P}\left(B \mid A_3\right)=1$ . Suy ra $\displaystyle \mathbb{P}\left(A_1 \mid B\right)=1/3\approx 0,333.$ Như vậy người chơi nên thay đổi lựa chọn của mình. $\Box$

Từ đầu cho đến thời điểm hiện tại ta đã thấy nhiều ví dụ mà $\displaystyle \mathbb{P}(A\mid B)\not=\mathbb{P}(B)$ , nghĩa là khi ta bổ sung thông tin $\displaystyle B$ thì khả năng xảy ra $\displaystyle A$ thay đổi. Nếu khi bổ sung $\displaystyle B$ mà khả năng xảy ra $\displaystyle A$ không thay đổi ta nói $\displaystyle A$ và $\displaystyle B$ là độc lập.

Định nghĩa 2. Cho một không gian xác suất $\displaystyle (\Omega,\mathcal{F},\mathbb{P})$ . Một họ các biến cố $\displaystyle \{A_i\}_{i\in I}$ được gọi là độc lập nếu với mỗi tập con hữu hạn $\displaystyle J$ của $\displaystyle I$ ,

$\displaystyle\mathbb{P}\left(\bigcap_{j\in J}A_j\right)=\prod_{j\in J}\mathbb{P}(A_j).$

Từ định nghĩa này ta thấy nếu $\displaystyle A$ và $\displaystyle B$ là hai sự kiện độc lập với $\displaystyle \mathbb{P}(A)\mathbb{P}(B)>0$ thì $\displaystyle \mathbb{P}(A\mid B)=\mathbb{P}(A)$ và $\displaystyle \mathbb{P}(B\mid A)=\mathbb{P}(B)$ .

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.

IMO 2024: Problems and results

Ngày thi thứ nhất (16/7/2024)

Bài 1. https://artofproblemsolving.com/community/c6h3358923

Tìm tất cả các số thực $\alpha$ sao cho với mỗi số nguyên dương $n$ , số

$[\alpha]+[2\alpha]+\cdots+[n\alpha]$

chia hết cho $n$ .

Bài 2. https://artofproblemsolving.com/community/c6h3358926

Tìm tất cả các cặp số nguyên dương $(a,b)$ sao cho tồn tại các số nguyên dương $g$ và $N$ thỏa mãn

$\gcd (a^n+b,b^n+a)=g$

với mọi số nguyên $n\geq N$ .

Bài 3. https://artofproblemsolving.com/community/c6h3358932

Cho dãy vô hạn các số nguyên dương $(a_n)_{n\geq 1}$ và số nguyên dương $N$ . Giả sử với mọi số nguyên $n>N$ , $a_n$ bằng số lần xuất hiện của $a_{n-1}$ trong dãy số $a_1$ , $a_2$ , $\ldots$ , $a_{n-1}$ . Chứng minh rằng một trong hai dãy số $(a_{2n-1})_{n\geq 1}$ và $(a_{2n})_{n\geq 1}$ là tuần hoàn kể từ lúc nào đó.

Ngày thi thứ hai (17/7/2024)

Bài 4. https://artofproblemsolving.com/community/c6h3359767

Cho $ABC$ là một tam giác với $AB < AC < BC$ . Gọi tâm đường tròn nội tiếp và đường tròn nội tiếp của tam giác $ABC$ lần lượt là $I$ và $\omega$ . Gọi $X$ là điểm trên đường thẳng $BC$ , khác $C$ , sao cho đường thẳng qua $X$ song song với $AC$ tiếp xúc với $\omega$ . Tương tự, gọi $Y$ là điểm trên đường thẳng $BC$ , khác $B$ , sao cho đường thẳng qua $Y$ song song với $AB$ tiếp xúc với $\omega$ . Đường thẳng $AI$ cắt lại đường tròn ngoại tiếp tam giác $ABC$ tại $P$ . Gọi $K$ và $L$ lần lượt là trung điểm của $AC$ và $AB$ . Chứng minh rằng $\angle KIL + \angle YPX = 180^{\circ}$ .

Bài 5. https://artofproblemsolving.com/community/c6h3359777

Ốc sên Turbo chơi trò chơi sau trên một bảng ô vuông cỡ $2024\times 2023$ . Trong $2022$ ô vuông con nào đó, có các con quỷ nấp ở đó. Ban đầu, Turbo không biết ô nào có quỷ, nhưng nó biết rằng trên mỗi hàng có đúng một con quỷ, trừ hàng đầu tiên và hàng cuối cùng, và trên mỗi cột có không quá một con quỷ.

Turbo thực hiện một dãy các phép thử để tìm cách đi từ hàng đầu đến hàng cuối của bảng. Tại mỗi lần thử, nó được quyền chọn một ô bất kỳ trên hàng đầu để xuất phát, sau đó liên tục di chuyển giữa các ô, mỗi bước từ một ô sang một ô có chung cạnh với ô mà nó đang đứng (nó được phép đến các ô đã từng đi qua). Nếu nó tới một ô có quỷ thì lần thử này dừng lại và nó được đưa trở lại hàng đầu để thực hiện một lần thử khác. Những con quỷ không di chuyển, và Turbo nhớ mỗi ô mà nó ghé qua có quỷ hay không. Nếu nó tới được một ô bất kỳ trên hàng cuối thì trò chơi kết thúc.

Xác định giá trị nhỏ nhất của $n$ sao cho Turbo luôn có chiến lược đảm bảo tới được hàng cuối cùng sau không quá $n$ lần thử, cho dù các con quỷ có nấp ở đâu.

Bài 6. https://artofproblemsolving.com/community/c6h3359771

Một hàm số $f:\mathbb{Q}\to\mathbb{Q}$ được gọi là đẹp nếu với mỗi số hữu tỷ $x$ và $y$ , $f(x+f(y))=f(x)+y$ hoặc $f(f(x)+y)=x+f(y)$ . Chứng minh rằng tồn tại số nguyên $c$ sao cho với mọi hàm số đẹp $f$ , có không quá $c$ số hữu tỷ có dạng $f(r)+f(-r)$ , với số hữu tỷ $r$ nào đó. Tìm giá trị nhỏ nhất của các số $c$ có tính chất này.