ข้อสอบวิชา คอมบินาทอริก 21 ตุลา 49
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 แผ่น มาวางซ้อนกันในแนวตั้ง จะมีวิธีวางซ้อนกันได้กี่วิธี คนที่พิมพ์สัญลักษณ์เก่ง วานช่วยพิมพ์ด้วยนะครับ ผมไม่เป็นจริง ๆ |
ผมไม่มีเวลาทด แต่พอแนะแนวคิดบางข้อได้ดังนี้ (ใครอยากแสดงวิธีทำเชิญได้เลยครับ)
1. แต่ละข้อย่อย ให้เลือกจำนวนคื่ตามเงื่อนไขโจทย์ก่อนเลือกจำนวนคู่ 2. ผมไม่แน่ใจว่าคนงานหนึ่งคนทำงานได้มากกว่าหนึ่งวันหรือไม่ (มีคนว่างงาน) ถ้าใช้ก็ใช้ stacks and bars แต่ถ้าไม่ใช่ ลองนึกถึงการเรียงสับเปลี่ยนเชิงเส้นดูนะครับ 3. จับคู่ แล้วใช้ stacks and bars 4. มันจะมีกรณีัที่สอดคล้องเงื่อนไขอยู่สามกรณี โดยพิจารณาเลชชี้กำลัง 5. เลือกแผ่นไม้แต่ละสีให้ครบ ก่อนเอามาเรีัยงซ้อนกัน |
จริงๆไม่ได้มีแค่ 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 วิธี(ไม่รู้ถูกรู้เปล่า:sweat: ) |
ข้อ 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$ ที่เหลือก็แทนค่าสูตรครับ |
อ้างอิง:
วิธีนับวิธีที่ 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}$$ |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 03:03 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha