ThangTongHop

bài 4 đại khái ý là thế này
Đặt $a_{i}=2^{k_{i}}.l_{i} (l_{i}$ lẻ).
Dễ thấy có n số mà từ 1 đến 2n có n số lẻ nên các $l_{i}$ là phân biệt và gói trọn tập {1,3,5...2n-1}
Do $ 3^{k} \leq 2n $ nên có không ít hơn $ k $ luỹ của 3 nhỏ hơn 2n, các số này đều nằm trong tập các $l_{i}$ .
Nếu có $a_{i}=3^{t}2^{x_{i}}$ và $a_{j}=3^{d}2^{x_{j}}$ với d>t thì $x_{i}<x_{j}$ để thỏa mãn yêu cầu của dãy (**)
Ứng dụng với các lũy thừa $1, 3,3^{2},...,3^{k}$
Do đó trong dãy a phải có 1 số chia hết cho $2^{k}$ (Do và (**))
từ đó suy ra đpcm

bai` nay` dung` Co si ^^ rất hay
do ko mất tjnh' TQ nên giả sử a=max {a,b,c}

De dang` chứng mjnh đc
$ a \geq b \geq c $

Sau đó cô si từng cặp ,đánh giá => đpcm ^^

Ah ha em quên, TH1 cần dùng Giả thiết chẵn. Để em post lại lời giải đầy đủ cuối cùng

Xét G là clique dài nhất và có 2k người
Ngoài G ta xét H là clique dài nhất và ko là clique con của G, đồng thời nó có ít người chung với G nhất
Ta cho tất cả những người trong H vào phòng B và tất cả nhg người còn lại vào phòng A
Giả sử G,H có chung j người và H có i người thì clique G trong phòng A còn lại 2k-j người và biến thành Clique G'

+TH1: $ 2k-j \geq i$
Nếu $ k \geq i$ TH này chỉ việc chia G thành 2 phần, mỗi phòng 1 nửa và bài toán xong, ko cần chuyển clique H
Nếu k<i
Ta chuyển dần người từ clique G sang phòng B đến khi 2 bên có cùng độ dài i( TH trong khi thực hiện B đạt độ dài >i sẽ vô lý vì clique đó gồm toàn ng' của G và từ đó $ k \geq i $

+TH2: $ 2k-j \leq i $
Ta chọn 1 clique bất kì của A và ta cho ng' từ B sang A cho đến khi ko thể được hoặc đạt maxB-maxA=1
Gọi $ S_{i} $ là số ng' cần chuyển ít nhất từ B->A vào clique i của A để có thể đạt trạng thái maxB-maxA=1 (với điều kiện clique này có thể thực hiện được như vậy)
Ta chọn số min $ S_{i} $=n và chuyển ngần ấy ng' của A vào clique i, ta có trạng thái maxB-maxA=1

Lúc này xét 1 trong các clique có độ dài bằng maxA
- Nếu clique đó nhận ít hơn n người ( trước khi x được chuyển) thì nghĩa là nó ko thể nhận thêm ng' từ B( vì nếu ko thì chỉ cần $ S_{i} $ ng' được chuyển là ta có maxB=maxA)

Ta chuyển 1 ng' bất kì x từ B -> A. Nếu lúc này maxB=maxA, bài toán xong, còn nếu maxA-maxB=1

Xét các clique có độ dài maxA
- clique đó nhận đúng n+1 người( do lý luận trên) ta chọn 1 ng' bất kì từ clique đó( khác nhg ng' bị chuyển) chuyển sang B
Sau những động tác trên ta thấy maxA giảm 1( do các clique max mất 1 ng') còn maxB ko đổi( vì nếu trong B có 1 clique>maxA thì ghép thêm n+1 ng' đã chuyển vào sẽ tạo ra 1 clique có độ dài >i và khác 2k ), do đó bài toán xong

Về TH2 anh xem cái đoạn phía dưới ý, em có post rõ lại rồi đấy, ghép 2 đoạn vào là ok:D

Sr em giải nhầm bài 6, nhờ các anh xem giúp bài 3 em giải thế có được ko