ช่วยพิสูจน์หน่อยครับ

[LightLucifer]

โดยใช้เหตุผลเชิงคอมบินาทอริคนะครับ

$\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+...+n\binom{n}{n}=n2^{n-1}$

[tatari/nightmare]

Hint : $k\binom{n}{k}$ ให้ลองเปลี่ยนเป็น $\binom{k}{1}\binom{n}{k}$ แล้วลองคิด
...เชิงคอมบินาทอริกดู

[LightLucifer]

ขอบคุณครับ ^^

[อยากเก่งเลขทำไงดีครับบบ]

จาก ที่เคยรู้ร่ะว่า

$\binom{n}{0} +\binom{n}{1} +\binom{n}{2} +...+\binom{n}{n} =2^n$

แล้วแต่งไปดูก็จะได้น่ะ

ลองดู

และก็จาก $\binom{n}{r} =\binom{n}{ืn-r}$ ด้วยน่ะ

ก็จะได้ดังที่ต้องการอ่าาา

เคยทำแล้ว ดีใจที่ทำได้ด้วย

อิอิ

[LightLucifer]

ช่วยเช็คคำตอบข้อนี้หน่อยครับ คือ ผมเพิ่งมาทำคอมบิได้ไม่นาน เลยไม่มั่นใจในคำตอบอ่ะครับว่าถูกหรือป่าว

ให้ $X,Y$ และ $Z$ เป็นเซตซึ่ง $Z$ เป็นเซตย่อยของ $Y$ และ $N(X)=k,N(Y)=n,N(Z)=r$
จงหาจำนวนฟังก์ชัน $f:X\rightarrow Y$ ทั้งหมดซึ่ง $Z$ เป็นเซตย่อยของ $f(x)$



ผมได้ $\sum_{i = 0}^{r}(-1)^i\binom{r}{i}(n-i)^k$ รบกวนช่วยเช็คหน่อยครับ

[passer-by]

ผมยังไม่ได้เช็คคำตอบให้นะครับ แค่จะบอกแนวคิดเฉยๆ

(1) เลือกสมาชิกใน X ออกมา i ตัว แล้วสร้างฟังก์ชันทั่วถึงไปหา Z

(2) สมาชิกอีก n(X)-i ตัว สร้างฟังก์ชันแบบปกติส่งไปหา Y-Z

[LightLucifer]

ขอตั้งถามโจทย์ที่สงสัยที่กระทู้นี้อีกนะครับจะได้ไม่เปลือง

จงแสดงว่า
$$(n+1)(n+2)...(2n)$$
เแ็นพหุคูณของ $2^n$ สำหรับทุกจำนวนเต็มบวก $n$

[nooonuii]

สองบรรทัดครับ

$n!(n+1)\cdots (2n)=(1\cdot 3\cdot 5\cdots (2n-1))(2\cdot 4\cdots (2n))$

เหลือไว้ให้เติมอีกบรรทัดนึง

[LightLucifer]

THX มากครับ (คิดวิธีแบบ induction ได้อีกวิธีหนึ่งด้วย)

มีอีกข้อครับ
$P_{r+1}^{n+1}=(r+1)(P_{r}^{n}+P_{r}^{n-1}+...+P_{r}^{r})$

[nooonuii]

มันสมมูลกับ

$\binom{n+1}{r+1}=\binom{n}{r}+\binom{n-1}{r}+\cdots+\binom{r}{r}$

ใช้ Pascal identity แตกออกมาก็น่าจะได้ครับ อันนี้ยังไม่ได้ลองทำดู

[LightLucifer]

ช่วยรังนกข้อนี้หน่อยครับ
ในตารางหมากรุกขนาด $n\times n$ แต่ละช่องติดหมายเลขตั้งแต่ $1$ ถึง $n^2$ โดยไม่ซ้ำกัน จงพิสูจน์ว่า จะต้องมีสองช่องที่ติดกันที่มีหมายเลขต่างอย่างน้อย $n$

[LightLucifer]

Any ideas?

ช่วยหน่อยเถอะนะครับ ปวดหัวกับข้อนี้จริงๆ T_T จะสอบแล้วด้วย

[passer-by]

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

ช่วยรังนกข้อนี้หน่อยครับ
ในตารางหมากรุกขนาด $n\times n$ แต่ละช่องติดหมายเลขตั้งแต่ $1$ ถึง $n^2$ โดยไม่ซ้ำกัน จงพิสูจน์ว่า จะต้องมีสองช่องที่ติดกันที่มีหมายเลขต่างอย่างน้อย $n$

วิธีที่จะทำให้ดู ไม่ได้ใช้รังนกพิราบครับ แต่ใช้ Extremal principle

ผมเริ่มให้ 3 บรรทัดก่อนแล้วกัน

Record ค่ามากสุดของ ทุกแถว ทุกคอลัมน์ สมมติเป็น $M_i$ โดย i=1,2,...,2n

และ take $ m= min \,\, M_i $ (สมมติ $ min \,\, M_i$ มาจากแถว $R_k$ และ m อยู่คอลัมน์ $C_j$)

พิจารณาคอลัมน์ $C_i $ โดย $ i \neq j $

(ลองไปทำต่อเอง ถ้าไม่ได้จริงๆค่อยกลับมาถามใหม่นะครับ)

[LightLucifer]

ผมลองอ่านเกี่ยวกับ Extremal principle แล้วอ่ะครับ
แต่ยังไม่ค่อยเกทเลยอ่ะครับ

[passer-by]

อ๋อ ไม่ต้องไปอ่านหรอกครับหัวข้อ Extremal principle มันแค่จะบอกว่า ในบางสถานการณ์ เราต้อง take min หรือ take max ของบางอย่างเพื่อจะได้ solve หรือ proof ได้ง่ายขึ้น

คือ พอดีผมเคยเห็นโจทย์ข้อนี้มาก่อนน่ะครับ ก็เลยตอบให้ได้

หลังจากบรรทัดที่ผมให้ไป ถ้าจะทำต่อ มันจะได้ว่า ทุกคอลัมน์ที่ไม่ใช่ $C_j$ จะมี 2 สมาชิกติดกันในแนวตั้ง ที่ ตัวหนึ่ง ไม่เกิน $m-1$ ส่วนอีกตัว $\geq m+1$ ผมเรียกว่าตัวน้อยกับตัวมาก แล้วกัน

จากนั้นก็เลือกคอลัมน์ที่ตัวมาก มีค่าเยอะสุดในบรรดาตัวมากทุกตัว ก็จะได้ 2 สมาชิกที่โจทย์ถามครับ