Bài toán: Cho $n$ là số nguyên dương. Tìm số đa thức $P(x)$ có hệ số thực thuộc $\{ 0, 1, 2, 3\}$ thỏa mãn $P(2)=n$.
Lời giải: 
Giả sử: $$P(x)=a_0+a_1x+a_2x^2+a_3x^3+...., \; \text{với } a_i\in\{ 0, 1, 2, 3\}$$ Do $P(2)=n$ nên $$a_0+2a_1+4a_2+...+2^ia_i+...=n\;\;\;\;\;\;\;\;\;\;\;\;(*)$$ Ta xây dựng hàm sinh cho phương trình $(*)$: $$\begin{aligned} G(x)&=\prod_{i\ge 0}\left( 1+x^{2^k}+x^{2.{2^k}}+x^{3.2^k}\right)\\&=\prod_{i\ge 0}\dfrac{1-(x^{2^k})^4}{1-x^{2^k}}\\&=\prod_{i\ge 0}\dfrac{1-x^{2^{k+2}}}{1-x^{2^k}}\\&=\dfrac{1}{(1-x)(1-x^2)}\\&=\dfrac{1}{4(1-x)}+\dfrac{1}{4(1+x)}+\dfrac{1}{2(1-x)^2}=\sum_{i\ge 0}\left( \dfrac{1}{4}+\dfrac{1}{4}(-1)^i+\dfrac{1}{2}C^{i}_{i+1}\right) x^i\end{aligned}$$ Số đa thức thỏa mãn bài toán cũng chính là hệ số của $x^n$ trong khai triển trên: $$\left[\dfrac{2n+3+(-1)^n}{4}\right]=\left[\dfrac{n}{2}\right]+1$$

Bài toán: Xét tập $A=\{1;2;...;n\}$. Với bất kì tập con khác rỗng $M$ của $A$, $$M=\left \{ m_1;m_2,...,m_k \right \}, m_1 > m_2 > ... > m_k$$ Đặt $$S(M) = m_1 -  m_2 + m_3 +... + (-1)^{k+1}m_k$$ Tính $S = \sum_{M \subset A}S(M)$
Lời giải:
Ta ký hiệu lại như sau:
Tổng cần tính là $$S_n=\sum_{k=1}^n f(k,n)$$ với $f(k,n)$ là tổng đan dấu các phần tử của mỗi tập con, tất cả các tập con có $k$ phần tử của $A$ trong đó phần tử lớn nhất mang dấu $(+)$
Ta sẽ chứng minh $f(k,n)=\left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}\quad(k\le n)\qquad(1)$
Rồi từ đó suy ra tổng cần tính là:
$$\boxed{\displaystyle S_n=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}=n.2^{n-1}}$$
Ta chứng minh $(1)$ bằng quy nạp theo $k$.
Ta có:
$$f(1,n)=1+2+...+n=\frac{n(n+1)}{2}=\left\lfloor\frac{1+1}{2}\right\rfloor {n+1\choose 1+1}$$Như vậy $(1)$ đúng với $k=1$
Giả sử $(1)$ đúng đến $k-1$ thỏa $1\le k-1<n$, ta chứng minh $(1)$ cũng đúng với $k$.
Xây dựng phép đếm $f(k,n)$ theo các tập con có phần tử lớn nhất là $j$ với $k\le j\le n$
Do $j$ là số lớn nhất nên có ${j-1\choose k-1}$ tập con $k$ phần tử bắt đầu bởi $j$. Bớt đi số hạng $j$ trong các tập con $k$ phần tử, ta được các tập con $k-1$ phần tử với phần tử lớn nhất là $j-1$
Như vậy ta có: $$\begin{align*}f(k,n)&=\sum_{j=k}^n \left(j{j-1\choose k-1}-f(k-1,j-1)\right)\\&=\sum_{j=k}^n \left(k{j\choose k}-\left\lfloor\frac{k}{2} \right\rfloor{j\choose k}\right)\quad\\&=\left(k-\left\lfloor\frac{k}{2} \right\rfloor\right)\sum_{j=k}^n {j\choose k}\\&=\left\lfloor\frac{k+1}{2}\right\rfloor \sum_{j=k}^n \left[{j+1\choose k+1}-{j\choose k+1}\right]\quad\\&=\left\lfloor\frac{k+1}{2}\right\rfloor{n+1\choose k+1}\end{align*}$$Như vậy, $(1)$ được chứng minh
Bây giờ, ta sẽ chứng minh:
$$\boxed{\displaystyle S_n=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}=n.2^{n-1}}$$
Ta có:
$$\begin{align*}S_n&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor {n+1\choose k+1}&\\&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor\left[{n\choose k}+{n\choose k+1}\right]\\&=\sum_{k=1}^n \left\lfloor\frac{k+1}{2}\right\rfloor{n\choose k+1}+\sum_{k=1}^n\left(k-\left\lfloor\frac{k}{2}\right\rfloor\right){n\choose k}\\&=S_{n-1}+\sum_{k=1}^n k{n\choose k-1}-\sum_{k=1}^n\left\lfloor\frac{k}{2}\right\rfloor{n\choose k}&\\&=S_{n-1}+n\sum_{k=1}^n{n-1\choose k-1}-\sum_{k=0}^{n-1}\left\lfloor\frac{k+1}{2}\right\rfloor{n\choose k+1}\\&=S_{n-1}+n\sum_{k=0}^{n-1}{n-1\choose k}-S_{n-1}\\&=n2^{n-1}&\end{align*}$$ Bài toán được chứng minh.

Bài toán (VMO 2012) Cho một nhóm gồm $5$ cô gái xếp từ trái sang phải, kí hiệu là $G_1, G_2, G_3, G_4, G_5$ và $12$ chàng trai. Có $17$ chiếc ghế sắp thành một hàng ngang. Người ta xếp nhóm người đã ngồi vào các chiếc ghế đó sao cho:

        $1.$ Mỗi ghế có đúng một người ngồi.
        $2.$ Giữa $G_1$ và $G_2$ có ít nhất $3$ chàng trai.
        $3.$ Giữa $G_4$ và $G_5$ có ít nhất $1$ chàng trai và không quá $4$ chàng trai.

  Hỏi có bao nhiêu cách xếp như vậy.

Lời giải :
   Kí hiệu $x_i$ là vị trí ngồi của bạn gái thứ $i$, thế thì: $$\begin{cases}1\le x_1<x_2<x_3<x_4<x_5\le 17\\x_2-x_1>3, 1<x_4-x_3\le 5\end{cases}$$ Từ điều kiện $x_2-x_1>3\Rightarrow x_2-3>x_1$, khi đó, ta có: $$1\le x_1<x_2-3<x_3-3<x_4-3<x_5-3<14$$ Đặt $x_1=y_1$, $y_i=x_i-3,  i=\{2,3,4,5\}$ Ta được: $$\begin{cases}1\le y_1<y_2<y_3<y_4<y_5<14\\y_4-y_3=\{2, 3, 4, 5\}\end{cases}$$ Tới đây, ta có $4$ trường hợp:
  Trường hợp 1: $y_4-y_3=2$, khi đó: $$1\le y_1<y_2<y_3<y_5-2\le 12$$ Ở trường hợp này có $C_{12}^4$ cách xếp.

  Trường hợp 2: $y_4-y_3=3$, khi đó: $$1\le y_1<y_2<y_3<y_5-3\le 11$$ Trường hợp này có $C_{11}^4$ cách xếp.

 Trường hợp 3: $y_4-y_3=4$, khi đó: $$1\le y_1<y_2<_3<y_5-4\le 10$$ Trường hợp này có $C_{10}^4$ cách xếp.

 Trường hợp 4: $y_4-y_3=5$, khi đó: $$1\le y_1<y_2<y_3<y_5-5\le 9$$ Trường hợp này có $C_{9}^4$ cách xếp.

 Như vậy ta thu được $C_{9}^4+C_{10}^4+C_{11}^4+C_{12}^4=1161$ cách. Tới đây, ta chú ý rằng $12$ chàng trai có thể hoán vị cho nhau. Như vậy, kết quả bài toán là: $12!.1161$

Bài toán: Cho $m, n$ là các số nguyên thỏa $m\ge n\ge 2$. Giả sử $x_1, x_2,...,x_n$ là các số nguyên dương sao cho $x_1+x_2+...+x_n=m$. Tìm GTNN của:

                                                                $ S=x_1^2+x_2^2+...+x_n^2$

Lời giải:

     Từ BDT Cauchy Schawrz, ta có:

                                                          $n(x_1^2+x_2^2+...+x_n^2)\ge (x_1+x_2+...+x_n)^2$

                                                     $\Leftrightarrow S\ge \dfrac{m^2}{n}$

      Dấu $"="$ xảy ra khi và chỉ khi $x_1=x_2=...=x_n=\dfrac{m}{n}$. Do đó, ta có nhận xét rằng $S$ đạt giá trị nhỏ nhất tại các biến $x_i$ đủ gần bằng nhau. Cụ thể là $x_{i+1}=x_i+1$

      Gọi $P$ là tập hợp tất cả các giá trị có thể có của $S$. Dễ thấy là $P$ là hữu hạn do đó tồn tại $N$ là giá trị nhỏ nhất của $S$.

      Giả sử khẳng định trên là không đúng, chẳng hạn $x_1-x_2>1$. Khi đó, chọn $x=x_1-1$ và $y=x_2+1$, thế thì $x^2+y^2<x_1^2+x_2^2$, điều này vô lí.
     
      Bây giờ, giả sử $x_1\le x_2\le ...\le x_n$ và đặt $m=dn+k$, với $k<n, k\in N$

    Từ điều kiện $x_1\le x_2\le ...\le x_n$ là hơn kém nhau tối thiểu là $1$ nên ta có:

                                                                  $x_1=x_2=...=x_{n-k}=d$

                                                                  $x_{n-k+1}=...=x_n=d+1$

    Từ đó, ta có ngay $N=(n-k)d^2+k(d+1)^2$

toán rời rạc

Bài toán 1: Cho hình chữ nhật có kích thước  x  được  chia thành các ô vuông đơn vị. Đánh số các ô từ trái sang phải là  (hàng ) và  (hàng ). Lát chúng bằng các quân domino  x sao cho chúng phủ kín hình chữ nhật và không có hai quân nào đè lên nhau. Ngoài ra, với  lẻ, ta được bổ sung thêm một quân domino “đặc biệt” có thể phủ kín hai ô  và . Hỏi có bao nhiêu cách lát như trên thỏa mãn bài toán.

Nguyên lí cực hạn

Bài toán 1: Có ba trường học, mỗi trường có  học sinh. Mỗi học sinh quen với ít nhất  từ hai trường khác. Chứng minh rằng ta có thể chọn ra từ mỗi trường một bạn sao cho ba học sinh chọn được đôi một quen nhau.

Lời giải:  Gọi A là học sinh có nhiều bạn nhất ở một trường khác, giả sử số bạn đó là . Giả sử A ở trường thứ nhất và tập hợp những bạn quen A là     ở trường thứ hai. Theo giả thiết, có ít nhất một học sinh C ở trường thứ ba quen với A. Do C quen không quá  học sinh ở trường thứ nhất nên theo giả thiết C quen ít nhất với  học sinh ở trường thứ hai. Đặt    là những học sinh mà C quen ở trường thứ hai .

Dễ dàng nhận ra rằng M và N đều thuộc tập hợp  học sinh và 

                                                    ||+||

do đó  . Ta chọn một bạn B trong tập  thì được ba bạn A, B, C thỏa mãn bài toán. 
Bài toán 2: Trên một bàn cờ vua cỡ  x , ta đặt các quân xe thỏa mãn điều kiện sau: nếu có một  ô  nào  đó  không  có  quân  xe  thì  tổng  các  quân  xe  đứng  cùng   hàng  và  cùng  cột  với  ô  đó không  nhỏ  hơn  .  Chứng  minh  rằng  số  quân  xe  trên  bàn  cờ  không  ít  hơn 
 
Lời giải:
   Vì số đường gồm hàng và cột trên bàn cờ là hữu hạn nên tồn tại một đường N (giả sử là hàng) có số quân xe nhỏ nhất. Gỉa sử số quân xe trên N là . Khi đó trên hàng N có  ô không có quân xe. Từ đó, suy ra trên mỗi cột chứa một ô như thế có ít nhất   quân xe. Như vậy, các cột này chứa ít nhất  quân xe.
   Do tính nhỏ nhất của , trên  cột còn lại, mỗi cột phải chứa ít nhất  quân xe, do đó số quân xe trên  cột này không nhỏ hơn . Vậy số quân xe trên bàn cờ không quá   . Từ đó chú ý tới bất đẳng thức       , 
  Suy ra đpcm.
Bài toán 3: Chứng minh rằng tồn tại vô số số nguyên dương  sao cho bất đẳng thức     thỏa mãn với mọi , trong đó  là tổng tất cả các ước số dương của .

Lời giải: Đặt . Giả sử chỉ có hữu hạn số nguyên dương thỏa mãn bất đẳng thức  với mọi . Gọi  là số lớn nhất trong các số  thỏa mãn điều này. Với mỗi số nguyên dương , đặt:

                                       

Khi đó, . Hơn nữa, do  lớn nhất,                                                                                                                                   

Suy ra . Từ đó, với mọi . Mặt khác, tập hợp các ước số dương của  chứa số  và tất cả các số dạng , với  là ước số dương của . Do đó:

                                                    

Suy ra                

Mâu thuẫn với tính lớn nhất của . Từ đây dễ dàng suy ra đpcm.