Chủ đề này có 3 trả lời

[doductai]

Cho các số nguyên dương $k,m,n$ tm $1<n \leq m-1 \leq k$. $S$ là một tập con của $ \{1,2,\ldots ,k\}$ thỏa mãn không tồn tại $n$ p/tử phân biệt tổng bằng $m$. Tìm số phần tử lớn nhất của $S$

Bài viết đã được chỉnh sửa nội dung bởi manutd: 07-01-2007 - 17:23

[tanlsth]

Bằng qui nạp theo $ n $ ta chứng minh được $|S| \leq k-[\dfrac{m}{n}-\dfrac{n-1}{2}] $
Việc chỉ ra không khó khăn lắm

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 08-01-2007 - 13:03

[doductai]

Kết quả thì đúng rồi.
Bạn thử post lời giải lên xem nào!Việc chuyển quy nạp trong bài này cũng không phải đơn giản lắm.

[tanlsth]

Chọn $ r $ lớn nhất thỏa mãn $ r+(r+1)+..+(r+n-1) \leq m $
Suy ra tập $ S=\{r+1,r+2,..,k\} $ thỏa mãn
Từ đó suy ra $ |S| \geq k-[\dfrac{m}{n}-\dfrac{n-1}{2}] $
Việc chứng minh vế còn lại ta đưa về xét phần tử $ t $ nhỏ nhất của $ S $
Nhận xét $ nr+\dfrac{n(n-1)}{2} \leq m $(nếu ngược lại ta có điều phải chứng minh)
Từ đó xét $ S - \{t\}=S_1 $ và $ S_2=\{s-t/s \in S_1\} $
Áp dụng giả thiết qui nạp ta có điều phải chứng minh

Bài viết đã được chỉnh sửa nội dung bởi tanlsth: 08-01-2007 - 20:09