โจทย์เตรียมตัวเข้าค่าย

[Tony]

ผมขออาศัยกระทู้นี้ไว้ถามโจทย์ครับ
1. ให้ $a$ และ $n$ เป็นจำนวนเต็มบวกที่ $ (a,n) =1$ จงพิสูจน์ว่า
$ \{ b,\ b+a,\ b+2a,\ ...,\ b+ (n-1)a \} $ เป็นระบบส่วนตกค้างบริบูรณ์มอดุโล n

[nongtum]

ข้อนี้หาก n|b ก็แทบไม่ต้องทำอะไรครับ หากหารไม่ลงตัวให้ลองหาเศษแล้วสลับลำดับครับ

[nooonuii]

Show that $\{0,a,...,(n-1)a\}$ is a complete residue system modulo n then shift by b.

[Tony]

2.แผ่นป้าย 10 แผ่น ที่มีหมายเลข 1-10 แผ่นละ 1 หมายเลข ต้องการนำมาแขวนเรียงกัน จะจัดได้กี่วิธี ถ้าต้องการให้เลขคู่เรียงลำดับจากแต้มน้อยไปมาก จากซ้ายไปขวา (แต่ไม่จำเป็นต้องติดหมด)

3. ชาย 4 คน หญิง 4 คน ยืนเข้าแถวหน้ากระดานได้กี่วิธี ถ้า
3.1 ชายที่สูงกว่าต้องอยู่ทางขวาของชายคนที่เตี้ยกว่าเสมอ
3.2 แต่ละเพศ คนที่สูงกว่าต้องอยู่ทางขวาของคนที่เตี้ยกว่าเสมอ

(เอามาจากหนังสือ คอมบินาทอริก ของสอวน.ครับ)

ตอนนี้ผมฟิตมากๆ กำลังอ่านเรื่อง การแจกของอยู่ครับ แต่อ่านไม่ค่อยรู้เรื่องเลย แล้ว
ก็มีสัญลักษณ์เพิ่มขึ้นเยอะด้วย เช่น $H^{n}_{r}$, $S(n,r)$
กำลังสงสัย โจทย์แนวนี้ครับ
- แบ่งคน 10 คนออกเป็น 3 กลุ่ม กลุ่มละ 3 คน 2 กลุ่ม และ 4 คน อีก 1 กลุ่ม จะแบ่งได้กี่วิธี
กับ - แบ่งคน 10 คนเข้าห้องพัก 3 ห้อง แต่ละห้องพักได้ 3, 3, 4 คน ตามลำดับ จะแบ่งได้กี่วิธี
(ผมคิดได้ $\frac{10!}{3!3!4!} \cdot \frac{1}{2!}$ กับ $\frac{10!}{3!3!4!} $ ตามลำดับ ... รึเปล่า)

คือ ผมไม่รู้ว่าตอนไหนต้องหารออกด้วยจำนวนที่ซ้ำกัน fractorial

อีกข้อหนึ่ง
- มีนักเรียน 15 คน ในจำนวนนี้มีนาย ก, ข และ ค รวมอยู่ด้วย ต้องการแบ่งนักเรียน ออกเป็น
3 กลุ่มๆ ละเท่าๆกัน จะแบ่งได้กี่วิธี เมื่อต้องการให้
1. นาย ก, ข, ค อยู่กลุ่มเดียวกัน $\Rightarrow \frac{12!}{2!5!5!} \cdot \frac{1}{2!}$
2. นาย ก, ข, ค อยู่คนละกลุ่ม $\Rightarrow \frac{12!}{4!4!4!} \cdot \frac{1}{3!}$
- มีนักเรียน 15 คน ในจำนวนนี้มีนาย ก, ข และ ค รวมอยู่ด้วย ต้องการแบ่งนักเรียนเข้าห้องพัก
ซึ่งมี 3 ห้อง โดยที่พักห้องได้ห้องละ 5 คน จะแบ่งได้กี่วิธี ถ้า
1. นาย ก, ข, ค อยู่ห้องเดียวกัน $\Rightarrow \frac{12!}{2!5!5!} $
2. นาย ก, ข, ค อยู่คนละห้อง $\Rightarrow \frac{12!}{4!4!4!} $

รบกวนช่วยตรวจคำตอบและอธิบายด้วยครับ

[gon]

ขอตอบเฉพาะเรื่องแบ่งกลุ่มนะครับ.

น้อง Tony มี My Maths เล่มที่ 11 ปีที่ 1 อยู่หรือเปล่าครับ (ถ้าไม่มีจะมาอธิบายให้ฟังเพิ่มเติม ถ้างง) เรื่องการแบ่งกลุ่ม ผมเขียนอธิบายไว้แล้ว มีโจทย์ลองคิดแถมท้ายด้วย แต่โจทย์ผิดนิดนึง คือ ต้องตัดคำว่า หนึ่งต่อหนึ่งออก

สำหรับวิธีที่แสดงมา เท่าที่ดูคร่าว ๆ น่าจะถูกหมด แต่ ข้อรองสุดท้าย คือ

ซึ่งมี 3 ห้อง โดยที่พักห้องได้ห้องละ 5 คน จะแบ่งได้กี่วิธี ถ้า
1. นาย ก, ข, ค อยู่ห้องเดียวกัน ควรเป็น $\frac{12!}{5! 5! 2! 2!} \cdot 3$

ขั้นที่ 1 : เลือกว่า จะให้ห้องไหนที่ทั้งสามคนอยู่ ทำได้ 3 วิธี
ขั้นที่ 2 : แบ่งคนที่เหลือออกเป็นกลุ่มละ 2, 5, 5 ทำได้ $\frac{12!}{5! 5! 2! 2!}$
ขั้นที่ 3 : กลุ่มละ 2 จะต้องอยู่ห้องเดียว ก ข ค โดยปริยาย ไม่ต้องเลือก ส่วนกลุ่มละ 5 ห้องไหนก่อนก็ได้เลือกได้ 2 วิธี จากนั้นกลุ่มละ 5 ที่เหลือก็ต้องเลือกห้องที่เหลือได้ 1 วิธี

เอาทั้ง 3 ขั้นมาคูณกันหมด ก็จะได้ $\frac{12!}{5! 5! 2! 2!} \cdot 3$

เอ้าไหน ๆ ก็เขียนแล้ว เขียนอธิบายลยล่ะกัน

การแบ่งของที่ต่างกันทั้งหมด ออกเป็นกลุ่ม ๆ ถ้ามีความซ้ำต้องหารด้วยจำนวนกลุ่มที่ซ้ำ

การแบ่งคนเข้าห้องโดยทั่วไป มี 2 ขั้น คือ
1. แบ่งกลุ่ม
2. เลือกห้อง

ถ้ามี 12 คน แบ่งเข้าห้อง 3 ห้อง ๆ ละ เท่า ๆ กัน ถ้าแต่ละห้องรับคนได้ 5 คน
ขั้นที่ 1 : แบ่งคนออกเป็น 4, 4, 4 ทำได้ $\frac{12!}{4!4!4!3!}$
ขั้นที่ 2 : กลุ่มใดก็ได้กลุ่มแรก เลือกว่าจะเข้าห้องใดเลือกได้ 3 วิธี กลุ่มต่อมาได้ 2 วิธี กลุ่มสุดท้ายได้ 1 วิธี

ดังนั้น ทำได้ $\frac{12!}{4!4!4!3!} \cdot 3 \cdot 2 \cdot 1 = \frac{12!}{4!4!4!}$

โจทย์เดิม ถ้าแบ่งเป็นกลุ่ม 5, 3, 2
ขั้นที่ 1 : แบ่งคนออกเป็น 5, 3, 2 ทำได้ $\frac{12!}{5! 3! 2!}$
ขั้นที่ 2 : กลุ่มใดก็ได้กลุ่มแรก เลือกว่าจะเข้าห้องใดเลือกได้ 3 วิธี กลุ่มต่อมาได้ 2 วิธี กลุ่มสุดท้ายได้ 1 วิธี

ดังนั้น ทำได้ $\frac{12!}{5! 3! 2!} \cdot 3 \cdot 2 \cdot 1 $

ถ้าแบ่งคน 12 คน เข้าห้องที่รับได้ห้องละ 5, 3, 2 ตามลำดับ จะทำได้ $\frac{12!}{5! 3! 2!} $ เพราะตอนเลือกห้อง กลุ่มละ 5 ก็ต้องเลือกห้องที่รับได้ 5 คนเท่าั้นั้น ทำได้ 1 วิธี ส่วนกลุ่มละ 3 กับ 2 ก็เช่นกัน

[[Cb : TkZ]]

เตรียมตัวเข้าค่ายอาไรเหรอคับเนี่ย

[Tony]

ค่ายสอวน.ครับ

ขอบคุณพี่ gon มากครับ
(ยังรอแนวคิดข้อ 2 กับ 3 อยู่นะครับ)

$4.$ ต้องจัดพนักงาน 6 คนออกเป็ฯกลุ่ม 3 กลุ่ม โดยจัดกลุ่มละกี่คนก็ได้ จะจัดได้กี่วิธี ถ้าไม่มีความแตก
ต่างระหว่างกลุ่มที่เท่ากัน

$5.$ รถโดยสารคันหนึ่งเมื่อเริ่มต้นมีผู้โดยสาร 25 คน รถคันนี้จะหยุดให้ผู้โดยสารลง 10 แห่ง มีกี่วิธีที่ผู้
โดยสารจะเลือกลงได้

$6.$ สร้างจำนวนเต็มบวกที่มี 3 หลักโดยใช้เลข 0-9 ได้กี่จำนวน ถ้าต้องการให้
6.1 เลขหลักหน่วย $\leq$ เลขหลักสิบ $\leq$ เลขหลักร้อย
6.2 เลขหลักหน่วย $\geq$ เลขหลักสิบ $\geq$ เลขหลักร้อย

$7.$ ให้ $S=\{1,2, \cdots , n+1\}$ เมื่อ $n \geq 2$ และให้
$$T=\{(x,y,z) \in S^{3} | x<z \ และ \ y<z\}$$
โดยการนับ $|T|$ จงแสดงว่า
$$ |T|=\left(\matrix{n+1\\ 2}\right)+2\left(\matrix{n+1\\ 3}\right) $$

$8.$ จงหาจำนวนเลข 7 หลักที่เลขโดแต่ละตัวปรากฎอย่างน้อย2 ครั้ง เช่น 1225511, 2222222

$9.$ ให้ $A=\{1,2, \cdots , 500\}$ จงหาว่ามีกี่วิธืในการเลือกสมาชิก $a, \ b $ และ $c$ จากเซต $A$ โดยที่
9.1 $4|a+b+c$
9.2 $4|a^{2}+b^{2}+c^{2}$

[Tony]

เย้ๆ ทำข้อ 7 ได้แล้ว ครับ

[nongtum]

ข้อ 4,5 ลองกลับไปอ่านนิยามการนับอีกรอบครับ
ข้อ 6 ลองคิดไล่จากหลักร้อยไปหาหลักหน่วย(หรือกลับกัน)ดูนะครับ และลองนึกดูนะครับว่าเลขสามหลักที่ขึ้นด้วย 0 นับเป็นเลขสามหลักหรือไม่
ข้อ 8 จำนวนเลขที่สอดคล้องเงื่อนไข=จำนวนเลขเจ็ดหลักทั้งหมด - จำนวนเลขเจ็ดหลักที่ไม่มีเลขหลักใดซ้ำกัน
ข้อ 9 ข้อย่อยแรกลองแจงกรณีตามเศษที่ได้จากการหารด้วย 4 ของ a,b,c ดูนะครับ ส่วนข้อย่อยหลังใช้ $n^2\equiv 0,1\pmod 4\ \forall n\in\mathbb Z$ ช่วยนะครับ

[Tony]

10. ให้ $A=\{1,2,3,...,n\}$
$U=\{f|f:A \rightarrow A\}$
$X=\{ f \in U| f(1)\not= f(2) \not= . . . \not= f(n) \not= f(1) \}$
จงหา $n(X)$

หมายความว่า f(1)นf(2) และ f(2)นf(3)
แต่ f(1) อาจเท่ากับ f(3) ได้

[gools]

น่าจะเป็น $n(n-1)^{n-1}$ นะครับ ใช้หลักการคูณธรรมดา

[warut]

น่าจะเป็น $n(n-1)^{n-2}(n-2)$ เมื่อ $n>2$ นะครับ เพราะ $f(n)$ จะเลือกได้เพียง 2 ค่า เนื่องจาก $f(n)\ne f(n-1)$ และ $f(n)\ne f(1)$ ด้วย

[gools]

อ่อคับ เข้าใจแล้ว

[nithi_rung]

ข้อความเดิมของคุณ warut:
น่าจะเป็น $n(n-1)^{n-2}(n-2)$ เมื่อ $n>2$ นะครับ เพราะ $f(n)$ จะเลือกได้เพียง 2 ค่า เนื่องจาก $f(n)\ne f(n-1)$ และ $f(n)\ne f(1)$ ด้วย

ถ้า $f(1) = f(n-1)$ ละครับ?
กำลังลองดูวิธีอื่นอยู่...

[nithi_rung]

คำตอบน่าจะเป็น $(n-1)^{n}+(-1)^{n}(n-1)$ นะครับ (ถ้าไม่มีอะไรผิดพลาด) ไว้ถ้าสงสัยจะมาเฉลยวิธีทำ