CÁC BÀI TOÁN TỔ HỢP TRÊN DÃY SỐ
Thầy Lê Phúc Lữ
(Lớp Cao học Khoa học tự nhiên TP.HCM)
Trong bài viết nhỏ này, chúng ta sẽ cùng xét khía cạnh tổ hợp của dãy số nguyên; khi cần đếm số lượng dãy thỏa mãn một điều kiện cho trước nào đó. Các phương pháp thường gặp: truy hồi, xuống thang, cực hạn, phản chứng, …
1. Các bài toán chọn lọc
Bài tập 1.1: Tìm tất cả các bộ số nguyên dương $x_1,\ x_2,\ x_3,\ \ldots ,\ x_{2017}$ sao cho có thể đặt chúng lên vòng tròn theo thứ tự đó mà $6$ số liên tiếp bất kỳ đều có thể chia thành hai nhóm $3$ có tổng bằng nhau.
Giải
Dùng phương pháp xuống thang.
Ta có $x_i+x_{i+1}+x_{i+2}+x_{i+3}+x_{i+4}+x_{i+5} \equiv 0 \pmod{2}$ với mọi $i=1,2,3,\ldots ,2017$ nên $x_i \equiv x_{i+6}$ với mọi $i.$
Vì $(6,2017)=1$ nên suy ra tất cả các số có cùng tính chẵn lẻ. Ta xét phép biến đổi dãy số sau:
- Nếu tất cả các số cùng chẵn thì thay bằng $y_i=\dfrac{x_i}{2}$.
- Nếu tất cả các số cùng lẻ thì thay bằng $y_i=\dfrac{x_i+1}{2}$.
Dễ thấy dãy mới cũng thỏa và tổng $S=\sum\limits_{i=1}^{2017} a_i$ sẽ giảm ngặt nếu có một số nào đó trong dãy khác $1$; suy ra quá trình biến đổi sẽ dừng lại khi tất cả đều là $1$. Vì ta thu được một dãy toàn là $1$ nên dãy ban đầu có tất cả các số hạng bằng nhau.
Nhận xét: Bài toán trên có thể thay việc chia 2 nhóm thành $3,4,5,\ldots $ nhóm và vẫn giải được bằng cách tương tự. Ta xét các bài tương tự sau:
Bài tập 1.2 (APMO 2017): Bộ năm số nguyên là tốt nếu có thể đặt chúng là $a,b,c,d,e$ để $a-b+c-d+e=29.$ Tìm tất cả các bộ $2017$ số sao cho $5$ số liên tiếp bất kỳ trong chúng đều tốt.
Ở bài toán này, điểm khó là không biết các số đã cho có dương hay không; vì thể, đại lượng tổng ở trên không xét tiếp tục được.
Tuy nhiên, cách áp dụng vẫn tương tự như sau:
- Trừ tất cả các số của bộ cho $29$, ta thu được điều kiện tốt trở thành $a-b+c-d+e=0.$
- Tất cả các số đã cho cùng tính chẵn lẻ, và chính xác là cùng chẵn.
- Xét đại lượng $S=\sum\limits_{i=1}^{2017}{\left| \frac{{{a}_{i}}}{2} \right|}$ thì thông qua phép chia 2, tổng này giảm ngặt. Từ đó suy ra tất cả các số này phải là $0$ và tất cả ban đầu phải là $29.$
Bài tập 1.3 (VMO 2014): Tìm tất cả các bộ số $2014$ số hữu tỷ không âm sao cho nếu bỏ đi bất kỳ số nào trong chúng thì các số còn lại có thể được chia thành $3$ nhóm rời nhau, mỗi nhóm có $671$ số sao cho tích các số trong mỗi nhóm là bằng nhau.
Bài này khó hơn vì: số hữu tỷ chứ không nguyên, tích chứ không phải tổng, … Ta lần lượt giải quyết điều đó như sau:
- Quy đồng mẫu để đưa về số nguyên.
- Xét số mũ của 1 ước nguyên tố để đưa về tổng.
- Chú ý thêm trường hợp số 0 (nếu có 1 số thì phải có ít nhất 4 số).
Bài tập 1.4: Cho dãy số nguyên dương $({{a}_{n}})$ thỏa mãn:
$i)$ Gồm các số phân biệt nhau.
$ii)$ Với mọi $n$ thì ${{a}_{n}}\ge n.$
$iii)$ $a_1=5,\ a_2=4,\ a_3=3$.
a) Chứng minh rằng tồn tại $n>2017$ sao cho $a_n \ne n+1$?
b) Giả sử $a_n=n+2$ với mọi $n>2017$, hỏi có tất cả bao nhiêu dãy số như thế?
Giải
a) Bài toán có thể giải quyết dễ dàng bằng phản chứng và Dirichlet. Thật vậy, nếu ${{a}_{n}}=n+1$ với mọi $n>2017$ thì các số hạng ${{a}_{4}}\to {{a}_{2017}}$ sẽ nhận các giá trị trong tập hợp $6\to 2018$. Khi đó, sẽ có hai số hạng bằng nhau, không thỏa.
b) Nếu đã có ${{a}_{n}}=n+2$ với mọi $n>2017$ thì các số hạng ${{a}_{4}}\to {{a}_{2017}}$ sẽ nhận các giá trị trong tập hợp $6\to 2019.$ Nhận xét:
- ${{a}_{2017}}\in \left\{ 2017,2018,2019 \right\}$ nên có $3$ cách chọn.
- ${{a}_{2016}}\in \left\{ 2016,2017,2018,2019 \right\}$ nhưng vì ${{a}_{2017}}$ đã lấy một số nên cũng còn $3$ cách chọn.
- Tương tự, đến ${{a}_{6}}$ vẫn có $3$ cách chọn. Còn lại ${{a}_{5}}$ có $2$ cách chọn và ${{a}_{4}}$ có $1$ cách chọn.
Theo nguyên lý nhân, ta có $2\cdot {{3}^{2012}}$ dãy thỏa mãn.
Bài tập 1.5: Xét lục giác $ABCDEF$ có độ dài cạnh là $1$ được điền các số như hình vẽ
Một con ếch xuất phát từ $A$ và nhảy đến các đỉnh sao cho mỗi bước nhảy đều có độ dài nguyên. Hành trình của ếch là dãy các tên đỉnh mà ếch đã nhảy qua; và hai hành trình được coi là khác nhau nếu ở một lần thứ $k$ nào đó, đỉnh mà ếch nhảy đến ở hai hành trình là khác nhau.
Gọi $m$ là số hành trình ếch nhảy sao cho tổng các số mà nó nhảy qua là $2017$. Chứng minh rằng $m$ không phải là số chính phương.
Giải
Ta thấy $ACE$ và $BDF$ là hai tam giác đều có cạnh là $\sqrt{3}$ nên mỗi lần, ếch sẽ nhảy từ tam giác đều này đến tam giác đều kia.
Chia nhóm:
- $I=(A,C,E)$ tương ứng với các số $(0,0,1)$.
- $II=(B,D,F)$ tương ứng với $(1,1,2)$.
Ta thấy $\left\{ x+y|x\in I,y\in II \right\}=\left\{ 1,1,1,1,2,2,2,2,3 \right\}$ chứng tỏ tổng các số trên hai bước nhảy liên tiếp của ếch sẽ nhận giá trị là $4$ số $1$, $4$ số $2$ và $1$ số $3.$ Nếu gọi ${{s}_{n}}$ là số hành trình của ếch có tổng là $n$ thông qua chẵn bước thì
$${{s}_{n}}=4{{s}_{n-1}}+4{{s}_{n-2}}+{{s}_{n-3}}.$$
Một cách tương tự, gọi ${{t}_{n}}$ là số hành trình của ếch có tổng là $n$ thông qua lẻ bước thì công thức truy hồi vẫn thế (chỉ khác ở các số hạng đầu).
Vì vậy nên nếu gọi ${{u}_{n}}={{s}_{n}}+{{t}_{n}}$ là số hành trình của ếch có tổng là $n$ thì
$${{u}_{n}}=4{{u}_{n-1}}+4{{u}_{n-2}}+{{u}_{n-3}} \text{ với } n\ge 3.$$
Ta có ${{u}_{0}}=1,{{u}_{1}}=6,{{u}_{2}}=28$ và từ công thức truy hồi thì $m={{u}_{2017}}\equiv {{u}_{1}}\equiv 2 \pmod{4}$ nên $m$ không thể là số chính phương, ta có đpcm.
Nhận xét: Bài toán có thể giải bằng cách gọi $6$ dãy truy hồi $a_n,\ b_n,\ c_n,\ d_n,\ e_n,\ f_n$ chỉ số hành trình của ếch có tổng là $n$ và kết thúc tại $A,B,C,D,E,F$. Tuy nhiên, cách tiếp cận đó khá phức tạp, đòi hỏi phải khai thác nhiều các liên hệ giữa các đường đi.
Một bài toán tương tự:
Bài tập 1.6 (Ả Rập TST 2017): Người ta đặt các số $1,2,3,4$ trên vòng tròn theo thứ tự đó. Một con kiến xuất phát từ số $1$ và ở mỗi bước, nó sẽ bò qua số bên cạnh. Hỏi con kiến có bao nhiêu cách bò sao cho tổng tất cả các số mà nó bò qua (kể cả số ban đầu) bằng 21?
Tương tự bài trên, ta cũng tìm được hệ thức truy hồi là $s_n=s_{n-3}+2s_{n-5}+s_{n-7}$. Từ đó tính được $s_{21}=167.$
Bài tập 1.7: Đếm số dãy số nguyên dương $\left( a_1,\ a_2,\ \ldots ,\ a_{12}\right) $ thỏa mãn các điều kiện sau:
a) $1\le a_1 \le a_2 \le \ldots \le a_{12} \le 2017$
b) $a_i \equiv i^2 (\bmod 12)$.
Giải
Theo giả thiết, ta có
${{a}_{1}}\equiv {{a}_{5}}\equiv {{a}_{7}}\equiv {{a}_{11}}\equiv 1\text{ }(\bmod 12) $
$ {{a}_{2}}\equiv {{a}_{4}}\equiv {{a}_{8}}\equiv {{a}_{10}}\equiv 4\text{ }(\bmod 12) $
$ {{a}_{3}}\equiv {{a}_{9}}\equiv 9\text{ }(\bmod 12) $
$ {{a}_{6}}\equiv {{a}_{12}}\equiv 0\text{ }(\bmod 12) $
Đặt ${{a}_{i}}=12{{b}_{i}}+{{r}_{i}}$ với $i=1,2,3,\ldots ,12$ và ${{r}_{i}}$ là số dư tương ứng đã chỉ ra ở trên.
Do tính không giảm của dãy nên ta phải có
$$0\le {{b}_{1}}\le {{b}_{2}}\le {{b}_{3}}<{{b}_{4}}<{{b}_{5}}<{{b}_{6}}\le {{b}_{7}}\le {{b}_{8}}\le {{b}_{9}}<{{b}_{10}}<{{b}_{11}}<{{b}_{12}}\le 168.$$
Từ đó suy ra
$0\le {{b}_{1}}<{{b}_{2}}+1<{{b}_{3}}+2<{{b}_{4}}+2<{{b}_{5}}+2<{{b}_{6}}+2\le {{b}_{7}}+3\le {{b}_{8}}+4\le {{b}_{9}}+5 $
$<{{b}_{10}}+5<{{b}_{11}}+5<{{b}_{12}}+5\le 173 $
Do các số liệt kê ở trên đều phân biệt và thuộc $[0;173]$ nên số cách chọn một bộ như thế là $C_{174}^{12}$. Đó cũng chính là số dãy cần tìm.
Nhận xét: Điều kiện thứ hai có thể thay bằng một hàm số tùy ý theo $i$ chứ không nhất thiết phải là ${{i}^{2}}$, cách giải vẫn tương tự như trên.
Bài tập 1.8: Hỏi có bao nhiêu hoán vị $a_1,\ a_2,\ …,\ a_{2017}$ của $2017$ số nguyên dương đầu tiên thỏa mãn đồng thời các điều kiện sau:
$i)$ $a_{i+1}-a_i\le 1$ với mọi $i=1,2,3,\ldots,2016.$
$ii)$ Có đúng một chỉ số $i$ với $1\le i\le 2017$ sao cho $a_i=i$?
Giải
Trước hết, ta sẽ chứng minh nhận xét rằng số hoán vị của $n$ số nguyên dương đầu tiên thỏa mãn điều kiện i), gọi là hoán vị đẹp, sẽ là ${{2}^{n-1}}$. Thật vậy,
- Đầu tiên, ta đặt số $1$ vào hoán vị.
- Số $2$ có thể xếp trước hoặc sau số $1$, có $2$ cách.
- Số $3$ có thể xếp vào đầu dãy hoặc ngay sau số $2$ đã xếp trước đó, có $2$ cách.
- Số $4$ có thể xếp vào đầu dãy hoặc ngay sau số $3$ đã xếp trước đó, cũng có $2$ cách. Cứ như thế cho đến $n.$
Do đó, có tất cả ${{2}^{n-1}}$ cách xếp, tương ứng vời ${{2}^{n-1}}$ hoán vị.
Tiếp theo, giả sử ta có ${{a}_{i}}=i$.
Khi đó ${{a}_{i+1}}\le {{a}_{i}}+1=i+1$, nhưng không thể có ${{a}_{i+1}}=i+1$ (do chỉ có 1 chỉ số thỏa mãn ii) nên ${{a}_{i+1}}\le i$, mà ${{a}_{i}}=i$ nên ${{a}_{i+1}}\le i-1$. Tiếp theo, ${{a}_{i+2}}\le {{a}_{i+1}}+1\le i$ nên ${{a}_{i+2}}\le i-1$.
Do đó, các số từ ${{a}_{i+1}}$ đến ${{a}_{2017}}$ nhận giá trị không vượt quá $i-1$.
Lập luận tương tự, các số từ ${{a}_{1}}$ đến ${{a}_{i-1}}$ phải nhận giá trị không nhỏ hơn $i+1.$
Do đó, hai đoạn hoán vị phía trước và phía sau ${{a}_{i}}$ phải có độ dài bằng nhau, tức là ${{a}_{1009}}=1009$ là số ở giữa.
Rõ ràng các hoán vị phía trước và phía sau $1009$ đều phải là hoán vị đẹp và được sắp xếp độc lập với nhau.
Vậy số hoán vị cần tìm là ${{\left( {{2}^{1007}} \right)}^{2}}={{2}^{2014}}.$
Nhận xét: Nếu đề đổi số $2017$ thành $2018$ thì sẽ tồn tại hai chỉ số $i$ như trên và chúng sẽ cách đều hai đầu $1$ và $2018$. Khi đó, đoạn ở giữa cũng sẽ cố định, tức là có $i<j$ để
${{a}_{k}}=k$ với mọi $k=i,i+1,\ldots ,j$ và $i+j=2019.$
Phần trước $i$ và phần sau $j$ sẽ đổi chỗ cho nhau với số cách xếp là ${{({{2}^{i-1}})}^{2}}$.
Bài tập 1.9: Cho dãy các số nguyên dương $(u_n)$ thỏa mãn điều kiện
$0\le u_{m+n}-u_m-u_n \le 1$ với mọi $m,n\in \mathbb{Z}^+$.
Chứng minh rằng tồn tại $a\in \mathbb{R}^+$ sao cho $-1\le u_n-\left[ an \right]\le 1$ với mọi $n=1,2,3,\ldots ,2017.$
Giải
Ta đưa điều cần chứng minh về
$$\frac{{{u}_{n}}}{n}<a<\frac{{{u}_{n}}+1}{n}.$$
Đến đây, gọi
$$m=\min \left\{ \left. \frac{{{u}_{n}}+1}{n} \right|n=1,2,3,\ldots ,2017 \right\}$$ và
$$M=\max \left\{ \left. \frac{{{u}_{n}}}{n} \right|n=1,2,3,\ldots ,2017. \right\}$$
Cần chỉ ra $m>M$ rồi chọn số $a$ nằm giữa $(m,M)$ là xong. Gọi $p,q$ lần lượt là các chỉ số nhỏ nhất để có dấu bằng xảy ra ở các đánh giá trên. Khi đó
${{u}_{p}}+1=pm$ và ${{u}_{q}}=Mq.$
Ngoài ra, ${{u}_{k}}+1>km,\forall k<p$ và ${{u}_{k}}<kq,\forall k<q.$
- Nếu $p=q$ thì hiển nhiên đúng.
- Nếu $p>q$, ta đặt $p=q+k$ thì $k<p$ nên ${{u}_{k}}+1>km$, vì ${{u}_{p}}\ge {{u}_{q}}+{{u}_{k}}$ (theo giả thiết) nên $pm-1>Mq+km-1\Leftrightarrow m>M.$
- Nếu $p<q$ thì cũng chứng minh tương tự với chú ý rằng ${{u}_{q}}\le {{u}_{p}}+{{u}_{k}}+1.$
Nhận xét: Nếu đề bài đổi giả thiết thành $0\le u_{m+n}-u_m-u_n\le 2$,
ta sẽ cần đến hai số $a,b$ sao mới thỏa mãn được kết luận (vì khoảng chênh lệch của các số hạng rộng hơn một tí), cụ thể là tồn tại $a,b>0$ để
$$-1\le u_n-\left[ an \right]-\left[ bn \right]\le 1.$$
Ở bài toán trên, ta còn chứng minh được một kết quả mạnh hơn là tồn tại $a$ để $u_n=[an]$ với mọi $n.$ Một bài toán tương tự trong đề trường Đông miền Trung:
Bài tập 1.10: Cho hàm số $f:\mathbb{R}\to \mathbb{R}$ thỏa mãn $\left| f(x+y)-f(x)-f(y) \right|\le 1,\forall x,y\in \mathbb{R}$. Chứng minh rằng tồn tại hàm cộng tính $g:\mathbb{R}\to \mathbb{R}$ thỏa mãn $\left| f(x)-g(x) \right|\le 1,\forall x.$
Đây có thể nói là một phiên bản trên $\mathbb{R}$ của bài toán trên (thay vì xét trên $\mathbb{N}$).
Tiếp theo, ta xét lớp các bài toán sử dụng một định lý thú vị trong dãy số, số học. Trước hết, ta xét định lý Beatty với nội dung như sau:
Cho hai số vô tỷ dương $\alpha ,\beta $. Xét hai dãy số:
- $[\alpha ],[2\alpha ],[3\alpha ],\ldots $ tạo thành dãy $A.$
- $[\beta ],[2\beta ],[3\beta ],\ldots $ tạo thành dãy $B.$
Khi đó $\dfrac{1}{\alpha }+\dfrac{1}{\beta }=1$ khi và chỉ khi $A,B$ là phân hoạch của $\mathbb{Z}^+$.
Chứng minh
Định lý này có thể chứng minh bằng cách sử dụng các BĐT về phần nguyên. Dưới đây là cách chứng minh cho chiều đảo:
Với mỗi số nguyên dương $k$, gọi $m,n$ là các số nguyên dương thỏa mãn
$$[m\alpha ]\le k<[(m+1)\alpha ] \text{ và } [n\beta ]\le k<[(n+1)\beta ].$$
Đặt $A=\{[i\alpha ],1\le i\le m\}$ và $B=\{[j\beta ],1\le j\le n\}$ thì $\left| A \right|=m,\left| B \right|=n$ và $A,B$ là phân hoạch của tập hợp $\left\{ 1,2,3,\ldots ,k \right\}$ theo định nghĩa của đề bài.
Do đó $m+n=k$. Theo bất đẳng thức phần nguyên thì $m\alpha -1<k<(m+1)\alpha $ nên $\dfrac{m}{k+1}<\dfrac{1}{\alpha }<\dfrac{m+1}{k}$.
Tương tự $\dfrac{n}{k+1}<\dfrac{1}{\beta }<\dfrac{n+1}{k}.$
Suy ra $$\dfrac{m+n}{k+1}<\dfrac{1}{\alpha }+\dfrac{1}{\beta }<\dfrac{m+n+2}{k} \text{ hay } \dfrac{k}{k+1}<\dfrac{1}{\alpha}+\dfrac{1}{\beta }<\dfrac{k+2}{k}.$$
Cho $k\to +\infty $, ta thu được $\dfrac{1}{\alpha }+\dfrac{1}{\beta }=1.$
Bài tập 1.11: Hai dung dịch $A,B$ có đặc điểm: số đo thể tích của $1$ kg $A$ bằng số đo khối lượng của $1$ lít $B.$ Ngoài ra, $p$ lít $A$ nặng bằng $q$ lít $B$ với $p,q$ nguyên tố khác nhau. Mỗi dung dịch được chia cho vào các bình nhỏ giống nhau, cùng chứa $1$ lít và vỏ nặng $1$ kg. Chứng minh rằng có đúng một cách ghép các bình cùng loại ($A$ hoặc $B$) lại với nhau mà khối lượng của chúng thuộc khoảng $(2017;2018).$
Giải
Gọi $x,y$ lần lượt là khối lượng riêng của các dung dịch thì $\dfrac{1}{x}=1\cdot y,px=qy$ nên $x=\sqrt{\dfrac{q}{p}},y=\sqrt{\dfrac{p}{q}}.$
Khối lượng mỗi bình là $\alpha =1+\sqrt{\dfrac{q}{p}},\beta =1+\sqrt{\dfrac{p}{q}}$. Dễ thấy $\dfrac{1}{\alpha }+\dfrac{1}{\beta }=1$, thỏa mãn định lý Beatty.
Suy ra hai dãy $[m\alpha ],[n\beta ]$ là phân hoạch của số nguyên dương nên ta có đpcm.
Bài tập 1.12 (APMO 2006): Với mỗi số nguyên dương $n$, gọi $a_n,\ b_n$ lần lượt là số cách viết $10^n$ trong hệ nhị phân, ngũ phân. Chứng minh rằng $(a_n),(b_n)$ là phân hoạch của $\mathbb{Z}^+ \backslash \{1\}.$
Giải
Để giải bài này, chú ý rằng: số chữ số của $M$ trong hệ $p$ phân là $[{{\log }_{p}}M]+1$.
Ngoài ra, $\alpha ={{\log }_{2}}10,\beta ={{\log }_{5}}10$ thỏa mãn điều kiện của định lý Beatty.
Từ đó, ta có một nhận xét thú vị rằng: tổng số chữ số của ${{2}^{n}}$ và ${{5}^{n}}$ trong hệ thập phân là $n+1.$
Bài tập 1.13 (VN TST 2000): Cho số nguyên dương $k$. Dãy số $(u_n)$ xác định bởi: $u_1=1$ và $u_{n+1}$ là số nguyên dương nhỏ nhất không thuộc tập hợp
$$\left\{ u_1,\ u_2,\ \ldots ,\ u_n,\ u_1+k,\ u_2+2k,\ \ldots ,\ u_n+nk \right\}.$$
Chứng minh rằng tồn tại $\alpha $ vô tỷ dương sao cho $u_n=\left[ n\alpha \right]$ với mọi $n.$
Giải
Để giải bài toán này, ta xét đa thức $P(x)={{x}^{2}}+(k-2)x-k$ với $k$ là số nguyên dương đã cho thì $P(x)$ có hai nghiệm phân biệt trái dấu. Hơn nữa, ${{\Delta }_{P(x)}}={{(k-2)}^{2}}+4k={{k}^{2}}+4$, không thể là số chính phương với bất kì số k nguyên dương nào nên hai nghiệm này đều là số vô tỉ. Ta thấy $$P(1)=1+(k-2)-k=-1<0,P(2)=4+2(k-2)-k=k>0$$ nên nghiệm dương của phương trình $P(x)=0$ thuộc khoảng $(1,2)$. Gọi nghiệm đó là $a.$
Đặt $b=a+k$ thì $a,b$ đều vô tỉ và $ab=a(a+k)={{a}^{2}}+ak=2a+k=a+b$ nên $\dfrac{1}{a}+\dfrac{1}{b}=1$.
Xét $f(n)=[na],g(n)=[nb]=f(n)+kn$ với $n$ là số nguyên dương.
Ta sẽ chứng minh rằng ${{x}_{n}}=f(n)$ bằng quy nạp. Thật vậy,
– Với $n=1$, khẳng định hiển nhiên đúng vì $1<a<2.$
– Giả sử ${{x}_{n}}=f(n)$ với mọi $n=1,2,3,…,m$. Ta sẽ chứng minh rằng ${{x}_{m+1}}=f({{x}_{m+1}})$.
Ta có $f(i)={{x}_{i}},g(i)=f(i)+ik={{x}_{i}}+ik$ với mọi $i=1,2,3,…,m$ nên ta có tập hợp
$H=\left\{ {{x}_{1}},{{x}_{2}},…,{{x}_{m}},{{x}_{1}}+k,{{x}_{2}}+2k,…,{{x}_{m}}+mk \right\} $
$ =\left\{ f(1),f(2),…,f(m),g(1),g(2),…,g(m) \right\} $
Rõ ràng $f(m+1)\notin H$ và $g(n)>f(n)$ với mọi $n$, $f(n)$ là hàm số đồng biến trên $\mathbb{N}*$ nên ta thấy rằng $f(m+1)$ chính là số tự nhiên nhỏ nhất không thuộc H. Theo định nghĩa dãy số $({{x}_{n}})$ đã cho thì ta có ${{x}_{m+1}}=f(m+1)$.
Do đó, khẳng định cũng đúng với $m+1.$ Theo nguyên lí quy nạp, ta có đpcm. Vậy số tự nhiên cần tìm chính là $a$ là nghiệm dương của phương trình ${{x}^{2}}+(k-2)x-k=0$.
Nhận xét: Đây là một kết quả có từ $1959$. Ta có thể phân tích cách tiếp cận như sau:
Xuất phát từ việc $\alpha =\sqrt{2},\beta =\sqrt{2}+2$ thỏa mãn điều kiện Beatty. Ta có hai dãy với công thức
$a_n=\left[ n\sqrt{2} \right],\ b_n=a_n+2n$ là phân hoạch của $\mathbb{Z}^+$.
Từ đó, để giấu dãy $b_n$ đi, ta chỉ cần xét $a_n+2n$.
Để ý $a_1=1,\ a_2=2,\ a_3=4,\ b_1=3,\ b_2=6,\ b_3=10$ nên $a_4$ có thể định nghĩa là số nguyên dương nhỏ nhất không thuộc $\left\{ a_1,\ a_2,\ a_3,\ a_1+2,\ a_2+4,\ a_3+6 \right\}$. Đó chính là cơ sở để có bài toán trên.
Bài tập 1.14 (Dãy Wythoff): Cho chuỗi $S_1=1$. Chuỗi $S_n$ được tạo thành từ chuỗi $S_{n-1}$ bằng cách thay $1\to 01$ và $0\to 1.$ Các chuỗi $S_1,\ S_2,\ S_3,\ \ldots $ được ghép liên tiếp lại với nhau thành một chuỗi vô hạn $L$. Gọi $a_n$ là vị trí của số $1$ thứ $n$ trong chuỗi $L.$ Chứng minh rằng tồn tại $\alpha $ vô tỷ dương sao cho $a_n=\left[ n\alpha \right],\forall n.$
Ở đây, ta có nhận xét rằng số $0$ thứ $n$ được sinh ra bởi số $1$ thứ $n$ nên nếu gọi $k_n$ là số các số $0$ đứng trước số $1$ thứ $n$ và $b_n$ là vị trí của số $0$ thứ $n,$ ta sẽ có $a_n=n+k_n$ và $b_n=2n+k_n$ nên $b_n=a_n+n$.
Chú ý rằng $(a_n),\ (b_n)$ chính là phân hoạch của $\mathbb{Z}^+$ nên dễ dàng tìm được $\alpha $ là nghiệm của $\dfrac{1}{\alpha }+\dfrac{1}{\alpha +1}=1$ hay $\alpha $ chính là tỷ số vàng.
Bài tập 1.15: Cho $n$ là số nguyên dương, hỏi có bao nhiêu dãy số $a_1,\ a_2,\ \ldots ,\ a_{2n}$ sao cho
$i)$ $a_i \in \left\{ -1,1 \right\}$ với $i=1,2,3,\ldots ,2n.$
$ii)$ $\left| \sum\limits_{i=2k+1}^{2l} a_i \right|\le 2$ với $0\le k<l\le n$?
Giải
Gọi $S$ là tập hợp các dãy thỏa mãn đề bài và đặt $\left| S \right|={{s}_{n}}$. Gọi $T$ là tập hợp tất cả các tổng các ${{a}_{i}}$ lấy từ chỉ số lẻ bất kỳ đến $2n.$ Theo giả thiết thì $T\subset \left\{ \pm 2,\pm 1,0 \right\}$, tuy nhiên, tất cả các tổng trong $T$ đều có chẵn số hạng mà mỗi số hạng đều là $\pm 1$ nên tất cả phải đều chẵn. Suy ra $T\subset \left\{ \pm 2,0 \right\}$.
Nếu trong $T$ chứa cả $2$ lẫn $-2$ thì giả sử $\sum\limits_{k=2i+1}^{2n}{{{a}_{k}}}=2$ và $\sum\limits_{k=2j+1}^{2n}{{{a}_{k}}}=-2$ với $i<j$ , khi đó
\[4=\sum\limits_{k=2i+1}^{2n}{{{a}_{k}}}-\sum\limits_{k=2j+1}^{2n}{{{a}_{k}}}=\sum\limits_{k=2i+1}^{2j}{{{a}_{k}}},\] mâu thuẫn.
Ứng với $({{a}_{1}},{{a}_{2}},\ldots ,{{a}_{2n}})\in S$, ta có phân loại sau:
- Tất cả các tổng trong $T$ đều là $0$, đặt số lượng dãy có tính chất này là ${{a}_{n}}$.
- Trong $T$ có chứa số $2$, đặt số lượng dãy có tính chất này là ${{b}_{n}}$.
- Trong $T$ có chứa số $-2$, đặt số lượng dãy có tính chất này là ${{c}_{n}}$.
Từ đó, ta dễ dàng chứng minh được hệ thức truy hồi
$ {{a}_{n+1}}=2{{a}_{n}} $
${{b}_{n+1}}={{a}_{n}}+2{{b}_{n}}+{{c}_{n}} $
$ {{c}_{n+1}}={{a}_{n}}+{{b}_{n}}+2{{c}_{n}} $
Chú ý rằng ${{a}_{n}}={{2}^{n}}$ và ${{a}_{n}}+{{b}_{n}}+{{c}_{n}}={{s}_{n}}$. Cộng hai công thức cuối lại, ta có
$${{b}_{n+1}}+{{c}_{n+1}}=2{{a}_{n}}+3({{b}_{n}}+{{c}_{n}})\Leftrightarrow {{s}_{n+1}}-{{2}^{n+1}}={{2}^{n+1}}+3({{s}_{n}}-{{2}^{n}})$$ hay
$${{s}_{n+1}}=3{{s}_{n}}+{{2}^{n}}\Leftrightarrow {{s}_{n+1}}+{{2}^{n+1}}=3({{s}_{n}}+{{2}^{n}}).$$
Với $n=1$, ta có $4$ dãy là $(1,1),(-1,-1),(-1,1),(1,-1)$ nên ${{s}_{1}}=4.$
Từ đẳng thức trên, ta có ${{s}_{n}}+{{2}^{n}}={{3}^{n-1}}({{s}_{1}}+{{2}^{1}})=2\cdot {{3}^{n}}$ nên ${{s}_{n}}=2\cdot {{3}^{n}}-{{2}^{n}}$.
Nhận xét: Bài toán thoạt nhìn có vẻ quen thuộc nhưng thật không đơn giản. Điều kiện đề cho là giá trị tuyệt đối của tất cả các tổng con từ vị trí lẻ đến vị trí chẵn bất kỳ đều không vượt quá $2$ buộc ta phải có đánh giá thích hợp mới có thể truy hồi được.
2. Bài tập áp dụng
Bài 1 (TP.HCM 2018): Hỏi có bao nhiêu hoán vị $(a_1,\ a_2,\ \ldots ,\ a_{164})$ của $164$ số nguyên dương đầu tiên sao cho $a_i \ne i$ và $ a_i \equiv i\text{ }(\bmod 41)$ với mọi $i=1,2,\ldots ,164?$
Bài 2: (Bài toán phát kẹo) Cô giáo có $10$ loại kẹo (mỗi loại có nhiều viên) và cần phát cho $30$ học sinh của lớp (một em nhận không quá $1$ viên/loại), giả sử rằng các em này có học lực đôi một khác nhau. Hỏi cô giáo có bao nhiêu cách phát kẹo, biết rằng nếu học sinh $A$ giỏi hơn $B$ thì $B$ có kẹo gì là $A$ có kẹo đó (tính cả trường hợp không em nào nhận được kẹo)?
Bài 3: (Bài toán con nhện) Một con nhện có $8$ cái chân, $8$ cặp vớ – giày khác nhau (vớ chỉ dùng chung với chiếc giày tương ứng). Con nhện có bao nhiêu thứ tự mang vớ và giày để sao cho trên cùng một chân, giày phải được mang vào sau vớ?
