[Bài viết được viết từ ngày 23.11.2024]
(Bài blog này tôi sẽ dịch thuật lại từ bài viết “Chicken McNugget Theorem” của Art of Problem Solving (link))
Trước khi đi sâu vào bài viết này, mình xin cảm ơn bạn Trần Hoàng Sơn (DennisTran) đã góp ý cho bài viết này.
Định lí Chicken McNugget (hay “Postage Stamp Problem”, “Frobenius Coin Problem”) phát biểu rằng
<aside> 💡
Đối với hai số nguyên dương $m$, $n$ bất kì nguyên tố cùng nhau ($gcd(m, n) = 1$), số nguyên lớn nhất không thể viết thành dạng $am + bn$ với $a, b$ là những số nguyên không âm là $mn - m - n$
</aside>
Có nhiều câu chuyện xoay quanh nguồn gốc định lí Chicken McNugget. Tuy nhiên, câu chuyện phổ biến nhất vẫn là Chicken McNugget.
Ban đầu, McDonald’s bán gà viên theo dạng gói 9 hoặc 20 viên. Những người đam mê toán học tò mò muốn tìm số lượng gà viên lớn nhất mà không thể mua được bằng những gói 9 hoặc 20, từ đó tạo ra định lí Chicken McNugget (câu trả lời là 151 viên gà).
Định lí Chicken McNugget cũng được gọi là Bài toán đồng xu Frobenius hoặc Bài toán Frobenius sau khi nhà toán học người Đức - Ferdinand Frobenius đặt ra câu hỏi về số lượng tiền lớn nhất không thể được tạo ra bằng một số loại tiền xu nhất định.
Ví dụ, nếu ta có $m =$ 11 và $n =$ 4, bảng số sẽ trông như thế này:
