ข้อสอบวิชา คอมบินาทอริก 21 ตุลา 49

[goodnews]

1. จงหาจำนวนเซตย่อยของเซต $\{1,2,3,...,2n \}$ ของจำนวนนับ ซึ่งสอดคล้องกับเงื่อนไขต่อไปนี้
1.1 มีเลขคี่อย่างน้อย 1 ตัว
1.2 มีเลขคี่และเลขคู่เป็นจำนวนเท่ากัน
1.3 มีเลขคี่มากกว่าเลขคู่

2. ในสัปดาห์หนึ่ง บริษัทจำทำงานดีจำกัด ต้องจัดคนงาน 6 คน เพื่อทำงานนอกเวลา 3 วัน วันละ 2 คน บริษัทแห่งนี้จะมีวิธีจัดแบ่งคนทำงานได้กี่วิธี


3. จงหาจำนวนผลเฉลยที่เป็นจำนวนเต็มคี่บวกของสมการ $X_1+X_2+X_3+X_4 = 36$


4. ให้ $n = 2^{17}\cdot3^8$ จำนวนเต็มบวกที่น้อยกว่า $n$ ที่หาร $n^2$ ได้ลงตัว แต่หาร $n$ ไม่ลงตัว มีทั้งหมดกี่จำนวน

5. แผ่นไม้ 3 สี สีละ 5 แผ่น ( เหมือนกัน ) ต้องการนำไม้เหล่านี้จำนวน 10 แผ่น มาวางซ้อนกันในแนวตั้ง จะมีวิธีวางซ้อนกันได้กี่วิธี


คนที่พิมพ์สัญลักษณ์เก่ง วานช่วยพิมพ์ด้วยนะครับ ผมไม่เป็นจริง ๆ

[nongtum]

ผมไม่มีเวลาทด แต่พอแนะแนวคิดบางข้อได้ดังนี้ (ใครอยากแสดงวิธีทำเชิญได้เลยครับ)

1. แต่ละข้อย่อย ให้เลือกจำนวนคื่ตามเงื่อนไขโจทย์ก่อนเลือกจำนวนคู่
2. ผมไม่แน่ใจว่าคนงานหนึ่งคนทำงานได้มากกว่าหนึ่งวันหรือไม่ (มีคนว่างงาน) ถ้าใช้ก็ใช้ stacks and bars แต่ถ้าไม่ใช่ ลองนึกถึงการเรียงสับเปลี่ยนเชิงเส้นดูนะครับ
3. จับคู่ แล้วใช้ stacks and bars
4. มันจะมีกรณีัที่สอดคล้องเงื่อนไขอยู่สามกรณี โดยพิจารณาเลชชี้กำลัง
5. เลือกแผ่นไม้แต่ละสีให้ครบ ก่อนเอามาเรีัยงซ้อนกัน

[tatari/nightmare]

จริงๆไม่ได้มีแค่ 5 ข้อครับมี 6 ข้อ
6.จงพิสูจน์โดยการให้เหตุผลทางคอมบินาทอริกว่า $${n\choose 1}+2{n\choose 2}+3{n\choose 3}+...+n{n\choose n}=n\bullet 2^{n-1}$$
ข้อ 5 ผมจำไม่ได้ว่าผมทำยังไงแต่ผมได้เท่ากับ 21 วิธี(ไม่รู้ถูกรู้เปล่า )

[nooonuii]

ข้อ 3 สามารถแปลงไปเป็นโจทย์มาตรฐานได้โดยการสมมติให้
$X_1=2Y_1+1$
$X_2=2Y_2+1$
$X_3=2Y_3+1$
$X_4=2Y_4+1$

จะได้สมการใหม่เป็น
$$Y_1+Y_2+Y_3+Y_4=16$$
เมื่อ $Y_1,Y_2,Y_3,Y_4\geq 0$
ที่เหลือก็แทนค่าสูตรครับ

[konkoonJAi]

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

จริงๆไม่ได้มีแค่ 5 ข้อครับมี 6 ข้อ
6.จงพิสูจน์โดยการให้เหตุผลทางคอมบินาทอริกว่า $${n\choose 1}+2{n\choose 2}+3{n\choose 3}+...+n{n\choose n}=n\bullet 2^{n-1}$$

พิจารณาการเลือกกรรมการนักเรียนจากนักเรียน n คน (ต้องเลือกกรรมการอย่างน้อย 1 คน) และในกรรมการที่เลือกมาจะต้องเลือกประธานอีก 1 ตำแหน่ง
วิธีนับวิธีที่ 1 เลือกประธาน 1 คนจาก n คน ได้ n วิธี และที่เหลือ n-1 คน จะเลือกมาเป็นกรรมการคือพิจารณาแต่ละคนว่าจะเลือกหรือไม่เลือก มี $2^{n-1}$ วิธี ดังนั้นจำนวนวิธีในการนับแบบที่ 1 คือ $2\cdot 2^{n-1}$
วิธีนับวิธีที่ 2
กรณีที่ 1 เลือกกรรมการ 1 คนและประธาน 1 คน มีวิธีเลือกคือ $\displaystyle{1\cdot {n \choose 1}}$
กรณีที่ 2 เลือกกรรมการ 2 คนและประธาน 1 คน มีวิธีเลือกคือ $\displaystyle{2\cdot {n \choose 2}}$
กรณีที่ 3 เลือกกรรมการ 3 คนและประธาน 1 คน มีวิธีเลือกคือ $\displaystyle{3\cdot {n \choose 3}}$
.
.
.
กรณีที่ n เลือกกรรมการ n คนและประธาน 1 คน มีวิธีเลือกคือ $\displaystyle{n\cdot {n \choose n}}$
ดังนั้นจำนวนวิธีในการนับแบบที่ 2 คือ $\displaystyle{{n\choose 1}+2{n\choose 2}+3{n\choose 3}+...+n{n\choose n}}$
ซึ่งจะได้ว่า $${n\choose 1}+2{n\choose 2}+3{n\choose 3}+...+n{n\choose n}=n\bullet 2^{n-1}$$