Bài tập 6, § 2

Cho $c$ là một số tự nhiên.

a) Tồn tại duy nhất một họ các ánh xạ $R_c: (\mathbf{N}^*)^c\rightarrow \mathbf{N}^*$, với $c\geqslant 2$, thỏa mãn các tính chất sau:

(i) Nếu tồn tại $i$ sao cho $n_i= 1$, thì $R_c(n_1, . . . , n_c) = 1$ ;

(ii) Ta có $R_2(m, n) = R_2(m-1, n) + R_2(m, n-1)$ nếu $m$ và $n$ là các số nguyên $\geqslant 2$ ;

(iii) Nếu $c\geqslant 3$, ta có $R_c(n_1, . . . , n_c) = R_{c-1}(n_1, . . . , n_{c-2},R_2(n_{c-1}, n_c))$ với mọi $(n_1, . . . , n_c)\in \mathbf{N}^c$.

b) Ta có $R_2(m, n) =(^{m+n-2}_{m-1})$ với mọi cặp $(m, n)$ các số nguyên $\geqslant 1$.

c) Với mọi dãy hữu hạn $(n_1, . . . , n_c)$ các số tự nhiên $\geqslant 1$ và mọi số tự nhiên $R\geqslant 1$, ta nói rằng tính chất $\mathbf{R}(n_1, . . . , n_c; R)$ được thỏa mãn nếu, với mọi đồ thị đầy đủ có tập hợp các đỉnh S có lực lượng $\geqslant R$ và mọi phân hoạch $P = (F_1, . . . ,F_c)$ của tập hợp F các mũi tên của nó, tồn tại một số nguyên $i\in \{1, . . . , c\}$ và một tập con A của S có lực lượng $n_i$ sao cho mọi mũi tên của G nối hai phần tử của A đều thuộc về $F_i$.

Chứng minh tính chất $\mathbf{R}(n_1, . . . , n_c; R_c(n_1, . . . , n_c))$.

d) Ta ký hiệu $R(n_1, . . . , n_c)$ là số nguyên nhỏ nhất $R\geqslant 1$ sao cho tính chất $\mathbf{R}(n_1, . . . , n_c; R)$ được thỏa mãn ("các số Ramsey").

e) Ta có $R(n,2) =n$ với mọi số nguyên $n\geqslant 2$ ; ta có $R(3,3) = 6$.

f) Chứng minh rằng $R(4,3) = 9$.

g) Tính $R(5,5)$ ; tính $R(6,6)$.