Leo thang và bài toán đếm

2021/03/18 16:31

#tổ hợp #đếm

Bài toán 1. Cho nn, kk, mm N\in \mathbb{N}^* thoả mãn điều kiện m>1m>11<kn1< k \leq n. Hỏi có tất cả bao nhiêu chỉnh hợp chập kk (a1,a2,ak)(a_{1},a_{2}, \cdots a_{k}) của nn số nguyên dương đầu tiên mà mỗi chỉnh hợp (a1,a2,ak)(a_{1},a_{2},\cdots a_{k}) đều thoả mãn ít nhất một trong hai điều kiện:

1. Tồn tại hai số ij{1,2,k}i \neq j \in \left \{ 1,2,\cdots k \right \} sao cho i<ji< jai>aja_{i} > a_{j}.

2. Tồn tại i{1,2,k}i \in \left \{ 1,2,\cdots k \right \} sao cho aiia_{i}-i không chia hết cho m.

Bài toán này có một lời giải sử dụng lời giải song ánh rất đẹp và ngắn gọn. Sau đây là một lời giải khác dài và xấu hơn.

Lời giải

Không gian mẫu ω=Ank|\omega|=A^k_{n}.

Gọi SS là tập các chỉnh hợp chập kk cần tìm.

Ta đi tính S\overline{S} là tập các chỉnh hợp chập kk thoả mãn:

  1. \forall ii, jj {1,2,k}\in \left \{ 1,2,\cdots k \right \} thì i<j    ai<aji< j \iff a_{i} < a_{j}.
  2. \forall i{1,2,k}i \in \left \{ 1,2,\cdots k \right \} thì aiia_{i}-i chia hết cho m.

Ta tưởng tượng một bảng có mm cột được đánh số các ô từ 11 đến nn từ trái qua phải, từ trên xuống dưới như sau. (n=45n=45, m=6m=6)

Ứng với mỗi chỉnh hợp (a1,a2,ak)(a_{1},a_{2}, \cdots a_{k}) S\in \overline{S} sẽ cho ta biết tuần tự từ ô xuất phát của chúng ta trên bảng cho đến ô cuối cùng.

  • Bởi vì ai+1>aia_{i+1}>a_{i} \forall i{1,2,k1}i \in \left \{ 1,2,\cdots k-1 \right \} nên thứ tự đi luôn là từ trái qua phải và từ trên xuống dưới cho tới ô cuối cùng.
  • Bởi vì aiia_{i}-i chia hết cho m \forall i{1,2,k}i \in \left \{ 1,2,\cdots k \right \} nên ở bước thứ ii ta luôn dừng ở ô thuộc cột thứ jj với jij \equiv i (mod(mod m)m)j{1,2,m}j \in \left \{ 1,2, \cdots m \right \}.

Như vậy ta có thể hình dung hành trình của chúng ta như sau:

  • Số bước: kk bước.
  • Hướng đi: Từ trái qua phải, từ trên xuống dưới.
  • Lúc đầu ta ở ngoài bảng. Bước đầu ta đến ô thuộc cột 11, bước tiếp theo sẽ đến ô thuộc cột 22 v.v cho tới bước cuối cùng.

Bây giờ ta sẽ đi đếm số hành trình như trên mà ta có thể thực hiện được.

Từ bước này tới bước kia ta sẽ “nhảy cột” và ta có thể chọn nhảy xuống một số hàng tuỳ ý.

Gọi hi1h_{i} \geq 1, i{1,2,k}i \in \left \{ 1,2,\cdots k \right \} là số thứ tự của hàng mà ta tới sau bước thứ ii. Quy ước h0=0h_{0}=0.

Dễ thấy hihi1h_{i} \geq h_{i-1}.

Gọi ai=hihi10a_{i}=h_{i} - h_{i-1} \geq 0, i{1,2,k}i \in \left \{ 1,2,\cdots k \right \} hay là số hàng lệch của hàng ta đang ở ở bước thứ ii so với bước thứ i1i-1.

Dễ thấy khi ta đang ở cột thứ mm, ta buộc phải xuống hàng nên i1(mod\forall i \equiv 1 (mod m)m), ai1a_{i} \geq 1. (1)(1)

Xét r,qNr,q \in \mathbb{N} sao cho n=mq+rn=mq+r với 0rm10 \leq r \leq m-1. Như vậy qq ở đây biểu thị số hàng của bảng và rr là số ô dư ra ở hàng cuối.

Xét r,qNr',q' \in \mathbb{N} sao cho k=mq+rk=mq'+r' với 0rm10 \leq r' \leq m-1. Từ (1)(1) suy ra có qq' bước mà ta buộc phải xuống hàng. Ta xét (b1,b2,bk)(b_{1}, b_{2}, \cdots b_{k}) trong đó {bi0bmt1\left\{\begin{matrix} b_i \geq 0\\ b_{mt} \geq 1 \end{matrix}\right. (tN)(t \in \mathbb{N}).

Có 2 trường hợp xảy ra:

TH1. rr' \leq rr. Khi đó hkqh_{k} \leq q.

Như vậy, số hành trình là số bộ thứ tự (b1,b2,bk)(b_{1}, b_{2}, \cdots b_{k}) thoả mãn

i=1kbi=i=1k(hihi1)q=hkqq\sum_{i=1}^{k} b_{i} =\sum_{i=1}^{k}(h_{i}-h_{i-1})-q'=h_{k} \leq q-q'.

Sử dụng Bài toán chia kẹo Euler, số bộ như vậy là (qq+kk)\binom{q-q'+k}{k}.

TH2. r>r' > rr. Khi đó hkq1h_{k} \leq q-1.

Như vậy, số hành trình là số bộ thứ tự (b1,b2,bk)(b_{1}, b_{2}, \cdots b_{k}) thoả mãn

i=1kbi=i=1k(hihi1)q=hkqq1\sum_{i=1}^{k} b_{i} =\sum_{i=1}^{k}(h_{i}-h_{i-1})-q'=h_{k} \leq q-q'-1.

Sử dụng Bài toán chia kẹo Euler, số bộ như vậy là (qq1+kk)\binom{q-q'-1+k}{k}.

Như vậy trong cả hai trường hợp, số hành trình luôn là ([nkm]+kk)\binom{[\frac{n-k}{m}]+k}{k}.

Suy ra S=([nkm]+kk)|\overline{S}|=\binom{[\frac{n-k}{m}]+k}{k}.

Kết luận. Số chỉnh hợp chập kk cần tìm chính là Ank([nkm]+kk)A^k_{n} - \binom{[\frac{n-k}{m}]+k}{k}.

Một bài toán khác có thể làm tương tự

Bài toán 2. (Hà Nội TST 2020) Tìm số bộ nguyên dương (a1,a2,a15)(a_1,a_2, \cdots a_{15}) thoả mãn:

1. 1a1<a2<20201 \leq a_1 < a_2 < \cdots 2020.

2. aii2(mod5),i=1,15a_i \equiv i^2 (mod5), \forall i =\overline{1,15}.

Quay trở về Blog