Bài viết sưu tầm

Xét bài toán điền các chữ số phân biệt thay cho các chữ cái S, E, N, D, M, O, R, Y sao cho phép cộng sau là đúng:

                                         SEND

                                         MORE

                                     MONEY                                                            

Các ràng buộc ban đầu:

-               Các chữ cái khác nhau không nhận cùng một giá trị.

-               Các ràng buộc số học (cộng có nhớ hoặc không có nhớ.

Gọi C1, C2, C3, C4 lần lượt lá số nhớ của các cột từ phải sang trái. Khi đó ta xây dựng các ràng buộc cụ thể như sau:

E, N, D,O, R, Y thuộc tập {0 ..9}                      (1)

S, M thuộc tập {1..9}                                        (2)

C1, C2, C3, C4 thuộc tập {0,1}                         (3)

D + E = Y + 10*C1                                             (4)

N + R + C1 = E + 10*C2                                                (5)

E + O + C2 = N + 10*C3                                                (6)

S + M + C3 = O + 10*C4                                         (7)

M = C4                                                                (8)

Từ ràng buộc (2) và (8) suy ra M = 1 và C4=1         (9)

Từ ràng buộc (7) và (9) suy ra S +C3 = O + 9, lúc này có hai phương án để lựa chọn:

Phương án 1:

C3 = 0, khi đó ta có S = O + 9, như vậy S = 9 và O = 0                  (10-1)

     Từ ràng buộc (6) ta có E + C2 = N, suy ra C2 = 1 và

E + 1 = N             (11-1)             

Từ ràng buộc (5), ta có R + C1 = 9, như vậy R = 8 vàC1 = 1 (12-1)

(do kết hợp với các ràng buộc (2) và (10-1).

Từ ràng buộc (4) ta có D + E = Y +10. Đến bứơc này ta có thể khảng định các giá trị của D, E, Y chỉ có thể nhận trong tập {2, 3, 4, 5, 6, 7}. Ngoài ra D + E >= 12. Vì vậy chỉ có các khả năng sau có thể xãy ra:

-               D = 5 và E = 7

-               D = 7 và E = 5            (hai truờng hợp này Y = 2)

-               D = 6 và E = 7

-               D = 7 và E = 6            (hai trường hợp sau Y = 3)

Xét khả năng thứ nhất. Từ ràng buộc (11-1) ta suy ra N = 8 mâu thuẫn với (12-1) nên bị loại

Xét khả năng thứ hai. Từ ràng buộc (11-1) ta suy ra N= 6. Kiểm tra điều kiện bài toán đều thoả mãn. Vậy ta có nghiệm là:

S = 9, E = 5, N= 6, D = 7, M= 1,  O = 0, R = 8, Y = 2.

Xét khả năng thứ ba. Từ ràng buộc (11-1) suy ra N = 8 mâu thuẫn với (12-1)

Xét khả năng thứ tư. Từ ràng buộc (11-1) suy ra N=7 = D mâu thuẫn.

Phương án 2.

     C3 = 1. Từ ràng buộc (7) ta có S = O + 8, suy ra S = 8 và O = 0          (10-2)

(vì M=1 và S <= 9).

     Từ ràng buộc (6) ta có E = N +10 mâu thuẫn với ràng buộc (1). vậy phương án 2 không có lời giải.