Note này được dựa trên Concrete Mathematics, 2.2

Khi ta gặp tổng dạng ~\sum_{k=0}^n a_k~, ta có thể đặt ~S_n = \sum_{k=0}^n a_k~ và viết lại ~S_n~ dưới dạng hệ thức truy hồi như sau:

~S_0 = a_0~

~S_n = S_{n-1} + a_n~

Để tinh ~S_n~, ta có thể giải hệ thức truy hồi bằng các phương pháp đã biết (ví dụ như repertoire method)

Ví dụ: ~a_0 = \alpha, a_n = \beta + \gamma n~

Khi đó, tổng có thể được viết dưới dạng hệ thức truy hồi như sau

~R_0 = \alpha~

~R_n = R_{n-1} + \beta + \gamma n~

Tính thử ~R_0, R_1, R_2, ...~, ta thấy ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~

Ta sẽ dùng repertoire method để giải hệ thức truy hồi này.

Khi ~R_n = 1~, ta có ~\alpha = 1, \beta = 0, \gamma = 0~.

Thay các giá trị này và ~R_n = 1~ vào ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~A(n) = 1~

Khi ~R_n = n~, ta có ~\begin{cases} \alpha = 0 \\ n = (n-1) + \beta + \gamma n \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ \beta + \gamma n = 1 + 0n \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ \beta = 1 \\ \gamma = 0 \end{cases}~.

Thay các giá trị này và ~R(n) = n~ vào ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~B(n) = n~

Khi ~R_n = n^2~, ta có ~\begin{cases} \alpha = 0 \\ n^2 = (n-1)^2 + \beta + \gamma n \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ 2n - 1 = \gamma n + \beta \end{cases} \Rightarrow \begin{cases} \alpha = 0 \\ \gamma = 2 \\ \beta = -1 \end{cases}~.

Thay các giá trị này và ~R(n) = n^2~ vào ~R_n = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~2C(n) - B(n) = n^2~

Giải hệ ~\begin{cases} A(n) = 1 \\ B(n) = n \\ 2C(n) - B(n) = n^2 \end{cases}~, ta được ~\begin{cases} A(n) = 1 \\ B(n) = n \\ C(n) = \frac{n^2 + n}{2} \end{cases}~

Ngược lại, nếu ta có một hệ thức truy hồi, ta có thể giải hệ thức truy hồi bằng cách tính tổng.

Ví dụ: Bài toán Tháp Hà Nội

~T_0 = 0~

~T_n = 2T_{n-1} + 1~

Chia hai vế cho ~2^n~, ta có

~\frac{T_0}{2^0} = 0~

~\frac{T_n}{2^n} = \frac{T_{n-1}}{2^{n-1}} + 2^{-n}~

Đặt ~S_n = \frac{T_n}{2^n}~, ta có:

~S_0 = 0~

~S_n = S_{n-1} + 2^{-n}~

dễ thấy ~S_n = \sum_{k=1}^n 2^{-k}~

Do ~(2^{-k})_{k=1}^\infty~ là một cấp số nhân, ta có thể dùng công thức để tính ra được ~S_n \sum_{k=1}^n 2^{-k} = 1 - 2^{-n} \Rightarrow T_n = 2^nS_n = 2^n - 1~

Ở ví dụ trên, ta nhân hai vế cho ~2^{-n}~. Liệu có cách nào để tổng quát hóa hằng số này hay không?

Câu trả lời là có. Xét hệ thức truy hồi ~T_n~ có dạng sau:

~a_n T_n = b_n T_{n-1} + c_n~

Giả sử ta cần giải hệ thức này bằng cách nhân hai vế với ~s_n~, khi đó

~s_n a_n T_n = s_n b_n T_{n-1} + s_n c_n~

Để có thể đặt ~S_n = s_n a_n T_n~ và quy về dạng ~S_n = S_{n-1} + s_n c_n~, ta cần có ~s_n b_n = s_{n-1} a_{n-1} \Rightarrow s_n = \frac{s_{n-1}a_{n-1}}{b_n} \Rightarrow \boxed{s_n = \frac{a_{n-1}a_{n-2}...a_1}{b_nb_{n-1}...b_2}}~

Lưu ý: Ta chỉ có thể áp dụng phương pháp khi ~s_n \ne 0~, hay ~\begin{cases} a_n \ne 0 \\ b_n \ne 0 \end{cases}~

Ví dụ: Số lần hoán đổi vị trí hai số kì vọng khi sắp xếp một mảng bằng thuật toán Quicksort

~C_0 = 0~

~C_n = n + 1 + \frac{2}{n} \sum_{k=0}^{n-1} C_k~

Ta cần tìm cách loại bỏ ~\frac{2}{n}~ và ~\sum_{k=0}^{n-1} C_k~

Ta có:

~C_n = n + 1 + \frac{2}{n} \sum_{k=0}^{n-1} C_k~

~\Rightarrow n C_n = n^2 + n + 2\sum_{k=0}^{n-1} C_k : (1)~

Công thức trên đúng với mọi ~n > 0~. Áp dụng công thức trên với ~n - 1 > 0~, ta có:

~(n-1)C_{n-1} = (n-1)^2 + (n-1) + 2\sum_{k=0}^{n-2} C_k : (2)~

Lấy ~(1) - (2)~, ta có:

~nC_n - (n-1)C_{n-1} = (n^2 - (n-1)^2) + (n - (n-1)) + 2(\sum_{k=0}^{n-1} C_k - \sum_{k=0}^{n-2} C_k)~

~\Rightarrow nC_n = (n+1)C_{n-1} + 2n : (3)~

Đặt ~a_n = n, b_n = n+1, c_n = 2n~, khi đó ta thấy có thể nhân hai vế với ~s_n~ để ra một hệ thức đẹp. Áp dụng công thức, ta có:

~s_n = \frac{a_{n-1}a_{n-2}...a_1}{b_nb_{n-1}...b_2} = \frac{(n-1)(n-2)...(1)}{(n+1)(n)...(3)} = \frac{2}{n(n+1)}~

Nhân hai vế của ~(3)~ với ~s_n~, ta có:

~\frac{2}{n+1}C_n = \frac{2}{n}C_{n-1} + \frac{4}{n+1}~

Đặt ~S_n = \frac{2}{n+1}C_n~, ta có ~S_n = S_{n-1} + \frac{4}{n+1}~

Dễ thấy ~S_n = \sum_{i=1}^n \frac{4}{n+1} \Rightarrow C_n = \frac{n+1}{2} \sum_{k=1}^n \frac{4}{k+1} = 2(n+1)\sum_{k=1}^n \frac{1}{k+1}~

Liệu có công thức nào cho ~\sum_{k=1}^n \frac{1}{k+1}~ hay không? Câu trả lời là không, nhưng vì biểu thức dạng này hay xuất hiện nên người ta đặt

~H_n = 1 + \frac{1}{2} + ... + \frac{1}{n} = \sum_{k=1}^n \frac{1}{k}~

Chữ ~H~ là viết tắt của từ harmonic, có nghĩa là "điều hòa". Dãy ~1, \frac{1}{2}, \frac{1}{3}, ...~ được gọi là dãy điều hòa.

Bây giờ, ta có thể viết lại ~C_n = 2(n+1)\sum_{1 \leq k \leq n} \frac{1}{k+1} = 2(n+1)\sum_{2 \leq k + 1 \leq n+1} \frac{1}{k+1} = 2(n+1)(H_{n} - 1 + \frac{1}{n+1}) = 2(n+1)H_n - 2(n+1) + 2 = \boxed{2(n+1)H_n - 2n}~

Bonus: Ta có thể dùng tích phân để chứng minh được ~H_n \in O(\log n)~, và đây cũng là lí do vì sao thuật toán Quicksort có độ phức tạp trung bình ~O(n \log n)~

(低羅沒路嘟 Cá tháng Tư)

命嗔得界紹典各伴沒排曰衛總分，差分。帝享應役使用"chữ tượng hình" 帝發展"tư duy" 立程，命嗔法得曰排呢朋"chữ Nôm" 台位字國語。

於立11，12 各伴諸得學衛各概念道咸吧辟分。各概念呢固忍性質窒葉，執眾些丹澗化役性算假治懶一，𡮈一，面辟，世辟，。。。。

相自，台概念差分吧總分共固忍性質葉相自道咸，辟分吧侞世執些性總沒隔丹澗欣。

1。差分

些諸別：

~f'(x) = \lim_{h \rightarrow 0} \frac{f(x+h) - f(x)}{h}~

由欺性總，~h~ 羅數元年欺 ~h \rightarrow 0~ 時 ~h~ 止固世羅 ~1~ 或 ~-1~. 帝丹澗化，些𩲡 ~h=1~ 帝固定義差

~\Delta(f(x)) = f(x+1) - f(x)~

~\Delta(f(x))~ 讀羅差分𧵑 ~f~ 在點 ~x~，或論欣羅差分𧵑 ~f(x)~

些固性質差𧵑道咸: ~(x^m)' = mx^{m-1}~

些仕此性差分𧵑 ~x^3~ 覘差分料固世固性質相自能空。

~\Delta(x^3) = (x+1)^3 - x^3 = 3x^2 + 3x + 1~

結果呢空葉吧易汝如 ~(x^3)' = 3x^2~, 位丕欺爫役某差分，些勤類累承特別噲羅累承減﹝能群噲羅皆承減﹞

~x^{\underline{m}} = x(x-1)(x-2)...(x-m+1)~

些𧡊低羅辟𧵑 ~m~ 承數減寅 ~x~, ~x-1~, ..., ~x-m+1~. 既號 ~x^{\underline{m}}~ 讀羅 ~x~ 帽 ~m~ 減

些此性差分𧵑 ~x^{\underline{m}}~

~\Delta(x^{\underline{m}}) = (x+1)^{\underline{m}} - x^{\underline{m}} = (x+1)x(x-1)(x-2)...(x-m+2) - x(x-1)(x-2)...(x-m+1) = x(x-1)(x-2)...(x-m+2)[(x+1) - (x-m+1)]~

~\Delta(x^{\underline{m}}) = mx(x-1)(x-2)...(x-m+2) = mx^{\underline{m-1}}~

丕些固公識葉吧易汝 ~\boxed{\Delta(x^{\underline{m}}) = mx^{\underline{m-1}}}~

於𨕭眾些某定義累承減某數帽揚。些仕定義累承減朱數帽空揚如差帝性質棟哈於𨕭中。

~x^{\underline{0}} = 1~

~x^{\underline{-m}} = \frac{1}{(x+1)(x+2)(x+3)...(x+m)}~ (~m > 0~)

差欺定義得累承減朱每數元，些徐固得公識人台累承減

~\boxed{x^{\underline{n+m}} = x^{\underline{n}}(x-n)^{\underline{m}}}~

同時，些共固公識差﹝種公識開展二識Newton﹞

~(x+y)^{\underline{n}} = \sum_{k=0}^n C_n^k x^{\underline{k}}y^{\underline{n-k}}~

沒性質葉女𧵑道咸羅 ~(e^x)' = e^x~. 料固沒咸 ~f(x)~ 鬧課滿 ~\Delta f(x) = f(x)~ 能空？

些固： ~\Delta f(x) = f(x) \Rightarrow f(x+1) - f(x) = f(x) \Rightarrow f(x+1) = 2f(x)~

易𧡊 ~f(x) = 2^x~ 羅沒咸課滿 ~f(x+1) = 2f(x)~, 吧位世 ~\boxed{\Delta(2^x) = 2^x}~

役性差分咸帽共可丹澗

~\Delta(c^x) = c^{x+1} - c^x \Rightarrow \boxed{\Delta(c^x) = (c-1)c^x}~

2。總分

些諸別：

~\int_a^b f(x) dx = \lim_{n \rightarrow \infty} \sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~

某 ~x_i = a + \frac{i}{n+1}(b-a)~ (tức ~x_0, x_1, ..., x_n, x_{n+1}~ 羅各點中斷 ~[a,b]~ 隔調饒)

﹝帝易想象吧汝公識呢，流意 ~\sum_{i=1}^{n-1} (x_{i+1} - x_i)f(x_i)~ 羅總面辟各刑字日用帝約量面辟噽𠁑途是咸數 ~f(x)~﹞

些禮敢興慈概念辟分帝定義總分如差：

~\sum_a^b f(x) \delta x = f(a) + f(a+1) + ... f(b-1) = \sum_{k=a}^{b-1} f(k)~

流意總止豸慈 ~a~ 典 ~b-1~ 帝總分固各性質種辟分差：

• ~\sum_a^b f(x) \delta x + \sum_b^c f(x) \delta x = \sum_a^c f(x) \delta x~ (種 ~\int_a^b f(x)dx + \int_b^c f(x)dx = \int_a^c f(x)dx~)
• 裊 ~g(x) = \Delta(f(x))~ 時
  • ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~ (種裊 ~g(x) = f'(x)~ 時 ~\int_a^b g(x) dx = f(x)]_a^b~)
  • 些既號 ~\sum g(x) \delta x = f(x) + C~ (種元咸)

瘴明性質裊 ~g(x) = \Delta(f(x))~ 時 ~\sum_a^b g(x) \delta x = f(x)]_a^b = f(b) - f(a)~

些固：

~\sum_a^b g(x) \delta x = \sum_{k=a}^{b-1} g(x) = \Delta(f(a)) + \Delta(f(a+1)) + \Delta(f(a+2)) + ... + \Delta(f(b-1))~

~\sum_a^b g(x) \delta x = (f(a+1) - f(a)) + (f(a+2) - f(a+1)) + (f(a+3) - f(a+2)) + ... + (f(b) - f(b-1))~

~\sum_a^b g(x) \delta x = f(b) - f(a)~

慈各公識性差分於𨕭，些易陽固得各公識性總分差：

• ~\sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~ (中欺 ~m \ne -1~)
• ~\sum c^x \delta x = \frac{c^x}{c-1} + C~ (中欺 ~c \ne 1~). 欺 ~c = 1~ 時 ~\sum c^x \delta x = \sum 1 \delta x = x + C~

悲徐些勤所公識朱 ~\sum x^{\underline{m}} \delta x~ 欺 ~m = -1~. 於門解辟，些別

~\int x^{-1} dx = \ln |x| + C~

相自，些共固

~\sum x^{\underline{-1}} = H_x + C~ 某 ~H_x = \sum_{1 \leq k \leq x} \frac{1}{k}~

調呢朱𧡊 ~H_x~ 固堯性質種某咸 ~\ln~. 倘些共諸瘴明得 ~|H_n - \ln n| < 1~ 欺 ~n~ 都懶.

3. 應用丹澗𧵑總分

察排算性 ~\square_n = \sum_{0 \leq k \leq n} k^2~

話𥆾時固𡲈如排算𨕭空連觀之典差分，總分位各性質於𨕭止停朱累承減𠹲空拜累承平常。雖然，些固世轉 ~k^2~ 朋總各累承減朋公識 ~k^2 = k^{\underline{2}} + k^{\underline{1}}~

些固：

~\sum_{0 \leq k \leq n} k^2 = \sum_0^{n+1} k^2 \delta k = \sum_0^{n-1} (k^{\underline{2}} + k^{\underline{1}}) \delta k~

~\boxed{\sum_{0 \leq k \leq n} k^2 = [\frac{k^{\underline{3}}}{3} + \frac{k^{\underline{2}}}{2}]_0^{n+1}}~

慈低些止役開展羅囉沒公識朱 ~\square_n~

相自，些固世用公識 ~k^3 = k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}~ 帝性 ~C_n = \sum_{0 \leq k \leq n} k^3~ 如差：

~C_n = \sum_0^{n+1} (k^{\underline{3}} + 3k^{\underline{2}} + k^{\underline{1}}) \delta k~

~C_n = [\frac{k^{\underline{4}}}{4} + k^{\underline{3}} + \frac{k^{\underline{2}}}{2}]_0^{n+1}~

爫世鬧帝些尋得各係數中各公識 ~k^2 = k^{\underline{2}} + k^{\underline{1}}~ 吧 ~k^3 = k^{\underline{3}} + 3k^{\underline{3}} + k^{\underline{1}}~. 俱者利羅些使用數Sterling 類I ﹝蓋呢共種役些使用數祖合能三角Pascal 帝尋係數𧵑各數巷中開展 ~(a+b)^n~ 丕﹞。

4. 差分𧵑沒辟，總分曾焚

察差分𧵑沒辟台咸 ~u~ 吧 ~v~. 些仕尋隔性 ~\Delta(uv)~ 慈 ~u, v, \Delta(u), \Delta(v)~

~\Delta(uv) = u(x+1)v(x+1) - u(x)v(x) = u(x+1)v(x+1) + u(x+1)v(x) - u(x+1)v(x) - u(x)v(x)~

﹝役共除 ~u(x+1)v(x)~ 棟𦠘路爫求綏𡧲台數巷﹞

~\Delta(uv) = u(x+1)[v(x+1) - v(x)] + v(x)[u(x+1) - u(x)]~

~\Delta(uv) = u(x+1)\Delta(v) + v(x)\Delta(u)~

帝公識呢葉欣，些定義 ~Eu(x) = u(x+1)~ (~E~ 羅曰悉𧵑慈"Extra" ﹝添﹞中㗂英﹞，些固世曰論公識呢又如差：

~\boxed{\Delta(uv) = Eu\Delta(v) + v\Delta(u)}~

中索，公識呢羅 ~\boxed{\Delta(uv) = u\Delta(v) + Ev\Delta(u)}~. 墨油台公識呢空對稱仍些固世瘴明眾朋饒。

於門解辟，公識性道咸𧵑沒辟執些固得公識性辟分曾焚。相自，些共固公識性總分曾焚如差：

~\sum u\Delta(v) = uv - \sum Ev\Delta(u)~

種如公識性辟分曾焚，些常使用得公識性總分曾焚裊中表識勤性，固沒焚性差分易吧沒焚性總分易。

圍裕 1: 性 ~\sum_{0 \leq k \leq n} k2^k~

頭先，些性 ~\sum x2^x \delta x~

達 ~u(x) = x \Rightarrow \Delta(u) = 1~, ~\Delta(v) = 2^x \Rightarrow v = 2^x \Rightarrow Ev = 2^{x+1}~

欺帝： ~\sum x2^x \delta x = x2^x - \sum 2^{x+1} \delta x = x2^x + 2^{x+1} + C~

位世麻 ~\sum_{0 \leq k \leq n} k2^k = \sum_0^{n+1} x2^x \delta x = [x2^x + 2^{x+1}]_0^{n+1}~

圍裕 2: 性 ~\sum_0^n H_x \delta x~

些𧡊 ~H_x~ 羅沒焚易性差分，位世年些達

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = 1 \Rightarrow v = x^{\underline{1}} = x\Rightarrow Ev = (x+1)^{\underline{1}}~

些固： ~\sum H_x \delta x = xH_x - \sum (x+1)^{\underline{1}}x^{\underline{-1}} \delta x~

~\sum H_x \delta x = xH_x - \sum 1 \delta x~

~\sum H_x \delta x = xH_x + x + C~

慈帝易陽性得 ~\boxed{\sum_0^n H_x \delta x = nH_n + n}~

圍裕 3: 性 ~\sum_0^n xH_x \delta x~

達：

~u(x) = H_x \Rightarrow \Delta(u) = x^{\underline{-1}}~

~\Delta(v) = x \Rightarrow v = \frac{x^{\underline{2}}}{2} \Rightarrow Ev = \frac{(x+1)^{\underline{2}}}{2}~

些固：

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \sum \frac{(x+1)^{\underline{2}}x^{\underline{-1}}}{2} \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{1}{2} \sum x \delta x~

~\sum xH_x \delta x = \frac{x^{\underline{2}}}{2}H_x - \frac{x^{\underline{2}}}{4} + C~

慈帝易陽性得 ~\boxed{\sum_0^n xH_x \delta x = \frac{n^{\underline{2}}}{2}H_n - \frac{n^{\underline{2}}}{4}}~

5. 總合見識

~\Delta(x^{\underline{m}}) = mx^{\underline{m-1}} \Rightarrow \sum x^{\underline{m}} \delta x = \frac{x^{\underline{m+1}}}{m+1} + C~

(特別： ~\Delta(H_x) = x^{\underline{-1}} \Rightarrow \sum x^{\underline{-1}} \delta x = H_x + C~)

~\Delta(c^x) = (c-1)c^x \Rightarrow \sum c^x \delta x = \frac{c^x}{c-1} + C~

(特別：~\Delta(2^x) = 2^x \Rightarrow \sum 2^x \delta x = 2^x + C~)

~\Delta(cf) = c\Delta(f) \Rightarrow \sum cf = c \sum f~ (~c~ 羅恆數)

~\Delta(f + g) = \Delta(f) + \Delta(g) \Rightarrow \sum (f + g) = \sum f + \sum g~

~\Delta(fg) = f\Delta(g) + Eg\Delta(f) \Rightarrow \sum f\Delta(g) = fg - \sum Eg\Delta(f)~

Note này được mình viết trong lúc đọc sách Concrete Mathematics, phần 1.3. Khi đọc sách Toán, mình thấy không nên chỉ đọc sơ qua mà nên bắt tay vào làm cùng theo chỉ dẫn của sách, khi đó thì mình sẽ nhớ và nắm kĩ ý tưởng giải bài hơn. Ngoài ra, mình viết note này để phục vụ bản thân là chính: một số phần mình thấy dễ hiểu thì mình bỏ qua, phần khó hiểu mình note kĩ hơn, và vì thế một số bạn sẽ thấy note hữu ích và một số bạn sẽ không học được gì từ mấy note này.

Cho ~n~ người đứng thành một vòng tròn, mỗi người được đánh số từ 1 đến ~n~. Bắt đầu từ vị trí số 1, mỗi người sẽ đếm lần lượt 1, 2, ..., ~k~, người đếm ~k~ sẽ bị loại khỏi vòng tròn, và mọi người tiếp tục đếm lại từ ~1~ cho đến khi chỉ còn lại một người. Hỏi người đánh số nào là người ở lại vòng tròn cuối cùng.

Trong khuôn khổ bài viết này, ta nghiên cứu trường hợp ~k = 2~.

Gọi ~J(n)~ là số của người ở lại vòng tròn cuối cùng, ta sẽ thử tính ~J(n)~ với một số giá trị nhỏ của ~n~:

• ~J(1) = 1~
• ~J(2) = 1~
• ~J(3) = 3~ (thứ tự loại ~2, 1~)
• ~J(4) = 1~ (thứ tự loại ~2, 4, 3~)
• ~J(5) = 3~ (thứ tự loại ~2, 4, 1, 3~)
• ~J(6) = 5~ (thứ tự loại ~2, 4, 6, 1, 3~)

Qua những giá trị ban đầu, ta thấy ~J(n)~ là một số lẻ, điều này là do ở lần đi qua vòng tròn đầu tiên thì ta đã loại hết tất cả số chẵn. Ngoài ra, tùy vào tính chẵn lẻ của ~n~ mà ~1~ bị loại ngay sau lần duyệt đầu tiên, hoặc an toàn khá lâu, vì vậy ta nghĩ đến việc xét tính chẵn lẻ của ~n~.

Ta xét trường hợp có ~2n~ người. Sau một lần đi qua vòng tròn, vòng tròn trở thành ~1, 3, 5, ..., 2n-3, 2n-1~ (~n~ người). Ta thấy vòng tròn này giống hệt vòng tròn ~1, 2, 3, ..., n~, ngoại trừ việc số của người ~x~ trở thành ~2x-1~. Do đó, ~J(2n) = 2J(n) - 1~.

Xét trường hợp có ~2n+1~ người. Ta thấy sau khi người 1 đếm "2" thì vòng tròn còn ~n~ người ~3, 5, ..., 2n+1~. Vòng tròn này giống hệt vòng tròn ~n~ người của trò chơi ban đầu, ngoại trừ việc số của người ~x~ trở thành ~2x+1~. Do đó ~J(2n+1) = 2J(n)+1~.

Vậy ta có công thức truy hồi:

• ~J(1) = 1~
• ~J(2n) = 2J(n) - 1~
• ~J(2n+1) = 2J(n) + 1~

Liệu có công thức tổng quát cho công thức truy hồi này không?

Sử dụng công thức truy hồi này, ta sẽ tính được kết quả cho một số ~n~ lớn hơn một chút. Ta thấy được quy luật sau (các giá trị ~J(n)~ dưới đây được viết từ ~J(1)~ theo thứ tự từ trái qua phải, từ trên xuống dưới để thể hiện quy luật)

• ~1~ (~n=1~)
• ~1,3~ (~n=2..3~)
• ~1,3,5,7~ (~n=4..7~)
• ~1,3,5,7,11,13,15~ (~n=8..15~)

Ta thấy có một "chu kì" mới bắt đầu khi ~n = 2^m~, và các số trong "chu kì" có dạng ~1, 3, 5, 7, ...~. Ta có thể biểu diễn điều này dưới dạng toán học như sau

~J(2^m + l) = 2l+1~ với ~m \geq 0~ và ~0 \leq l < 2^m~ (cách kí hiệu này khá giống kí hiệu ~q, r~ trong định nghĩa phép chia hai số tự nhiên)

Ta sẽ chứng minh công thức tổng quát này bằng quy nạp theo ~m~

Nếu ~m = 0~, khi đó do ~0 \leq l < 2^m = 1~ nên ~l = 0~. ~J(2^m + l) = J(1 + 0) = J(1) = 1 = 2(0) + 1 = 2l+1~, nên trường hợp khởi đầu đúng.

Nếu ~m \geq 1~, ta có hai trường hợp

• Nếu ~l~ chẵn, ~J(2^m + l) = 2J(\frac{2^m+l}{2}) - 1 = 2J(2^{m-1} + \frac{l}{2}) - 1 = 2(2(\frac{l}{2}) + 1) + 1 = 2l + 1~

• Nếu ~l~ lẻ, ~J(2^m + l) = 2J(\frac{2^m+l-1}{2}) + 1 = 2(2(\frac{l-1}{2}) + 1) + 1 = 2l+1~

Từ hai trường hợp trên, ta thấy trường hợp quy nạp cũng đúng.

Do đó theo nguyên lí quy nạp thì công thức đúng.

Bây giờ ta sẽ thử mở rộng bài toán để có thể giải được các bài toán khác.

Ta thấy công thức xuất hiện số ~2^m~, và vì thế ta nghĩ đến việc viết lại công thức dưới dạng hệ nhị phân xem có gì đặc biệt không.

Giả sử ~n = (b_mb_{m-1}...b_1b_0)_2 = b_m \cdot 2^m + b_{m-1} \cdot 2^{m-1} + ... + b_1 \cdot 2^1 + b_0 \cdot 2^0~.

Khi ~n = 2^m + l~ thì

~n = (1b_{m-1}...b_1b_0)_2~

~l = (0b_{m-1}...b_1b_0)_2~

~2l = (b_{m-1}...b_1b_00)_2~ (dịch bit sang trái)

~2l + 1 = (b_{m-1}...b_1b_01)_2~

Nói cách khác, ~J((1b_{m-1}...b_1b_0)_2) = (b_{m-1}...b_1b_01)_2~, tức ta chỉ cần cyclic left shift số ~n~ là tính được ~J(n)~

Một cách mở rộng bài toán khác là giả sử ta không may mắn gặp phải một công thức truy hồi có dạng sau:

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

thì liệu ta có giải được không?

Đầu tiên, ta lại thử với ~n~ nhỏ để tìm quy luật:

• ~f(1) = 1\alpha + 0\beta + 0\gamma~
• ~f(2) = 2\alpha + 1\beta + 0\gamma~
• ~f(3) = 2\alpha + 0\beta + 1\gamma~
• ~f(4) = 4\alpha + 3\beta + 0\gamma~
• ~f(5) = 4\alpha + 2\beta + 1\gamma~
• ~f(6) = 4\alpha + 1\beta + 2\gamma~
• ~f(7) = 4\alpha + 0\beta + 3\gamma~

Ta thấy xuất hiện các chu kì giống như trong dãy Josephus.

Đặt ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~. Khi viết ~n = 2^m + l~, dễ thấy

• ~A(n) = 2^m~
• ~B(n) = 2^m - l - 1~
• ~C(n) = l~

Nếu giả sử các hàm ~A(n), B(n), C(n)~ không dễ thấy như trên thì liệu ta có thể dùng kĩ thuật nào khác để mò ra các hàm nào không. Ta có thể sử dụng repertoire method, với tư tưởng chính là:

• Chọn các hàm ~f(n)~ đặc biệt, rồi lấy ~\alpha, \beta, \gamma~ ứng với các hàm đó.
• Các ~\alpha, \beta, \gamma, f(n)~ sẽ tạo ra hệ phương trình ẩn ~A(n), B(n), C(n)~
• Giải hệ phương trình.

Ở ví dụ này, ta dễ thấy ~\boxed{A(n) = 2^m}~ với ~n = 2^m + l~, nhưng có thể ta không thấy được ~B(n), C(n)~. Ta sẽ ứng dụng repertoire method để giải.

Đầu tiên, a muốn tìm ~\alpha, \beta, \gamma~ để ~f(n) = 1~. Thay vào

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

Ta có: ~\alpha = 1~, ~1 = 2 + \beta \Rightarrow \beta = -1~, ~1 = 2 + \gamma \Rightarrow \gamma = -1~. Thay các giá trị ~\alpha, \beta, \gamma~, và ~f(n) = 1~ vào ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được: ~\boxed{A(n) - B(n) - C(n) = 1}~

Lấy ~f(n) = n~. Thay vào hệ thức truy hồi, ta có:

~\alpha = 1~

~2n = 2n + \beta \Rightarrow \beta = 0~

~2n + 1 = 2n + \gamma \Rightarrow \gamma = 1~

Thay các giá trị này cùng với ~f(n) = n~ vào ~f(n) = A(n)\alpha + B(n)\beta + C(n)\gamma~, ta được ~\boxed{A(n) + C(n) = n}~

Giải hệ ~\begin{cases} A(n) = 2^m \\ A(n) - B(n) - C(n) = 1 \\ A(n) + C(n) = n \end{cases}~, ta ra được ~A(n), B(n), C(n)~ như quan sát ở trên.

Số ~2^m~ lại xuất hiện trong ~A(n)~ và ~B(n)~. Điều này khiến ta nghĩ tới việc giải công thức truy hồi dạng tổng quát dưới dạng hệ nhị phân.

Để thuận tiện, ta viết lại

~f(1) = \alpha~

~f(2n) = 2f(n) + \beta~

~f(2n+1) = 2f(n) + \gamma~

thành

~f(1) = \alpha~

~f(2n + j) = 2f(n) + \beta_j~ với ~j \in \{0,1\}~ (~\beta_0 = \beta, \beta_1 = \gamma~)

Khi đó

~f((b_mb_{m-1}...b_1b_0)_2) = 2f((b_mb_{m-1}...b_1)_2) + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 4f((b_mb_{m-1}...b_2)_2) + 2\beta_{b_1} + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 8f((b_mb_{m-1}...b_3)_2) + 2^2\beta_{b_2} + 2^1\beta_{b_1} + \beta_{b_0}~

...

~f((b_mb_{m-1}...b_1b_0)_2) = 2^mf((b_m)_2) + 2^{m-1}\beta_{b_{m-1}} + ... + 2^1\beta_{b_1} + \beta_{b_0}~

~f((b_mb_{m-1}...b_1b_0)_2) = 2^m\alpha + 2^{m-1}\beta_{b_{m-1}} + ... + 2^1\beta_{b_1} + \beta_{b_0}~

Nếu ta cho phép các chữ số trong kí hiệu hệ nhị phân được lấy giá trị bất kì, ta có thể viết

~f((b_mb_{m-1}...b_1b_0)_2) = (\alpha\beta_{b_{m-1}}...\beta_{b_1}\beta_{b_0})_2~

(cho ~\alpha~ làm số đầu tiên trong đáp án, với ~m-1~ số còn lại, đổi chữ số ~i~ thành ~\beta_i~)

Ví dụ, với bài toán Josephus ban đầu (~\alpha = 1, \beta_0 = -1, \beta_1 = 1~), để tính ~J(100)~, ta có thể làm như sau:

~100 = (1100100)_2~

Cho ~\alpha = 1~ ở đầu, trong ~m-1~ số còn lại, thay số 0 bằng -1 và thay số 1 bằng 1, ta có:

~J(100) = ((1)(1)(-1)(-1)(1)(-1)(-1))_2 = 64 + 32 - 16 - 8 + 4 - 2 - 1 = 73~

Ta thấy công thức truy hồi trên còn số 2 ta chưa tổng quát. Giả sử ta có hệ thức truy hồi sau

~f(j) = \alpha_j~ với ~1 \leq j < d~

~f(dn + j) = cf(n) + \beta_j~ với ~0 \leq j < d~ và ~n \geq 1~

thì bằng cách viết ~n~ dưới dạng hệ cơ số ~d~ và viết đáp án dưới dạng hệ cơ số ~c~, ta cũng ra được kết quả

~f((b_mb_{m-1}...b_1b_0)_d) = (\alpha_{b_m}\beta_{b_{m-1}}...\beta_{b_1}\beta_{b_0})_c~

Trong một đề luyện tập Tin học trẻ của trường THPT Kim Liên vừa rồi có bài toán sau:

Cho ~n, k~ (~1 \leq n \leq 10^8, 1 \leq k \leq 10^3~), tính giá trị của ~1^k + 2^k + ... + n^k = \sum_{i=1}^n i^k~ (sau khi chia lấy dư cho ~10^9 + 7~)

Link nộp bài: https://oj.vnoi.info/problem/bvd_tongmu

Hiển nhiên việc phương pháp duyệt với độ phức tạp ~O(nk)~ (hoặc ~O(n \log k)~ nếu dùng thuật toán tính lũy thừa nhanh) sẽ không giải quyết được bài toán này trong 1 giây, do số phép tính ~\approx nk \approx 10^{11} > 10^8~.

Ta thấy: Nếu ~k = 1~ thì ta có công thức tổng quát tính là ~\frac{n(n+1)}{2}~, nếu ~k = 2, 3~ thì trong sách giáo khoa Toán lớp 11 (cũ) cũng đã giới thiệu công thức tổng quát tính là một hàm bậc ~3~ và ~4~. Chính vì thế mà ta dự đoán được với mỗi ~k~ thì sẽ có một công thức tính dạng hàm số bậc ~k+1~ có biến ~n~.

Vậy ta mò công thức đó như thế nào?

Gọi công thức cần tìm là ~f(n)~

Đầu tiên, ta đã biết qua hai điểm không cùng hoành độ thì ta sẽ xác định được một đường thẳng (có phương trình là hàm bậc nhất), qua ba điểm không cùng hoành độ ta cũng xác định được một đường parabol (có phương trình là hàm bậc hai), vì vậy ta dự đoán được để tìm phương trình bậc ~(k+1)~ thì ta cần lấy ~(k+2)~ điểm không cùng hoành độ. Dễ nhất là ta lấy các điểm ~(1, f(1)), (2, f(2)), ..., (k+2, f(k+2))~. Mỗi điểm ta cần tối đa ~O(k \log k)~ phép tính để tính (dùng thuật toán tính lũy thừa nhanh), vì vậy ta sẽ mất ~O(k^2 \log k)~ phép tính cho bước này.

Ý tưởng chủ đạo của nội suy Lagrange để tìm một hàm đa thức đi qua các điểm là tách hàm ~f(n)~ thành tổng của các hàm ~g_1(n), g_2(n), ..., g_{k+2}(n)~ sao cho

~g_i(n) = \begin{cases} f(i) \text{ nếu } n = i \\ 0 \text{ nếu } n \text { là các hoành độ khác} \end{cases}~

Dễ thấy khi tìm được các hàm ~g~ thỏa mãn điều kiện trên thì ~f(n) = g_1(n) + g_2(n) + ... + g_{k+2}(n)~

Bây giờ ta tìm ~g_i(n)~ như thế nào.

Do ~g_i(n) = 0~ khi ~n~ là các hoành độ khác, điều này nghĩa là ~1, 2, 3, ..., i-1, i+1, ..., k+2~ (tất cả các số nguyên từ ~1~ đến ~k+2~ mà khác ~i~) là các nghiệm của ~g_i(n) = 0~. Do đó, ~g_i(n)~ sẽ có dạng ~\boxed{g_i(n) = (n-1)(n-2)(n-3)...(n-(i-1))(n-(i+1))...(n-(k+2))m_i}~ với ~m_i \in \mathbb{R}~ là một hằng số nào đó mà ta chưa biết. Ở đây có hai điểm đáng chú ý

• Cái này giống mẹo giải phương trình bằng cách nhẩm nghiệm ~x_0~, rồi cố gắng phân tích ra nhân tử ~(x - x_0)~ để ta có thể tính luôn nghiệm này và đơn giản hóa bài toán.
• Lí do ta biết ~m_i~ là hằng số là do phần ~(n-1)(n-2)(n-3)...~ là đã một đa thức bậc ~k+1~, mà ~f(n)~ là một đa thức bậc ~k+1~ nên ~m_i~ không được làm tăng bậc của ~g_i(n)~, hay nói cách khác, ~m_i~ là đa thức bậc 0 và là hằng số.

Để tính ~m_i~, ta sử dụng tính chất ~g_i(n) = f(i) \text{ nếu } n = i~.

Ta có: ~g_i(i) = f(i) \Rightarrow (i-1)(i-1)...(i-(i-1))(i - (i+1))...(i - (k+2))m_i = f(i) \Rightarrow \boxed{m_i = \frac{f(i)}{(i-1)(i-1)...(i-(i-1))(i - (i+1))...(i - (k+2))}}~

(ở phần mẫu không có thừa số nào bằng ~0~ vì hoành độ các điểm phân biệt, nên ta có thể chia được)

Vậy từ ~m_i~ ta ra được công thức của ~g_i(n)~, từ ~g_i(n)~ ta ra được công thức của ~f(n)~. Việc tính ~g_i(n)~ sẽ tốn ~O(k)~ phép tính, và ta cần tính ~k+2~ hàm như vậy, nên theo quy tắc nhân, độ phức tạp cuối cùng của bước này là ~O(k^2)~ (hoàn toàn không phụ thuộc vào ~n~)

Tổng độ phức tạp là ~O(k^2\log k + k^2) = O(\max(k^2\log k, k^2)) = O(k^2\log k)~

~k^2\log k \approx 10^7 < 10^8~, nên thuật toán sử dụng công thức ta mò ra bằng nội suy Lagrange có thể chạy được trong 1 giây.

Vào 8h tối thứ tư (27/07/2022), mình sẽ tổ chức buổi trình bày thứ sáu trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022 với chủ đề Số học. Ở bài trình bày này, các bạn sẽ được biết:

• Ước chung lớn nhất, Bội chung nhỏ nhất. Thuật toán Euclid. Giải phương trình Diophantine dạng ~ax+by=c~
• Sàng nguyên tố và một số biến thể đơn giản.
• Phép chia lấy dư: Tính ~A + B~, ~A - B~, ~AB~, ~\frac{A}{B}~, ~\frac{A}{B} + \frac{C}{D}~ sau khi chia lấy dư với một số nguyên tố.
• Giới thiệu sơ qua một vài kiến thức nâng cao về số học và các nguồn tài liệu để các bạn có thể tìm hiểu thêm.

Để có thể theo dõi bài trình bày này, bạn cần nắm được các tính chất của tập số nguyên, và các khái niệm ước, bội, số nguyên tố. Ngoài ra các bạn cũng cần nắm được cách cài đặt thuật toán kiểm tra số nguyên tố và thuật toán tìm ước chung lớn nhất, bội chung nhỏ nhất đã được trình bày trong chương trình Tin học 10.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây .

Vào lúc 4h chiều thứ tư tuần này (06/07/2022), mình sẽ tổ chức buổi trình bày thứ năm trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022 với chủ đề Cây phân đoạn. Ở bài trình bày này, các bạn sẽ được làm quen với:

• Cây phân đoạn dưới góp nhìn của phương pháp Chia để trị
• Cách xây dựng cây, các hàm cập nhật, lấy thông tin từ cây để giải một số bài toán đơn giản (bao gồm phân tích độ phức tạp tính toán)
• Kĩ thuật lazy update, và việc kết hợp cây phân đoạn với các cấu trúc dữ liệu trong C++ STL / PBDS.
• Hầu hết thời gian của bài trình bày sẽ được dùng để mình code mẫu. Trong lúc code, mình sẽ cung cấp thêm cho các bạn một số mẹo để tránh những lỗi sai không đáng có khi lập trình cây phân đoạn.

Để có thể theo dõi tốt bài trình bày, bạn cần nắm được cách làm một số bài toán Chia để trị đơn giản đã được trình bày trong phần 1, và cách phân tích độ phức tạp tính toán của một thuật toán chia để trị.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Vào lúc 8h tối thứ tư (22/06/2022), mình sẽ tổ chức buổi trình bày thứ tư trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Cách nhân nhanh hai đa thức trong ~O(n^{\log_2 3})~ và ứng dụng của việc nhân đa thức trong bài toán Cái túi phiên bản đếm, bài toán đếm cấp số cộng độ dài 3 trong một mảng, bài toán tìm số đoạn thẳng có cùng độ dài và một bài toán xử lí xâu.
• Giới thiệu sơ lược về phương pháp Chia để trị trên cây và phương pháp Chia để trị trên đa giác.

Để có thể theo dõi bài trình bày, bạn cần nắm được các kiến thức Tổ hợp trong chương trình Đại số và Giải tích 11 hoặc trong chương trình Toán 10 mới.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây .

Vào lúc 8h tối thứ ba (14/06/2022), mình sẽ tổ chức buổi trình bày thứ ba trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Chủ đề của tập 3, tập 4, và có thể là tập 5 là "Chia để trị."

Để có thể theo dõi được bài trình bày này, các bạn cần nắm được phương pháp chứng minh quy nạp, cách phân tích độ phức tạp tính toán, cách viết hàm đệ quy. Nếu được thì các bạn cũng nên tìm hiểu trước về hàm lô-ga-rít.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Hàm lô-ga-rít và ứng dụng trong một số bài tập tin học.
• Tìm kiếm nhị phân và ứng dụng trong các bài toán tìm giá trị lớn nhất hoặc nhỏ nhất.
• Cách tính nhanh ~x^n~ với ~n~ lớn.
• Thuật toán Mergesort để sắp xếp dãy số trong ~O(n\log{n})~ trong trường hợp xấu nhất.
• Cách giải bài toán cặp điểm gần nhất (và bài toán đếm số cặp nghịch thế nếu có thời gian)
• Phân tích độ phức tạp tính toán của một thuật toán sử dụng phương pháp Chia để trị bằng phương pháp hình chữ nhật.

Nội dung của một số bài trình bày tiếp theo:

• Cây phân đoạn (Segment Tree) dưới góc nhìn của phương pháp Chia để trị.
• Cách nhân nhanh hai đa thức trong ~O(n^{1.6})~ và ứng dụng.
• Giới thiệu sơ qua về phương pháp Chia để trị trên cây và Chia để trị trên đa giác.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Vào lúc 8h tối thứ tư tuần này (08/06/2022), mình sẽ tổ chức buổi trình bày thứ hai trong chuỗi buổi trình bày về thuật toán miễn phí Hè 2022.

Chủ đề của buổi thứ hai là "Đánh giá hiệu quả thuật toán." Để có thể theo dõi bài trình bày này, bạn cần nắm được cách chứng minh mệnh đề chứa dấu ~\forall, \exists~ và mệnh đề "nếu ... thì ..." (đã được trình bày ở bài đầu tiên), nắm được khái niệm thuật toán, và biết một số bất đẳng thức đơn giản như ~\forall x \in \mathbb{R}: x^2 \geq 0~ và bất đẳng thức trung bình cộng - trung bình nhân.

Ở buổi trình bày này, các bạn sẽ được làm quen với:

• Cách phân tích độ phức tạp của một thuật toán.
• Biểu diễn độ phức tạp bằng kí pháp chữ ~O~ lớn. Sử dụng kí pháp chữ ~O~ lớn để đánh giá xem thuật toán có chạy đủ nhanh trong thời gian quy định hay không.
• Một số kĩ thuật tăng tốc độ chạy của thuật toán như lợi dụng hằng số nhỏ của ~\sum i^k~, sử dụng bitset, hai con trỏ, và chia căn đơn giản.

Địa điểm tham gia livestream: Kênh Voice general của server Discord From VNOI with love. Các bạn có thể tham gia server qua link https://discord.gg/WDgKQcHjQC

Các bạn có thể xem lại các tư liệu của bài trình bày (gồm video bài trình bày, slides đã chỉnh sửa, hình ảnh được sử dụng và nháp) tại đây.

Bài 1:

Phần a:

~P = \sqrt[3]{7 + 5\sqrt{2}} + \sqrt[3]{7 - 5\sqrt{2}}~

Sử dụng hằng đẳng thức ~(a+b)^3 = a^3 + b^3 +3ab(a+b)~ với ~a = \sqrt[3]{7 + 5\sqrt{2}}~ và ~b = \sqrt[3]{7 - 5\sqrt{2}}~, ta có

~P^3 = (7 + 5\sqrt{2}) + (7 - 5\sqrt{2}) + 3\sqrt[3]{7 + 5\sqrt{2}}\sqrt[3]{7 - 5\sqrt{2}}(\sqrt[3]{7 + 5\sqrt{2}} + \sqrt[3]{7 - 5\sqrt{2}})~

~\Rightarrow P^3 = 14 +3\sqrt[3]{49-25 \times 2}P~

~\Rightarrow P^3 = 14 - 3P~

~\Rightarrow P^3 - 3P - 14 = 0~

Ta thấy ~2~ là một nghiệm của phương trình ẩn ~P~ này nên

~P^3 - 2P^2 + 2P^2 - 4P + 7P - 14 = 0~

~\Rightarrow (P-2)(P^2 + 2P + 7) = 0~

~\Rightarrow (P-2)((P+1)^2 + 6) = 0~

Do ~(P+1)^2 + 6 \geq 6 > 0~ nên ~P - 2 = 0 \Rightarrow \boxed{P = 2}~

Phần b:

Giả sử ~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

Do ~0 \in \mathbb{Z}, P(0) \in \mathbb{Z}~ nên ~c \in \mathbb{Z}~

Do ~1 \in \mathbb{Z}, P(1) \in \mathbb{Z}~ nên ~a + b + c \in \mathbb{Z}~. Do ~\begin{cases} c \in \mathbb{Z} \\ a + b + c \in \mathbb{Z} \end{cases} \Rightarrow (a+b+c) - c \in \mathbb{Z} \Rightarrow a + b \in \mathbb{Z}~

Do ~-1 \in \mathbb{Z}, P(-1) \in \mathbb{Z}~ nên ~a - b + c \in \mathbb{Z}~.

Do ~\begin{cases} a+b+c \in \mathbb{Z} \\ a - b + c \in \mathbb{Z} \end{cases}~ nên ~2a + 2c \in \mathbb{Z}~.

Do ~c \in \mathbb{Z}~ nên ~-2c \in \mathbb{Z}~

Do ~\begin{cases} 2a + 2c \in \mathbb{Z} \\ -2c \in \mathbb{Z} \end{cases}~ nên ~2a \in \mathbb{Z}~

Ta có thể kết luận:

~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z} \Rightarrow \begin{cases} 2a \in \mathbb{Z} \\ a + b \in \mathbb{Z} \\ c \in \mathbb{Z} \end{cases}~

Giả sử ~2a, a+b, c \in \mathbb{Z}~, ta cần chứng minh ~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

Chọn số ~x \in \mathbb{Z}~ bất kì.

Do ~2a \in \mathbb{Z}~, hoặc ~a \in \mathbb{Z}~ hoặc ~a = \frac{m}{2}~ với ~m \in \mathbb{Z}~

Trường hợp 1: Giả sử ~a \in \mathbb{Z}~.

Do ~\begin{cases} a + b \in \mathbb{Z} \\ a \in \mathbb{Z} \end{cases}~ nên ~b \in \mathbb{Z}~

Do ~a,b,c,x \in \mathbb{Z}~ nên ~P(x) \in \mathbb{Z}~

Trường hợp 2: Giả sử ~a = \frac{m}{2}~ với ~m \in \mathbb{Z}~

Do ~a+b \in \mathbb{Z}~, điều này nghĩa là ~b = \frac{n}{2}~ với ~n \in \mathbb{Z}~

Khi đó ~P(x) = \frac{m}{2}x^2 + \frac{n}{2}x + c~

Do ~x \in \mathbb{Z}~ nên ~x = 2k~ hoặc ~x = 2k+1~ với ~k \in \mathbb{Z}~

Trường hợp 2.1: Nếu ~x = 2k~ thì ~P(x) = \frac{m}{2}4k^2 + \frac{n}{2}2k + c = m(2k^2) + nk + c \in \mathbb{Z}~

Trường hợp 2.2: Nếu ~x = 2k+1~ thì ~P(x) = \frac{m}{2}(4k^2 + 2k + 1) + \frac{n}{2}(2k+1) + c = m(2k^2 + k) + \frac{m}{2} + nk + \frac{n}{2} + c = m(2k^2 + k) + a + nk + b + c \in \mathbb{Z}~

Tổng hợp hai trường hợp 2.1 và 2.2, ta được ~P(x) \in \mathbb{Z}~

Do ở cả hai trường hợp, ta được ~P(x) \in \mathbb{Z}~ và ta chọn số ~x \in \mathbb{Z}~ bất kì, ta có thể kết luận

~\forall x \in \mathbb{Z}: P(x) \in \mathbb{Z}~

và đây là điều phải chứng minh.

Bài 4:

Giả sử có cách viết 10 số thỏa mãn yêu cầu bài toán.

Đánh số các điểm như hình dưới đây

Ta có:

~a_1 + a_5 + a_2 = a_1 + a_8 + a_4 = ... = k~

~\Rightarrow 3(a_1 + a_2 + a_3 + a_4) + a_5 + a_6 + a_7 + a_8 + a_9 + a_{10} = 6k~

~\Rightarrow 2(a_1 + a_2 + a_3 + a_4) + \sum_{i=1}^{10} a_i = 6k~

~\Rightarrow 2(a_1+a_2+a_3+a_4) + 45 = 6k~

~\Rightarrow 45 = 2(3k + a_1 + a_2 + a_3 + a_4) \Rightarrow 2 \mid 45~ (vô lí)

Do đó, giả sử ban đầu sai. Nói cách khác, không có cách viết 10 số thỏa mãn yêu cầu bài toán.

Bài 5:

Phần a:

Gọi 5 điểm được cho là ~A_1, A_2, A_3, A_4, A_5~

Gọi ~H~ là tập các đỉnh của bao lồi của ~5~ điểm được cho. Do không có 3 điểm nào thẳng hàng, ~3 \leq |H| \leq 5~

Trường hợp 1: ~|H| = 3~

Không làm mất tính tổng quát, giả sử ~H = \{A_1, A_2, A_3\}~. Khi đó, ~A_4~ nằm trong tam giác ~A_1A_2A_3~

~\Rightarrow \angle A_1A_4A_2 + \angle A_2A_4A_3 + \angle A_3A_4A_1 = 360^o~

Khi đó, một trong ba góc này sẽ phải lớn hơn hoặc bằng ~120^o~, tức lớn hơn ~90^o~. Không làm mất tính tổng quát, giả sử góc đó là ~\angle A_1A_4A_2~. Khi đó tam giác ~A_1A_4A_2~ là tam giác tù, tức ta tìm được một tam giác tù.

Trường hợp 2: ~|H| = 4~

Không làm mất tính tổng quát, giả sử bao lồi là tứ giác ~A_1A_2A_3A_4~. Khi đó, ~A_5~ nằm trong tứ giác ~A_1A_2A_3A_4~

~\Rightarrow \angle A_1A_5A_2 + \angle A_2A_5A_3 + \angle A_3A_5A_4 + \angle A_4A_5A_1 = 360^o~

Giả dụ cả bốn góc này không có góc tù nào. Khi đó, cả bốn góc đều có số đo ~90^o~. Ta sẽ có ~\angle A_1A_5A_2 + \angle A_2A_5A_3 = 180^o \Rightarrow \angle A_1A_5A_3 = 180^o \Rightarrow A_1, A_5, A_3~ thẳng hàng, trái với giả thiết ban đầu rằng không có ba điểm nào thẳng hàng. Vì thế giả dụ ban đầu sai, tức ít nhất một trong bốn góc phải là góc tù, và vì thế ta tìm được một tam giác tù.

Trường hợp 3: ~|H| = 5~

Không làm mất tính tổng quát, giả sử bao lồi là đa giác ~A_1A_2A_3A_4A_5~. Do đây là đa giác lồi, ta có

~\sum_{i=1}^5 \angle A_i = 180 \times 3 = 540^o~

Do ~\frac{540^o}{5} = 108^o~, sẽ có ít nhất một góc lớn hơn hoặc bằng ~108^o~, tức một góc lớn hơn ~90^o~. Không làm mất tính tổng quát, giả sử góc đó là góc ~A_1A_2A_3~, khi đó tam giác ~A_1A_2A_3~ tù.

Từ ba trường hợp trên, ta có thể kết luận rằng cho 5 điểm bất kì trên mặt phẳng sao cho không có ba điểm nào thẳng hàng, ta có thể tìm được một tam giác có đỉnh là 3 trong 5 điểm được cho.

Phần b:

Gọi 2022 điểm được cho là ~A_1, A_2, A_3, A_4, ..., A_{2022}~

Gọi ~H~ là tập đỉnh của bao lồi của 2022 điểm được cho. Do không có 3 điểm nào thẳng hàng, ~3 \leq |H| \leq 2022~.

Gọi ~k~ là số điểm nằm trong bao lồi. Ta có ~k = 2022 - |H|~

Nếu ~|H| \leq 4~ thì ~k \geq 2018~. Với mỗi điểm trong bao lồi, ta có thể tìm được một tam giác tù có điểm đó là đỉnh và hai đỉnh còn lại là hai đỉnh của đa giác bao lồi, và vì thế ta tìm được ít nhất ~k~ tam giác tù. Do ~k \geq 2018~, ta có điều phải chứng minh.

Xét trường hợp ~|H| \leq 5~.

Không làm mất tính tổng quát, giả sử bao lồi là đa giác ~A_1A_2A_3...A_n~ (~n = |H| = 2022 - k~)

Chia đa giác thành các tam giác ~A_1A_2A_3~, ~A_1A_3A_4~, ..., ~A_1A_{n-1}A_n~. Do không có ba điểm nào thẳng hàng, mỗi điểm trong bao lồi sẽ nằm trọn trong một trong các đa giác này, và từ đó với mỗi điểm trong bao lồi, ta tìm được một tam giác tù có điểm đó là một đỉnh và hai đỉnh còn lại là hai đỉnh của tam giác chứa nó (và đồng thời là hai đỉnh của đa giác bao lồi). Nói cách khác, ta tìm được ~k~ tam giác tù.

Ta có:

~\sum_{i=1}^n \angle A_i = 180(n-2)~

Giả dụ có nhiều hơn 4 góc không tù. Không làm mất tính tổng quát, giả sử các góc ~A_1, A_2, A_3, A_4, A_5~ là các góc không tù, khi đó ~\sum_{i=6}^n \angle A_i > 180(n-2) - 450 = 180(n - \frac{9}{2})~

Nếu ~n = 5~ thì điều này nghĩa là ~0 > 90~, vô lí.

Nếu ~n > 5~ thì điều này nghĩa là có một góc ~\angle A_i \geq \frac{180(n-\frac{9}{2})}{n-5}~. Mà khi ~n > 5~, ~\frac{180(n-\frac{9}{2})}{n-5} > 180~ nên ~\angle A_i > 180^o~. Điều này vô lí do một góc của một đa giác lồi không thể có số đo vượt quá ~180^o~

Do cả hai trường hợp đều dẫn đến điều vô lí, điều này nghĩa là có nhiều nhất 4 góc không tù, tức đa giác bao lồi có ít nhất ~n - 4~ góc tù. Mỗi một góc tù sẽ tạo ra một tam giác tù nên ta có ít nhất ~n - 4~ tam giác tù.

Tổng số tam giác tù ít nhất là ~k + (n-4) = n+k - 4 = 2022 - 4 = 2018~, tức là ta sẽ tìm được ít nhất 2018 tam giác tù.

Kết hợp hai trường hợp, ta có được điều phải chứng minh.