หัวข้อ 1_5 และ 1_6

คณิตศาสตร์เชิงการจดั หนา้ – 55 – ดร.บรรทม สุระพร1.5 วิธีการนบั เพิ่มเติม 1.5.1 ปญั หาการแจกจา่ ย ในหัวขอ้ ทผ่ี ่านมาเปน็ ปญั หาการจดั หมู่ ซ่ึงเป็นเรื่องการแจกจา่ ยสงิ่ ของทีแ่ ตกต่างกันทัง้ หมด แตใ่ นหัวข้อนเ้ี ราจะพิจารณาการจัดหมู่หรอื แจกจา่ ยสิง่ ของชนิดเดยี วที่เหมือนกัน หรอื มหี ลายชนิด ซง่ึ แตล่ ะชนดิ น้ันมีส่ิงของท่เี หมือนกันตัวอย่างที่ 1.5.1 มลี ูกบอล 7 ลูก ใส่ลงกล่อง 3 ใบ ได้ก่วี ิธี โดยที่กลอ่ งแตล่ ะใบรับลกู บอลได้หลายลกู และมเี ง่ือนไขดงั น้ี1.5.1.1 ลูกบอลตา่ งกนั และกล่องต่างกนั1.5.1.2 ลกู บอลเหมือนกันทุกลูก แตก่ ล่องตา่ งกนั1.5.1.3 ลูกบอลต่างกัน แตก่ ล่องเหมอื นกันทกุ ใบ1.5.1.4 ลกู บอลเหมือนกันทุกลูก และกลอ่ งเหมือนกนั ทุกใบวิธีทา 1.5.1.1 เปน็ วธิ ซี ง่ึ เราได้กลา่ วมาแลว้ นามาเพอ่ื เปรยี บเทยี บกับกรณอี ่นื ๆสาหรบั ลูกบอลแต่ละลูก สามารถจัดลงกลอ่ งได้ 3 วธิ ี ดังนั้นเรามีวิธีจดั ลูกบอล 7 ลูก ลงกลอ่ งได้ 37 วิธี1.5.1.2 ในกรณีท่ีลูกบอลเหมอื นกนั ดงั นัน้ วธิ ที ่ีแตกตา่ งกันกค็ อื การท่กี ล่องมจี านวนลกู บอลต่างกัน เราเขยี นจานวนลกู บอลต่างๆ ไดด้ ังน้ีรปู แบบ สลบั ท่กี ันได(้ วิธี) รูปแบบ สลับท่ีกนั ได้(วิธี)0 0 7 3! = 3 1 1 5 3! = 3 2!1! 2!1!0 1 6 3! = 6 124 3! = 60 2 5 3! = 6 133 3! = 3 2!1!0 3 4 3! = 6 223 3! = 3 2!1!รวมจานวนวิธีทงั้ หมด คอื 36 วธิ ี1.5.1.3 ในกรณที ลี่ กู บอลตา่ งกัน แต่กล่องเหมือนกัน ดงั นัน้ ถ้ากลอ่ งมีจานวนลูกบอลเทา่ กันการสลบั กลอ่ งจะเป็นวธิ เี ดยี วกนั เช่นถ้ากลอ่ ง 2 ใบ แตล่ ะใบมลี ูกบอล 1 ลกู การทลี่ ูกบอล ก ลงกล่องใบท่ีหนึง่ และลกู บอล ข ลงกลอ่ งใบทสี่ อง จะเหมือนกบั การทลี่ ูกบอลก ลงกล่องใบทสี่ องและลูกบอล ข ลงกลอ่ งใบที่หนึ่ ง ซง่ึ ถ้าจานวนลกู บอลในกลอ่ งตา่ งกนั จะถอื วา่ กลอ่ งต่างกนั เรามาพจิ ารณาลูกบอลลงกล่องในแบบ 1 1 5 จะไดจ้ านวนวธิ ี  7 5  1 วิธี คือตอ้ ง 1 1  2! หารดว้ ยจานวนการสลบั ท่ีของกล่องที่เหมอื นกนั สาหรบั 1 1 5 กับ1 5 1 และ 5 1 1 น้ันเราถือวา่ เป็นวธิ เี ดียวกนั ดงั นน้ั โดยการพจิ ารณาดังกลา่ ว เราหาจานวนวธิ ีไดด้ ังน้ี

คณิตศาสตร์เชิงการจดั หนา้ – 56 – ดร.บรรทม สุระพร รูปแบบ สลบั ท่กี ันได(้ วิธี) รปู แบบ สลับท่ีกนั ได้(วธิ ี) 007 7 =1 115  7 1 = 21   1   0 0 7  1 5  2! 016 7 =7 124 7 = 105   1   0 1 6  2 4  025 7 = 21 133  7 1 = 70  5 1 3 3 2!  0 2 034 7 = 35 223  7 1 = 105  4   3  0 3  2 2 2! รวมจานวนวิธีทัง้ หมด คือ 365 วธิ ี 1.5.1.4 เม่ือลกู บอลเหมือนกันและกล่องเหมือนกนั วธิ ที ตี่ ่างกันก็คือการท่มี ี จานวนลกู บอลในกล่องต่างกัน และการสลับกล่องถอื ว่าเหมอื นกนั เช่น เมื่อจานวนลูกบอลในกล่องเป็น 0 2 5 จะต่างกับ 1 1 5 แต่ ว่า 0 2 5 กับ 2 0 5 ถือวา่ เปน็ วธิ ีเดยี วกัน ดงั น้นั วิธที ่ตี ่างกัน คือ และ0 0 7, 0 1 6, 0 2 5, 0 3 4, 1 1 5, 1 2 4, 1 3 3 2 2 3 มี 8 วิธีพจิ ารณาปญั หาต่อไปน้ี1. มลี ูกบอลสแี ดง 7 ลูก สขี าว 7 ลูก สีดา 7 ลูก ลกู บอลสีเดียวกันเหมือนกนั ถา้ นาลูกบอลเหลา่ นีม้ า7 ลูก จะเป็นลกู บอลสตี ่างๆ ไดก้ วี่ ิธี2. จงหาจานวนคาตอบทเ่ี ป็นจานวนเต็มบวกหรือศูนยข์ องสมการอ X + Y + Z = 7 ถา้ ให้ X เป็นจานวนลูกบอลสีแดง Y เปน็ จานวนลูกบอลสขี าว และ Z เป็นจานวนลูกบอลสีดา3. ปัญหาการจัดลูกบอลทเี่ หมอื นกนั 7 ลกู ลงกล่องตา่ งๆ กัน 3 ใบ ถ้าให้ X เปน็ จานวนลูกบอลในกล่องใบทห่ี นง่ึ Y เป็นจานวนลกู บอลในกลอ่ งใบทีส่ อง และ Z เป็นจานวนลกู บอลในกลอ่ งใบที่ 3จะเหน็ ว่าปัญหาทั้ง 3 ข้อเป็นปญั หาเดยี วกันทั้งนัน้ แล ปญั หาทงั้ สามขอ้ น้ี ไดค้ าตอบ 36 วธิ ี ดงั ตัวอยา่ งท่ี 1.5.1 แต่เรามวี ิธีหาคาตอบอกี วธิ หี น่ึงสมมตวิ า่ เรานาลูกบอลทีเ่ หมือนกัน 7 ลกู นามาจดั ลาดบั โดยเพ่มิ ตวั แบ่งกนั้ อีก 2 ชนิ้ ซงึ่ จะแบง่ เป็น 3ช่อง ปัญหาการจัดลูกบอลลงกล่องก็จะเปน็ ปญั หาการจัดลาดบั ของสง่ิ ของ 9 ชิน้ มี 2 ชนิด คือลกู บอล7 ลูกทเี่ หมือนกัน และตวั แบง่ กั้น 2 อันที่เหมอื นกัน xxx|xx|xx การจัดลาดับกระทาได้ 9! = 36 วธิ ี 7!2!ทฤษฎบี ท จานวนวธิ ีของการจัดตอ่ ไปนเ้ี ทา่ กัน1. การจัดสงิ่ ของ n สิง่ ท่ีเหมือนกนั นามาจัดลงช่องตา่ งๆ กนั k ชอ่ ง2. มีสิ่งของ k ชนิด แตล่ ะชนดิ เหมอื นกันมจี านวนมาก นาส่ิงของเหล่าน้ีมา n ชีน้3. จานวนคาตอบทเ่ี ป็นจานวนเตม็ ไมเ่ ป็นลบของสมการ X1+X2+X3+…+ Xk = n4. การเรียงสับเปลีย่ นของสิ่งของ 2 ชนิด แตล่ ะชนิดน้ันเหมอื นกัน ชนดิ แรกมีจานวน n ช้ิน อกี ชนิดหนึง่ มจี านวน k – 1 ชิ้นจานวนวิธีของการจัดเท่ากบั C(n  k 1, n)   n  k 1  (n  k 1)! วธิ ี  n    n!(k 1)!

คณิตศาสตร์เชิงการจดั หนา้ – 57 – ดร.บรรทม สุระพรตวั อย่างที่ 1.5.2 ก. จงหาจานวนวิธที จี่ ะนาหนงั สอื ทเี่ หมอื นกัน 10 เลม่ แจกนกั เรยี น 4 คน ให้แจกทัง้ หมด โดยท่ีแต่ละคนตอ้ งไดร้ ับไม่นอ้ ยกว่า 1 เลม่ข. จงหาจานวนคาตอบทเี่ ปน็ จานวนเตม็ ของสมการ x+y+z+w = 10 เม่อื x > 0, y > 0, z > 0 และ w > 0ค. จงหาจานวนคาตอบทเี่ ป็นจานวนเต็มของสมการ x+y+z+w = 10 เม่อื x > 1, y > 2, z  0 และ w  0วธิ ีทา ก. นาหนงั สือแจกใหก้ ่อนคนละ 1 เลม่ เหลอื หนังสอื 6 เลม่ แจกให้คน 4 คนกระทาได้ C(6  4  1, 6)   9   9x8x7  84 วิธี  6  3x2  ข. ให้ X = x+1, Y = y+1, Z = z+1, W = w+1 ได้สมการเป็น X+1+Y+1+Z+1+W+1 = 10 ดังน้ัน การหาจานวนคาตอบทเี่ ป็นจานวนเตม็ ของสมการX+Y+Z+W = 10 – 4 = 6 เม่อื X  0, Y  0, Z  0 และ W 0 ได้จานวนคาตอบเท่ากับ C(6  4  1, 6)   9   9x8x7  84 จานวน  6  3x2  ค. ให้ X = x+2, Y = y+3 ได้สมการเปน็ X+2+Y+3+z+w = 10 ดงั นั้น ปัญหาจะเป็นการหาจานวนคาตอบทเี่ ปน็ จานวนเตม็ ของสมการ X+Y+z+w = 10 – 5= 5 เม่อื X  0, Y  0, z  0 และ w  0 ไดจ้ านวนคาตอบเท่ากับC(5  4  1,5)   8  8x7x6  56 จานวน  5 3x2 ตวั อย่างท่ี 1.5.3 จงหาจานวนวธิ ีจัดเรียงอักษรในคา CEMETERY ได้ก่ีวิธีโดยทอี่ กั ษร E ไม่ตดิ กนัวธิ ีทา จดั อกั ษร E ก่อน โดยมที ่วี า่ งระหว่างอักษร _E_E_E_ แลว้ ใสอ่ ักษรอะไรกไ็ ด้2 ตวั ระหวา่ ง E เหลอื อักษรอีก 3 ตวั แจกลงชอ่ ง 4 ช่อง ทาได้ 6 = 20    3 = C(3 4 1,3) คูณด้วยจานวนการสลบั ท่ีของอกั ษรทีต่ า่ งกัน 5 ตวั ได้จานวนทั้งหมด 5! x 20 = 2,400 วิธีแบบฝึกหดั ที่ 1.5 1. มีทีมบาสเกต็ บอล n ทีม แตล่ ะทมี แขง่ กบั ทีมอืน่ ทมี (คู่แข่ง) ละไมเ่ กนิ 1 ครัง้ จงแสดงว่า จะมี อยา่ งน้อย 2 ทมี ที่มีจานวนคร้ังของการแขง่ ขนั เท่ากนั

คณติ ศาสตร์เชิงการจดั หนา้ – 58 – ดร.บรรทม สุระพร

คณติ ศาสตร์เชิงการจดั หนา้ – 59 – ดร.บรรทม สุระพร1.6 หลกั การช่องรังนกพริ าบ (The Pigeonhole Principle) มีนกพริ าบ 6 ตัว นกทกุ ตัวจะบินเข้ารังซ่งึ มีรงั เพียง 5 รงั ดังนนั้ จะต้องมีอยา่ งน้อย 1 รงั ทีม่ ี นกพริ าบมากกว่า 1 ตวั เราจะเหน็ ได้ชัดเจนว่าคากลา่ วน้เี ป็นจรงิ แทบจะไม่ต้องมีการพิสจู น์ เราเรียก หลักการน้วี า่ หลกั การรังนกพริ าบ ทฤษฎีบทท่ี 1 มนี กพิราบ m ตวั นกท้ังหมดจะเข้ารงั ท่มี ีอยู่ n รงั ถ้า m > n จะมีรงั นกอยา่ งนอ้ ย 1 รงั ทีม่ นี กพริ าบมากกว่า 1 ตวั หลกั การดังกล่าวอาจเขยี นในรูปแบบคณติ ศาสตร์ ไดว้ ่า ถ้า A และ B เปน็ เซตจากัด ถ้า n(A) > n(B) แล้วทกุ ๆ ฟังกช์ ัน f: A B จะไม่เป็นฟังกช์ นั หนงึ่ ตอ่ หนง่ึ ตัวอยา่ งท่ี 1.6.1 มกี ระดาษจานวน 5 หน้า เมือ่ ตรวจสอบแลว้ แต่ละหน้ามีจานวนคาผดิ ไม่เกนิ 3 คา จงพิสูจนว์ ่ามกี ระดาษอย่างน้อย 2 หน้าท่ีมจี านวนคาผิดเทา่ กัน วิธที า สมมติว่ากระดาษคือนกพริ าบ จานวนคาผิด คอื 0, 1, 2, 3 เป็นรังนก มี 4 รงั ดงั น้นั ยอ่ มมีรังหนึ่งทม่ี ีนกเกนิ 1 ตวั คือมอี ย่างน้อย 2 หน้ากระดาษ ทม่ี ีจานวนคาผิด เท่ากนั ตัวอยา่ งท่ี 1.6.2 ในเขตกรงุ เทพมหานคร จะมีคนอย่างนอ้ ย 2 คน ที่มผี มบนศีรษะจานวนเทา่ กนั (ไม่ นบั คนท่ศี ีรษะไม่มเี สน้ ผม) วิธที า จากการสารวจเส้นผมของคนพบว่าแต่ละคนจะมีเสน้ ผมประมาณ 150,000 เสน้ และเราเชอื่ ว่าจานวนคนในกรุงเทพฯ (ยิ่งช่วงนีเ้ กิดเหตุการณย์ ดึ กรุงเทพฯ 15 มค. 2557 จากกลุ่มมวลมหาประชาชน) มมี ากกวา่ 1 ลา้ นคน ดังนัน้ โดยหลกั การรงั นกพิราบคนคือนกและเสน้ ผมคอื รงั จะได้ว่ามีคนอย่างน้อย 2 คนทม่ี จี านวนเสน้ ผม เท่ากนั ตวั อยา่ งท่ี 1.6.3 จงแสดงว่ามีจานวนเต็มบวก 12 จานวน จะมอี ยา่ งน้อย 1 คู่ ทีผ่ ลต่างถูกหารลงตัว ดว้ ย 11 วธิ ีทา จานวนท่หี ารด้วย 11 จะเหลอื เศษ 0, 1, 2,…,10 เทียบกับในทฤษฎบี ทเศษเหลา่ น้ี คือรังนกและจานวนแตล่ ะจานวนเปน็ ตวั นก ซ่ึงมี 12 ตัว ดังน้ันจะมอี ยคู่ ู่หน่ึงทหี่ าร ด้วย 11 แลว้ เหลอื เศษเท่ากัน น่นั คอื ผลต่างของจานวนค่ทู ่ีกล่าวน้ถี กู หารลงตัวด้วย 11

คณติ ศาสตร์เชิงการจดั หนา้ – 60 – ดร.บรรทม สุระพรทฤษฎีบทท่ี 2 มนี กพิราบ m ตวั นกท้งั หมดจะเข้ารังทมี่ ีอยู่ n รงั จะมีรังนกอยา่ งนอ้ ย 1 รัง ท่มี ีนกพิราบอยา่ งนอ้ ย  m  ตัว (เมอื่ x คือจานวนเตม็ น้อยสุดทม่ี ากกว่าหรือเท่ากบั  n x)ตัวอย่างที่ 1.6.4 โรงเรียนแห่งหนึ่งมนี ักเรียน 1,000 คน และมหี ้องเรียน 30 หอ้ ง จงพิสจู นว์ า่ มีอยา่ งนอ้ ย 1 ห้องทม่ี นี กั เรยี นอยา่ งน้อย 34 คนวิธีทา อาจใชท้ ฤษฎีบทที่ 2 เมือ่ นักเรียนเปน็ นก และห้องเรยี นเปน็ รังนก ได้วา่ มีอย่างน้อย1 รัง ท่มี นี กอยา่ งนอ้ ย 1000  = 34 ตวั คอื มีอยา่ งนอ้ ย 1 หอ้ งที่มีนกั เรียนอยา่ ง  30 น้อย 34 คนตัวอย่างที่ 1.6.5 ถ้าใสจ่ ุด 5 จดุ ลงในสามเหลีย่ มดา้ นเทา่ ทีม่ ีแตล่ ะด้านยาว 1 หน่วย จงแสดงว่าจะมีจดุ อย่างน้อยคูห่ น่งึ ทหี่ ่างกันนอ้ ยกวา่ 0.5 หน่วยวิธีทา เราจะพยายามวางจุดให้แต่ละจดุ อยู่ห่างกนั มากท่ีสดุ จงึ สรา้ ง สามเหล่ยี มดา้ นเทา่ 4 รปู ใส่จดุ 5 จดุ ลงไป จะมอี ยา่ งนอ้ ย 2 จดุ ท่ี   อยูใ่ นสามเหลยี่ มเล็กๆ รปู เดียวกนั ดังน้ันสองจดุ นั้นจะหา่ งกนั ไม่  เกนิ 0.5 หน่วยตัวอย่างที่ 1.6.6 กาหนดจานวนเตม็ 3 จานวน จงแสดงว่า เราสามารถเลอื กมา 2 จานวนท่ีมีผลบวก เป็นจานวนคู่ วธิ ีทา ให้จานวนเต็มเป็นนก มี 3 ตัว จานวนค่จู านวนคเ่ี ป็นรงั นก มี 2 รัง ดงั น้ันโดยหลกั การรงั นกพริ าบ ยอ่ มมรี ังหนงึ่ (จานวนค่หู รือค่ี) ท่มี นี กเกนิ 1 ตัว (จานวนเต็ม 2 จานวน)

คณติ ศาสตร์เชิงการจดั หนา้ – 61 – ดร.บรรทม สุระพรแบบฝึกหัดท่ี 1.6 2. มที มี บาสเก็ตบอล n ทีม แตล่ ะทีมแขง่ กับทมี อื่น ทีม (คู่แขง่ ) ละไม่เกนิ 1 ครั้ง จงแสดงว่า จะมี อยา่ งนอ้ ย 2 ทมี ท่ีมจี านวนครง้ั ของการแขง่ ขนั เทา่ กัน 3. ในห้องหน่งึ มีคน n > 1 คน แต่ละคนจะแลกนามบัตรกบั คนอ่ืนๆ จงพิสจู น์วา่ จะมสี องคนทมี่ ี นามบตั รท่แี ลกมาเทา่ กนั 4. กลอ่ งใบหน่ึงมีปากกาสแี ดง 10 ดา้ ม สีนา้ เงิน 8 ด้าม สเี ขียว 8 ด้ามและสีเหลือง 4 ดา้ ม จะหยบิ ปากกามาอยา่ งนอ้ ยก่ดี ้าม จงึ จะแนใ่ จวา่ ได้สเี ดยี วกันไมน่ อ้ ยกวา่ 4 ดา้ ม (13) 5. หอ้ งหนง่ึ มนี ักเรยี น 33 คน มีอายรุ วมกนั 430 ปี จริงหรือไมท่ ี่จะมกี ลุม่ นักเรียน 20 คน ทีม่ ีอายุ รวมกันมากกวา่ 260 ปี 6. มีกลอ่ ง 500 ใบ บรรจสุ ้มกล่องละไม่เกิน x ผล จงหาค่า x มากทสี่ ดุ ทจ่ี ะแนใ่ จไดว้ ่ามีอยา่ งนอ้ ย 3 กลอ่ งท่มี ีจานวนสม้ เทา่ กัน (249) 7. กาหนดจานวนเตม็ 7 จานวน จงแสดงว่ามกี ล่มุ ของจานวนเหลา่ นี้ (อาจมจี านวนเดียว) ทีผ่ ลบวก หารดว้ ย 7 ลงตัว 8. จงแสดงวา่ สาหรบั จานวนเต็มบวก n ใดๆ จะมจี านวนทีม่ ีเลขแตล่ ะหลักเปน็ 5 หรอื 0 ทีจ่ านวน นนั้ ถกู หารดว้ ย n ลงตวั 9. กาหนดจานวนเตม็ 52 จานวน จงแสดงวา่ มีจานวนคู่หนงึ่ ทผี่ ลบวกหรอื ผลลบถกู หารด้วย 100 ลง ตวั 10. จงพิสจู นว์ ่ามจี านวนที่เขียนในแบบ 19971997…1997 ถกู หารลงตัวดว้ ย 1999 11. ใสจ่ ุด 51 จุด ลงในสีเ่ หลีย่ มจตั รุ ัสท่ีมแี ตล่ ะดา้ นยาว 1 หนว่ ย จงแสดงว่า มีอย่างนอ้ ย 3 จดุ ทอ่ี ยู่ ภายในวงกลมท่ีมรี ัศมีนอ้ ยกวา่ 1/7 หน่วย 12. มีเส้นตรงทีไ่ ม่ขนานกัน 7 เส้น บนระนาบ จงแสดงว่ามเี สน้ ตรงอย่างน้อยคหู่ นง่ึ ที่ตดั กันเปน็ มุม นอ้ ยกว่า 26 องศา 13. มเี สน้ ขนานแนวตง้ั 3 เส้น เส้นขนานแนวนอน 9 เส้น มสี ี 2 สี ใส่สีท่จี ดุ ตดั จดุ ละสี จงแสดงวา่ มี สเ่ี หลี่ยมผืนผา้ อย่างนอ้ ย 1 รูปทีจ่ ดุ มมุ มีสีเดียวกัน 14. .. 15. .. 16. ..

คณติ ศาสตร์เชิงการจดั หนา้ – 62 – ดร.บรรทม สุระพร17. ..18. ..19. ..20. ..21. ..22. ..23. ..24. ..25. ..26. ..27. ..28. ..29. ..30. ..