โจทย์คอมบินาทอริก 5 ข้อ

[bakured]

มีโจทย์คอมบินาทอริกที่ไม่เข้าใจมาให้ช่วยเหลือหน่อยครับ

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ทั้งหมดเท่าใด

[LightLucifer]

ข้อ 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 ก็จบการพิสูจน์
ถ้าไม่ก็ตัดตัวที่ซ้ำกันออกผลรวมก็ยังคนเท่ากัน ก็จบการพิสูจน์

[bakured]

สับเซตแท้มันต้องลบออกไปด้วยหรือเปล่าครับ

[LightLucifer]

ครับ ผมลืมไป =="

ข้อ 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)$

[bakured]

โห พี่ไลธ์โหดมากทำได้หมดเลย ขอข้อหนึ่งด้วยนะครับ--*
ว่าแต่ข้อ5ทำไมได้แบบนั้นช่วยอธิบายหน่อยสิครับ
แล้วก็ข้อ4ไอช่วงหลังที่เป็นxi+21นิมายังไงหรือครับ งง

[LightLucifer]

ไม่ได้โหดหรอกครับ
ข้อ 4,5 ครูเขาสอนโจทย์คล้ายๆกันในค่ายอ่ะครับ
ข้อ 1 ผมก็ไม่ค่อยมั่นใจ เท่าที่ทดดู PIE น่าจะออกถ้ายอมถึก(มาก)หน่อย
ข้อ 4 สร้างขึ้นมาเอง เพื่อให้มันลบกันได้ 21 วันพอดีอ่ะครับ
ข้อ 5 ให้ $A$ คือ เซตของวิธีที่ไม่มีตัวใดส่งไป$a$ ส่วน $B$ กับ $C$ ก็ทำเหมือน $A$ แล้วเอา $N(U)-N(A\cup B\cup C)$

[bakured]

อ้อๆครับ
ขอบคุณมากครับ

[bakured]

มีคำถามมาเพิ่มอะครับขอความช่วยเหลือต่อ
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ขั้น จงหาว่าจะมีวิธีการก้าวขึ้นบันไดได้ทั้งหมดกี่แบบ

ขอบคุณครับ

[MiNd169]

ข้อ 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

[MiNd169]

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

มีคำถามมาเพิ่มอะครับขอความช่วยเหลือต่อ
1. ถ้าช่องสี่เหลี่ยมเรียงกัน8ช่อง และ ต้องการระบายสีลงในช่องสี่เหลี่ยมนี้โดยระบายด้วยสีแดง4ช่อง และ ช่องสีขาวสี่ช่องถามว่ามีวิธีระบสยทั้งหมดกี่แบบ ทั้งนี้รูปแบบสมมาตรกันด้านซ้าย ขวา ให้ถือว่าเป็นแบบเดียวกัน

ได้ $ \frac{8!}{4!4!} - \frac{4!}{2!2!} $

[bakured]

อ้อ ครับ ขอบคุณนะครับแต่ฝากอีกสองที่เหลือด้วยนะครับ--*

ผมอยากให้ช่วยเพิ่มอีกสามข้ออะครับ

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ด้านจง หาว่ามีด้านสีน้ำเงินอยู่ทั้งหมดกี่ด้าน

[bakured]

อร๊ากกกก ดันครับๆๆๆๆ ช่วยผมด้วยคร้าบบบบบ

[bakured]

มาขอเพิ่มอีก1ข้อครับ
ถ้าในห้องหนึ่งมีคน10คนซึ่งไม่มีคนใดอายุมากกว่า60ปี(คิดอายุเป็นจำนวนนับ)และแต่ละคนมีอายุอย่างน้อย1ปีจงพิสูจน์ว่าเราสามารถหากลุ่มค นในห้องสองกลุ่ม(โดยที่คนๆหนึ่งอยู่ได้เพียงกลุ่มเดียว)ซึ่งมีผลรวมของอายุเท่ากัน

[Amankris]

#11 ได้ Soln ยังครับ

#13 ใช้นกครับ

[bakured]

#14 ยังครับยังไม่ได้solnทีครับ
ใช้นกยังไงอะครับผมใช้ไม่เป็น(งงโจทย์)