Bài toán Frobenius

Định lý Tem thư. Cho a, b là các số nguyên dương nguyên tố cùng nhau. Khi đó

            1) Với mọi n > ab – a – b = n₀, n có thể biểu diễn được dưới dạng

                        n = ax + by với x, y là các số nguyên không âm.

            2) Với mọi k, 0 £ k £ n₀, có đúng một trong hai số k, n₀-k biểu diễn được dưới dạng  ax + by với x, y nguyên không âm.

Kết quả này là của Sylvester. Đây là trường hợp đặc biệt của bài toán Frobenius:

Cho trước n số nguyên dương a₁, a₂, …, a_n với (a₁, a₂, …, a_n) = 1. Tìm số G_n lớn nhất không biểu diễn được dưới dạng  a₁x₁ + … + a_nx_n với x_i Î N.

Số nguyên G_n như vậy luôn tồn tại do điều kiện (a₁, a₂, …, a_n) = 1 và được suy ra từ định lý Schur (định lý khẳng định số nghiệm nguyên không âm của phương trình x = a₁x₁ + … + a_nx_n bằng

Cho đến gần đây, ngay cả trường hợp n=3 vẫn chưa giải được. Có một số người khẳng định rằng họ đã giải được trường hợp n=3. Tuy nhiên, khi xem lời giải của họ thì họ không tìm được công thức cho G₃. Đúng hơn là họ đã đưa ra một thuật toán “đơn giản” để tìm G₃. Thuật toán này được mô tả trên vài trang giấy. Nếu theo nghĩa này thì trường hợp tổng quát cũng có lời giải. Còn công thức cho G_n có lẽ là không tồn tại, ngay cả trong trường hợp n = 3.

Davidson chứng minh được đánh giá chặn dưới cho G₃(a₁, a₂, a₃) như sau:

            G₃(a₁, a₂, a₃) >= căn(a1*a2*a3) - a1 - a2 - a3

Bạn đọc quan tâm đến bài toán Frobenius (còn gọi là Frobenius coin problem) có thể xem thêm tại địa chỉ

[1] http://en.wikipedia.org/wiki/Coin_problem

Bài tập

1. Cho (a, b) = 1. Ngân hàng trung ương Sikinia phát hành chỉ 2 loại tiền a- và b-Kulotnik. Bạn có thể trả được những khoản tiền nào nếu

(a) bạn có thể nhận tiền trả lại       (b) bạn không nhận tiền trả lại

2. Ở Sikinia có ba loại quả cân: 15, 20 và 48 Slotnik. Hỏi có thể cân được những trọng lượng nào nếu dùng cân

            (a) 2 đĩa                                             (b) một đĩa

3. (IMO 1983) Cho a, b, c là các số nguyên dương với (a, b) = (b, c) = (c, a) = 1. Chứng minh rằng 2abc – ab – bc – ca là số nguyên lớn nhất không biểu diễn được dưới dạng xbc + yca + zab với x, y, z là các số nguyên không âm.

4. Với tập hợp A, ký hiệu |A| và s(A) tương ứng là số phần tử và tổng các phần tử của tập hợp A (nếu A = Æ thì |A| = s(A) = 0). Cho S là tập hợp gồm các số nguyên dương sao cho

            a) tồn tại hai phần tử x, y thuộc S với (x, y) = 1.

            b) nếu x, y thuộc S thì x + y thuộc S.

Gọi T là tập hợp tất cả các số không nằm trong S. Chứng minh rằng

Chứng minh tính chia hêt của một nhóm số tự nhiên

Gia sư tại nhà sưu tầm 1 dạng bài toán chứng minh về tínhchia hết của vài nhóm số tự nhiên đặc biệt từ dễ đến khó để HSG toán rèn luyện phương pháp chứng minh

Bài 1

Trong 3 số tự nhiên tùy ý chọn ( a, b, c ε N ), chứng minh rằng luôn có ít nhất 1 cặp số ( 2 số trong 3 số đó) mà tổng và hiệu của chúng chia hết cho 2.

Giải : Áp dụng quy tắc chẵn –lẻ

Xét các trường hợp:

·        a, b, c cùng chẵn è đương nhiên chọn bất kỳ cặp nào cũng có

                                          tổng và cả hiệu của chúng là số chia hết cho 2

·        a, b, c cùng lẻ è đương nhiên chọn bất kỳ cặp nào cũng có

                                          tổng và cả  hiệu của chúng là số chia hết cho 2

·        a, b, c có 1 cặp là số lẻ è Hiệu và tổng của 2 số lẻ chia hết cho 2

·        a, b, c có 1 cặp là số chẵnè Hiệu và tổng của 2 số chẵn chia hết cho 2

         Hai trường hợp đầu có 3 cặp số thỏa mãn đầu bài

        Hai trường hợp cuối có 1 cặp số thỏa mãn đầu bài

è Vậy có ít nhât 1 cặp số mà tổng và hiệu của chúng chia hết cho 2 (ĐPCM)

Bài 2

Trong 4 số tự nhiên tùy ý chọn ( a, b, c, d ε N ), chứng minh rằng luôn có ít nhất 1 cặp số ( 2 số trong 4 số đó) mà tổng hoặc hiệu của chúng chia hết cho 5.

Giải :  Áp dụng qui tắc số dư

    Ta thấy phép chia cho 5 có thể được các số dư là  0, 1, 2, 3, 4,

Xét các trường hợp:

·        cả 4 số có số dư khác nhau (0,1,2,3);(0,2,3,4);(0,1 4,2); (0,4,2,3);(1,2,3,4)

     bao giờ cũng có ít nhất 1 cặp số có số dư là (1+4) hoặc (2+3)

                  è Tổng 1 cặp số đó chia hết cho 5

    Với nhóm số có số dư (1,2,3,4) è 2 cặp có tổng chia hết cho 5

·        cả 4 số có số dư trùng nhauè 6 cặp từng đôi một có hiệu = 0

                                                                                        è chia hết cho 5

·        2 cặp có số dư trùng nhau è Hiệu của 2 cặp đó = 0 è chia hết cho 5

·        1 cặp có số dư trùng nhau è Hiệu của 1 cặp đó = 0 è chia hết cho 5

Vậy ít nhất cũng chọn ra 1 cặp số mà tổng hoặc hiệu của chúng chia hết cho 5.

Bài 3

Chứng minh rằng trong 7 số tự nhiên bất kỳ tùy chọn, bao giờ cũng có 4 số mà tổng của chúng chia hết cho 4

Giải:

Đặt 7 số TN đó là A, B, C, D, E, F, G. Lấy kết quả của bài 1: Trong 3 số tự nhiên bất kỳ luôn có 2 số là số chẵn ( chia hết cho 2)

                A,  B,     C   Và   D, E, F    mỗi nhóm có 1 cặp chia hết cho 2

    

* Giả thử (A+B) =2 m  và  (D+E)=2n è (A+B) + (C+D)= 2(m+n)

     

                     Còn 3 số   C     F    G  sẽ có 1 cặp chia hết cho 2

                                     ( C + F) = 2 p    Với m,n,p cúng là số tự nhiên

Trong 3 số m, n, p  luôn chọn được 2 số có tổng chia hết cho 2.

*Giả thử (m + n) =2 q  ( q là số TN) thì ta có

     (A+B) + (C+D)= 2(m+n) = 4q  ==> A+B+C+D chia hết cho 4 (ĐPCM)

Tương tự nếu chon các nhóm số khác ta cũng được 4 số trong 7 số bât kỳ trên chia hết cho 4

Lưu ý:

- Với bài toán chứng minh ta phải xét tất cả các trường hợp có thể xảy ra như bài 1 và bài 2; Với bài 3, tài liệu này chi nêu 1 trường hợp, còn các trường hợp khác nêu “CM tương tự”

- Bài 1 và bài 2 chú ý kết luận có sự khác nhau bởi 2 chữ và với chữ hoặc !

Tính nhanh tổng của một dãy số cho trước.

Khi cho một dãy số (có quy luật viết nhất định), yêu cầu học sinh phải tính nhanh tổng của dãy số này. nếu ta không hướng dẫn học sinh một phương pháp tính thì sẻ gặp nhiều khó khăn, trong mục này tôi xin đưa ra 2 ví dụ cụ thể, sau đó rút ra một cách tính tổng quát để khi gặp phải dạng toán này học sinh có thể giải một cách dễ dàng.

       Bài 1: Cho dãy số: 1,4,7,10,13,…52,55,57. Hãy tìm tổng của dãy số đó?

    Đây là  một bài toán có dạng đặc biệt. Cách tính nhanh nhất là phải sử dụng các tính chất của phép cộng (giao hoán, kết hợp) để tìm ra các tình nhanh nhất và từ đó rút ra cách giải một cách tổng quát nhất.                                       

Cách làm như sau:

     Ta nhận thấy, dãy số này bắt đầu từ số 1, kết thúc là số 57; số sau lớn hơn số trước nó 3 đơn vị; dãy có 10 số. Nếu tính cách thông thường thưc hiện từ trái sang phải thì rất lâu mà ta phải hướng dẫn học sinh  sử dụng tính chất giao hoán để tính. Ta có:

(1 + 58) + (4 + 55) + (7 + 52) +...+ (25 + 34) +(28 + 31) có 10 cặp. Mỗi cặp có tổng số là 59. Như vậy tổng của dãy số dễ dàng là: 5910 = 590.

      Bài 2.  Cho dãy số: 1 , 3, 5, 7, ….,77, 79 . Hãy tính tổng dãy số đó bằng cách nhanh nhất.

          Ta có thể làm như bài 1, nghĩa là lấy só đầu (1) cộng với số cuối (79)   số thứ 2 (3) cộng với  só thứ 2 cuối (77) và theo trình tự như vậy cho đến hết....sở dĩ như vậy là ta chọn 2 số sao cho có tổng tròn chục (80). Từ 1 đến 79 có 40 số và do cách làm trên nên ta sẻ có 20 cặp ( tổng mỗi cặp là 80) nên dễ dàng tìm được tổng của dãy số là: 80 * 20 = 1600.

   Từ cách giải trên nếu ta dừng lại đây thì chưa đủ, thực tế có nhiều bài toán   dẫy số có rất nhiều số, nên học sinh sể rất mất công để tìm ra có bao nhiêu số trong dãy số đó, để tìm ra bao nhiêu cặp . Lại nữa, muốn tìm xem  một số nào đó trong dãy số là số thứ mấy của dãy số? Rồi số thứ n nào đó của dãy là số mấy?...

     Ví dụ: Cho dãy số 2 ; 4 ; 6 ; 8 ; 10 ;....2002 ; 2004. Hãy:

                a, Tìm  tổng của dãy số?

                b, Số Thứ 50 của dãy số là số mấy?

                c, Số 1802 của dãy số là số thứ bao nhiêu của dãy?

      Để giúp học sinh giải bài toán này và các bài toán tương tự ta hãy cùng gia sư toán tại nhà xây dựng một công thức tổng quát mà trong phạm vi học sinh tiểu học có thể chấp nhận và áp dụng được.

    Gọi dãy số cho trước là a₁,a₂,a₃,...a_n trong đó a₁,a₂,a₃ là các số thứ 1,2,3 của dãy số, a_n là số cuối cùng của dãy số. ta hãy tìm công thức tổng quát, từ ví dụ cụ thể sau:

       Ví dụ:  Cho dãy số 1,5,9,13,17,21,25,29. Hãy tìm tổng của dãy số đó?

     + Để tìm tổng của dãy số trước hết ta phải tìm xem dãy số gồm có bao nhiêu số.Ví dụ: Cho dãy số 1,5,9,13,17,21,25,29. Nhận xét:

     + Dãy số có 8 số tức bằng  (29 - 1)/(5 - 1) + 1= 8 trong đó 29 là số cuối của dãy; 1 là số đầu của dãy; 5 là số thứ 2 của dãy (tương đương với các số a_n,a₁,a₂ trong dãy số tổng quát ) và  (29 - 1)/(5 - 1) = 7 chỉ số từ 1(số đầu dãy) đến 29 (số cuối dãy) có 7 khoảng và như toán trồng cây ta phảicộng thêm 1để để tìm ra dãy số có bao nhiêu số và từ đây ta có công thức tìm dãy có bao nhiêu số.

    Bây giờ ta trở lại giải bài tập trên.

     Bài 1: Cho dãy số 2, 4, 6, 8, 10,....2002, 2004. Hãy:

         a, Tìm  tổng của dãy số?

         b, Số Thứ 50 của dãy số là số mấy?

          c, Số 1802 của dãy số là số thứ bao nhiêu của dãy?

       Ta có thể làm như sau:

   * Trước hết ta tìm xem đãy số đã cho có bao nhiêu số (tức là tìm n):

III MỘT SỐ BÀI TẬP KHÁC

Bµi 1: TÝnh nhanh:

a) 237 + 357 + 763       b) 2345 + 4257 - 345      c) 5238 - 476 + 3476    d) 1987 - 538 - 462                                   

e)  4276 + 2357 + 5724 + 7643                            g) 3145 + 2496 + 5347 + 7504 + 4653

h) 2376 + 3425 - 376 - 425                                   i)  3145 - 246 + 2347 - 145 + 4246  - 347

k) 4638 - 2437 + 5362 - 7563                               l) 3576 - 4037 - 5963 + 6424

Bµi 1: TÝnh nhanh:

a) 5+ 5 + 5 + 5+ 5 + 5 +5+ 5 + 5 +5	b) 25 + 25 + 25 + 25 + 25 + 25 +25 + 25
c) 45 + 45 + 45 + 45 + 15 + 15 + 15 + 15	d) 2 + 4 + 6 + 8 + 10 + 12 + 14 + 16 + 18
e) 125 + 125 + 125 + 125 - 25 - 25 - 25 - 25

Bµi 2: TÝnh nhanh:

a) 425 x 3475 + 425 x 6525	b) 234 x 1257 - 234 x 257
c) 3876 x 375 + 375 x 6124	d) 1327 x 524 - 524 x 327
e) 257 x 432 + 257 x 354 + 257 x 214	g) 325 x 1574 - 325 x 325 - 325 x 24
h) 312 x 425 + 312 x 574 + 312	i) 175 x 1274 - 175 x 273 - 175

Bµi 3: TÝnh nhanh:

a) 4 x 125 x 25 x 8	b) 2 x 8 x 50 x 25 x 125
c) 2 x 3 x 4 x 5 x 50 x 25	d) 25 x 20 x 125 x 8 - 8 x 20 x 5 x 125

    

Bµi 4*: TÝnh nhanh:

a) 8 x 427 x 3 + 6 x 573 x 4	b) 6 x 1235 x 20 - 5 x 235 x 24
c) (145 x 99 + 145) - (143 x 102 - 143)	d) 54 x 47 - 47 x 53 - 20 - 27

 

 Bµi 5*:  TÝnh nhanh:

a) 10000 - 47 x 72 - 47 x 28

b) 3457 - 27 x 48 - 48 x 73 + 6543

Bµi 6*: TÝnh nhanh:

a) 326 x 728 + 327 x 272	b) 2008 x 867 + 2009 x 133
c) 1235 x 6789x (630 - 315 x 2)	d) (m : 1 - m x 1) : (m x 2008 + m + 2008)

Bµi 7*: TÝnh nhanh:

a)    (399*45 + 399*55)/(1995*1996 - 1995*1991)	b) (1995*1993 - 18)/(197%*1993*1994)
c)       (1996*1995 - 996)/(1000 + 1994*1996)	d)

                                          

 Bµi 8*: Cho A = 2009 x 425      B = 575 x 2009. Không tính A, B hãy tính kết quả B - A?

Trường Marie – Curie ĐỀ THI TIẾNG VIỆT VÀO LỚP 6

Trường Marie – Curie

ĐỀ THI TIẾNG VIỆT VÀO LỚP 6

Câu 1 (2 điểm): Từ nào không thuộc nhóm từ đồng nghĩa trong mỗi dãy từ sau? Vì sao?

a) ngào ngạt, sực nức, thoang thoảng, thơm nồng, thơm nức.

b) rực rỡ, sặc sỡ, tươi thắm, tươi tắn, thắm tươi.

c) long lanh, lóng lánh, lung linh, lung lay, lấp lánh

Câu 2 (2 điểm)

Cho câu sau: "Bún chả ngon"

a) Hãy tách câu trên thành từ và tìm chủ ngữ, vị ngữ của câu theo hai cách hiểu khác nhau.

b) Ví sao hai câu trên có thể tách như vậy? Với mỗi cách hiểu, câu trên ý nói gì?

Câu 3 (1 điểm)

Chọn từ trong ngoặc đơn em cho là hay nhất để điền vào chỗ trống trong câu văn sau, nói rõ vì sao em chọn từ đó:

"Lời ru nồng nàn, tha thiết của mẹ...vào tâm hồn thơ ngây, trong trắng của tôi biết bao yêu thương". (rót, trút, đổ)

Câu 4 (5 điểm)

Em đã từng xem một bộ phim hoặc đọc, nghe kể một câu chuyện trong đó có nhân vật là các con vật ngộ nghĩnh, thông minh, dễ thương. 

Em hãy tưởng tượng và tả lại con vật mà em yêu thích nhất.

Một số bài toán quy hoạch động kinh điển

Chúng ta đều biết rằng điều khó nhất để giải một bài toán quy hoạch động (QHĐ) là biết rằng nó là một bài toán QHĐ và tìm được công thức QHĐ của nó. Rất khó nếu ta mò mẫm từ đầu, nhưng nếu chúng ta đưa được bài toán cần giải về một bài toán QHĐ kinh điển thì sẽ dễ dàng hơn nhiều. Do đó, tìm hiểu mô hình, công thức và cách cài đặt những bài toán QHĐ kinh điển là một việc rất cần thiết.

I. Dãy con đơn điệu dài nhất
1. Mô hình
Cho dãy a₁,a₂,..a_n. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy.
2. Công thức QHĐ
Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a₁ đến a_i và phần tử cuối cùng là a_i.
Ta có công thức QHĐ để tính L(i) như sau:
L(1) = 1
L(i) = max(1, L(j)+1 với mọi phần tử j: 0 < j < i va` a_j ≤ a_i).
3. Cài đặt
Bảng phương án là một mảng một chiều L để lưu trữ các giá trị của hàm QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau:
for i := 1 to n do begin
L[i] := 1;
for j:=1 to i - 1 do
if (a[j]<=a[i]) and (L[i]
L[i]:=L[j]+1;
end;
Như vậy chi phí không gian của bài toán là O(n), chi phí thời gian là O(n²). Có một phương pháp cài đặt tốt hơn so với phương pháp trên, cho chi phí thời gian là O(nlogn), bạn đọc có thể tham khảo trong bài báo của thầy Trần Đỗ Hùng trên tạp chí số tháng 10 năm 2004.

4. Một số bài toán khác  - gia sư tin học tại nhà
Bài toán dãy con đơn điệu tăng dài nhất có biến thể đơn giản nhất là bài toán dãy con đơn điệu giảm dài nhất, tuy nhiên chúng ta có thể coi chúng như là một. Sau đây là một số bài toán khác.
a) Bố trí phòng họp
Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm ai và kết thúc ở thời điểm bi. Do chỉ có một phòng hội thảo nên 2 cuộc họp bất kì sẽ được cùng bố trí phục vụ nếu khoảng thời gian làm việc của chúng chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để phục vụ được nhiều cuộc họp nhất.
Hướng dẫn:
Sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc (b_i). Thế thì cuộc họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu j < i va` b_j ≤ a_i. Yêu cầu bố trí được nhiều cuộc họp nhất có thể đưa về việc tìm dãy các cuộc họp dài nhất thoả mãn điều kiện trên.
b) Cho thuê máy
Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của n khách hàng. Khách hàng i muốn sử dụng máy trong khoảng thời gian từ a_i đến b_i và trả tiền thuê là c_i. Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê).
Hướng dẫn:
Tương tự như bài toán a), nếu sắp xếp các đơn đặt hàng theo thời điểm kết thúc, ta sẽ đưa được bài toán b) về bài toán tìm dãy con có tổng lớn nhất. Bài toán này là biến thể của bài toán tìm dãy con tăng dài nhất, ta có thể cài đặt bằng đoạn chương trình như sau:
for i:=1 to n do
begin
L[i]:=c[i];
for j:=1 to i -1 do
if (b[j]<=a[i]) and (L[i]
L[i]:=L[j]+c[i];
end;
c) Dãy tam giác bao nhau
Cho n tam giác trên mặt phẳng. Tam giác i bao tam giác j nếu 3 đỉnh của tam giác j đều nằm trong tam giác i (có thể nằm trên cạnh). Hãy tìm dãy tam giác bao nhau có nhiều tam giác nhất.
Hướng dẫn:
Sắp xếp các tam giác tăng dần về diện tích. Khi đó tam giác i sẽ bao tam giác j nếu j < i và 3 đỉnh của j nằm trong i. Từ đó có thể đưa về bài toán tìm dãy tăng dài nhất.
Việc kiểm tra điểm M có nằm trong tam giác ABC không có thể dựa trên phương pháp tính diện tích: điểm M nằm trong nếu S(ABC) = S(ABM) + S(ACM) + S(BCM).
Bài toán có một số biến thể khác như tìm dãy hình tam giác, hình chữ nhật bao nhau có tổng diện tích lớn nhất.
d) Dãy đổi dấu Cho dãy a₁, a₂,... a_n. Hãy dãy con đổi dấu dài nhất của dãy đó. Dãy con con đổi dấu a_i1,a_i2,... a_ik phải thoả mãn các điều kiện sau:
a_i1 <A_i2 > a_i3 <... hoặc _i1 > a_i2 < a _i3 >... các chỉ số phải cách nhau ít nhất L: i₂ - i₁ ≥ L, i₃ -i₂ ≥ L...
chênh lệch giữa 2 phần tử liên tiếp nhỏ hơn U: |a_i1 - a_i2| ≤ U, |a_i2 - a_i3| ≤ U...
Hướng dẫn:
Gọi L(i) là số phần tử của dãy con đổi dấu có phần tử cuối cùng là a_i và phần tử cuối cùng lớn hơn phần tử đứng trước. Tương tự, P(i) là số phần tử của dãy con đổi dấu có phần tử cuối cùng là a_i và phần tử cuối cùng nhỏ hơn phần tử đứng trước. Ta dễ dàng suy ra:
L(i) = max(1, P(j)+1): j ≤ i - L và a_i - U ≤ a_j < a_i.
P(i) = max(1, L(j)+1): j ≤ i - L và a_i < a_j ≤ a_i + U.

II. Chia kẹo
1. Mô hình
Cho dãy a₁, a₂,.. a_n. Tìm một dãy con của dãy đó có tổng bằng S.
2. Công thức
Đặt L(i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a₁,a₂,..a_i. Ngược lại thì L(i,t)=0. Nếu L(n,S)=1 thì đáp án của bài toán trên là 'có'.
Ta có thể tính L(i,t) theo công thức: L(i,t) = 1 nếu L(i - 1,t)=1 hoặc L(i-1,t - a[i])=1.
3. Cài đặt
Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i -1. Bảng phương án khi đó chỉ cần 1 mảng 1 chiều L[0..S] và được tính như sau:
L[t]:=0; L[0]:=1;
for i := 1 to n do
for t := S downto a[i] do
if (L[t]=0) and (L[t - a[i]]=1) then L[t]:=1;
Dễ thấy chi phí không gian của cách cài đặt trên là O(m), chi phí thời gian là O(nm), với m là tổng của n số. Bạn đọc hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to.
4. Một số bài toán khác
a) Chia kẹo
Cho n gói kẹo, gói thứ i có a_i viên. Hãy chia các gói thành 2 phần sao cho chênh lệch giữa 2 phần là ít nhất.
Hướng dẫn: Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thoả mãn:
S ≤ T/2.
Có một dãy con của dãy a có tổng bằng S. Khi đó sẽ có cách chia với chênh lệch 2 phần là T - 2S là nhỏ nhất và dãy con có tổng bằng S ở trên gồm các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo còn lại.

b) Market (Olympic Balkan 2000)
Người đánh cá Clement bắt được n con cá, khối lượng mỗi con là ai, đem bán ngoài chợ. ở chợ cá, người ta không mua cá theo từng con mà mua theo một lượng nào đó. Chẳng hạn 3 kg, 5kg...
Ví dụ: có 3 con cá, khối lượng lần lượt là: 3, 2, 4. Mua lượng 6 kg sẽ phải lấy con cá thứ 2 và và thứ 3. Mua lượng 3 kg thì lấy con thứ nhất. Không thể mua lượng 8 kg.
Nếu bạn là người đầu tiên mua cá, có bao nhiêu lượng bạn có thể chọn?
Hướng dẫn:

Thực chất bài toán là tìm các số S mà có một dãy con của dãy a có tổng bằng S. Ta có thể dùng phương pháp đánh dấu của bài chia kẹo ở trên rồi đếm các giá trị t mà L[t]=1.
c) Điền dấu
Cho n số tự nhiên a₁,a₂,...,a_n. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu '?': a₁?a₂?...?a_n. Cho trước số nguyên S, có cách nào thay các dấu '?' bằng dấu + hay dấu - để được một biểu thức số học cho giá trị là S không?
Hướng dẫn : Đặt L(i,t)=1 nếu có thể điền dấu vào i số đầu tiên và cho kết quả bằng t. Ta có công thức sau để tính L:
L(1,a[1]) =1.
L(i,t)=1 nếu L(i - 1,t+a[i])=1 hoặc L(i - 1,t - a[i])=1.
Nếu L(n,S)=1 thì câu trả lời của bài toán là có. Khi cài đặt, có thể dùng một mảng 2 chiều (lưu toàn bộ bảng phương án) hoặc 2 mảng một chiều (để lưu dòng i và dòng i - 1). Chú ý là chỉ số theo t của các mảng phải có cả phần âm (tức là từ - T đến T, với T là tổng của n số), vì trong bài này chúng ta dùng cả dấu - nên có thể tạo ra các tổng âm.
Bài này có một biến thể là đặt dấu sao cho kết quả là một số chia hết cho k. Ta có thuật giải tương tự bài toán trên bằng cách thay các phép cộng, trừ bằng các hép cộng và trừ theo môđun k và dùng mảng đánh dấu với các giá trị từ 0 đến k - 1 (là các số dư có thể có khi chia cho k). Đáp số của bài toán là L(n,0).
d) Expression (ACM 10690)
Cho n số nguyên. Hãy chia chúng thành 2 nhóm sao cho tích của tổng 2 nhóm là lớn nhất.
Hướng dẫn : Gọi T là tổng n số nguyên đó. Giả sử ta chia dãy thành 2 nhóm, gọi S là tổng của một nhóm, tổng nhóm còn lại là T - S và tích của tổng 2 nhóm là S*(T - S). Bằng phương pháp đánh dấu ta xác định được mọi số S là tổng của một nhóm (như bài Market) và tìm số S sao cho S*(T - S) đạt max.

III. Xâu con chung dài nhất
1. Mô hình
Cho 2 xâu X,Y. Hãy tìm xâu con của X và của Y có độ dài lớn nhất.
2. Công thức QHĐ
Gọi L(i,j) là độ dài xâu con chung dài nhất của xâu X(i) gồm i kí tự phần đầu của X (X(i)= X[1..i]) và xâu Y(j) gồm j kí tự phần đầu của Y (Y(j) =Y[1..j]).
Ta có công thức quy hoạch động như sau:
L(0,j)=L(i,0)=0.
L(i,j) = L(i - 1,j - 1)+1 nếu X[i] = Y[j].
L(i,j) = max(L(i - 1,j), L(i,j - 1)) nếu X[i] ≠ Y[j].
3. Cài đặt
Bảng phương án là một mảng 2 chiều L[0..m,0..n] để lưu các giá trị của hàm QHĐ L(i,j). Đoạn chương trình cài đặt công thức QHĐ trên như sau:
for i:=0 to m do L[i,0]:=0;
for j:=0 to n do
L[0,j]:=0;
for i:=1 to m do
for j:=1 to n do
if X[i]=Y[j] then
L[i,j]:=L[i - 1,j - 1]+1
else
L[i,j]:=max(L[i - 1,j],L[i,j - 1]]);
Như vậy chi phí không gian của bài toán là O(n²), chi phí thời gian là O(n²). Có một phương pháp cài đặt tốt hơn, chỉ với chi phí không gian O(n) dựa trên nhận xét sau: để tính ô L[i,j] của bảng phương án, ta chỉ cần 3 ô L[i - 1,j-1],L[i-1,j] và L[i,j-1]. Tức là để tính dòng L[i] thì chỉ cần dòng L[i -1]. Do đó ta chỉ cần 2 mảng 1 chiều để lưu dòng vừa tính (P) và dòng đang tính (L) mà thôi. Cách cài đặt mới như sau:
for j:=0 to n do
P[j]:=0;
for i:=1 to m do
begin
L[0] := 0;
for j:=1 to n do
if X[i]=Y[j] then
L[i,j]:=P[j - 1]+1
else L[i,j]:=max(P[j], L[j -1]);
P := L;
end;
4. Một số bài toán khác
a) Bắc cầu
Hai nước Anpha và Beta nằm ở hai bên bờ sông Omega, Anpha nằm ở bờ bắc và có M thành phố được đánh số từ 1 đến m, Beta nằm ở bờ nam và có N thành phố được đánh số từ 1 đến n (theo vị trí từ đông sang tây). Mỗi thành phố của nước này thường có quan hệ kết nghĩa với một số thành phố của nước kia. Để tăng cường tình hữu nghị, hai nước muốn xây các cây cầu bắc qua sông, mỗi cây cầu sẽ là nhịp cầu nối 2 thành phố kết nghĩa. Với yêu cầu là các cây cầu không được cắt nhau và mỗi thành phố chỉ là đầu cầu cho nhiều nhất là một cây cầu, hãy chỉ ra cách bắc cầu được nhiều cầu nhất.
Hướng dẫn:
Gọi các thành phố của Anpha lần lượt là a₁, a₂,...a_m; các thành phố của Beta là b₁,b₂,...b_n. Nếu thành phố a_i và b_j kết nghĩa với nhau thì coi a_i'bằng' b_j. Để các cây cầu không cắt nhau, nếu ta đã chọn cặp thành phố (a_i, b_j) để xây cầu thì cặp tiếp theo phải là cặp (a_u,b_v) sao cho u>i và v>j. Như vậy các cặp thành phố được chọn xây cầu có thể coi là một dãy con chung của hai dãy a và b.
Bài toán của chúng ta trở thành bài toán tìm dãy con chung dài nhất, ở đây hai phần tử 'bằng' nhau nếu chúng có quan hệ kết nghĩa.
b) Biến đổi xâu
Cho 2 xâu X,Y. Có 3 phép biến đổi với xâu X: chèn 1 kí tự, thay thế một kí tự hoặc xoá một kí tự. Hãy tìm số ít nhất các phép biến đổi để biến xâu X thành xâu Y.
Hướng dẫn:
Gọi F(i,j) là số phép biến đổi ít nhất để biến xâu X(i) gồm i kí tự phần đầu của X (X(i)= X[1..i]) thành xâu Y(j) gồm j kí tự phần đầu của Y (Y(j) =Y[1..j]). Dễ thấy F(0,j)=j và F(i,0)=i.
Nếu X[i]=Y[j] thì ta chỉ phải biến đổi xâu X(i-1) thành xâu Y(j-1). Do đó F(i,j)=F(i-1,j-1).
Ngược lại, ta có 3 cách biến đổi:
- Xoá kí tự X[i] và biến đổi xâu X(i-1) thành Y(j). Khi đó F(i,j)=F(i-1,j)+1.
- Thay thế X[i] bởi Y[j] và biến đổi X(i-1) thành Y(j-1). Khi đó F(i,j)=F(i-1,j-1)+1.
- Chèn Y[j] vào X(i) và biến đổi X(i) thành Y(j-1). Khi đó F(i,j)=F(i,j-1)+1.
Tổng kết lại, ta có công thức QHĐ:
F(0,j)=j
F(i,0)=i
F(i,j) =F(i - 1,j - 1) nếu X[i] = Y[j].
F(i,j) = min(F(i - 1,j),F(i,j - 1),F(i - 1,j - 1))+1 nếu X[i] ≠ Y[j].
c) Palindrom (IOI 2000) Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
Hướng dẫn:
Bài toán này có một công thức QHĐ như sau:
Gọi L(i,j) là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở thành đối xứng. Đáp số của bài toán sẽ là L(1,n) với n là số kí tự của S. Ta có công thức sau để tính L(i,j):
L(i,i)=0.
L(i,j)=L(i+1,j - 1) nếu S[i]=S[j]
L(i,j)=max(L(i+1,j), L(i,j - 1)) nếu S[i] ≠ S[j]
Bạn đọc dễ dàng có thể kiểm chứng công thức đó. Ta có thể cài đặt trực tiếp công thức đó bằng phương pháp đệ quy có nhớ. Tuy nhiên khi đó chi phí không gian là O(n²). Có một phương pháp cài đặt tiết kiệm hơn (bạn đọc có thể tham khảo ở bài báo trên của thầy Trần Đỗ Hùng), tuy nhiên phương pháp đó khá phức tạp.
Ta có thuật toán đơn giản hơn như sau:
Gọi P là xâu đảo của S và T là xâu con chung dài nhất của S và P. Khi đó các kí tự của S không thuộc T cũng là các kí tự cần thêm vào để S trở thành đối xứng. Đáp số của bài toán sẽ là n - k, với k là độ dài của T. Ví dụ: S=<b>edbabcd, xâu đảo của S là P=<b>dcbabde. Xâu con chung dài nhất của S và P là T=<b>dbabd. Như vậy cần thêm 2 kí tự là e và c vào để S trở thành xâu đối xứng.