VỀ PHÂN HOẠCH TẬP CÁC SÔ NGUYÊN DƯƠNG THÀNH HAI TẬP CÓ TỔNG CÁC PHẦN TỬ BẰNG NHAU

VỀ PHÂN HOẠCH TẬP CÁC SÔ NGUYÊN DƯƠNG THÀNH HAI TẬP CÓ TỔNG CÁC PHẦN TỬ BẰNG NHAU.

Nguyễn Hải Đăng – Nguyễn Thành Khang – Nguyễn Văn Lợi

Trong bài báo này ta chi ra đươc rằng chỉ cần thỏa mãn một số điêu kiên biểu diễn đơn giản, chúng ta có thể xây dựng môt cầu trung chuyển giứa thuật toán xếp ba lô và thuât toán ăn tham. Do đó một loạt các criteria - vê phân hoach các tập sô nguyên dương thành hai tâp bằng nhau- đươc chưng minh.

Bắt đâu từ những năm 1990 các nghiên cứu các bai toán tối ưu của toán học dời dạc bắt đâu phát triển. Trong viêc phân bổ các tâp hợp con theo nhưng điều kiên cho trước, rât nhiều lần thuât toán xếp ba-lô và thuât toán ăn tham được sử dụng. Thuât toán xếp ba-lô có thể phát biểu như sau: các đô vật được xếp vào hai chiếc ba–lo làm sao cho đầy nhất. Đầu tiên ta sắp xếp đồ vật theo thứ tự giảm dần. Sau đó lân lươtt chúng ta xếp vào mỗi ba-lô một vật. Sau môi lân xếp , người ta lại kiêm tra xem ba-lô nào còn nhiều chỗ hơn, thì sẽ được ưu tiên xếp trước. Cứ tiếp tục quá trinh như vậy ta sẽ nhận được một cách sắp xếp tối ưu. Về thuật toán tham ăn, nội dung của nó là: ta cứ xếp vào các ba-lô cho đến khi không con bỏ thêm đươc nữa, sau đo mới băt đầu thay đôi vị trí các đồ vât từ ba-lô này sang ba-lô kia, để hơp ly hóa công việc sắp xếp. Trong bài này chúng tôi sử dụng môt phương pháp trung gian lưu chuyển giữa hai thuât toán này. Trước khi sắp xếp chung ta lựa chọn ra những đồ vật nhỏ nhất thành một tập hơp K, với mục đich: khi đã „ăn tham” tương đối đầy các ba-lô, thi ta dùng tâp các đồ vật nhỏ từ K, để tiếp tục chèn vào những lô hổng, cho đến khi đày chặt ba-lô. Một tập hợp các vât nhỏ như vây được gọi là biểu diễn được đến k, nếu các vật nặng từ 1 (nhỏ) đến k (đủ nặng) đều có thể biểu diễn được bằng tổng các đồ vật lấy từ tập K.

I) MỞ ĐẦU.

Chúng ta chỉ làm viêc với tâp hợp các số nguyên dương, và các tâp có hữu hạn phần tử. Môt định lý quen thuộc được sử dụng nhiều trong quá trình chứng minh.

PROPOSITION 1.1. Từ n số nguyên cho trước, Luôn chọn đươc môt vài số để tổng của chung chia hêt cho n.

E G Z -THEOREM 1.2. Từ 2n-1 số nguyên cho trước, luôn chọn được n số sao cho tổng của chúng chia hết cho n.

Định lý EGZ (Erdős Pál, Abraham Ginzburg és Abraham Ziv) đươc chứng minh năm 1961.

LEMMA 1.3. Với (n-1) số nguyên dương bất kì, mà không tôn tại một vài số nào, để tổng của chúng chia hết cho n, thì n-1 số đó sẽ có cùng số dư khi chia cho n.

Proof. Giả sử n-1 số đã cho là a₁, a_2,…, a_n-1. Ta chưng minh bằng phản chứng rằng tồn tại 2 số không có cùng sô dư khi chia cho n. Không mất tổng quát gọi 2 số đó là a₁ và a₂ với 2i ≤ (n-1) đặt s_i=a₁+a₂+…+a_i. Xét dẫy a₁, a₂, s₂, s₃, .., s_n-1 có n số, và không số nào chia hêt cho n. Vậy tồn tại hai số có cùng số dư khi chia cho n. Xét hiệu của hai số này. Vi (a₁- a₂) ≠ 0 mod n , nên chi có thể là hiệu cua s_i va một số nào đó trong a_1, a_2, hoăc s_j. Trong bất ki trường hợp nào, hiệu đó cung là tổng của một vài số trong (n-1) sô ban đầu. Do đó chi có thể là tât cả (n-1) có cùng số dư khi chia cho n.

Môt vân đề đươc đặt ra là: Cho môt tập A có k số ( phần tử) là các số nguyên dương không lớn hơn N và tổng của các số này bằng 2N.

Tồn tại hay không giá tri K nhỏ nhất để với mọi k ≥ K, tâp A luôn phân hoạch thành hai tập con có tổng các phần từ mỗi tập bằng N. (*)

Đinh lý sau sẽ cho môt chặn trên của của số K , va trong trường hợp N là lẻ thi giá tri K=N+1 cung là giá trị nhỏ nhất cần tìm.

THEOREM 1.4. Với k=(N+1) sô nguyên dương không lớn hơn N, có tổng là 2N, luôn phân hoach đươc thành hai tâp con, mỗi tập có tổng là N.

Proof. từ (N+1) số đã cho lấy N số bât kì, khi đó theo (1.1) ta co thể chọn từ N số này môt vai số có tổng chia hết cho N . Tổng này nhỏ hơn 2N và dương vì vây chỉ có thể là N. Phần bù của tập nêu trên cũng sẽ có tổng là N.

Ghi chú: Nếu N lẻ, và số phần tư k=N, xét tâp A={ 2, 2, 2,…, 2 : N số 2}. Tổng cac số cua A bằng 2N, Nhưng vì tất cả các phân tử của A là chẵn, nên A không thể phân hoạch thành hai tập con có tổng bằng N ( là số lẻ). Điều này cũng chứng tỏ K=N+1 là giá tri cần tìm thỏa mãn tính chât (*) khi N là số lẽ.

Trường hợp N là số chẵn, tinh hinh phức tạp hơn hẳn. Ta co thể cảm nhận được qua mệnh đề sau:

PROPOSITION 1.5. Với N=2n và A là tâp của k (=2n-1) số nguyên dương không lớn hơn N và có tổng là 2N, thi A luôn co thể phân hoach đươc thành hai tập con, mỗi tập có tổng là N.

Proof. theo đinh lý E-G-Z áp dụng cho 2n-1, ta luôn chọn đươc từ cac số của A n số sao cho tổng của chung chia hêt cho k. tông này chỉ có thể là k,2k,3k. Nêu bằng 2k=N thi phân hoach đã xong. Ta chi cân xet truongf hợp còn lại. ta co 2 tâp a₁≤ a₂≤ …≤a_k và b₁≤ b₂≤…≤ b_k-1. Đặt a=∑a_i và b=∑b_j khi đo {a, b}={k, 3k}.

i)Xét trường hơp:a=k và b=3k. Có đúng k sô nên a₁=a₂=…=a_k=1. Vi b=3k nên

b_k-1 ≥3. Nếu b_k-1 ≥k thi chọn b_k va môt sô sô 1 ta tao đươc tổng N. Nếu b_k-1< k Xét a_1,, a_2, b₁, b₂,…,b_k-2 (b_k-1 bi loại) ta co k số, theo (1,1) ta có môt vài số co tổng chia hết cho k. nếu bằng 2k thi xong. Vi không thể bằng 3k nên chi con trường hơp bằng k. vi b_k-1 co thể bù thêm cac giá tri 1 để bằng k – nên gộp hai lủa chọn này ta co tông 2k.

ii) Xét trường hơp:a=3k và b=k. ta cũng suy ra b₁=b₂=…=b_k-2=1 và b_k-1=2. Đổi a_k va b₁ cho nhau. lý luận tương tự như phân trên ta cũng chon dduoc tông N. Mệnh đề được chứng minh hoàn toàn.

Để ý rằng trong mệnh đề 1.5 ta hoàn toàn dùng thuât toán tham ăn. Mệnh đề 1.5 cho ta thấy trong trường hợp N chẵn thi viêc đi tim cận dưới K của số các phần tử còn nhiều trở ngại.

Một sô vi dụ:

Trong tât cả các trường hợp sau 2N là tổng các phân tử trong tâp A. k là số phần tử của A. Ta chỉ xét trường hợp N là số chẵn.

a) Với N=6m+2.

Phản ví dụ với k=4m+2 cho A={1; 3, 3,…,3 : có một số 1 và 4m+1 số 3} khi đó, dù bât ki mọi phân hoach, ta có một tổng chia hêt cho 3 và tông còn lạikhông chia hêt cho 3, do đo không tồn tai phân hoach chia đôi. Điêu này chứng tỏ K≥4m+3

b) Với N=6m+4.

Phản ví dụ với k=4m+3 Cho A={2; 3, 3,…,3 : có môt số 2 và 4m+2 sô 3} khi đó dù bât kì mọi phân hoạch, ta có môt tổng chia hêt cho 3 và một tổng không chia hêt cho 3, do đó không tồn tai phân hoach chia đôi. Điều này chứng tỏ K ≥ 4m+4.

c) Với N=6m.

Phản ví dụ với k=3m+1. Cho A={2; 2, …,2, 3, (6m-1) : có (3m-1 số 2, một sô 3 và môt sô (6m-1)} , pt (6m-1)+ x =6m không co lời giải trong A. Điêu này chứng tỏ K ≥ 3m+2.

Để tiêp tục nghiên cứu các khả năng phân hoạch của 2N, chung ta phải đi sâu hơn nữa vào sự có măt của các phân tử tạo thành của tâp A.

II. Cấu trúc của các tập số và khả năng phân hoạch chia đôi (công cụ biểu diễn hoàn chỉnh).

Trong phần này chung ta sẽ xây dưng một ly thuyêt nhỏ để lam cầu nôi giữa hai hai thuât toan : Thuât toán xếp ba lô và thuật toán ăn tham. Cụ thể là ta dung thuât toán ăn tham lúc đầu , nhưng trước đó đã chuân bi sẵn môt tâp hơp cac số đủ nhỏ để gài vào cac chô hở mà những đô vật lớn không con khả năng chèn vào tiếp tục. Với phương pháp nay viêc phân hoach của chung ta vân con khả năng và sô phân tư phân chia cung giảm hẳn đươc. Bí quyêt cua thuật toán này chinh là cac khả năng biểu diễn đươc các đai lượng bằng 1,2,3,…..

Tập A các số nguyên dương goi là biêu diễn đươc đến s nếu tât cả các số từ 1 đến s đều có thể viết bằng tổng của một vài số lấy từ A và các sô lấy ra không sử dụng quá số lần mà nó có mặt trong tập A.

Vi dụ: A={1,1,2,3} thi 4=1+3 là cho phép, nhưng 4=2+2 là không cho phép vi 2 chi có mặt trong tập A một lần . Biểu diễn 5=1+1+3 cho phép vì số 1 có 2 lần trong A.

Tập A được goi là hoàn chỉnh (HC) nếu a là tổng các sô của A , thi A biểu diên được đến a.

PROPOSITION 2.1: Nếu A và B là hai tâp hoan chỉnh thi C=A U B cung là tập hoàn chỉnh.

Proof: Cho a=Sum(A) và b=Sum(B). không mất tổng quát ta co thê cho a ≤ b. Gọi C=A U B. Khi đó c=Sum(C)=b+Sum(A-B) và c≤ a+b. Giả sử x là môt sô sao cho b< x< c vậy x=c-(c-x). Mặt khác

c-x<a+b-b=a ≤ b,

do đó chi cần từ B loại những số biểu diễn c-x, ta sẽ có tổng từ C biểu diễn x.

Goi H là hợp của tât cả các tâp hoàn chỉnh trong A. ( có hữu hạn phần tử) khi đó theo (2.1.) H cung là tâp hoàn chỉnh. Từ cách chọn H suy ra H là lớn nhất. Ta có kết quả sau:

LEMMA 2.2. Cho A là tập của các số nguyên dương và 1 nằm trong A. Khi đó luôn luôn tồn tại duy nhât tập con hoàn chinh lớn nhất trong A. Goi tâp hoàn chỉnh này là H, nếu tât cả cac phân tử của A đêu nhỏ hơn h=sum(h_i:h_i trong H) thi H=A. Nêu a không nằm trong H thi a ≥ h+2.

Cho tâp A ={ a₁,a₂,…, a_r : a_i nguyên dương }. Vi ta đang nghiên cứu viêc phân hoach A thành hai tập con bằng nhau, nên đòi hỏi tổng các sô của A chẵn, là hiển nhiên. Ki hiệu

2N=a₁+a₂+…+a_r (và a_i ≤N).

tâp A như trên đươc ki hiêu ngắn gọn là A(2N,r). Ta luôn có điêu kiên cac số không vươt quá nửa tông của cac số (a_i ≤N).

Ký hiệu <N/p> = N/p nếu N/p nguyên va <N/p> = [N/p]+1, nêu N/p không là số nguyên ( thực chất đây là kí hiêu phần nguyên chặn trên của số N/p).

PROPOSITION 2.3. Nếu tập A(2N, r ≥ <N/2>+2). Thì A có ít nhất 3 số có giá trị nhỏ hơn 4.

Proof: Vi 4(r-3) ≥ 4(<N/2>+2-3) ≥ 4(N/2-1)= 2N-4, và

4(r-2) ≥ 4(<N/2>+2-2) ≥ 4N/2= 2N.

như vậy không còn giá tri cho các sô khác. nên các sô có giá tri lớn hơn 3 có nhiều nhât là r-3 số.

Cac dạng co thể của 3 số ban đầu:

a) (1, 1, 1) ; (1, 1 , 2) , (1, 1, 3), (1, 2, 2), (1, 2, 3) các bộ số hoàn chỉnh (HC), và

b) (1, 3, 3), (2, 2, 2), (2, 2, 3), (2, 3, 3) và (3, 3, 3) các bộ không biểu diễn được.

THEOREM 2.4. Cho A(2N, r ≥ <N/2>+2) H là tâp hoàn chỉnh lớn nhất trong A. nếu H biểu diễn đươc it nhất đến 3 thi tập A phân hoạch đươc thành hai phân bằng nhau.

proof. đặt S=sum(H),theo (2.2) ta có viết :

2N=S + a₁+a₂+…+a_p trong đo a_i ≥ S+ 2 (1)

i)Đầu tiên ta chứng minh S ≥ N/2-1. giả thiêt phản chứng S<N/2-1, ta sẽ chưng minh 2N không viêt đươc dưới dang (1). Gọi q là số phân tử cua H, khi đo r = q+p. Rõ rằng S ≥ q ,

S + a₁+a₂+…+a_p ≥ S+ p.(S+2)=S+(r-q)(S+2) ≥ S+ (r-S)(S+2)

≥ S+2r+ rS -S² -2S= -S² +(r-1)S+2r >= -S² +(N/2+1)S+(N+4) = f(S)

khi đó

f(S)-2N = -S² +(N/2+1)S – (N-4) = -2S² +(N+2)S – 2(N-4) .

ta có : D=(N-6)² + 32 >0 suy ra với S trong khoảng 2 nghiệm thi biểu thưc luôn dương, co nghĩa là f(S)-2N>0. Xét

[(N+2)+ căn(D)]/4 > S > [(N+2)- căn(D)]/4

vì [(N+2)+ căn(D)]/4>(N+2+N-6)/4=N/2 -1

[(N+2)- căn(D)]/4<(N+2-N+6)/4=2 < 3

tông hợp cả hai truong hợp ta đươc nếu 3 ≤ S ≤ N/2 - 1

2N ≥ f(S) > 2N , vô lý. Điều đó chứng tỏ S ≥ N/2 – 1.

b) truong hợp S ≥ N/2 – 1. Ta sẽ chưng minh A phân hoạch được.

2N = S+ a₁ + a₂ +…+a_p với a_i ≥ S+2 ≥ N/2 + 1

2N ≥ S+ p(S+2) ≥ (N/2-1)+p(N/2+1)

è do đo p ≤ 2. (vì p nguyên) .

q la số phân tử của S do đo: r=q+p= N/2 +2 suy ra nếu

i) p=2 => (N/2+2) < a₁, a₂ ≤ N, ta có

N/2-1+N ≥ S+a₁ ≥ N/2-1+ N/2+1=N

vi thế x= (S+a₁)-N ≤ S nên có thể bớt x từ S để phân cò lai của S và a₁ sẽ đươc tổng N.

ii) p=1 không thể vì khi đó a₁>N.

Do đo tập A(2N, r ≥ <N/2>+2) phân hoạch được thanh hai phân bằng nhau. dpcm.

Ghi chú: các phân hoach (1, 1, 1) ; (1, 1 , 2) , (1, 1, 3), (1, 2, 2), (1, 2, 3) là các bộ sô tốt, biêu diên được it nhất đến 3.

Bây giờ ta tiếp tuc khảo sát các truong hơp 3 sô đâu là a) (2, 2, 2) hoặc b) (2, 2, 3):

a) Trường hợp(2,2,2). Như vây cả dãy mỗi số it nhât là 2, tông cộng: 2.r= 2.<N/2>+2 >= N+4. Chi còn N-4 để phân chia cho các số còn lai.

b) trường hợp(2,2,3) chi còn N-5 để phân chia cho các số còn lai.

PROPOSITION 2.5. Nếu A(2N, r ≥ <N/2>+2) la môt cấu hinh mà sô thứ nhất không nhỏ hơn 2. thi bất ki hai số nào của dãy đều có tổng không vượt quá N.

Proof. mỗi sô đêi có giá tri ít nhât là 2, như vây độ lơn tự do để phân cho các sô không còn quá N-4. Vì thế tổng 2 số không thể vượt quá : (N-4)+2+2 = N.

THEOREM 2.6. Trong trương hợp A(2N=4M, r>=M+3) và ba số đâu tiên của câu hình là

a) (2, 2, 2) hoăc b) (2,2,3)

thi A(2N, r) phan hoach được thành hai phần bằng nhau.

Proof. Vi N=2M, nên r ≥ <N/2>+3=M+3. Trong cả hai trường hợp số thứ 6 không vượt quá 3 vì : 2.6+4.(M-3)=4M. vi thế trong trường hơp (b) 6 sô đàu tiên phải là (2,2,3,3,3,3).

Chia các số của tâp A thành 2 nhóm: nhóm các số chẵn a₁, a₂,…, a_u , và b₁, b₂,…,b_v là nhóm các số lẻ. Khi đó r=u+v=M+3 va u≥ 3 ( trường hợp (a) hoặc u≥ 2 trường hợp (b)

2N=4M=(a₁+a₂+…+a_u)+(b₁+b₂+…+b_v)

vi 2N chẵn nên v phải là số chẵn). Ta lâp môt dãy mới: c₁=b₁+b₂, c₂=b₃+b₄ ….. ( cứ hai số lẻ ta gép lai thành một số chẵn). Ta đươc các số a₁,a₂,…,a_u, c₁, c₂,….. c_t trong đo t=v/2 ( v là số chẵn).

Xét bộ số : d_i=a_i/2 ( i=1,2,…, u) va d_u+j=c_j/2 (j=1,2,…,t). Ký hiệu

D={ d_i : i=1,2,…, (u+t) }. ( D gôm u+t số mỗi só bằng môt nửa sô tương ứng của dãy trước). Các sô này có tổng là 2M=2N.

2M=d₁+d₂+…+d_u+t

Trường hơp (a) d₁=d₂=d₃=1 . Trường hơp (b) d₁=d₂=1 và d₃=d₄=3.

i) Xét Trường hợp u≥ 3

u+t=3+(u-3)+v/2 =3+(u-3)/2 + (u+v-3)/2

=3+(u-3)/2+ (M+3-3)/2 ≥ 3+ M/2= 2 + (M+2)/2 ≥ <M/2>+2.

tâp D(2M, r≥ <M/2>+2) biểu diễn đươc it nhât đến 3 , do đó áp dụng được (3.4.) D có thể phân hoạch thanh hai tập con có tổng các sô bằng nhau va bằng M.

ii) Trường hợp u=2. khi đo r≥ M+3=u+v=2+v n vậy v=M+1. Vi v là số chẵn do đó M lẻ.

u+t>=2+(M+1)/2=2+<M/2>.

tâp D(2M, r>=<M/2>+2) và biểu diễn đươc ít nhât đến 8 (1,1,3,3) do đó áp dụng được (3.4.) D có thể phân hoach thanh hai tập con có tông cac sô bằng nhau va bằng M.

Vi D phân hoạch đươc, nên khi gấp đôi trở lại cácgiá tri của D, ta đươc phân hoạch của tâp hợp A thành hai phân bằng nhau và bằng 2M=N. dpcm

Các trường hợp (1;3;3);(2;3;3) và (3;3;3) sẽ được giải quyết triêt để trong trương hợp N=6n. trong phân áp dung sau đây.

III. ÁP DỤNG.

COROLARY 3.1. Cho N=6n+2, va r=4n+3. Tập A(2N, r) phân hoạch được thành hai tập có tổng bằng nhau.

Proof. Số phần tử của A thỏa mãn :

r = 4n+3> (3n+1)+3 = <(6n+2)/2> +3 = (3n+1)+3

Sắp xếp các phần tử của A theo thứ tự tăng dần. a₁ ≤ a₂ ≤…≤a_r . Nếu a₃ >2 thì

a₃ + a₄ +…+ a_r ≥ 3.(4n+1)=12n+3

suy ra a₁+a₂ ≤ 1 vô ly , vi đây là dãy các sô nguyên dương. Các trường hợp có thể xảy ra với 3 số đâu tiên là:(1,1,1) , (1,1,2), (1,2,2), hoăc có dạng (2,2,2). theo đinh lý (2.4) ba trường hợp đầu, hoăc Đinh lý (2.6.) trường hợp cuối, tâp A phân hoạch được thành hai phân bằng nhau.

COROLARY 3.2. Cho N=6n+4, va r=4n+4. tâp A(2N, r) phân hoach dươc thanh hai tâp bằng nhau.

Proof. 2N=12n+8. số phân tử của A thỏa mãn

4n+4 ≥ (3n+2)+2= <(6n+4)/2> +2 =(3n+2)+2

tương tự như chứng minh trên, ta có

a₄ + a₅ +…+ a_r ≥ 3.(4n+1)=12n+3

suy ra a₁+a₂+a₃ ≤ 5. Do đó ba sô nhỏ nhât của dẫy chi có thể là (1,1,1) , (1,1,2) và (1,2,2). Theo định lý (2.4.) tâp A phân hoach đươc thành hai phần bằng nhau.

COROLARY 3.3. Cho N=6n, va r=3n+3. tâp A(2N, r) phân hoạch dươc thanh hai tâp có tổng bằng nhau.

Proof. Nếu a₄ >3 thi

a₄ + a₅ +…+ a_r >=4.(3m-1)=12m-4

do đó a₁+a₂+a₃ ≤ 4 cac truong hợp có thể: (1,1,1) ( 1,1,2) đêu là tâp hoàn chỉnh.

nếu a₄ ≤ 3 khi đó : hoặc (a₁, a₂, a₃, a₄ ) hoàn chỉnh, hoặc

các trường hợp khác có thể: (2,2,2,2), (2,2,2,3), (2,2,3,3). Cac trường hơp này Đinh lý ( 2.6.) đêu phân hoạch được.

Với các trương hợp (1,3,3,3) (2,3,3,3), và (3,3,3,3). Nhận thấy rằng các tập trên đêu có it nhất ba số 3. ta phân làm hai nhóm

nhóm chia hêt cho 3 : b₁, b₂,…, b_u khi đó u>=3 và b₁=b₂=b₃=3

nhóm không chia hêt cho 3: c₁, c₂, …, c_v.va u+v = r >3n+3.từ (1.1) đảm bảo cho ta lại phân được các sô c_i thành các khối số gồm không quá 3 số, và có tông chia hêt cho 3. Gọi các số mới đươc thành lâp tư cach phân khối trên la d₁, d₂,…, d_t. Nhận thây rằng t ≥ <v/3> ( phân nguyên chặn trên của v/3). từ cac sô b_i, dj ( là cac số chia hêt cho 3) ta tạo thành dãy mới: e_i=b_i/3, i=1,…,u và e_n+j=d_j/3 ta đươc dãy 1,1,1, e₄,....,e_u, e_u+1, …, e_u+t. xét thấy

u+t>3+(u-3)+v/3≥ 3+ (u+v-3)/3=3+(3n+3-3)/3=3+n.

tông cac sô của dãy mới là 4n. Số phần tử là (n+3). Dãy này có 3 số đầu tiên là (1,1,1) vậy biểu diễn được đến 3. Theo Định lý (2.4) tập

E(4n, r=n+3) phân hoạch đươc thành hai phần bằng nhau. Từ đây chi cấn nhân cac khối số với 3, và tách các số ra khổi, ta đươc phân hoạch thanh hai phân bằng nhau cua tâp hợp A.

Cuôi cung ta giai quyêt bài tâp có tác dung thuc đẩy toàn bộ nghiên cứu này.

COROLARY 3.4. Chứng minh rằng 35 sô nguyên dương không vươt qua 50 và có tổng bằng 100, thì chia đươc thành hai tâp con có tổng bằng 50.

a)Chưng minh thứ 1. ta sử dụng đinh lý 3.4.

N=50. 2N=100. r=35 > <N/2>+2 = 25+2=27. Vi 32.3=96, vây 3 số nhỏ nhất cua dãy đêu nhỏ hơn 3. các truong hơp có thể (1,1,1), (1.1.2), (1,2,2). cac tâp này đêu hoàn chỉnh. vây tâp của ta phân hoach đươc thanh hai phân bằng nhau.

b)Cach thứ 2 là chứng minh độc lâp của riêng bài toán này.

Bổ đề dung nhiều nhất:

BỔ ĐỀ : trong 5 sô nguyên luôn tim được một vài số để tổng của chúng chia hết cho 5.

1) phân hoạch 35 số thành các nhóm, mà tổng các số trong mỗi nhóm chia hết cho 5. Theo bổ đề viêc này hoàn toàn thưc hiện được. Môt phân hoạch được goi là mịn nếu không có nhóm nào có thể chia thành 2 nhóm nhỏ hơn và vẫn chia hết cho 5. Môt phân hoach mịn đươc gọi là rất mịn nêu sô lượng nhóm của nó là cực đại.

2) Với môt phân hoạch mịn số các số trong một nhóm không quá 5. Trong một phân hoạch mịn it nhất phải có 7 nhóm.(2*)

3) từ 5 nhóm của môt phân hoạch (chia hết cho 5) đều tìm được môt sô nhóm mà tổng các số của các nhóm đươc chọn chia hêt cho 25.(bổ đề sử dung 2 lần liên tiêp). (3*)

4) trong môt phân hoach từ 7 nhóm trở lên, nếu co 1 nhóm có tổng các sô là 25

( hoăc 50) thi sẽ tôn tại chia đôi các số, để có tổng 50 và 50. ( từ ít nhất 6 nhóm sẽ chọn đươc tổng 25 hoăc 50 bằng cách chọn ra 5 nhóm và áp dụng bổ đề). ky hiêu trường hợp này kí hiệu là (4*).

Ta quay về chứng minh cho bài toán. Với giả thiết phản chứng.

a) Không tìm được phân hoạch có tổng 50 và 50 ( vi đây là kêt quả không cần xét)

b) không tôn tại phân hoạch co it nhât 7 nhóm và có một nhóm có tổng bằng 25 (vì (4*) đã giải quyết.)

(cac nhóm ki hiệu là A1, A2,…, An xếp theo thứ tự tăng dần.)

5) T.hợp co it nhất 10 nhóm, có hai cách lựa chọn: A1,A2,…,A5 và A6,A7,..,A10 hoăc A1,A2,A3,A4, A10 va A1, A6,A7,A8,A9 sẽ chon đuợc tông 50.

6) TH có 9 nhóm: từ A1,A2,A3,A4,A5 chỉ chọn được tổng 25. Nếu không quá 3 nhóm làm nên tông 25. thi gộp chúng lai thành một nhóm va bài toán được giải quyêt theo (4*). Suy ra phải có it nhât 4 nhóm làm nên tổng 25è 25=5+5+5+10) hoăc 25=5+5+5+5+5. Mặt khác, nêu A9=20 thi chi có thê có câu trúc 75=15+20+20+20. Hoặc 25<A9<50, cả hai trường hợp này luôn chọn được tổng 50.

7) T. hợp có 8 nhóm: khi đó A7+A8>25(vi nêu là 25 thi ghép chúng vào một nhom như vây xẩy ra trường hợp (4*)). Từ A1,A2,…,A5 như vây chi có thể chọn tổng 25. tổng này cũng đươc tạo từ it nhât 3 nhóm ( từ hệ quả (4*)) do đó co nhóm có tổng 5 (bé nhât) vây cũng có luôn A1=5. Xet tiêp tục, chọn A2, A3, A4,A5,A6 ta lại có tổng 25 và it nhất 3 nhóm tạo nên. Do đó lai có 1 nhom 5, suy ra A2=5. Tiếp nữa, không thể có nhóm có giá tri 20 vi lại xảy ra (4*). Do đo hoăc A3=A4=…=A8=15 từ đây 50=5+15+15+15, hoăc A8>25 (vi 4*). Lại chọn được từ A3,A4,…,A7 một tổng 25, lý luận tương tự A3=5. Nếu A8>30 thi từ A1= A2=A3 =5 luôn bỏ sung được thành 50. Vay còn THợp A8=30. chon A1, A2,A3,A7, A8 khi đo lạii co tổng 25, do đo chi co thể A7=10 hoăc 15.(không thê 20 và 25). Nêu A7=10 thi 5+5+5+10+10+10+10+30 không đủ 100. vây A7=15. khi đo 5+5+5+10+15+15+15+30 la xắp xếp tướng ứng. vây ta cũng chon đươc 50.

8) Trường hợp phân hoạch có 7 nhóm: mỗi nhóm có đúng 5 số. Đây là phân chia rât min nên giưa hai số bât kì từ hai nhóm khác nhau luôn luôn co khoảng cách là sô chia hết cho 5 , từ đo suy ra trong môt nhóm thi khoảng cach giưa 2 sô cung phải luôn luôn phải chia hêt cho 5(ki hiệu 8*). Mặt khác trong 35 sô phải co hoăc số 1 hoăc số 2 va theo (8*) hai sô này không đi cùng nhau. Nếu sô đầu tiên ( số bé nhât là 2) ta có : 2.35=70. và mỗi số co dang 2+5k .Như vây chi co thể có không quá 6 (=30:5) số lớn hơn 2. vây có it nhât 29 (=35-6) sô 2, từ đây chon 25.2=50.

Nếu sô đâu tiên là 1, cac sô co dang 1+5k. do đo có không quá 13(= 65:5) số lớn hơn 1, tức là có ít nhất 22 số 1. Do đó có 4 nhóm toàn sô 1 ( tông bằng 5) còn lại 3 nhóm tổng bằng 80.Suy ra nhóm A7 >=30. Do đo A7 va 4 sô 5 sẽ tạo đươc 50. Nêu A7 > 50, ta dùng thay đôi vi tri các con số từ A5, A6 để làm giảm tổng của A7 xuống dưới 50. A7 chỉ có thể là 55, 60, 65, 70 . Nêu A7>=55 thi A5+A6<=25 suy ra A5<=10 vây A4=1+1+1+1+1 hoăc A4=1+1+1+1+6. Và nêu A7 chứa sô không nhỏ hơn 21 thi đổi môt sô 1 của A4 cho sô đó, nêu không có, thi đổi 2 sô 1 cho 2 sô lớn nhất của A7. Ta đã hạ đươc độ lớn của A7 xuống dưới 50. Và như vậy voi 4 sô 5 ban đầu ta lại điêu chinh đươc để co tổng 50.

ĐPCM.

REFERENCES

Lovász L. Pelikán J. Vesztergombi K. Discrete matematics

(Erdős Pál, Abraham Ginzburg és Abraham Ziv: Theorem in additive number Theory. Bull. Research Council, Israel, 10F; 4 1-43; 1961.).