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$ (ทำไมกันน่า?) หมายเหตุ : จะเหลือ $|S| = m \cdot \dfrac{(2k+1)!}{(k+1)!^2}$ 4) พิสูจน์ว่า $m=k+1$ |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 20:35 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha