โจทย์คอมบินาทอริก 5 ข้อ
มีโจทย์คอมบินาทอริกที่ไม่เข้าใจมาให้ช่วยเหลือหน่อยครับ
1.จงหาจำนวนวิธีทั้งหมดในการส่งบัตรอวยพรปีใหม่6ใบ คือa,b,c,d,e,fให้ผู้หญิง3คนคือA1,A2,A3และผู้ชายสามคนคือ B1,B2,B3 โดยที่ทราบว่า A1จะไม่ชอบบัตรbและd A2จะไม่ชอบaและe A3ชอบทุกใบ B1ไม่ชอบaและe B2ไม่ชอบ d B3ไม่ชอบ f 2.วางจุด27จุดเป็น3แถว9คอลัมภ์(คอลัมภ์ตั้งฉากกับแถว) ทาสีแต่ละจุดด้วยสีฟ้าหรือสีแดง จงแสดงว่าจะต้องมีจุด4จุดที่มีสีเดียวกันและเป็นจุดยอดของ4เหลี่ยมมุมฉากที่มีด้านขนานกับแถวและคอลัมภ์ 3.ให้x$\subseteq${1,2,3,...,99}และ$\left|\,x\right|$=10จงแสดงว่ามีสับเซตแท้yและzของx โดยที่y$\cap$z=$\phi $ซึ่ง zigma(y$\left|\,\right.$y$\in$Y )=zigma(z$\left|\,\right.$z$\in$Z ) 4.นักแข่งขันหมากรุกผู้หนึ่งมีเวลาเตรียมตัวสำหรับการแข่งขัน11สัปดาห์ในการฟิตซ้อมเพื่อเข้าแข่งขันเขาจะเล่นอย่างน้อย1ครั้งต่อวันและ ไม่เกิน12ครั้งต่อ1สัปดาห์ จงแสดงว่าจะมีช่วงเวลาหนึ่งใน11สัปดาห์นี้ที่เขาเล่น21ครั้งพอดี 5. ถ้าxเป็นเซตที่มีขนาดเท่ากับkและy={a,b,c}จะมีฟังก์ชั่นทั่วถึงจากxไปyทั้งหมดเท่าใด |
ข้อ 2
พิจรณาแต่ละคอลัมภ์ มีช่องอยู่ 3 ช่อง สามารถระบายสีได้ $2^3=8$ แบบ แต่เรามี 9 คอลลัมภ์ จะได้ว่ามีอย่างน้อยสองคอลัมภ์ที่ระบายสีแบบเดียวกัน ซึ่งสองคอลัมภ์นั้นสามารถสร้างสี่เหลี่ยมผืนผ้าดังเงื่อนไขโจทย์ได้ ข้อ 3 สังเกตว่ามี $y,z$ ที่เป็นไปได้ทั่งหมด $2^{10}-2$ เซต แต่ $1022>99+98+...+91=$ค่าสูงสุดของผลบวกของสมาชิกในy,z และ $1=$ค่าต่ำของผลบวกของสมาชิกในy,z แสดงว่าผลบวกของสมาชิกในy,zที่เป็นไปได้มี $<1022$ จะได้ว่ามีอย่างน้อยสองเซตที่ผลบวกเท่ากัน สมมติว่าถ้าสองเซตนั้น disjoint ก็จบการพิสูจน์ ถ้าไม่ก็ตัดตัวที่ซ้ำกันออกผลรวมก็ยังคนเท่ากัน ก็จบการพิสูจน์ |
สับเซตแท้มันต้องลบออกไปด้วยหรือเปล่าครับ
|
ครับ ผมลืมไป =="
ข้อ 4 ให้ $x_i$ เป็นจำนวนครั้งที่เขาซ้อมตั้งแต่วันแรกถึงวันที่ $i$ พิจรณาเซต $A=${$x_1,x_2,...,x_{77},x_1+21,x_2+21,...,x_{77}+21$} จะได้ $min(A)=1$,$max(A)=(11\times 12)+21=153$ แต่ $|A|=154$ จะได้ว่ามีอยู่สองตัวที่มีค่าเท่ากัน แต่ตั้งแต่ $x_1,x_2,...,x_{77}$ มีค่่าต่างกันหมด และ $x_1+21,x_2+21,...,x_{77}+21$ ก็มีค่าต่างกันหมดเช่นกัน แสดงว่ามี $i,j$ ซึ่ง $x_i=x_j+21$ จะได้ $x_i-x_j=$จำนวนครั้งที่ฝึกตั้งแต่วันที่ $j$ ถึงวันที่ $i$ $=21$ ข้อ 5 ได้ $T(k,3)=3^k-3(2^k)+3(1^k)$ |
โห พี่ไลธ์โหดมากทำได้หมดเลย ขอข้อหนึ่งด้วยนะครับ--*
ว่าแต่ข้อ5ทำไมได้แบบนั้นช่วยอธิบายหน่อยสิครับ แล้วก็ข้อ4ไอช่วงหลังที่เป็นxi+21นิมายังไงหรือครับ งง |
ไม่ได้โหดหรอกครับ
ข้อ 4,5 ครูเขาสอนโจทย์คล้ายๆกันในค่ายอ่ะครับ ข้อ 1 ผมก็ไม่ค่อยมั่นใจ เท่าที่ทดดู PIE น่าจะออกถ้ายอมถึก(มาก)หน่อย ข้อ 4 สร้างขึ้นมาเอง เพื่อให้มันลบกันได้ 21 วันพอดีอ่ะครับ ข้อ 5 ให้ $A$ คือ เซตของวิธีที่ไม่มีตัวใดส่งไป$a$ ส่วน $B$ กับ $C$ ก็ทำเหมือน $A$ แล้วเอา $N(U)-N(A\cup B\cup C)$ |
อ้อๆครับ
ขอบคุณมากครับ |
มีคำถามมาเพิ่มอะครับขอความช่วยเหลือต่อ
1. ถ้าช่องสี่เหลี่ยมเรียงกัน8ช่อง และ ต้องการระบายสีลงในช่องสี่เหลี่ยมนี้โดยระบายด้วยสีแดง4ช่อง และ ช่องสีขาวสี่ช่องถามว่ามีวิธีระบสยทั้งหมดกี่แบบ ทั้งนี้รูปแบบสมมาตรกันด้านซ้าย ขวา ให้ถือว่าเป็นแบบเดียวกัน 2.มีตัวอักษรสองชนิด คือ AและBเรียงต่อกันทั้งหมด15ตัว(จากซ้ายไปขวา) โจทย์ข้อนี้เกียวกับการตรวจสอบการเรียงซ้ำของตัวอักษร(ทั้งหมด14ตำแหน่ง) ยกตัวอย่างเช่น AABBAAAABAABBBB มีตัวอักษร ABเรียงซ้ำ3ครั้ง BAเรียงซ้ำ2ครั้ง BBเรียงซ้ำ4ครั้ง ถ้ากำหนดให้มีตัวอักษร AA เรียงซ้ำกัน5ครั้ง และ อักษรAB BA BB มีการเรัียงซ้ำกัน3ครั้ง การเรียงของตัวอักษรที่เป็นไปตามเงื่อนไขนี้จะทำได้ทั้งหมดกี่แบบ 3.ที่บริษัทแห่งหนึ่ง เลขานุการจะนำเอกสารมาวางไว้ในถาดเอกสารบนโต๊ะของ ผจญ. เมื่อ ผจญ.มีเวลาว่างก็จะหยิบเอกสารในถาดออกมาอ่านแล้วประทับตราอนุมัติโดยเลขานุการจะวางเอกสารไว้บนสุดเสมอ และ ผจญ.ก็จะหยิบเอกสารที่อยู่บนสุดมาอ่านก่อนเสมอ มีอยู่วันหนึ่ง เอกสารในช่วงเช้าและช่วงบ่ายมีรวมกัน9ชุดและมีการระบุหมายเลข1-9กำกับไว้ที่ตัวเอกสารด้วย ถ้าในวันนั้น ผจญ. ประทับตราเอกสารหมายเลข8ในช่วงเช้า อยากทราบว่าการเรียงลำดับของเอกสารที่รอประทับตราในช่วงบ่ายจะมีได้กี่แบบ 4. ในการก้าวขึ้นบันได10ขั้น ถ้าสามารถเลือกได้ระหว่างการก้าวทีละขั้นกับการก้าวทีละ2ขั้น จงหาว่าจะมีวิธีการก้าวขึ้นบันไดได้ทั้งหมดกี่แบบ ขอบคุณครับ |
ข้อ 4
จะมีรูปแบบการก้าวขึ้นดังนี้ 1+1+1+1+1+1+1+1+1+1 ได้ $\frac{10!}{10!} = 1$ 2+1+1+1+1+1+1+1+1 ได้ $\frac{9!}{8!1!} = 9$ 2+2+1+1+1+1+1+1 ได้ $\frac{8!}{6!2!} = 28$ 2+2+2+1+1+1+1 ได้ $\frac{7!}{4!3!} = 35$ 2+2+2+2+1+1 ได้ $\frac{6!}{4!2!} = 15$ 2+2+2+2+2 ได้ $\frac{5!}{5!} = 1$ รวม 1 + 9 + 28 + 35 + 15 + 1 = 89 |
อ้างอิง:
|
อ้อ ครับ ขอบคุณนะครับแต่ฝากอีกสองที่เหลือด้วยนะครับ--*
ผมอยากให้ช่วยเพิ่มอีกสามข้ออะครับ 1.จงใช้วิธีการนับสองทางแสดงว่า$\binom{n}{m}\binom{m}{r}$=$\binom{n}{r}\binom{n-r}{m-r}$ 2. จงแสดงว่า$\sum_{r = 0}^{m} \frac{m!(n-r)!}{n!(m-r)!}$=$\frac{n+1}{n-m+1}$ 3. นำรูปสี่เหลี่ยมขนาด1X1 มาปูต่อกันเป็นรูปสี่เหลี่ยมขนาด15X15จุดยอดแต่ละจุดยอดของจัตุรัสรูปเล็กจะทาสีแดงหรือน้ำเงิน ถ้ามีจุดยอดสีแดงทั้งหมด133จุดโดยมี2จุดเป็นจุดยอดสี่เหลี่ยมรูปใหญ่และมี32จุดอยู่บนด้าน(และไม่ใช่จุดยอด)ของรูปสี่เหลี่ยมรูปใหญ่จาก นั้นทาสีด้านแต่ละด้านของจัตุรัสรูปเล็กดังนี้ ถ้าจุดปลายของด้านเป็นสีเดียวกันให้ทาเป็นสีเดียวกับจุดปลายแต่ถ้าจุดปลายมีสีต่างกันให้ทาเป็นสีเหลืองถ้ามีด้านสีเหลืองทั้ง196ด้านจง หาว่ามีด้านสีน้ำเงินอยู่ทั้งหมดกี่ด้าน |
อร๊ากกกก ดันครับๆๆๆๆ ช่วยผมด้วยคร้าบบบบบ
|
มาขอเพิ่มอีก1ข้อครับ
ถ้าในห้องหนึ่งมีคน10คนซึ่งไม่มีคนใดอายุมากกว่า60ปี(คิดอายุเป็นจำนวนนับ)และแต่ละคนมีอายุอย่างน้อย1ปีจงพิสูจน์ว่าเราสามารถหากลุ่มค นในห้องสองกลุ่ม(โดยที่คนๆหนึ่งอยู่ได้เพียงกลุ่มเดียว)ซึ่งมีผลรวมของอายุเท่ากัน |
#11 ได้ Soln ยังครับ
#13 ใช้นกครับ |
#14 ยังครับยังไม่ได้solnทีครับ
ใช้นกยังไงอะครับผมใช้ไม่เป็น(งงโจทย์) |
เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 04:06 |
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha