418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงการจัด

ข้อ 1

มีจำนวนเต็มบวกที่มีตัวเลขอยู่ 4 ตัว (กล่าวคือจำนวนเต็มบวกที่อยู่ระหว่าง 1000 และ 9999) กี่ตัวที่

1. 9 หารลงตัว?
2. เป็นจำนวนคู่
3. 3 หารไม่ลงตัว?
4. 5 หรือ 7 หารลงตัว?
5. ทั้ง 5 และ 7 หารไม่ลงตัว?
6. 5 หรือ 7 หรือ 11 หารลงตัว?
7. 5 และ 7 หารลงตัวแต่ 11 หารไม่ลงตัว? - -*

เฉลย

ข้อ 2

ในงานแต่งงานของคู่บ่าวสาวคู่หนึ่ง ช่างภาพจะทำการถ่ายภาพคน 6 คนจากกลุ่มคน 10 คน โดยที่กลุ่มคน 10 คนนี้รวมเจ้าบ่าวและเจ้าสาวอยู่ด้วย มีวิธีกี่วิธีที่เจ้าภาพจะจัดคนให้ยืนเรียงหน้ากระดานเพื่อถายรูปโดยที่

1. เจ้าสาวจะต้องอยู่ในรูป
2. ทั้งเจ้าสาวและเจ้าบ่าวจะต้องอยู่ในภาพ
3. เจ้าสาวหรือเจ้าบ่าวเพียงแค่คนเดียวเท่านั้นอยู่ในรูป
4. เจ้าสาวจะต้องอยู่ข้างเจ้าบ่าว
5. เจ้าสาวจะต้องไม่อยู่ติดกับเจ้าบ่าว
6. เจ้าสาวจะต้องยืนอยู่ทางด้านซ้ายของเจ้าบ่าว แต่ไม่จำเป็นต้องอยู่ติดกัน

เฉลย

ข้อ 3

ตัวอักษรภาษาอังกฤษมีพยัญชนะอยู่ 21 ตัวและมีสระอยู่ 5 ตัว

มีสตริงความยาว 6 ที่ประกอบขึ้นจากตัวอักษรภาษาอังกฤษ กี่ตัวที่:

1. มีสระ 1 ตัว
2. มีสระ 2 ตัว
3. มีสระอย่างน้อย 1 ตัว
4. มีสระอย่างน้อย 2 ตัว
5. ไม่มีสระใดๆ ปรากฎมากกว่า 1 ครั้ง
6. ไม่มีตัวอักษรใดๆ ปรากฏมากกว่า 1 ครั้ง

เฉลย

ข้อ 4

1. มีบิตสตริงกี่ตัวที่ประกอบด้วยเลขศูนย์ 8 ตัวและเลขหนึ่ง 10 ตัวโดยที่เลขศูนย์ทุกตัวจะต้องมีเลขหนึ่งอยู่ทางด้านขวาของมันเสมอ
2. มีบิตสตริงกี่ตัวที่ประกอบด้วยเลขศูนย์ 5 ตัวและเลขหนึ่ง 14 ตัวโดยที่เลขศูนย์ทุกตัวจะต้องมีเลขหนึ่งอยู่ทางด้านขวาของมันอย่างน้อย 2 ตัวเสมอ
3. มีบิตสตริงความยาว 10 กี่ตัวที่ประกอบด้วยเลขศูนย์อย่างน้อย 3 ตัวและเลขหนึ่งอย่างน้อย 3 ตัว

เฉลย

ข้อ 5

ในปัญหาข้อนี้เราจะนับจำนวนวิธีการเดินจากจุด (0,0) ไปยังจุด (m,n) ในระนาบ xy โดยที่เส้นทางเดินจะประกอบด้วยการเดินเป็นก้าวๆ แต่ละก้าวจะเป็นการเดินไปทางด้านขวา (กล่าวคือเดินจากจุด (x,y) ไปยังจุด (x+1,y)) หรือเดินขึ้นด้านบน (กล่าวคือเดินจากจุด (x,y) ไปยังจุด (x,y+1))

1. จงแสดงว่าเส้นทางเดินที่ว่านี้สามารถแทนด้วยบิตสตริงความยาว m+n ที่มีเลขศูนย์ m ตัวและเลขหนึ่ง n ตัว
2. จงแสดงว่ามีเส้นทางเดินที่แตกต่างกันทั้งหมด ${m+n \choose m}$

เฉลย

ข้อ 6

สมการ $x_{1}+x_{2}+x_{3}+x_{4}+x_{5}+x_{6}=29\,$ โดยที่ $x_{i}\,$ โดยที่ $i=1,2,3,\ldots ,6\,$ เป็นจำนวนเต็มที่ไม่เป็นลบและ

1. $x_{i}>1\,$ สำหรับค่า $i\,$ ทุกค่า
2. $x_{1}\geq 1,x_{2}\geq 2,x_{3}\geq 3,x_{4}\geq 4,x_{5}\geq 5,\,$ และ $x_{6}\geq 6\,$
3. $x_{1}\leq 5\,$
4. $x_{1}<8\,$ และ $x_{2}>8\,$

เฉลย

ข้อ 7

อสมการ $x_{1}+x_{2}+x_{3}\leq 11\,$ มีคำตอบกี่คำตอบโดยที่ $x_{1},x_{2},x_{3}\,$ เป็นจำนวนเต็มที่ไม่เป็นลบ

เฉลย

ข้อ 8

ต้องการจัดหนังสือ n เล่ม ลงในชั้นหนังสือ k ชั้นที่แตกต่างกัน

1. ถ้าหนังสือทุกเล่มเหมือนกัน จะมีวิธีการจัดทั้งหมดกี่วิธี
2. ถ้าหนังสือทุกเล่มแตกต่างกัน และถ้าลำดับในการวางหนังสือในแต่ละชั้นแตกต่างกันเราก็จะถือว่าวิธีการจัดหนังสือนั้นต่างกันด้วย จะมีวิืธีการจัดทั้งหมดกี่วิธี (กล่าวคือ ถ้าในชั้นหนังสือหมายเลข 1 เราวางหนังสือหมายเลข 1, 2, 3 จากซ้ายไปขวา จะต่างกับการวางหนังสือหมายเลข 2, 1, 3 จากซ้ายไปขวา)

เฉลย

ข้อ 9

1. มีสตริงทั้้งหมดกี่แบบที่ได้จากการเรียงตัวอักษรในคำว่า MISSISSIPPI ใหม่
2. มีสตริงทั้งหมดกี่แบบที่ได้จากการเรียงตัวอักษรในคำว่า AARDVARK ใหม่โดยที่ตัวอักษร A ทั้งสามตัวจะต้องอยู่ติดกัน
3. มีสตริงความยาวอย่างน้อย 5 ทั้งหมดกี่แบบที่ได้จากการเลือกตัวอักษรบางตัวจากคำว่า SEERESS มาเรียงใหม่
4. มีสตริืงความยาวอย่างน้อย 7 ทั้งหมดกี่แบบที่ได้จากการเลือกตัวอักษรบางตัวจากคำว่า EVERGREEN มาเรียงใหม่

เฉลย

ข้อ 10

จงหาจำนวนคำตอบของสมการ $x_{1}+x_{2}+x_{3}+x_{4}=17\,$ โดยที่ $x_{1},x_{2},x_{3},x_{4}\,$ เป็นจำนวนเต็มที่ไม่เป็นลบ และ $x_{1}\leq 3,x_{2}\leq 4,x_{3}\leq 5,$ และ $x_{4}\leq 8$

เฉลย

ข้อ 11

จงคำนวณจำนวนวิธีกระจายลูกบอลที่แตกต่างกัน 8 ลูกลงในไหที่แตกต่างกันสามไห โดยที่ไหแต่ละไหจะต้องมีลูกบอลอย่างน้อย 1 ลูก

เฉลย

ข้อ 12

(โดย Richard P. Stanley) กำหนดจำนวนเต็มบวก $n\,$ และ $k\,$ จงหาจำนวนลำดับ $(S_{1},S_{2},\ldots ,S_{k})\,$ โดยที่ $S_{i}\,$ เป็นซับเซตของเซต $\{1,2,\ldots ,n\}\,$ โดยที่

1. $S_{1}\subseteq S_{2}\subseteq S_{3}\subseteq \dotsb \subseteq S_{k}$
2. $S_{1},S_{2},\ldots ,S_{k}$ ไม่มีส่วนร่วมกันเป็นคู่ๆ
3. $S_{1}\cap S_{2}\cap S_{3}\cap \dotsb \cap S_{k}=\emptyset$

เฉลย