Gọi \(l(n)\) là lá được rút ra cuối cùng:

• \(l(1) = 1\).
• Với \(n\) chẵn thì \(l(n) = 2*l(\frac{n}{2}) - 1\).
• Với \(n\) lẻ thì \(l(n) = 2*l(\frac{n - 1}{2}) + 1\).

(Để chứng minh hai điều trên, để ý rằng những lá bài ở vị trí chẵn được rút ra trước)

Từ đây ta xây dựng được hàm đệ quy tính \(l(n)\), ĐPT \(O(log(n))\)

Cách chứng minh cụ thể công thức truy hồi trên và công thức tường minh có thể xem tại link.

Bạn đọc hãy tự giải những bài toán liên quan:

• Lá bài được rút ra thứ \(k\) ghi số mấy ?
• Lá bài ghi số \(k\) được rút ra ở bước thứ mấy ?