Một chương trình nối file PDF miễn phí chỉ cho phép nối tối đa 2 file cùng một lúc. Sau mỗi lần hợp nhất, chương trình tạo ra một file mới trên ổ đĩa. Giả sử ban đầu ta có n files: a1, a2, …, an; ta có thể nối các file lại như sau: Lần nối thứ nhất được [n/2] files: b1= a1+a2, b2 = a3+a4,…, b[n/2] =an-1+an nếu n chẵn. Còn n lẻ thì b[n/2] =an-2+an-1. Tiếp đó, đến lần nối thứ 2: c1=b1+b2, c2=b3+b4,… Nếu số file b ở lần nối đầu tiên tạo ra là số chẵn, thì sau khi nối xong ta chuyển sang lần nối thứ 3 hợp nhất các file bj (j=1, 2,…,[n/2]), còn nếu là số lẻ, trường hợp n (số file a ban đầu) chẵn, ta để nguyên b[n/2] cho lần nối tiếp theo, trường hợp n lẻ, ta hợp nhất ngay b[n/2] với an để tạo thành một file mới. Quá trình cứ tiếp diễn như vậy cho tới khi tạo ra được một file PDF duy nhất. Kí hiệu [x] để chỉ phần nguyên của số x.
1/ Tổng số file trung gian tạo ra bởi chương trình này là bao nhiêu, kể cả file cuối cùng? (Nghĩa là, tổng số files b1, b2,…, b[n/2], c1, c2… cho đến file cuối cùng được tạo ra). Đây cũng chính là tổng số lần thao tác để hợp nhất n files ban đầu lại thành một file duy nhất.
2/ Giả sử file ai có dung lượng là ai (ai>0). Có thể nối các file như thế nào để dung lượng các file trung gian mà chương trình tạo ra là ít nhất? Điều này giúp ta tiết kiệm được tối đa không gian của bộ nhớ. Tổng số lần thao tác trong trường hợp này là bao nhiêu?
