สมาชิกในเซต

[holmes]

ให้ m,n เป็นจำนวนเต็มบวกใดๆ ที่ m<n ให้ F เป็นเซตของ(สับเซตที่มีสมาชิก m ตัวของ เซตที่มีสมาชิก n ตัว)โดยที่แต่ละสับเซตจะมีสมาชิกร่วมกันอย่างน้อย 1 ตัว จงหาว่าสมาชิกใน F เป็นไปได้มากที่สุดเท่าไร

[JanFS]

ถ้าจำไม่ผิดข้อนี้ตอบ $\binom{n-1}{m-1}$ นะครับ เดี๋ยวจะเอาพิสูจน์มาให้ครับ

[JanFS]

พิสูจน์
อันดับแรกจะแสดงว่า ไม่มีทางที่จะสร้างเซต $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$ ตามต้องการ

[holmes]

ข้อความเดิมเขียนโดยคุณ JanFS

พิสูจน์
อันดับแรกจะแสดงว่า ไม่มีทางที่จะสร้างเซต $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$ ตามต้องการ

แล้วเราทราบได้อย่างไรว่าทุกเซตจะมีสมาชิกร่วมกันที่เหมือนกัน
เช่น n =3 m=2
{1,2,3}
อาจจะเป็น {1,2} {1,3} {2 3}

ถ้าผมเข้าใจผิดประการใดช่วยอธิบายด้วยครับ

[JanFS]

ข้อความเดิมเขียนโดยคุณ holmes

ให้ m,n เป็นจำนวนเต็มบวกใดๆ ที่ m<n ให้ F เป็นเซตของ(สับเซตที่มีสมาชิก m ตัวของ เซตที่มีสมาชิก n ตัว)โดยที่แต่ละสับเซตจะมีสมาชิกร่วมกันอย่างน้อย 1 ตัว จงหาว่าสมาชิกใน F เป็นไปได้มากที่สุดเท่าไร

อ้าว ขอโทษครับ ผมเข้าใจว่า

โดยที่แต่ละสับเซตจะมีสมาชิกร่วมกันอย่างน้อย 1 ตัว หมายถึงว่า มีสมาชิกหนึ่งตัวที่อยู่ในทุกแต่ละสับเซต

ผมงงเองครับ ขออภัย "- -