Thống kê

  • truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Vui mừng chào đón

    0 khách và 0 thành viên
    Gốc > THUẬT TOÁN >

    Bài toán Hàn Tín điểm binh

    Tục truyền rằng , ngày xưa, Hàn Tín danh tướng của Lưu Bang (Hán Cao Tổ) điểm binh theo cách sau đây: bảo lính xếp hàng ba, hàng năm, hàng bẩy rồi ghi các số lẻ tương ứng sẽ suy ra số lính bằng cách sau đây:

    Nhân số lẻ hàng ba cho 70, số lẻ hàng năm cho 21, nhân số lẻ hàng bẩy cho 15. Cộng các kết quả ấy lại. Thêm số đó với một bội số thich hợp của 105 sẽ được số lính

    Nếu ký hiệu số lính là S, số lẻ xếp hàng 3, hàng 5, hàng 7 tương ứng là a, b, c.

    thì S = 70.a + 21.b + 15.c + 105.k

    (k là số nguyên chọn thích hợp với số lính của một đại đội, một tiểu đoàn hay trung đoàn...)

    CHỨNG MINH


    Bài toán trên được đặt ra như sau: Tìm số S sao cho khi chia S cho 3, cho 5, cho 7 thi số dư tương ứng là a, b, c . (a, b, c, S đều là các số tự nhiên, a < 3, b < 5, c < 7. Hoăc có thể viết:

    S = 3A + a

    S = 5B + b

    S = 7C + c

    Nhân hai vế đẳng thức đầu với 5.7.m (35m) ; được

    35.m.S = 105.m.A + 35.m.a.

    Nhân hai vế của đẳng thức thứ hai với 3.5.n ; được

    21.n.S = 105.n.B + 21.n.b

    Nhân hai vế của đẳng thức thứ ba với 3.5.p được

    15.p.S = 105.p.c

    Cộng 3 đẳng thức mới được

    (35m + 21n + 15p)S = 105(mA + nB + pC) + 35ma + 21nb + 15pc (1)

    Ta sẽ tìm ba số nguyên m, n. p nghiệm đẳng thức sau này:

    35m + 21n + 15p = 105k + 1 (2)

    (chỗ này HOÀNG XUÂN HÃN không giải thích tại sao phải có đẳng thức (2))

    Ta viết (2) như sau

    35m - 1 = 3(35k - 7n - 5p)

    Thế tỏ ra vế đầu chia đúng cho 3 . Ví dụ m là 2 thì có

    35.2 - 1 = 3. 23

    Trừ hai đẳng thức trên, ta sẽ thấy:

    35(m - 2) = 3D

    Vế đầu chia 3 đúng, nhưng 35 không chia cho 3 đúng. Vởy m - 2 chia cho 3 đúng.

    Và m = 2 + 3M .

    Tương tự ta tìm được

    n = 1 + 5N và p = 1 + 7P

    Làm như thế, ta tìm được vô số m, n, p nghiệm đẳng thức (2).

    Cho M = N = P = 0, ta được ba số m = 2, n = 1, p = 1 gọn nhất.

    Thay nó vào đẳng thức (1) ta sẽ thấy:

    (105 + 1) S = 105 (2A + B + C) + 70a + 21b + 15c

    Hay là:

    S = 105 T + (70a + 21b + 15c).

    Vậy số S bằng 70a + 21b + 15c rồi thêm bớt một bội số của 105.

    Đó là quy tắc “ Hàn Tín điểm binh “ mà HOÀNG XUÂN HÃN đã chứng minh. Sau đây chúng tôi sẽ bổ sung thêm vài cách chứng minh quy tắc đó

    Cách 1. Gọi S là số TN thỏa mãn điều kiện chia cho 3, 5, 7 thì được số dư tương ứng là a, b, c. S không duy nhất mà sai khác một bội số của 105. Thực vậy nếu S1 thỏa mãn đk của bài toán thì S2 = S1 + 105.k (k là sớ tự nhiênh bất kỳ) cũng thỏa mãn đk của bài toán. Vì vậy S có dạng

    S = 105k + h , h là số nhỏ nhất thỏa mãn đk chia cho 3 dư a, chia cho 5 dư b chia cho 7 dư c. Vậy h phải có dạng:

    h = h1 + h2 + h3 . Trong đó h1 là số bé nhất chia hết cho 5, 7 nhưng chia cho 3 dư a ; h2 là số bé nhất chia hết cho 3, 7, nhưng chia cho 5 dư b . h3 là số bé nhất chia hết cho 3, 5, nhưng chia cho 7 dư c . Ta lần lượt tìm các số h1, h2, h3

    h1 có dạng:

    h1 = 35.m , chọn số bé nhất m để (35m - a) chia hết cho 3 ; 35 không phải là bội của a nên m là một bội số của a: m = m’.a . (35m - a) = (35.m’ - 1) a là bội số của 3 suy ra (35m’ - 1) chia hết cho 3. Số nhỏ nhất m’ để (35.m’ - 1) chia hết cho 3 là 2 ; m = 2a .

    Suy ra h1 = 70.a thỏa mãn yêu cầu nói trên.

    Tương tự ta tìm được

    h2 = 21b và h3 = 15p

    Vậy

    S = 105k + 70a + 21b + 15c



    Cách 2. Để dễ dàng trong lập luận chứng minh của HOÀNG XUÂN HÃN, ta đưa vào quan hệ mod(k) giữa các số nguyên s, s’ như sau:

    Định nghĩa Ta gọi s, s’ cùng mod(k) hoặc s = s’mod(k) nếu s-s’ chia hết cho k

    Suy ra: Nếu u = u’mod(k), v = v’mod(k)

    thì (u + v) = (u’ + v’)mod(k) ; u. v = u’v’mod(k)

    Trở lại chứng minh quy tắc Hàn Tín của HOÀNG XUÂN HÃN (giải thích tại sao có đẳng thức (2))

    Từ dẳng thức (1) (35m + 21n + 15p).S = 105k + (35ma + 21nb + 15pc) (1)

    Ký hiệu u = 35m + 21n +15pc , v = 35ma + 21nb + 15pc, (1) được viết

    u S = vmod(105) (1’). Nếu tìm đựơc các số nguyên m, n, p sao cho

    u = 1mod(105) (3) thì S có thể viết S = v.mod(105)

    Tìm m, n, p thỏa mãn (3) như sau:

    u = 35m + 21n + 15p = 1 + 105k hoặc 35m - 1 = 105k -21n - 15p (4)

    Vế phải của (4) chia hết cho 3 nên vế trái cũng chia hết cho 3. Dễ dàng tìm được m = 2 là số nguyên dương nhỏ nhất để (35m - 1) chia hết cho 3.

    Tương tự ta tìm được n = 1, p = 1 là các số nguyên dương nhỏ nhất thỏa mãn (4).

    Vậy

    S = 105.k + (70a + 21b + 15p)

    Quy tắc trên được tóm tắt trong bốn câu thơ của Trình Đại Vỹ đời nhà Minh sau đây:

    Tam nhân đồng hành thất thập hy

    Ngũ thụ mai hoa trấp nhất chi.

    Thất tử đoàn viên chính bán nguyệt

    Trừ bách linh ngũ tiện đắc tri

    Dịch

    Ba người cùng đi ít bẩy mươi

    Năm cõi mai hoa hăm mốt cành

    Bẩy gã xum vầy vừa nửa tháng.

    Trừ trăm linh năm biết số thành. (bài thơ chữ Hán do HOÀNG XUÂN HÃN sưu tầm và dịch)

    MỞ RỘNG QUY TẮC HÀN TÍN

    Tìm số tự nhiên S sao cho khi chia S lần lượt cho các số nguyên tố p1, p2, p3, .

    được số dư tương ứng là q1, q2, q3, . .

    S = p1p2p3. k + p2p3q1m1 + p3p1q2m2 +p1p2q3 m3

    Trong đó m1, m2, m3 là các số tự nhiên nhỏ nhất sao cho

    (p2p3m1 -1), (p3p1m2 - 1), (p1p2m3 - 1) theo thứ tự chia hết cho p1, p2, p3.

     

                                                        Vntoanhoc.com (GS Hoàng Xuân Hãn)
    Nhắn tin cho tác giả
    Đỗ Văn Cường @ 17:34 14/03/2011
    Số lượt xem: 1511
    Số lượt thích: 0 người
     
    Gửi ý kiến