ข้อสอบคอมบิ สอวน มข. ค่าย1 54

[Thgx0312555]

1. ให้ $ n\geqslant 4, n\in \mathbb{Z} ^+$ p,q เป็น จำนวนเฉพาะบวก ซึ่ง $p|n! \bigwedge q|[(n-1)!-1]$ พิสูจน์ว่า $p < q$ (ข้อนี้โจทย์เดิมเขียนเครื่องหมายผิด แก้แล้ว)

2. ในการแข่งปิงปองแบบพบกันหมด มีนักกีฬา 100 คน ผลการแข่งเป็นแพ้หรือชนะเท่านั้น
สำหรับ i = 1,2,...,100

ให้ $a_i$ เป็นจำนวนครั้งที่นักกีฬาคนที่ i ชนะ
$b_i$ เป็นจำนวนครั้งที่นักกีฬาคนที่ i แพ้

จงพิสูจน์ $a_1^2+a_2^2+a_3^2+...+a_{100}^2=b_1^2+b_2^2+b_3^2+...+b_{100}^2$

3. $k, n\in \mathbb{N} , k < n, $จงหาจำนวนเซตย่อยของ {1,2,3,...,n} ที่ผลต่างสมาชิกมากที่สุด และน้อยที่สุด = k

4. จงหาจำนวนคู่อันดับ (A,B) ที่ $A\subseteq B\subseteq C$

5. คน 6 คนหนักไม่เท่ากันต้องการต่อตัวดังรูปโดยคนหนักกว่าห้ามอยู่บนคนเบากว่าได้กี่วิธี
----A
---/ \
--B--C
-/ \ / \
D--E--F

6. เดือนพฤษภาคม ตร.ทางหลวงตั้งด่านตรวจวัดความเร็ว 10 วันโดยไม่ตั้งด่าน 2 วันติดกัน ตั้งได้กี่วิธี

7. โยนลูกเต๋า 1 ลูก 6 ครั้ง หาจำนวนวิธีที่แต้มรวมเท่ากับ 21

8. จัดเรียงสมาชิกในแต่ละ subset ของ S = {1,2,3,4,5,6,7} โดย subset นั้นไม่เป็นเซตว่างจากมากไปน้อย และใส่เครื่องหมาย + - สลับกันโดยให้ตัวแรกเป็น + เช่น {7,3,2} จะมีผลลัพธ์ = 7-3+2=6

จงหาผลรวม ของผลลัพธ์ ของsubset ของ S

9. ครูหญิง 1 คน นร.หญิง 6 คน เข้าพักบ้านหลังหนึ่ง มีห้องพัก 3 ห้อง ห้องละไม่เกิน 3 คน มีกี่วิธี

[Cachy-Schwarz]

เป็นข้อสอบ TMo ทั้งหมดทุกข้อเลยหนิ รึเปล่า = =''

[Thgx0312555]

ใช่ จะมี AIME อีกข้อ

[LightLucifer]

รู้สึกว่าข้อ 1 ไม่ใช่คอมบินะ

[Thgx0312555]

เพิ่มข้อ 6-9 แล้วครับ
อยากได้คำตอบข้อ 3-9 ข้อ1เหมือนทฤษฎีจำนวนเลย = =

[Keehlzver]

ผมทำได้แค่แนะนำครับ พลังคิดเลขผมมันหดหายไปไหนก็ไม่รู้ (ที่ผมแนะไปอาจจะแก้ได้หรือไม่ได้ก็พิจารณาดูเอาเองนะครับ )
1.น่าจะพิสูจน์ขัดแย้งได้ ถ้า $p\mid n!$ และ $p>q$ จะได้ $q\mid n!$ ซึ่งพิสูจน์ต่อไปได้ว่า เป็นไปไม่ได้ที่ $q\mid n!$ และ $q\mid (n-1)!-1$
2.มันคือ TMO 7 ถ้าจำไม่ผิด
3.น่าจะบวกเข้าตัดออก
4.โจทย์ไม่ครบหรือเปล่า
5.โจทย์ไม่เคลียร์ตรงที่ใครหนักมากกว่าใครยังไงรึเปล่า? ถ้าโจทย์มีแค่นี้ สมมติให้น้ำหนักเรียงจากน้อยไปมากเป็น A,B,C,D,E,F แล้วมองแบบความสัมพันธ์เวียนบังเกิดได้หรือเปล่า
6.เหมือนว่าจะเป็น stars and bars
7.มันคือจำนวนผลเฉลยของสมการ a+b+c+d+e+f=21 โดยที่ $1\leq a,b,c,d,e,f \leq 6$ ใช่หรือเปล่า
8.โจทย์ข้อนี้น่าจะมีสมมาตรบางอย่าง หาให้เจอ
9.คน 7 คนเข้าพัก 3 ห้อง ห้องละไม่เกิน 3 คน คือผลจำนวนผลเฉลยของสมการ $a+b+c=7$ โดยที่ $1 \leq a,b,c \leq 3$ ข้อนี้เหมือนว่านับตรงๆเลยดีกว่าไหมครับ เชคถ้า $a=1,2,3$ b กับ c จะเป็นอะไรได้บ้าง

[Keehlzver]

มีคนเมลล์มาถาม ผมเฉลยเต็มให้ครับ (กว่าจะเคาะสนิมได้) ข้อ 7 ใช้บวกเข้าตัดออกครับ

ให้ $U$ เป็นเซตของผลเฉลยทั้งหมดที่เป็นจำวนเต็มบวกของสมการ $x+y+z+w+s+t=21$
ให้ $X$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มบวก ซึ่งมี $a\geq 6$
ให้ $Y$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มบวก ซึ่งมี $b\geq 6$
ให้ $Z$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มบวก ซึ่งมี $c\geq 6$
ให้ $W$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มบวก ซึ่งมี $d\geq 6$
ให้ $S$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มบวก ซึ่งมี $e\geq 6$
ให้ $T$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มบวก ซึ่งมี $f\geq 6$

เปลี่ยนตัวแปรให้ $(a,b,c,d,e,f)=(x-1,y-1,z-1,w-1,s-1,t-1)$ จะได้ว่า $a+b+c+d+e+f=15$ โดยที่ $a,b,c,d,e,f \geq 0$

จากหลักการบวกเข้าและตัดออก
$N(\overline{XYZWST})=N(U)-[N(X)+...+N(T)]+[N(XY)+...+N(ST)]-[N(XYZ)+...+N(WST)]+[N(XYZW)+...+N(ZWST)]-[N(XYZWS)+...+N(YZWST)]+N(XYZWST)$

จำนวนผลเฉลยที่เป็นจำนวนเต็มไม่ติดลบของสมการ $x_{1}+...+x_{k}=n$ มีค่าเท่ากับ $\binom{n+k-1}{n}$

ดังนั้น
$N(U)=\binom{15+6-1}{15}=15504$
$N(X)=N(Y)=...=N(T)=\binom{9+6-1}{9}=2002$
$N(XY)=N(YZ)=...=N(ST)=\binom{3+6-1}{3}=56$
$N(XYZ)=N(YZW)=...=N(WST)=0$
$N(XYZW)=N(YZWS)=...=N(ZWST)=0$
$N(XYZWS)=N(YZWST)=...=N(XZWST)=0$
$N(XYZWST)=0$

แทนค่าจะได้ว่า $N(\overline{XYZWST})=15504-\binom{6}{1}2002+\binom{6}{2}56=4332$ จบแล้วครับ

ส่วนข้อ 9 ก็ทำแบบเดียวกัน

[PP_nine]

เห ใช้ PIE หรอเนี่ย นึกไม่ถึงเลย เห็นว่าเป็นค่าย 1 ซะด้วย

[Keehlzver]

ผมมาเฉลยเล่มเทาข้อ 21,22 ซึ่งข้อ 22 เป็น Generalization ของข้อ 7 กับข้อ 9 ให้ครับ

22. ให้ $k,m,n \in \mathbb{N}$ จงแสดงว่าจำนวนคำตอบที่เป็นจำนวนเต็มของสมการ $x_{1}+x_{2}+...+x_{n}=m$ โดยที่ $1\leq x_{i} \leq k$ สำหรับทุก $i=1,2,...,n$ เท่ากับ $$\sum_{n = 0}^{n} (-1)^i\binom{n}{i}\binom{m-ki-1}{n-1}$$

ให้ $U$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มทั้งหมดของสมการ $x_{1}+x_{2}+...+x_{n}=m$
ให้ $X_{i}$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มทั้งหมดของสมการ $x_{1}+x_{2}+...+x_{n}=m$ โดยที่ $a_{i}\geq k$

เปลี่ยนตัวแปรให้ $x_{i}=a_{i}+1$ จะได้ว่า $a_{1}+a_{2}+...+a_{n}=m-n$ เมื่อ $a_{i}\geq 0$

จะได้ว่า
$N(U)=\binom{m-n+n-1}{m-n}=\binom{m-1}{n-1}$
$N(X_{i})=\binom{m-n-k+n-1}{m-n-k}=\binom{m-k-1}{n-1}$
$N(X_{i}X_{j})=\binom{m-n-2k+n-1}{m-n-2k}=\binom{m-2k-1}{n-1}$
$\vdots$
$N(X_{1}X_{2}...X_{n})=\binom{m-n-nk+n-1}{m-n-nk}=\binom{m-nk-1}{n-1}$

จากหลักการบวกเข้าตัดออกจะได้ว่า
$N(\overline{X_{1}X_{2}...X_{n}})=N(U)-\sum X_{i}+\sum X_{i}X_{j}-\sum X_{i}X_{j}X_{k}+...+(-1)^pX_{1}X_{2}...X_{p}$

แทนค่าจะได้ว่า $N(\overline{X_{1}X_{2}...X_{n}})=\binom{n}{0}\binom{m-1}{n-1}-\binom{n}{1}\binom{m-k-1}{n-1}+\binom{n}{2}\binom{m-2k-1}{n-1}-...+(-1)^i\binom{n}{i}\binom{m-ki-1}{n-1}+...+(-1)^n\binom{n}{n}\binom{m-nk-1}{n-1}=\sum_{i = 0}^{n} (-1)^i\binom{n}{i}\binom{m-ki-1}{n-1}$ ตามต้องการ
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
ส่วนข้อ
21. ให้ $k,m,n \in \mathbb{N}$ จงแสดงว่าจำนวนคำตอบที่เป็นจำนวนเต็มของสมการ $x_{1}+x_{2}+...+x_{n}=m$ โดยที่ $0\leq x_{i} \leq k$ สำหรับทุก $i=1,2,...,n$ เท่ากับ $$\sum_{n = 0}^{n} (-1)^i\binom{n}{i}\binom{m-(k+1)i+n-1}{n-1}$$

ทำเหมือนกันแต่แค่ไม่ต้องเปลี่ยนตัวแปร $x_{i}=a_{i}+1$ พิจารณา $X_{i}$ เป็นเซตของผลเฉลยที่เป็นจำนวนเต็มทั้งหมดของสมการ $x_{1}+x_{2}+...+x_{n}=m$ โดยที่ $x_{i}\geq k+1$