combi USAMO 1999 proposal
 

ให้ n,k,m, เป็นจำนวนเต็มบวกโดยที่ n>2k ให้ S เป็นเซต(ที่ไม่เป็นเซตว่าง)ของ สับเซตที่มีขนาด k ของเซต {1,2,...,n} โดยที่ ทุกสับเซตขนาด k+1 ของ {1,2,...,n} จะมี m เซตจาก S ที่เป็นสับเซตของมัน จงพิสูจน์ว่า S เป็นเซตของ สับเซตขนาด k ของ {1,2,...,n} ทุกเซต

(เผื่อผมเขียนไม่ชัดเจน) Let n, k and m be positive integers with n > 2k. Let S be a nonempty set of k-element subsets of {1, 2, ..., n} such that every (k+1)-element subsets of {1, 2, ..., n} contains exactly m elements of S. Prove that S must contain every k-element subsets of {1, 2, ..., n}.


ป.ล.double counting ได้ m(n เลือก k+1)=(n-k)|S| แล้วอะครับ ทำยังไงต่อ

This heavily involved the use of Number Theory !! :happy:

1) $|S| = m \cdot \dfrac{n!}{(n-k)!(k+1)!}$ จากที่คุณได้มาก่อนหน้านี้

2) $|S|$ must be an integer

3) เพียงพอที่จะพิสูจน์ในกรณีี $n=2k+1$ (ทำไมกันน่า?)
หมายเหตุ :
4) พิสูจน์ว่า $m=k+1$