The degree of a vertex

Bài này là phần tiếp theo của bài https://nttuan.org/2023/09/01/graph02/

Cho đồ thị $\displaystyle G=(V,E).$ Bậc của một đỉnh $\displaystyle v\in G,$ ký hiệu $\displaystyle \deg_G(v)$ hoặc $\displaystyle \deg (v),$ là số đỉnh của $\displaystyle G$ kề với $\displaystyle v.$ Đỉnh có bậc bằng $\displaystyle 0$ được gọi là đỉnh cô lập. Đỉnh có bậc bằng $1$ được gọi là lá. Nếu mọi đỉnh của $\displaystyle G$ đều có bậc $\displaystyle k$ thì ta nói $\displaystyle G$ là $\displaystyle k-$ đều.

Định lý 1. Trong mỗi đồ thị có cấp lớn hơn $\displaystyle 1$ , tồn tại ít nhất hai đỉnh có cùng bậc.

Chứng minh. Gọi $\displaystyle n$ là cấp của đồ thị. Bậc của mỗi đỉnh của đồ thị là một số tự nhiên bé hơn $\displaystyle n$ . Vì vậy, nếu các đỉnh của đồ thị có bậc đôi một khác nhau thì có đỉnh cô lập và có đỉnh kề với mọi đỉnh khác, vô lý. $\Box$

Định lý 2. Với mỗi đồ thị $\displaystyle G=(V,E),$ ta có

$\displaystyle \displaystyle \sum_{v\in V}\deg (v)=2\mid E\mid.$

Chứng minh. Khi ta cộng tất cả bậc của các đỉnh, ta đã đếm mỗi cạnh đúng hai lần, một cho mỗi đầu mút của nó. $\Box$

Hệ quả. Số đỉnh bậc lẻ trong một đồ thị là số chẵn.

Ví dụ 1. Có đồ thị với dãy bậc của đỉnh như sau hay không?

(a) $\displaystyle 3,2,2,2.$

(b) $\displaystyle 3,3,2,2.$

Hướng dẫn. Ý đầu là không vì tổng bậc phải chẵn, ý thứ hai là có. Ý thứ ba là không, vì nếu có thì khi xét hai đỉnh bậc $\displaystyle 4,$ có ít nhất $\displaystyle 6$ cạnh đến các đỉnh bậc $\displaystyle 1,$ vô lý. $\Box$

Vào năm 1960, Paul Erdos và Tibor Gallai đã tìm được kết quả sau:

Định lý 3 (Erdos-Gallai). Dãy số nguyên không âm $\displaystyle d_1\geq d_2\geq\ldots \geq d_n$ là dãy bậc của một đồ thị trên $\displaystyle n$ đỉnh khi và chỉ khi $\displaystyle \sum d_i$ chẵn và

$\displaystyle \sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min\{d_i,k\},\quad \forall k=\overline{1,n}.$

Ví dụ 2. Cho một tập hợp $\displaystyle S$ gồm $\displaystyle 100$ điểm trong mặt phẳng sao cho khoảng cách giữa hai điểm bất kỳ trong $\displaystyle S$ không bé hơn $\displaystyle 1.$ Chứng minh rằng có không nhiều hơn $\displaystyle 300$ cặp điểm (không kể thứ tự) mà khoảng cách giữa hai điểm trong mỗi cặp bằng $\displaystyle 1.$

Hướng dẫn. Xét đồ thị $\displaystyle G$ trên $\displaystyle S$ được xác định như sau: Tập con $\displaystyle \{A,B\}$ của $\displaystyle S$ là một cạnh của $\displaystyle G$ khi và chỉ khi $\displaystyle AB=1.$ Vì $\displaystyle \deg (v)\leq 6$ với mọi $\displaystyle v\in S$ , nên $\displaystyle \mid E(G)\mid \leq 1/2\times 6\times 100=300$ . $\Box$

Ví dụ 3. Cho một lớp học có số học sinh là số chẵn. Chứng minh rằng tồn tại hai học sinh trong lớp có số người quen chung trong lớp là số chẵn.

Lời giải. Xét đồ thị $\displaystyle G$ trên tập hợp $\displaystyle V$ các học sinh trong lớp được xác định như sau: với hai đỉnh $\displaystyle a$ và $\displaystyle b$ của $\displaystyle G,$ có một cạnh nối $\displaystyle a$ và $\displaystyle b$ khi $\displaystyle a$ và $\displaystyle b$ quen nhau. Giả sử ngược lại rằng với mỗi $\displaystyle a$ và $\displaystyle b$ phân biệt thuộc $\displaystyle V,$ $\displaystyle \mid N(a)\cap N(b)\mid$ là số lẻ. Nói riêng, mỗi hai đỉnh có ít nhất một láng giềng chung.

Nhận xét. Mọi đỉnh của $\displaystyle G$ đều có bậc chẵn.

Chứng minh. Xét một đỉnh $\displaystyle x$ bất kỳ và xem $\displaystyle N(x)$ như đồ thị con cảm sinh của $\displaystyle G.$ Ta thấy $\displaystyle \sum_{y\in N(x)}\deg_{N(x)}(y)$ là số chẵn và mỗi số hạng là lẻ, suy ra $\mid N(x)\mid$ là số chẵn. $\Box$

Bây giờ cố định một đỉnh $\displaystyle x$ bất kỳ của $\displaystyle G.$ Đặt $\displaystyle X=V\setminus (N(x)\cup \{x\}).$ Khi đó $\displaystyle X$ có số phần tử lẻ. Ta quan tâm đến số $\displaystyle \alpha$ các cạnh có một đầu mút thuộc $\displaystyle X$ đầu mút kia thuộc $\displaystyle N(x)$ theo hai cách. Nếu chọn đầu mút thuộc $\displaystyle X$ trước thì ta thấy $\displaystyle \alpha$ là số lẻ, trong khi nếu chọn đầu mút thuộc $\displaystyle N(x)$ trước thì ta thấy $\displaystyle \alpha$ là số chẵn (theo nhận xét), vô lý. $\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$

IMO Shortlist 2022: Combinatorics

Trong bài này tôi sẽ dịch phần Tổ hợp trong cuốn IMO Shortlist 2022. Các năm trước bạn có thể tìm ở đường dẫn https://nttuan.org/2023/07/02/isl/.

Phần Hình của năm 2022 tôi đã dịch ở đây

IMO Shortlist 2022: Geometry

C1. Một $\pm 1$ -dãy là một dãy gồm $2022$ số $a_1, \ldots, a_{2022},$ mỗi số bằng $+1$ hoặc $-1$ . Tìm số $C$ lớn nhất sao cho, đối với bất kỳ dãy $\pm 1$ nào, tồn tại một số nguyên $k$ và các chỉ số $1 \le t_1 < \ldots < t_k \le 2022$ để $t_{i+1} - t_i \le 2$ với mọi $i$ , và $\displaystyle \left| \sum_{i=1}^{k} a_{t_i} \right| \ge C.$

C2. Ngân hàng Oslo phát hành hai loại tiền xu: nhôm (ký hiệu là $A$ ) và đồng (ký hiệu là $B$ ). Alpha có $n$ đồng xu nhôm và $n$ đồng xu đồng được sắp xếp thành một hàng theo thứ tự ban đầu tùy ý. Một chuỗi là bất kỳ dãy con nào các đồng xu liên tiếp có cùng loại. Cho một số nguyên dương cố định $k \leq 2n$ , Beta lặp đi lặp lại thao tác sau: anh ta xác định chuỗi dài nhất chứa đồng xu thứ $k$ từ bên trái và di chuyển tất cả đồng xu trong chuỗi đó sang đầu bên trái của hàng. Ví dụ: nếu $n=4$ và $k=4$ , quá trình bắt đầu từ $AABBBABA$ sẽ là

$AABBBABA \to BBBAAABA \to AAABBBBA \to BBBBAAAA \to ...$

Tìm tất cả các cặp $(n,k)$ với $1 \leq k \leq 2n$ sao cho với mỗi cách xếp các đồng xu lúc đầu, tại một thời điểm nào đó trong quá trình, $n$ đồng xu ngoài cùng bên trái có cùng loại.

C3. Trong mỗi ô vuông của một khu vườn có dạng bảng ô vuông cỡ $2022 \times 2022$ , ban đầu có một cái cây cao $0$ . Một người làm vườn và một thợ đốn gỗ thay phiên nhau chơi trò chơi sau, người làm vườn sẽ chơi ở lượt đầu tiên:

(1) Người làm vườn chọn một ô vuông trong vườn. Sau đó mỗi cây trên ô vuông đó và tất cả các ô vuông xung quanh trở thành cao hơn một đơn vị.

(2) Người thợ đốn gõ chọn bốn ô vuông khác nhau trong vườn. Sau đó mỗi cây có chiều cao dương trên các ô vuông đó sẽ trở thành thấp hơn một đơn vị.

Ta nói rằng một cái cây là hùng vĩ nếu chiều cao của nó ít nhất là $10^6$ . Tìm số $K$ lớn nhất sao cho người làm vườn có thể đảm bảo cuối cùng sẽ có $K$ cây hùng vĩ trong vườn, bất kể người thợ đốn gỗ chơi như thế nào.

C4. Cho một số nguyên $n > 3$ . Giả sử rằng $n$ đứa bé được sắp xếp thành một vòng tròn và $n$ đồng xu được phân phát cho chúng (một số bé có thể không có đồng xu nào). Ở mỗi bước, bé có ít nhất $2$ đồng xu có thể đưa $1$ đồng xu cho mỗi bé ngay bên phải và bên trái của mình. Hãy tìm tất cả các cách phân phát các đồng xu ban đầu sao cho sau một số hữu hạn bước, mỗi bé có đúng một đồng xu.

C5. Cho $m,n \geqslant 2$ là các số nguyên, $X$ là một tập hợp có $n$ phần tử, và $X_1$ , $X_2$ , $\ldots$ , $X_m$ là các tập hợp con khác rỗng phân biệt của $X$ . Một hàm $f \colon X \to \{1,2,\ldots,n+1\}$ được gọi là tốt nếu tồn tại một chỉ số $k$ sao cho $\displaystyle\sum_{x \in X_k} f(x )>\sum_{x \in X_i} f(x), \quad \forall i \ne k.$ Chứng minh rằng số hàm tốt ít nhất là $n^n$ .

C6. Cho $n$ là một số nguyên dương. Chúng ta bắt đầu với $n$ đống sỏi, mỗi đống ban đầu chỉ chứa một viên sỏi. Người ta có thể thực hiện các bước di chuyển theo hình thức sau: chọn hai đống, lấy một số viên sỏi bằng nhau từ mỗi đống và tạo thành một đống mới từ những viên sỏi này. Tìm, theo $n$ , số nhỏ nhất các đống sỏi khác rỗng mà một người có thể thu được bằng cách thực hiện một dãy hữu hạn các bước di chuyển có dạng này.

C7. Lucy bắt đầu bằng cách viết $s$ bộ $2022$ số nguyên lên bảng đen. Sau khi làm điều đó, cô ấy có thể lấy hai bộ bất kỳ (không nhất thiết phải khác nhau) $\mathbf{v}=(v_1,\ldots,v_{2022})$ và $\mathbf{w}=(w_1,\ldots,w_{ 2022})$ mà cô ấy đã viết và áp dụng một trong các thao tác sau để lấy bộ mới:

$\mathbf{v}+\mathbf{w}=(v_1+w_1,\ldots,v_{2022}+w_{2022})$

$\mathbf{v} \lor \mathbf{w}=(\max(v_1,w_1),\ldots,\max(v_{2022},w_{2022}))$

rồi viết bộ này lên bảng. Sau hữu hạn bước, theo cách này, Lucy có thể viết bất kỳ bộ $2022$ số nguyên nào lên bảng. Số $s$ nhỏ nhất có thể là bao nhiêu?

C8. Cho $n$ là một số nguyên dương. Hình vuông Bắc Âu là một bảng ô vuông $n \times n$ chứa tất cả các số nguyên từ $1$ đến $n^2$ sao cho mỗi ô chứa đúng một số. Hai ô khác nhau được gọi là kề nếu chúng có chung một cạnh. Mỗi ô chỉ kề với các ô chứa số lớn hơn được gọi là thung lũng. Đường lên dốc là một dãy gồm một hoặc nhiều ô sao cho các điều kiện sau được thỏa mãn đồng thời:

(i) ô đầu tiên trong dãy là một thung lũng,

(ii) mỗi ô tiếp theo trong dãy kề với ô trước đó,

(iii) các số trên các ô trong dãy lập thành một dãy tăng theo thứ tự.

Tìm, theo $n$ , số nhỏ nhất đường lên dốc có thể có trong một hình vuông Bắc Âu.

C9. Xét các song ánh $f:\mathbb N\times \mathbb N \to \mathbb N$ có tính chất: mỗi khi $f(x_1,y_1) > f(x_2, y_2)$ , thì $f(x_1+1, y_1) > f(x_2 + 1, y_2)$ và $f(x_1, y_1+1) > f(x_2, y_2+1)$ . Gọi $k$ là số cặp số nguyên $(x,y)$ sao cho $0\le x,y<100$ và $f(x,y)$ is số nguyên lẻ. Tìm giá trị lớn nhất và giá trị nhỏ nhất của $k$ .

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$ .