Trả tiền bằng những đồng xu lạ#
Hãy tưởng tượng một đất nước có các đồng xu mệnh giá 1, 2, 3, 5, 8, 13, 21, 34, 55 và cứ thế. Mỗi đồng xu bằng tổng của hai đồng xu trước nó. Bạn muốn trả một số tiền bất kỳ, dùng mỗi đồng xu nhiều nhất một lần, và không bao giờ dùng hai đồng xu nằm cạnh nhau trong danh sách đó.
Bạn có luôn làm được không? Có, và theo đúng một cách. Đó là định lý Zeckendorf. Trang này cho thấy phương pháp, rồi đến chứng minh mà giảng viên của bạn đã đưa ra.
Dãy Fibonacci#
Bắt đầu với F0 = 0 và F1 = 1. Sau đó, mỗi số hạng là tổng của hai số hạng trước nó: Fn = Fn−1 + Fn−2. Một quy tắc như vậy, xây dựng mỗi số hạng từ các số hạng trước, được gọi là một công thức truy hồi (recurrence).
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Fn | 0 | 1 | 1 | 2 | 3 | 5 | 8 |
| n | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|
| Fn | 13 | 21 | 34 | 55 | 89 | 144 |
Hai điểm kiểm tra từ bài giảng bắt được hầu hết các sai sót: F5 = 5 và F10 = 55. Nếu bảng của bạn không khớp ở một trong hai chỗ, bạn đã bắt đầu đánh chỉ số sai.
Một tính chất đáng biết: nếu m chia hết n, thì Fm chia hết Fn. Ví dụ 5 chia hết 10, và F5 = 5 chia hết F10 = 55. Tương tự, 3 chia hết 9, và F3 = 2 chia hết F9 = 34.
Phát biểu định lý một cách cẩn thận#
Định lý Zeckendorf. Mọi số nguyên n ≥ 1 đều có thể viết thành
n = Fk₁ + Fk₂ + … + Fkₗ
trong đó các chỉ số k₁ > k₂ > … > kₗ thỏa hai quy tắc:
- Không có hai chỉ số liên tiếp. Mỗi chỉ số nhỏ hơn chỉ số đứng trước nó ít nhất 2.
- Chỉ số nhỏ nhất ít nhất là 2. F1 không được phép.
Vì sao cấm F1? Vì F1 = F2 = 1. Nếu cho phép F1, thì 3 có thể viết là F4 và cũng viết là F3 + F1 = 2 + 1, và biểu diễn sẽ không duy nhất.
Phương pháp: luôn lấy đồng xu lớn nhất vừa đủ#
Để viết n, tìm số Fibonacci lớn nhất mà ≤ n. Trừ nó đi. Lặp lại trên phần còn lại.
Ví dụ: 50. Số Fibonacci lớn nhất ≤ 50 là 34 = F9, còn lại 16. Số lớn nhất ≤ 16 là 13 = F7, còn lại 3 = F4. Vậy
50 = F9 + F7 + F4 = 34 + 13 + 3. Các chỉ số 9, 7, 4 không bao giờ chạm nhau.
Các trường hợp nhỏ từ bài giảng, cũng là các trường hợp cơ sở của chứng minh:
| n | Biểu diễn Zeckendorf |
|---|---|
| 1 | F2 = 1 |
| 2 | F3 = 2 |
| 3 | F4 = 3 |
| 4 | F4 + F2 = 3 + 1 |
| 5 | F5 = 5 |
| 6 | F5 + F2 = 5 + 1 |
| 7 | F5 + F3 = 5 + 2 |
| 8 | F6 = 8 |
| 9 | F6 + F2 = 8 + 1 |
| 10 | F6 + F3 = 8 + 2 |
| 11 | F6 + F4 = 8 + 3 |
Vì sao cần quy nạp mạnh#
Trong quy nạp thông thường bạn chứng minh trường hợp n + 1 chỉ bằng trường hợp n. Ở đây điều đó là không đủ.
Để xử lý 50 bạn trừ 34 và cần một biểu diễn của 16, không phải của 49. Số bạn cần là phần còn lại sau phép trừ lớn nhất, và nó có thể thấp hơn n rất nhiều. Bạn không biết trước nó sẽ là số nào.
Quy nạp mạnh giải quyết điều này. Giả thiết của nó giả sử mệnh đề đúng với mọi trường hợp từ đầu cho đến n, không chỉ với n. Khi đó phần còn lại nào bạn gặp, bạn đều được phép dùng. Quy nạp mạnh tương đương về mặt logic với quy nạp thông thường; nó chỉ đưa cho bạn nhiều thứ hơn để làm việc.
Chứng minh, từng bước#
Bước cơ sở. Bảng ở trên kiểm tra trực tiếp n = 1 đến 11.
Giả thiết quy nạp. Cho n ≥ 11 và giả sử mọi m với 1 ≤ m ≤ n đều có một biểu diễn thuộc loại yêu cầu.
Mục tiêu. Chỉ ra rằng n + 1 cũng có một biểu diễn.
Gọi Fk₁ là số Fibonacci lớn nhất thỏa Fk₁ ≤ n + 1.
Trường hợp 1: Fk₁ = n + 1. Khi đó n + 1 tự nó là một số Fibonacci, một biểu diễn một số hạng. Xong.
Trường hợp 2: Fk₁ < n + 1. Đặt m = n + 1 − Fk₁. Khi đó m ≥ 1, và m ≤ n vì Fk₁ ≥ 1. Vậy giả thiết quy nạp áp dụng cho m:
m = Fk₂ + … + Fkₗ, với các chỉ số không liên tiếp.
Cộng Fk₁ trở lại: n + 1 = Fk₁ + Fk₂ + … + Fkₗ.
Điều cuối cùng cần kiểm tra là k₂ không nằm cạnh k₁, tức là k₂ ≤ k₁ − 2. Giả sử không phải vậy, tức là k₂ ≥ k₁ − 1. Các số Fibonacci tăng dần, nên
n + 1 ≥ Fk₁ + Fk₂ ≥ Fk₁ + Fk₁−1 = Fk₁+1.
Bước cuối chính là quy tắc Fibonacci. Nhưng khi đó Fk₁+1 là một số Fibonacci lớn hơn mà vẫn vừa dưới n + 1, mâu thuẫn với việc chọn Fk₁ là số lớn nhất. Vậy k₂ ≤ k₁ − 2.
Kết luận. Theo nguyên lý quy nạp toán học mạnh, mọi n ≥ 1 đều có một biểu diễn Zeckendorf. Bài giảng để tính duy nhất cho một video khác; cùng ý tưởng “số hạng lớn nhất” cũng là cốt lõi của chứng minh đó.
Lấy số Fibonacci lớn nhất vừa đủ, và nếu số kế tiếp là hàng xóm của nó thì hai số sẽ cộng lại thành một số Fibonacci lớn hơn cũng vừa đủ, điều này là không thể.
Sai ở chỗ nào#
- Bắt đầu từ nhỏ thay vì lớn. 1 + 2 + 3 = 6 dùng các số hạng liên tiếp. Phương pháp tham lam phải lấy số hạng lớn nhất trước.
- Dùng các số hạng liên tiếp mà tình cờ có tổng đúng. 34 + 8 + 5 + 3 = 50, nhưng 8 và 5 là hàng xóm. Hãy gộp chúng thành 13.
- Dùng F1. Nó trùng với F2 và phá vỡ tính duy nhất.
- Viết giả thiết như quy nạp thông thường. “Giả sử nó đúng với n” không bao phủ phần còn lại m. Hãy viết “với mọi m thỏa 1 ≤ m ≤ n”.
- Quên kiểm tra tính không liên tiếp. Tồn tại một tổng Fibonacci nào đó thì dễ. Lập luận mâu thuẫn mới là phần ghi điểm.
Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí
Luyện tập Discrete Math theo chủ đề: dùng được khi không có mạng, không quảng cáo, không cần tài khoản.
Luyện tập Fibonacci và Zeckendorf →Câu hỏi thường gặp#
Định lý Zeckendorf là gì?
Mọi số nguyên dương đều có thể viết theo đúng một cách thành tổng các số Fibonacci F_k với k ≥ 2 và không có hai chỉ số liên tiếp. Ví dụ 50 = F9 + F7 + F4 = 34 + 13 + 3.
Làm sao tìm biểu diễn Zeckendorf của một số?
Theo cách tham lam: trừ đi số Fibonacci lớn nhất không lớn hơn số đó, rồi lặp lại trên phần còn lại. Với 100 điều đó cho 89, rồi 8, rồi 3, nên 100 = 89 + 8 + 3.
Vì sao định lý Zeckendorf được chứng minh bằng quy nạp mạnh?
Sau khi trừ số Fibonacci lớn nhất khỏi n + 1, phần còn lại có thể nhỏ hơn n rất nhiều, và bạn không thể đoán trước nó là giá trị nào. Quy nạp mạnh giả sử mệnh đề đúng với mọi số nhỏ hơn, nên phần còn lại nào xuất hiện cũng được bao phủ.
Vì sao các chỉ số Fibonacci không thể liên tiếp?
Hai số Fibonacci liên tiếp cộng lại bằng số kế tiếp: F_k + F_(k−1) = F_(k+1). Nếu biểu diễn dùng cả hai, số Fibonacci kế tiếp cũng sẽ vừa, mâu thuẫn với việc số lớn nhất đã được chọn trước.
F5 và F10 là gì?
Với F0 = 0 và F1 = 1, F5 = 5 và F10 = 55. Hai giá trị này là những điểm kiểm tra hữu ích để đảm bảo một bảng Fibonacci được đánh chỉ số đúng.
Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.