III. Các công thức và hàm Toán học quan trọng trong Tin học (tiếp)

4. Dãy số Harmonic (Harmonic Series)

4.1. Định nghĩa

Dãy số Harmonic là dãy số có thể nhiều bạn đã khá quen thuộc. Trong Toán học, đây là một dãy tổng vô hạn các số phân biệt:

$\sum_{n = 1}^\infty\frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\cdots$

Tổng của dãy số này có cận trên là $\log(n) + \gamma$ với $\gamma$ là hằng số Euler. Điều này đôi khi rất hữu dụng trong việc tính toán độ phức tạp thuật toán, ví dụ như trong giải thuật sàng lọc số nguyên tố Eratosthene. Đó là lí do giải thuật này có độ phức tạp là $\approx O(n\log(n)),$ trên thực tế còn nhanh hơn rất rất nhiều.

4.2. Bổ đề Harmonic

Phát biểu: Xét dãy số: $\lfloor{\frac{n}{1}} \rfloor, \lfloor{\frac{n}{2}} \rfloor, \lfloor{\frac{n}{3}}\rfloor,..., \left \lfloor{\frac{n}{n}} \right \rfloor$. Bổ đề Harmonic nói rằng:

• Dãy số trên là một dãy không tăng và có tối đa $2\sqrt{n}$ giá trị phân biệt.
• Dãy số trên có tổng tiến tới $n.\log(n)$.

Chứng minh:

• Đối với ý đầu tiên của bổ đề, ta có: Giả sử $d(i) = \lfloor{\frac{n}{i}} \rfloor$. Xét đoạn giá trị $i$ từ 1 tới $\sqrt{n},$ có tối đa $\sqrt{n}$ giá trị khác nhau của $d(i)$ trong đoạn này (vì có $\sqrt{n}$ giá trị $i$ khác nhau). Phần còn lại gồm các giá trị $i$ lớn hơn $\sqrt{n}$ thì $d(i) < \sqrt{n}$ và $d(i)$ là một số nguyên dương, vì vậy có tối đa $\sqrt{n}$ giá trị khác nhau của $d(i)$ trong đoạn này. Vậy số lượng giá trị khác nhau nhiều nhất của dãy số là $2.\sqrt{n}$.
• Đối với ý thứ hai, ta chứng minh đơn giản vì dãy số Harmonic có tổng tiến tới $\log(n) + \gamma,$ nên dãy số ban đầu sẽ có tổng xấp xỉ bằng $n.\log(n) + n.\gamma \approx n.\log(n)$.

Bổ đề Harmonic chỉ được sử dụng trong một số bài toán rất đặc biệt, chẳng hạn như tính tổng các ước nguyên dương của mọi số từ $1$ tới $N$. Nhìn chung, các định lý, bổ đề trong Tin học sẽ ít khi gặp trong bài thi, chỉ trong một vài bài toán rất cụ thể thì mới phải dùng đến chúng mà thôi.

5. Tìm biểu diễn thập phân của một số hữu tỉ

Chúng ta đều biết rằng, một số hữu tỉ là số có thể biểu diễn được dưới dạng phân số $\frac{a}{b},$ với $a$ và $b$ là các số nguyên với $b \ne 0$. Khi biểu diễn số hữu tỉ dưới hệ cơ số $10,$ ta có hai dạng là số thập phân hữu hạn và số thập phân vô hạn tuần hoàn. Dưới đây ta có hai tính chất quan trọng của số hữu tỉ:

• Một phân số tối giản với mẫu dương và mẫu không có ước nguyên tố nào ngoài $2$ và $5$ thì viết được dưới dạng số thập phân hữu hạn. Ví dụ như $\frac{4}{25}$ có mẫu $25=5^2$ nên $\frac{4}{25}=0.16$. Một số thập phân hữu hạn cũng có thể coi là một số thập phân vô hạn tuần hoàn với chu kỳ là $0$.
• Một phân số tối giản với mẫu dương và mẫu có ít nhất một ước nguyên tố ngoài $2$ và $5$ thì viết được dưới dạng số thập phân vô hạn tuần hoàn.

Bài toán đặt ra ở đây là làm sao tìm được chu kỳ của số thập phân vô hạn tuần hoàn khi biết dạng phân số của nó là $\frac{a}{b}$, nếu như ta coi số thập phân hữu hạn cũng là số thập phân vô hạn tuần hoàn với chu kỳ là $0$. Dưới đây mình sẽ giới thiệu một phương pháp của trung học cơ sở:

• Bước $1$: Đặt phép $a$ chia $b,$ ghi nhận thương nguyên ở lần chia đầu tiên. Thương này là phần nguyên của số thập phân. Kế đến tiếp tục đặt phép chia với số dư của phép chia đàu tiên, lưu các thương và số dư ở mỗi lần chia tiếp theo vào hai mảng phân biệt.
• Bước $2$: Lặp lại liên tục quá trình chia $a$ cho $b$ giống như phép chia số thập phân: Lấy số dư nhân thêm $10$ rồi chia cho $b,$ tiếp tục lưu thương và số dư của phép chia mới và lại lặp lại quá trình,…
• Bước $3$: Lặp lại bước $2$ cho tới khi thấy số dư bị lặp lại. Gọi vị trí xuất hiện đầu tiên của số dư này trên dãy số dư là $x,$ thì chu kỳ của số thập phân sẽ bắt đầu từ vị trí $x$ trên dãy thương cho tới hết dãy thương. Còn các chữ số nằm trước vị trí $x$ trên dãy thương sẽ là các chữ số thập phân tự do.

Ví dụ: Giả sử phân số là $\frac{1}{14}$. Đầu tiên thực hiện phép chia có dư, thu được phần nguyên là $0,$ số dư là $1$. Gọi thương và số dư của các phép chia tiếp theo lần lượt là $k$ và $r,$ quy trình để tìm ra biểu diễn thập phân của nó là:

• Lần chia thứ nhất: $k = 0, r = 1$.
• Lần chia thứ hai: $k = 7, r = 2$.
• Lần chia thứ ba: $k = 1, r = 6$.
• Lần chia thứ tư: $k = 4, r = 4$.
• Lần chia thứ năm: $k = 2, r = 12$.
• Lần chia thứ sáu: $K = 8, r = 8$.
• Lần chia thứ bảy: $k = 5, r = 10$.
• Lần chia thứ tám: $k = 7, r = 2$ (số dư bị lặp lại ở vị trí $2,$ không lưu thương này mà tính luôn chu kỳ). Số thập phân lúc này sẽ là: $0.0(714285)$.

Cài đặt:

void decimal_presentation(int a, int b)
{
    cout << a / b << '.'; // Đưa ra phần nguyên trước.

    int pos = 0;
    mark[a % b] = pos++; // Mảng mark lưu vị trí xuất hiện của các số dư.
    a %= b; // Đặt a = a % b để tiếp tục phép chia.

    int loop_start = 0;
    vector < int > quotient; // Vector lưu các thương.
    while (true) // Tiếp tục quá trình chia để tìm các số sau dấu chấm.
    {
        a *= 10;
        long long r = a % b;
        quotient.push_back(a / b);
        if (mark[r]) // Số dư bị lặp lại.
        {
            loop_start = mark[r]; // Vị trí bắt đầu chu kỳ.
            break;
        }
        else // Nếu chưa lặp lại thì tiếp tục chia và lưu số dư.
        {
            mark[r] = pos++;
            a = r; 
        }
    }

    // In ra biểu diễn thập phân của số hữu tỉ a/b.
    for (int i = 0; i < loop_start; ++i)
        cout << quotient[i];
    cout << '(';
    for (int i = loop_start; i < quotient.size(); ++i)
        cout << quotient[i];
    cout << ')';
}

6. Vài đẳng thức đáng lưu ý

Qua quá trình nghiên cứu và đúc kết từ các kỳ thi HSG Tin học các cấp và kinh nghiệm cá nhân, mình nhận thấy các dãy số với công thức có sẵn thường được áp dụng rất nhiều trong các bài toán về chủ đề Số học trong Tin học. Tất nhiên, không ai cho các bạn một dãy số rồi bắt tìm công thức của nó cả, nhưng những dãy số sẽ được lồng ghép vào các bài toán lớn để gây khó khăn cho người giải ở những bước tìm kết quả cuối cùng. Vì vậy, mình đã tổng hợp những dãy số rất hữu ích có thể sử dụng trong lập trình thi đấu, hy vọng nó đủ dùng. Các dãy số chủ yếu sẽ có được công thức từ việc chứng minh quy nạp hoặc biến đổi theo phương pháp của THCS, bạn đọc cố gắng đọc kĩ để hiểu được thì sẽ nhớ rất lâu!

5.1. $1^2 + 2^2 + 3^2 + \cdots + n^2=\frac{n(n+1)(2n+1)}{6}$

Chứng minh: Sử dụng quy nạp toán học:

• Với $n=1,$ ta thấy $1^2=\frac{1(1+1)(2+1)}{6}=1,$ đẳng thức đúng.
• Giả sử đẳng thức đúng với $n=k,$ tức là $1^2 + 2^2 + 3^2 + \cdots + k^2=\frac{k(k+1)(2k+1)}{6} \cdot$
• Chứng minh đẳng thức đúng với $k+1$: $1^2 + 2^2 + \cdots + k^2 + (k+1)^2$. $= \frac{k(k + 1)(2k + 1)}{6} + (k+1)^2$ (Do giả thiết quy nạp). $= \frac{1}{6}\cdot(k+1).[k(2k+1)+6(k+1)]$. $= \frac{1}{6}\cdot (k+1).(2k^2+7k+6)$. $= \frac{1}{6}\cdot(k+1).(k+2).(2k+3)$. $= \frac{1}{6}\cdot(k+1).[(k+1)+1].[2(k+1)+1]$ (điều phải chứng minh).

Vậy đẳng thức đúng với mọi $n \in N^{*}$.

5.2. $1^3 + 2^3 + \cdots + n^3=(1+2+\cdots+n)^2$

Chứng minh:

• Với $n=1,$ ta có $1^3=1^2,$ đẳng thức đúng.
• Giả sử đẳng thức đúng với $n=k,$ tức là $1^3+2^3+\cdots + k^3=(1+2+\cdots+k)^2$.
• Chứng minh đẳng thức đúng với $n=(k+1)$: $1^3+2^3 + \cdots + k^3 + (k+1)^3$. $=(1+2+\cdots+k)^2 + (k+1)^3$. $=(\frac{k(k+1)}{2})^2 + (k+1)^3$. Giờ ta cần chứng minh: $(\frac{k(k+1)}{2})^2 + (k+1)^3=(\frac{(k+1)(k+2)}{2})^2 \ (1)$. Thật vậy, ta có: $(1)\Leftrightarrow (k^2+3k+2)^2-(k^2+k)^2=4.(k+1)^3$ $\Leftrightarrow 4k^3 +12k^2 + 12k + 4 = 4.(k+1)^3$ $\Leftrightarrow 4.(k+1)^3 = 4.(k+1)^3,$ đẳng thức đúng.

Vậy đẳng thức (1) đúng với $n=k+1,$ đồng nghĩa với việc đẳng thức ban đầu đúng với $\forall n\in N^{*}$.

5.3. $1+3+5+ \cdots + (2n-1)=n^2$

Chứng minh:

• Với $n=1,$ ta có $1=1^2,$ đẳng thức đúng.
• Giả sử đẳng thức đúng với $n=k,$ tức là $1+3+5+...+(2k-1)=k^2$.
• Chứng minh đẳng thức đúng với $n=(k+1)$: $1+3+5+ \cdots + (2k-1)+[2(k+1)-1]=(k+1)^2$. Thật vậy, ta có: $1+3+5+ \cdots + (2k-1)+[2(k+1)-1]$ $=k^2+[2(k+1)-1]$ (Do giả thiết quy nạp). $=k^2+2k+1$. $=(k+1)^2$.

Vậy ta có điều phải chứng minh, đẳng thức đúng với $\forall n \in N^{*}$.

5.4. $2+5+8+ \cdots + (3n-1)=\frac{n.(3n+1)}{2}$

Chứng minh:

• Với $n=1,$ ta có $2=\frac{1.4}{2},$ đẳng thức đúng.
• Giả sử đẳng thức đúng với $n=k,$ tức là $2+5+8+...+(3k-1)=\frac{k.(3k+1)}{2}$.
• Chứng minh đẳng thức đúng với $n=(k+1)$: $2+5+8+ \cdots + (3k-1)+[3(k+1)-1]=\frac{(k+1).[3.(k+1)+1]}{2}$. Thật vậy, ta có: $2+5+8+ \cdots + (3k-1)+[3.(k+1)-1]$. $=\frac{k.(3k+1)}{2}+[3.(k+1)-1]$ (Do giả thiết quy nạp). $=\frac{3k^2+7k+4}{2} \cdot$ $=\frac{3(k+1)(k+\frac{4}{3})}{2} \cdot$ $=\frac{(k+1).[3.(k+1)+1]}{2} \cdot$

Vậy ta có điều phải chứng minh, đẳng thức đúng với $\forall n \in N^{*}$.

IV. Bất đẳng thức

Các bất đẳng thức được ứng dụng nhiều nhất trong Toán học cũng như Tin học ở mức độ thi HSG sẽ là bất đẳng thức AM - GM và bất đẳng thức Bunyakovsky. Trong các bài toán số học, hai bất đẳng thức này sẽ có tác dụng rất lớn trong việc đặt cận cho bài toán, từ đó dễ dàng thực hiện các công việc liên quan tới đếm số lượng. Quá trình chứng minh của các bất đẳng thức này là thành quả toán học lâu dài và cũng không cần thiết cho bạn đọc nên mình xin phép không trình bày ở đây.

1. Bất đẳng thức AM - GM

Các bạn thường được biết đến bất đẳng thức này trong chương trình Toán trung học là bất đẳng thức Cauchy. Nhưng thực ra nó chỉ được chứng minh bởi Cauchy mà thôi, còn tên quốc tế của nó phải là Bất đẳng thức AM - GM, hay Bất đẳng thức trung bình cộng - trung bình nhân. Bất đẳng thức này được phát biểu như sau: "Trung bình cộng của $n$ số luôn luôn lớn hơn hoặc bằng trung bình nhân của chúng. Dấu bằng xảy ra khi và chỉ khi cả $n$ số đó bằng nhau":

$\frac{x_1 + x_2 + \cdots + x_n}{n} \ge {\sqrt[ {n}]{x_{1}.x_{2}...x_{n}}}$

$\text{Dấu "=" xảy ra } \Leftrightarrow x_1 =x_2=\cdots =x_n$

Bất đẳng thức này cũng hoàn toàn đúng trong trường hợp hai giá trị trung bình có hệ số: Với $n$ số $x_1, x_2,..., x_n$ và các hệ số $\alpha_1, \alpha_2,..., \alpha_n,$ nếu đặt $\alpha=\alpha_1 + \alpha_2 + \cdots + \alpha_n$ thì:

$\frac{\alpha_1x_1 + \alpha_2x_2 + \cdots + \alpha_nx_n}{\alpha} \ge {\sqrt[ {\alpha}]{x_1^{\alpha_1}.x_2^{\alpha_2}...x_n^{\alpha_n}}}$

$\text{Dấu "=" xảy ra } \Leftrightarrow x_1 =x_2=\cdots =x_n$

2. Bất đẳng thức Bunyakovsky

Là dạng cơ bản của bất đẳng thức Cauchy - Schwarz, một bất đẳng thức được áp dụng trong nhiều lĩnh vực của Toán học. Dưới đây là dạng tổng quát của bất đẳng thức Bunyakovsky cho hai bộ số $(a_1, a_2,..., a_n)$ và $b_1, b_2,..., b_n$:

$(a_1^2+a_2^2 +\cdots + a_n^2)(b_1^2 + b_2^2 + \cdots + b_n^2) \ge (a_1b_1 + a_2b_2 + \cdots + a_nb_n)^2$

$\text{Dấu "=" xảy ra } \Leftrightarrow \frac{a_1}{b_1}=\frac{a_2}{b_2}=\cdots \frac{a_n}{b_n}. \text{ Quy ước nếu }b_i = 0 \text{ thì } a_i=0.$

V. Lời kết

Như vậy, chúng ta đã cùng nhau tìm hiểu những công thức, định lý rất thú vị và hữu ích trong Toán học có thể ứng dụng trong Tin học. Tuy nhiên, đó không phải là tất cả. Toán học là một chủ đề cực kỳ rộng lớn và chắc chắn không thể tóm gọn trong vài trang giấy. Vì vậy, trên đây chỉ là một phần rất nhỏ những thứ có thể giúp ích cho các bạn học sinh trong quá trình rèn luyện Thuật toán mà thôi.

Những bài tập của công thức Toán học rất phong phú, phần nhiều sẽ xuất phát từ những công thức rất đơn giản, chỉ cần biến đổi một chút là thu được kết quả. Vì vậy, trước khi suy nghĩ đến những công thức quá phức tạp, bạn đọc hãy tìm cách tạo ra công thức Toán học thông qua những biến đổi thông thường như giải phương trình, chuyển vế đổi dấu hay nhân phá ngoặc,...rất có thể sẽ giúp các bạn tìm ra đáp án bài toán nhanh chóng.

Cuối cùng, hãy chịu khó rèn luyện thật nhiều các bài toán số học để tăng cường khả năng tư duy và mở rộng tầm hiểu biết của bản thân về các công thức toán học. Nơi luyện tập phù hợp nhất chính là thông qua các kỳ thi trên trang web codeforces.com.

VI. Tài liệu tham khảo

• https://codeforces.com/blog/entry/55912
• https://toanhoc247.com/ly-thuyet-va-bai-tap-ve-phuong-phap-quy-nap-toan-hoc-a10798.html
• https://codeforces.com/blog/entry/51272
• https://vnoi.info/wiki/translate/he/Number-Theory-4.md
• https://www.geeksforgeeks.org/eulers-totient-function/
• https://www.geeksforgeeks.org/legendres-formula-highest-power-of-prime-number-that-divides-n/
• https://www.geeksforgeeks.org/largest-power-k-n-factorial-k-may-not-prime/
• https://vi.wikipedia.org/wiki/Bất_đẳng_thức_Cauchy–Schwarz