Graph theory: Basic definitions

Đây là bài thứ hai của tôi về lý thuyết đồ thị. Các bạn có thể xem bài trước ở

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

Với mỗi tập hợp $X,$ ký hiệu $[X]^2$ là tập gồm tất cả các tập con có $2$ phần tử của $X.$

Định nghĩa 1. Một đồ thị là một cặp $G=(V,E)$ các tập hợp sao cho $E\subset [V]^2.$

Như vậy, các phần tử của $E$ là các tập con có $2$ phần tử của $V.$ Các phần tử của $V$ được gọi là các đỉnh của đồ thị $G,$ các phần tử của $E$ được gọi là các cạnh của $G.$ Đồ thị có tập các đỉnh $V$ được gọi là đồ thị trên $V$ . Cách thông thường để vẽ một đồ thị là mỗi đỉnh biểu thị bởi một dấu chấm và nối hai trong các dấu chấm này bởi một đường cong nếu hai đỉnh tương ứng tạo thành một cạnh.

Trong hình trên ta có một đồ thị trên $V=\{1,2,\ldots,6\}$ với tập cạnh $E=\{\{1;2\},\{2;3\},\{6;5\},\{2;4\}\}.$ Khi vẽ một đồ thị ta không quan tâm các đỉnh hay cạnh được vẽ thế nào, điều quan trọng duy nhất ở đây là hai đỉnh nào được nối với nhau. Tập các đỉnh của một đồ thị $G$ được ký hiệu bởi $V(G),$ trong khi tập cạnh của nó được ký hiệu bởi $E(G).$ Ta thường không phân biệt đồ thị và tập cạnh hoặc tập đỉnh của nó. Chẳng hạn, ta có thể nói đỉnh $v$ thuộc $G$ (thay vì $v\in V(G)),$ một cạnh $e$ của $G,$ …

Số đỉnh của $G$ được gọi là cấp của nó, ký hiệu bởi $\mid G\mid$ . Một đồ thị $G$ được gọi là hữu hạn nếu $V(G)$ và $E(G)$ là hai tập hữu hạn, vô hạn nếu $V(G)$ hoặc $E(G)$ là một tập vô hạn. Trong bài giảng này ta chỉ xét các đồ thị hữu hạn. Khi $\mid G\mid =0$ ta gọi $G$ là đồ thị rỗng, ký hiệu $\emptyset.$ Nếu cấp của $G$ bằng $n$ thì ta cũng nói $G$ là đồ thị trên $n$ đỉnh.

Định nghĩa 2. Cho một đồ thị $G.$ Đỉnh $v$ của $G$ được gọi là đầu mút của một cạnh $e$ của $G$ nếu $v\in e.$ Nếu hai đầu mút của một cạnh $e$ là $x$ và $y$ thì ta nói $e$ nối $x$ và $y,$ hoặc $e$ kề với hai đỉnh $x$ và $y$ .

Một cạnh $\{x;y\}$ thường được viết là $xy$ hoặc $yx.$

Định nghĩa 3. Cho một đồ thị $G$ . Hai đỉnh $x$ và $y$ của $G$ được gọi là kề nhau nếu $\{x;y\}$ là một cạnh của $G.$ Trong trường hợp đó ta nói $x$ và $y$ là láng giềng của nhau.

Với mỗi đỉnh $x,$ tập gồm tất cả các đỉnh kề với $x$ được ký hiệu là $N(x)$ hoặc $N_G(x).$ Hai cạnh phân biệt $e$ và $f$ của $G$ được gọi là kề nhau nếu chúng có chung một đầu mút. Nếu tất cả các đỉnh của $G$ là đôi một kề nhau ta nói $G$ là một đồ thị đầy đủ. Một đồ thị đầy đủ trên $n$ đỉnh được ký hiệu bởi $K_n$ . $K_3$ được gọi là tam giác. Một cặp các đỉnh hay cạnh được gọi là độc lập nếu chúng không kề nhau.

Định nghĩa 4. Cho hai đồ thị $G=(V,E)$ và $G^{\prime}=(V^{\prime},E^{\prime}).$ Một ánh xạ $\varphi: V\to V^{\prime}$ được gọi đồng cấu từ $G$ đến $G^{\prime}$ nếu nó bảo toàn quan hệ kề giữa các đỉnh, nghĩa là $\varphi (x)$ và $\varphi (y)$ kề nhau mỗi khi $x$ và $y$ kề nhau. Nếu đồng cấu $\varphi$ từ $G$ đến $G^{\prime}$ là một song ánh và $\varphi^{-1}$ cũng là một đồng cấu, thì ta nói $\varphi$ là một đẳng cấu hoặc $G$ và $G^{\prime}$ là đẳng cấu.

Ta không phân biệt các đồ thị đẳng cấu, vì thế ta thường viết $G=G^{\prime}$ để chỉ $G$ và $G^{\prime}$ đẳng cấu. Trong một số trường hợp ta cũng nói $G^{\prime}$ là một bản sao của $G$ .

Continue reading →

IMO1986/3

The Pentagon Problem

Một bài viết rất công phu về IMO1986/3.

Trên mỗi đỉnh của một ngũ giác đều có viết một số nguyên, sao cho tổng của chúng là dương. Nếu ba đỉnh liên tiếp được viết lần lượt các số $x$ , $y$ , $z$ , với $y<0$ , thì phép toán sau được phép thực hiện: $x$ , $y$ , $z$ lần lượt được thay bởi $x+y$ , $-y$ , $z+y$ . Thao tác như vậy được thực hiện lặp đi lặp lại miễn là có ít nhất một trong năm số âm. Xác định xem quy trình này có nhất thiết phải kết thúc sau một số hữu hạn bước hay không.

IMO 2023: Problems and results

Bài viết này có hai phần: Phần thứ nhất là đề thi IMO 2023, phần thứ hai là kết qủa của kỳ thi.

Ngày thi thứ nhất, 8/7/2023

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

Tìm tất cả các hợp số $n$ có tính chất: nếu $d_1, d_2, \ldots, d_k$ là tất cả ước dương của $n$ với $1=d_1<d_2<\cdots<d_k=n$ , thì $d_i$ chia hết $d_{i+1}+d_{i+2}$ với mọi $1 \leqslant i \leqslant k-2$ .

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

Cho tam giác nhọn $ABC$ với $AB<AC$ . Gọi $S$ là điểm chính giữa của cung $BC$ chứa $A$ của $(ABC)$ . Đường thẳng qua $A$ vuông góc với $BC$ cắt $BS$ tại $D$ và cắt lại $(ABC)$ tại $E$ . Đường thẳng qua $D$ song song với $BC$ cắt $BE$ tại $L$ . $(BDL)$ cắt lại $(ABC)$ tại $P$ . Chứng minh rằng tiếp tuyến của $(BDL)$ tại $P$ cắt $BS$ trên phân giác của góc $BAC$ .

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

Với số nguyên $k>1,$ tìm tất cả các dãy vô hạn số nguyên dương $a_1,a_2,\ldots$ sao cho tồn tại đa thức $P$ với hệ số nguyên không âm có dạng $P(x)=x^k+c_{k-1}x^{k-1}+\cdots+c_1x+c_0$ để $P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}$ với mọi số nguyên dương $n.$

Ngày thi thứ hai, 9/7/2023

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

Cho $2023$ số thực dương $x_1,x_2,\ldots,x_{2023}$ đôi một khác nhau thỏa mãn

$\displaystyle a_n=\sqrt{\left(x_1+x_2+\cdots+x_n\right)\left(\frac{1}{x_1}+\frac{1}{x_2}+\cdots+\frac{1}{x_n}\right)}$

là số nguyên với mọi $n=1,2,\ldots,2023$ . Chứng minh rằng $a_{2023}\geq 3034$ .

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

Cho $n$ là một số nguyên dương. Một tam giác Nhật Bản gồm $1+2+\cdots+n$ hình tròn được xếp thành một hình tam giác đều sao cho với mỗi $i = 1, 2, ..., n$ , hàng thứ $i$ có đúng $i$ hình tròn và trên hàng đó có đúng một hình tròn được tô màu đỏ. Một đường đi ninja trong một tam giác Nhật Bản là một dãy gồm $n$ hình tròn nhận được bằng cách xuất phát từ hàng trên cùng, đi lần lượt từ một hình tròn xuống một trong hai hình tròn ngay dưới nó, và kết thúc tại hàng dưới cùng. Trong hình vẽ là một tam giác Nhật Bản với $n = 6$ và một đường đi ninja có chứa hai hình tròn màu đỏ.

Như một hàm số của $n$ , tìm giá trị lớn nhất của $k$ sao cho trong mỗi tam giác Nhật Bản luôn có một đường đi ninja chứa ít nhất $k$ hình tròn màu đỏ.

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

Cho $ABC$ là một tam giác đều. Gọi $A_1,B_1,C_1$ là các điểm nằm trong tam giác $ABC$ sao cho $BA_1=A_1C$ , $CB_1=B_1A$ , $AC_1=C_1B$ , và

$\angle BA_1C+\angle CB_1A+\angle AC_1B=480^\circ.$

Giả sử $BC_1$ và $CB_1$ cắt nhau tại $A_2,$ $CA_1$ và $AC_1$ cắt nhau tại $B_2$ , $AB_1$ và $BA_1$ cắt nhau tại $C_2.$ Chứng minh rằng nếu tam giác $A_1B_1C_1$ là tam giác không cân thì ba đường tròn ngoại tiếp các tam giác $AA_1A_2, BB_1B_2$ và $CC_1C_2$ đi qua hai điểm chung.

Dưới đây là kết quả của IMO 2023.

Continue reading →

International Mathematical Olympiad: Shortlisted Problems

Trong bài này chúng tôi sẽ dịch đề bài từ các bộ IMO Shortlist sang tiếng Việt.

Các bạn có thể tải các tài liệu khác ở https://nttuan.org/download/ .

IMO2014SL_Vie Download

IMO2015SL_Vie Download

Continue reading →

IMO2021/6

Trong bài này tôi giới thiệu hai lời giải cho bài 6 trong đề thi IMO 2021, lời giải thứ hai có dùng bổ đề Siegel mà tôi đã giới thiệu cách đây rất lâu ở đường dẫn https://nttuan.org/2007/10/21/siegel/. Các bạn có thể tìm các bài toán khác trong đề IMO 2021 ở đây https://nttuan.org/2021/07/25/imo2021/

Bài toán (IMO2021/6). Cho số nguyên $m\ge 2,$ $A$ là một tập hữu hạn các số nguyên và $B_1,$ $B_2,$ …, $B_m$ là các tập con của $A$ . Giả sử rằng với mỗi $k=1,2,...,m$ , tổng các phần tử của $B_k$ là $m^k$ . Chứng minh rằng $A$ có ít nhất $\frac{m}{2}$ phần tử.

Lời giải 1. Đặt $k=|A|$ và giả sử $A = \{a_1,a_2,\ldots,a_k\}$ . Từ giả thiết, với mỗi $i\in [m]$ , ta có $\displaystyle m^i = \sum_{j=1}^{k}b_{i,j}a_{j}\quad (1)$ với các $b_{i,j} \in \{0;1\}$ . Với mỗi $0 \le x \le m^{m}-1$ , biểu diễn $mx$ theo cơ số $m$ và kết hợp với $(1)$ ta được $\displaystyle mx = \sum_{j=1}^{k}c_{j}a_{j},$ trong đó các $c_j$ là số nguyên thỏa mãn $0 \le c_j \le (m-1)m,\quad\forall j\in [k]$ . Vế trái của đẳng thức này nhận đúng $m^{m}$ giá trị, do đó $\displaystyle m^{m} \le [m(m-1)+1]^{k} < m^{2k},$ suy ra $|A|=k>m/2$ . $\Box$