Nội dung từ topic sumset sang, do thớt du lịch dưới biển lâu quá nên mình vớt một phần nội dung của thớt kia lên bờ.
Đề bài như sau (chép nguyên xi)
Một trong các solution
Gọi T(N) là số cách biểu diễn thoả đề bài.
Đối với trường hợp N chẵn, xét trường hợp N = 6:
6 = 1 + 1 + 1 + 1 + 1 + 1
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 4
6 = 2 + 2 + 2
6 = 2 + 4
Giờ chia thành 2 nhóm
Nhóm có số 1 ở vế phải, số lượng là T(5) = 4
6 = 1 + 5 = 1 + (1 + 1 + 1 + 1 + 1)
6 = 1 + 5 = 1 + (1 + 1 + 1 + 2)
6 = 1 + 5 = 1 + (1 + 2 + 2)
6 = 1 + 5 = 1 + (1 + 4)
Nhóm không có số 1 vế phải, số lượng là T(6/2) = T(3) = 2
6 = 2(1 + 1 + 1)
6 = 2(1 + 2)
Vậy T(2n) = T(2n-1) + T(n)
Đối với trường hợp N lẻ, vì N lẻ nên trong biểu diễn phải có 1, suy ra T(2n+1) = T(2n)
7 = 6 + 1 = 1 + (1 + 1 + 1 + 1 + 1 + 1)
7 = 6 + 1 = 1 + (1 + 1 + 1 + 1 + 2)
7 = 6 + 1 = 1 + (1 + 1 + 2 + 2)
7 = 6 + 1 = 1 + (1 + 1 + 4)
7 = 6 + 1 = 1 + (2 + 2 + 2)
7 = 6 + 1 = 1 + (2 + 4)
Hay T(2n) = T(2n-1) + T(n) = T(2n-2) + T(n)
Tóm lại, có công thức truy hồi như sau:
- T(1) = 1
- T(2) = 2
- T(2n) = T(2n-2) + T(n)
- T(2n+1) = T(2n)
Mình muốn hỏi dãy kết quả của bài trên (sequence) có được đặt tên hay không? Có công thức tổng quát cho dãy?
2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166,...
Vì mình thấy nó có tính chất thế này:
Ban đầu loại đi các phần tử trùng nhau
2, 4, 6, 10, 14, 20, 26, 36, 46, 60, 74, 94, 114, 140, 166, ...
Trừ 2 phần tử liên tiếp, được dãy mới giống như dãy ban đầu.
2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26,...
Nếu tiếp tục lặp lại, 2 bước, khử phần tử trùng và trừ 2 phần tử liên tiếp, thì được các dãy như sau. Trong đó các dãy được đánh dấu (*) là các dãy giống như dãy kết quả.
2, 4, 6, 10, 14, 20, 26,...
2, 2, 4, 4, 6,... // *
2, 4, 6,...
2, 2,... // *
2,...
Vì dãy là vô tận, nên sau mỗi lần khử và trừ thì được dãy cũ, cứ thế lặp đi lặp lại liên tục.