#1
|
|||
|
|||
สมาชิกในเซต
ให้ m,n เป็นจำนวนเต็มบวกใดๆ ที่ m<n ให้ F เป็นเซตของ(สับเซตที่มีสมาชิก m ตัวของ เซตที่มีสมาชิก n ตัว)โดยที่แต่ละสับเซตจะมีสมาชิกร่วมกันอย่างน้อย 1 ตัว จงหาว่าสมาชิกใน F เป็นไปได้มากที่สุดเท่าไร
08 สิงหาคม 2008 20:58 : ข้อความนี้ถูกแก้ไขแล้ว 2 ครั้ง, ครั้งล่าสุดโดยคุณ holmes |
#2
|
|||
|
|||
ถ้าจำไม่ผิดข้อนี้ตอบ $\binom{n-1}{m-1}$ นะครับ เดี๋ยวจะเอาพิสูจน์มาให้ครับ
__________________
ผักกาด - Pakaj 27 กรกฎาคม 2008 14:06 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ JanFS เหตุผล: แก้จาก \choose เป็น \binom |
#3
|
|||
|
|||
พิสูจน์
อันดับแรกจะแสดงว่า ไม่มีทางที่จะสร้างเซต $F$ ที่สมาชิกเกิน $\binom{n-1}{m-1}$ สมมติว่ามีเซต $F$ ที่สมาชิกเกิน $\binom{n-1}{m-1}$ เนื่องจากทุกเซตใน $F$ ต้องมีสมาชิกร่วมกันอย่างน้อย 1 ตัว และต้องเป็นสับเซตของเซตที่มีสมาชิก n ตัว ซึ่งจะเรียกเซตนี้ว่า $\mathbb{A}$ ให้สมาชิกที่ร่วมกันนั้นเป็น $x$ จะได้ว่า $x\in\mathbb{A}$ ดังนั้น เซตที่เป็นสมาชิกของ $F$ จะต้องมี $x$อยู่ และสมาชิกที่เหลือ $m-1$ตัว อยู่ใน $\mathbb{A}-\{x\}$ นั่นคือ สมาชิกของ $F$ จะต้องมีไม่เกิน $\binom{n-1}{m-1}$ ต่อไปจะสร้างเซต $F$ ดังกล่าว ซึ่งก็ไม่ยาก เพราะเรายึดสมาชิกตัวนึงจาก $\mathbb{A}$ ไว้ แล้วเลือกสมาชิก $m-1$ ตัวจาก $n-1$ ตัวที่เหลือให้ครบทุกแบบ แล้วใส่ $x$ เข้าไปด้วย เพื่อประกอบเป็นเซต นำเซตทั้งหมดที่ได้ประกอบเป็น $F$ ตามต้องการ
__________________
ผักกาด - Pakaj 27 กรกฎาคม 2008 14:22 : ข้อความนี้ถูกแก้ไขแล้ว 4 ครั้ง, ครั้งล่าสุดโดยคุณ JanFS |
#4
|
|||
|
|||
อ้างอิง:
เช่น n =3 m=2 {1,2,3} อาจจะเป็น {1,2} {1,3} {2 3} ถ้าผมเข้าใจผิดประการใดช่วยอธิบายด้วยครับ |
#5
|
|||
|
|||
อ้างอิง:
โดยที่แต่ละสับเซตจะมีสมาชิกร่วมกันอย่างน้อย 1 ตัว หมายถึงว่า มีสมาชิกหนึ่งตัวที่อยู่ในทุกแต่ละสับเซต ผมงงเองครับ ขออภัย "- -
__________________
ผักกาด - Pakaj |
|
|