#5 - Câu chuyện đầu năm

“Theo truyền thuyết, có một con yêu quái đáng sợ tên là “Tuỵ”. Hàng năm vào đêm giao thừa, nó sẽ đến chạm vào đầu trẻ em đang ngủ ba lần. Sợ quá, em bé sẽ khóc lớn và sau đó sẽ bị đau đầu, bị sốt, và nói nhảm. Khi những triệu chứng này biến mất, đứa trẻ sẽ trở nên ngu đần.

Vì sợ yêu quái Tuỵ hãm hại trẻ nhỏ, cha mẹ chúng thường không tắt đèn và thức qua đêm giao thừa để xua đuổi yêu quái. Đây là nguồn gốc tập tục thức qua đêm giao thừa.

Có một nhà họ Quan nọ sinh sống tại thành phố Gia Hưng, tuổi đã cao mới sinh hạ được một cậu con trai nên rất cưng chiều.

Vào một đêm giao thừa, sợ Tuỵ đến hãm hại, họ cũng thức tỉnh cậu bé. Họ cho cậu ta 8 đồng xu để đùa nghịch. Cậu bé bọc những đồng xu này vào tờ giấy đỏ, mở ra, rồi lại bọc lại, lặp đi lặp lại như thế đến khi chú bé mệt quá và ngủ thiếp đi mất, 8 đồng xu khi ấy đang được bọc bởi giấy đỏ và đặt ngay bên cạnh gối cậu ta. Lúc ấy đôi vợ chồng ngồi ngay bên cạnh để trông chừng.

Vào nửa đêm, một cơn gió lạnh thổi tung cánh cửa và làm tắt đèn. Đúng lúc quỷ Tuỵ vươn tay đến đầu cậu bé, từ bao giấy đỏ tỏa ra một luồng sáng bạc làm cho yêu quái khiếp sợ và bỏ trốn.

Vào Tết năm đó, đôi vợ chồng đã kể cho hàng xóm láng giềng về câu chuyện hôm giao thừa. Từ đó về sau, họ bắt đầu bắt chước làm theo và trẻ em không còn bị quấy nhiễu nữa.

Hóa ra 8 đồng xu kia chính là 8 vị Thần đã âm thầm bảo vệ cậu bé. Vì thế người ta gọi tiền lì xì là Tiền may mắn trong Năm Mới.”

Theo truyencotich.vn

Câu chuyện trên có một điểm mâu thuẫn: “đây là nguồn gốc tập tục thức qua đêm giao thừa". Nếu lì xì đã xua đuổi được con quỷ, thì tại sao người ta vẫn phải thức qua đêm giao thừa? Chuyện này giờ đây cũng không thực sự quan trọng lắm, dù gì thì ta cũng không thể phủ nhận được rằng giây phút cùng cha mẹ thắp nén hương thành kính trước bàn thờ tổ tiên đêm giao thừa là một trong những khoảnh khắc hạnh phúc nhất trong năm với mỗi người, hiếm hoi lắm ta mới tìm được một người muốn ngủ qua giao thừa.

Ý nghĩa ban đầu của lì xì giống như một lá bùa, 8 đồng xu để một đứa trẻ có được giấc ngủ ngon. Thời gian trôi qua, lì xì không chỉ còn dành cho trẻ em. Lì xì được con cháu dùng để chúc sức khoẻ ông bà, lì xì thầy cô gửi học trò chúc chúc học giỏi, lì xì cấp trên gửi cấp dưới và ngược lại… Giá trị vật chất của lì xì cũng không còn dừng lại ở 8 đồng xu như cũ. Lì xì ai nhiều hay ít tuỳ thuộc vào các yếu tố như quan hệ xã hội, ý nghĩa tâm linh v.v... Nhưng dù là hình thức nào hay giá trị bao nhiêu, những đồng tiền mới trong phong bao đỏ vẫn là lời chúc một năm mới may mắn, thành công, là một nét đẹp văn hoá của dân tộc.

…

Một ngày đẹp trời bạn nói với mẹ rằng bạn đã lớn, và mẹ cho phép bạn giữ tiền mừng tuổi, bạn sẽ làm gì với chúng? Bạn đã hết tuổi thích mua đồ chơi và muốn những đồng tiền được sử dụng có ý nghĩa. Và vậy là bạn quyết định đem tiền đi đầu tư.

Giả sử bạn có x VNĐ. Bạn biết đổi 1 VNĐ được bao nhiêu USD, đổi 1 USD được bao nhiêu VNĐ (2 giá trị này có thể không phải là nghịch đảo của nhau). Bạn cũng biết tỉ giá hối đoái giữa VNĐ và EUR, giữa USD và EUR. Câu hỏi đặt ra là bạn có nên đầu tư không, và nếu có thì nên đổi như thế nào để cuối cùng bạn có nhiều hơn x VNĐ. Mở rộng ra nếu số loại tiền không phải 3 mà là n, thì bạn sẽ tính toán như thế nào để có lợi?

Dĩ nhiên là một khi đã thấy có lợi, thì bạn nên đổi hết toàn bộ số tiền mình có để được lợi nhuận tối đa. Vấn đề là đổi từ loại nào sang loại nào và theo thứ tự nào.

Giả sử bạn đang có x đồng tiền loại 1 và 1 đồng loại 1 đổi được a đồng loại 2, thì khi đổi sang loại 2 bạn sẽ có a.x đồng. Thay vì quan tâm đến x, bạn có thể quan tâm đến log(x). Khi x tăng thì log(x) cũng tăng, nhưng quan trọng hơn là với logarit, bạn có thể biến phép nhân thành phép cộng. Logarit của lượng tiền loại 2 mà bạn đổi được sẽ là log(a.x) = log(a) + log(x). Bây giờ bạn có thể dựng một đồ thị có hướng, mỗi nút biểu thị 1 loại tiền, trọng số mỗi cạnh là logarit của hệ số hối đoái từ loại này sang loại kia. Ví dụ như trong trường hợp trên, cạnh từ loại 1 sang loại 2 sẽ có trọng số log(a).

Vậy khi nào thì bạn nên tham gia đầu tư? Đó là khi mà đồ thị dựng được có chu trình âm. Một thông tin thú vị hơn nữa là khi đồ thị có chu trình âm, bạn sẽ trở thành tỉ phú VNĐ! Bằng việc đổi chác dựa trên chu trình âm, lượng tiền bạn có sẽ tăng lên vô hạn. Nghe mới hấp dẫn làm sao!

Nếu để ý bạn có thể thấy là ngay cả khi chơi game, người ta cũng dùng cách mua đi bán lại để nâng cao tài sản của mình. Ứng dụng của thuật toán tìm chu trình âm không phải là hiếm. Bản thân nó cũng đã từng nhiều lần xuất hiện trong các cuộc thi lập trình. Nói một cách đơn giản, để xác định đồ thị có chu trình âm hay không, ta dùng thuật toán Ford-Bellman, nếu có một đỉnh được cập nhật |V| lần (|V| là số đỉnh của đồ thị), thì đồ thị có chu trình âm, nếu không thì đồ thị không có chu trình âm. Bạn có thể tìm hiểu thêm tại: https://sites.google.com/site/kc97ble/algorithm-graph/fordbellmanqueue-cpp

Còn về ý tưởng sử dụng logarit, bạn có thể thử sức với 2 bài tập: http://vnoi.info/problems/show/C11NHL/ và http://www.ioinformatics.org/locations/ioi15/contest/day2/horses-en.pdf

…

Đồ thị có chu trình âm, bạn có thể trở thành tỉ phú! Tuy nhiên trong x VNĐ của bạn có rất nhiều tiền lẻ, và bạn muốn đổi chúng thành tiền chẵn để tiện cho việc giao dịch. Phải đổi sao để bạn sẽ chỉ phải cầm ít đồng tiền nhất?

Đây là một trong những vấn đề cơ bản nhất mà bạn gặp khi học giải thuật quy hoạch động. Gọi f[i][s] là số đồng tiền ít nhất có thể có tổng là s tạo thành từ i loại đồng tiền đầu tiên. Giả sử đồng tiền loại i có giá trị là v và s ≥ v, thì f[i][s] = min(f[i-1][s], f[i][s-v]+1). Nếu s < v thì f[i][s] = f[i-1][s]. Ta có f[0][0] = 0, f[0][s] = ∞ với x > 0, và kết quả là f[n][x], với n là số loại tiền.

Độ phức tạp của thuật giải trên là O(n.x), nó tỉ lệ với số tiền cần đổi và số loại tiền. Khi số tiền cần đổi quá lớn, chi phí tính toán sẽ là không hề nhỏ. Hãy tưởng tượng bạn áp dụng nó cho những giới hạn lớn hàng “nghìn tỉ đồng", thì điều gì sẽ xảy ra.

Tuy nhiên trong một số điều kiện đặc biệt, độ phức tạp có thể giảm bớt. Chẳng hạn như nếu mệnh giá của các đồng tiền đôi một chia hết cho nhau, bạn có thể áp dụng giải thuật tham lam lấy từ lớn đến bé, khi đó thời gian tính toán sẽ là O(n.log(n)), tính cả chi phí sắp xếp.

…

Tuần trước, trong lúc gom tiền đi trả nợ cuối năm, tình cờ mình nghĩ ra một bài toán. Mình đã dành cả thời gian ngồi trên máy bay về nhà để tìm một lời giải thoả đáng cho nó. Thử đố vui mọi người để xem mọi người có cách làm nào đơn giản hơn không:

“Giả sử trên tay bạn có 450 nghìn đồng. Hãy chứng minh rằng bạn luôn luôn có thể chia nó ra thành 2 phần là 200 nghìn và 250 nghìn. Các loại tiền được sử dụng là các đồng tiền đang được lưu hành ở Việt Nam (200k, 100k, 50k, 20k, 10k, 5k, 2k, 1k, 500, 200, 100).”

Dưới đây là lời giải của mình:

Trước hết ta chia 450 nghìn thành các nhóm có tổng nằm trong tập {200k, 100k, 50k, 20k, 10k, 5k, 2k, 1k, 500, 200, 100}, sao cho không thể gom các nhóm nhỏ hơn để tạo thành một nhóm lớn hơn được nữa (ví dụ 5 nhóm 200 có thể gom lại thành một nhóm 1k). Ta sẽ chứng minh có ít nhất 1 nhóm 200k tồn tại, từ đó chia được tiền.

Ta thấy số nhóm 100k không thể vượt quá 1, nếu không ta có thể gom 2 nhóm 100k để tạo thành nhóm 200k, tương tự với các nhóm 50k, 10k, 5k, 1k, 500, 100. Số nhóm 200 không thể vượt quá 4, nếu không ta có thể gom 5 nhóm 200 để tạo thành nhóm 1k, tương tự với các nhóm 2k, 20k, 200k.

Từ nhận xét trên suy ra tổng số tiền tối đa từ các nhóm nhỏ hơn 50k là 100 + 500 + 1k + 5k + 10k + (200 + 2k + 20k)*4 = 105400. Hơn nữa tổng số tiền từ các nhóm nhỏ hơn 50k phải chia hết cho 50k, vì 450k chia hết cho 50k. Như vậy tổng số này chỉ có thể nhận 3 giá trị: 0, 50k và 100k. Bởi vì có không quá 1 nhóm 50k và 100k, nên tổng số tiền tối đa tạo được từ các nhóm nhỏ hơn 200k là 100k + 50k + 100k = 250k < 450k. Như vậy ta suy ra phải tồn tại ít nhất 1 nhóm 200k, và đó là điều phải chứng minh.

…

Nhân dịp đầu xuân, cảm ơn các bạn đã đồng hành với Free Contest trong suốt một năm qua. Chúc các bạn có một năm mới dồi dào sức khoẻ, thành công trong học tập. Hãy tham gia Free Contest nhiều hơn trong năm nay nhé, và đừng quên đón đọc “Kí ức thuật toán" của mình. Chúc mừng năm mới!

TĨNH LẶNG