Combinatorics Marathon

[Arsene Lupin]

มีคำตอบ (1,18) หนิครับ เท่าที่ผมลองทำๆดูก็ใช้การลงสีอ่ะครับ โดย ระบายคล้าย ตารางหมากรุก เเต่ทเเยงข้างเดียวครับ เเล้วเว้นเเบบกักตา 5ช่องครับ

[Arsene Lupin]

กำหนดตารางมี11คอลัมน์คือA B ... K
12แถวคือ1 2 ... 12
พิจารณาว่าถ้าเราแรเงาที่ช่องD1 K1 C2 J2 B3 I3 A4 H4 G5 F6 E7 D8 K8 C9 J9 B10 I10 A11 H11 G12
รวม20ช่อง จะเห็นได้ว่าบล็อก1x6และ1x7สามารถวางทับช่องที่แรเงาได้มากสุด1ช่องเท่านั้น ดังนั้นต้องมีบล็อกอย่างน้อย 20อัน แต่มีบล็อกเพียง19อัน ทำให้เกิดข้อขัดแย้ง จึงสรุปได้ว่าวางไม่ได้
Creditคุณ p_m.o.c. ครับ

[ฟินิกซ์เหินฟ้า]

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

กำหนดตารางมี11คอลัมน์คือA B ... K
12แถวคือ1 2 ... 12
พิจารณาว่าถ้าเราแรเงาที่ช่องD1 K1 C2 J2 B3 I3 A4 H4 G5 F6 E7 D8 K8 C9 J9 B10 I10 A11 H11 G12
รวม20ช่อง จะเห็นได้ว่าบล็อก1x6และ1x7สามารถวางทับช่องที่แรเงาได้มากสุด1ช่องเท่านั้น ดังนั้นต้องมีบล็อกอย่างน้อย 20อัน แต่มีบล็อกเพียง19อัน ทำให้เกิดข้อขัดแย้ง จึงสรุปได้ว่าวางไม่ได้
Creditคุณ p_m.o.c. ครับ

ถูกแล้วครับ ผมขอตั้งข้อต่อไปนะครับ
พิจารณาการเดินบนด้านของรูปห้าเหลี่ยมด้านเท่ารูปหนึ่ง โดยแต่ละก้าวสามารถเดินจากจุดยอดหนึ่งไปยังจุดยอดอื่นที่ติดกันเท่านั้น จงหาจำนวนเส้นทางการเดินที่จะกลับมายังจุดตั้งต้นหลังเดินไป$n$ก้าว

[Arsene Lupin]

ข้อความเดิมเขียนโดยคุณ ฟินิกซ์เหินฟ้า

ถูกแล้วครับ ผมขอตั้งข้อต่อไปนะครับ
พิจารณาการเดินบนด้านของรูปห้าเหลี่ยมด้านเท่ารูปหนึ่ง โดยแต่ละก้าวสามารถเดินจากจุดยอดหนึ่งไปยังจุดยอดอื่นที่ติดกันเท่านั้น จงหาจำนวนเส้นทางการเดินที่จะกลับมายังจุดตั้งต้นหลังเดินไป$n$ก้าว

คิดว่า ใช้ความสัมพันธ์เวียนเกิด เเต่ยังคิดๆอยู่ว่าจะใช้ยังไงครับ (ไม่ได้ใช้ความสัมพันธ์เวียนเกิดมานานจนขึ้นสนิมหมดละ)

[polsk133]

มันทำแบบนี้รึเปล่าช่วยดูให้หน่อยสิครับ

ให้จุด ABCDE เป็นจุดกำกับมุมที่เรียงกันของห้าเหลี่ยมดังกล่าง

$A_n$ คือจำนวนวิธีเดิน n ก้าวจากจุด A มาที่จุด A
$B_n$ คือจำนวนวิธีเดิน n ก้าวจากจุด B หรือ C มาที่จุด A
$C_n$ คือจำนวนวิธีเดิน n ก้าวจากจุด D หรือ E มาที่จุด A

เราจะได้ว่า

$A_n=2B_{n-1}$
$C_n=B_{n-1}+C_{n-1}$
$A_n=2A_{n-2}+2C_{n-2}$

พิจารณา $C_n=B_{n-1}+C_{n-1}$ จะได้

$2(C_n-C_{n-1})=2B_{n-1}=A_n$

พิจารณา $A_n=2A_{n-2}+2C_{n-2}$ ........(1)

ได้ $A_{n-1}=2A_{n-3}+2C_{n-3}$ .........(2)

(1)-(2); $A_n-A_{n-1}=2A_{n-2}-2A_{n-3}+A_{n-2}$

ดังนั้น $A_n=A_{n-1}+3A_{n-2}-2A_{n-3}$ โดยที่ $n>3 , A_1=0, A_2=2, A_3=0$

[Pitchayut]

มาปลุกหน่อยก็แล้วกันครับ ร้างมาเกือบ 2 ปี แล้ว

10. ให้
$$\prod_{n = 1}^{\infty}(1+nx^{3^n})=a_0+a_1x+a_2x^2+a_3x^3+... $$
จงหาค่าของ $a_{2015}$

[Scylla_Shadow]

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

มาปลุกหน่อยก็แล้วกันครับ ร้างมาเกือบ 2 ปี แล้ว

10. ให้
$$\prod_{n = 1}^{\infty}(1+nx^{3^n})=a_0+a_1x+a_2x^2+a_3x^3+... $$
จงหาค่าของ $a_{2015}$

สวัสดีค่ะ
sketch of the solutions มั้ง หวังว่าคงถูก
เพราะว่า $2015=2202122_3$
แสดงว่า $2015$ ไม่สามารถเขียนให้อยู่ในรูป $3^{x_1}+3^{x_2}+...+3^{x_n}$ สำหรับบาง $x_1,x_2,x_3,...,x_n$ ที่เป็นจำนวนเต็มบวกที่แตกต่างกันได้
นั่นคือไม่สามารถสร้าง $x^{2015}$ จากบรรดา $x^{3^i}$ ต่างๆได้
ทำให้ $a_{2015}=0$

ตอนนี้ยังไม่มีโจทย์คอมบิที่(น่า)สนใจค่ะ
ขอลงโจทย์ไว้นิดนึง ซึ่งได้แรงบันดาลใจจากคลาสที่ลงค่ะ

11. กำหนด $A=\{x \in \mathbb{N} \ | \ x \leq 13\}$ และ $f$ เป็นฟังก์ชันจาก $A$ ไป $A$ ที่นิยามโดย
$f(1)=2,f(2)=3,f(3)=4,f(4)=1$
$f(5)=6,f(6)=7,f(7)=5$
$f(8)=9,f(9)=8$
และ $f(i)=i$ เมื่อ $i=10,11,12,13$

จงหาจำนวนฟังก์ชั่นหนึ่งต่อหนึ่งทั่วถึง $g$ จาก $A$ ไป $A$ ซึ่ง
ฟังก์ชั่น $g \circ f \circ g^{-1} =h$ สอดคล้องกับ
$h(9)=8,h(8)=7,h(7)=6,h(6)=9$
$h(5)=4,h(4)=3,h(3)=5$
$h(2)=1,h(1)=2$
และ $h(i)=i$ เมื่อ $i=10,11,12,13$

[Pitchayut]

วิธีทำถูกครับ ส่วนโจทย์ข้อ 11. แบบนี้ผมถือว่าเป็น combi นะครับ แต่ท่าทางจะยากพอสมควรเลยแหละ