Mathcenter Forum  

Go Back   Mathcenter Forum > คณิตศาสตร์โอลิมปิก และอุดมศึกษา > คอมบินาทอริก
สมัครสมาชิก คู่มือการใช้ รายชื่อสมาชิก ปฏิทิน ค้นหา ข้อความวันนี้ ทำเครื่องหมายอ่านทุกห้องแล้ว

ตั้งหัวข้อใหม่ Reply
 
เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
  #1  
Old 18 มีนาคม 2019, 14:05
boat25451's Avatar
boat25451 boat25451 ไม่อยู่ในระบบ
จอมยุทธ์หน้าใหม่
 
วันที่สมัครสมาชิก: 05 พฤษภาคม 2013
ข้อความ: 82
boat25451 is on a distinguished road
Default โจทย์คอมบิช่วยหน่อยครับ

จงหาจำนวนวิธีการสร้างคำที่มีความยาวnตัวอักษร โดยใช้ตัวอักษรa, b, c, dโดยห้ามa,และbติดกัน

18 มีนาคม 2019 14:06 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ boat25451
ตอบพร้อมอ้างอิงข้อความนี้
  #2  
Old 11 ธันวาคม 2020, 11:15
Napper's Avatar
Napper Napper ไม่อยู่ในระบบ
เริ่มฝึกวรยุทธ์
 
วันที่สมัครสมาชิก: 14 สิงหาคม 2014
ข้อความ: 26
Napper is on a distinguished road
Default

แนวคิดข้อนี้คือใช้ความสัมพันธ์เวียนเกิดครับ

สำหรับ $n \ge 1$ กำหนดให้ $A_n,B_n,C_n,D_n$ คือจำนวนวิธีเรียงสตริง (ชุดตัวอักษร) ความยาว $n$ ตามเงื่อนไข (a,b ห้ามติดกัน) และขึ้นต้นด้วย a,b,c,d ตามลำดับ ดังนั้น คำตอบที่เราต้องการคือ $A_n+B_n+C_n+D_n$

สังเกตว่า a,b มีความสมมาตรกัน เพราะถ้าหากแทน a ด้วย b และแทน b ด้วย a ในสตริงหนึ่งๆที่ขึ้นต้นด้วย a ก็จะได้สตริงที่ขึ้นต้นด้วย b และการกระทำนี้ไม่ส่งผลต่อเงื่อนไขที่ว่า a,b ห้ามติดกัน จึงสรุปได้ว่า $A_n=B_n$ ทุก $n \ge 1$ และในทำนองเดียวกัน เราจะได้ว่า $C_n=D_n$ ทุก $n \ge 1$ เช่นกัน

ค่าเริ่มต้น

\begin{align}
A_1 &= 1 && \textrm{a}\\[5pt]
A_2 &= 3 && \textrm{aa, ac, ad}\\[5pt]
A_3 &= 11 && \textrm{aaa, aac, aad}\\
&&& \textrm{aca, acb, acc, acd}\\
&&& \textrm{ada, adb, adc, add}\\[15pt]

C_1 &= 1 && \textrm{c}\\[5pt]
C_2 &= 4 && \textrm{ca, cb, cc, cd}\\[5pt]
C_3 &= 14 && \textrm{caa, cac, cad}\\
&&& \textrm{cbb, cbc, cbd}\\
&&& \textrm{cca, ccb, ccc, ccd}\\
&&& \textrm{cda, cdb, cdc, cdd}
\end{align}

ความสัมพันธ์เวียนเกิด

ในการสร้างสตริงความยาว $n+1$ ที่ขึ้นต้นด้วย a เราสามารถแปะสตริงความยาว $n$ ข้างหลัง a ได้ทั้งสิ้น $A_n+C_n+D_n$ วิธี เพราะสตริงที่นำมาแปะต่อนั้นต้องขึ้นต้นด้วย a, c หรือ d เท่านั้น ห้ามขึ้นต้นด้วย b จึงได้ว่า

$A_{n+1}=A_n+C_n+D_n \quad$ ทุก $n \ge 1$

แต่ในการสร้างสตริงความยาว $n+1$ ที่ขึ้นต้นด้วย c นั้น เราสามารถแปะสตริงความยาว $n$ หลัง c ด้วยอะไรก็ได้ จึงได้ความสัมพันธ์เป็น

$C_{n+1}=A_n+B_n+C_n+D_n \quad$ ทุก $n \ge 1$

จากข้อมูล $A_n=B_n$ และ $C_n=D_n$ ลดรูปเหลือเป็นระบบสมการเวียนเกิดเชิงเส้น

\begin{align}
A_{n+1}&=A_n+2C_n\\[5pt]
C_{n+1}&=2A_n+2C_n
\end{align}
จัดให้เหลือตัวแปรเดียวโดยคำนวณ $A_{n+2}-2A_{n+1}$ และเขียน $A_{n+2}$ ในรูปของพจน์ที่ต่ำกว่าดังนี้

\begin{align}
A_{n+2}-2A_{n+1} & =(A_{n+1}+2C_{n+1})-2(A_n+2C_n)\\[5pt]
A_{n+2} & =3A_{n+1}-2A_n+2(C_{n+1}-2C_n)\\[5pt]
A_{n+2} & =3A_{n+1}-2A_n+2(2A_n)\\[5pt]
A_{n+2} & =3A_{n+1}+2A_n
\end{align}
สมการเวียงเกิดเชิงเส้นนี้มี characteristic equation คือ $r^2=3r+2$ ซึ่งมีรากเป็น $r=\frac{3 \pm \sqrt{17}}{2}$ ได้รูปแบบทั่วไปเป็น

$$A_n = k_1 \left(\frac{3 + \sqrt{17}}{2}\right)^n + k_2 \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

โดยที่ค่าคงที่ $k_1,k_2$ หาได้จากเงื่อนไขเริ่มต้น $A_1=1$ และ $A_2=3$ จะได้ $k_1=\frac{1}{\sqrt{17}}$ และ $k_2=-\frac{1}{\sqrt{17}}$ นั่นคือ

$$A_n = \frac{1}{\sqrt{17}} \left(\frac{3 + \sqrt{17}}{2}\right)^n - \frac{1}{\sqrt{17}} \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

เราสามารถหารูปทั่วไปของ $C_n$ ได้ในทำนองเดียวกัน หรือคำนวณจากความสัมพันธ์ $C_n=\frac{1}{2}(A_{n+1}-A_n)$ ได้เช่นกัน ได้ว่า

$$C_n = \left(\frac{1+\sqrt{17}}{4\sqrt{17}}\right) \left(\frac{3 + \sqrt{17}}{2}\right)^n + \left(\frac{-1+\sqrt{17}}{4\sqrt{17}}\right) \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

ซึ่งการคำนวณโดยใช้สูตรได้ว่า $A_3=11$ และ $C_3=14$ ตรงกับวิธีนับโดยตรงตอนหาเงื่อนไขเริ่มต้น

คำตอบ

โจทย์นี้ต้องการหาวิธีทั้งหมด จึงรวมทุกกรณีเป็น $A_n+B_n+C_n+D_n=2A_n+2C_n=C_{n+1}$ ซึ่งมีค่าเท่ากับ

$$\left(\frac{5+\sqrt{17}}{2\sqrt{17}}\right) \left(\frac{3 + \sqrt{17}}{2}\right)^n + \left(\frac{-5+\sqrt{17}}{2\sqrt{17}}\right) \left(\frac{3 - \sqrt{17}}{2}\right)^n$$

สำหรับทุก $n \ge 1$
ตอบพร้อมอ้างอิงข้อความนี้
ตั้งหัวข้อใหม่ Reply


เครื่องมือของหัวข้อ ค้นหาในหัวข้อนี้
ค้นหาในหัวข้อนี้:

ค้นหาขั้นสูง

กฎการส่งข้อความ
คุณ ไม่สามารถ ตั้งหัวข้อใหม่ได้
คุณ ไม่สามารถ ตอบหัวข้อได้
คุณ ไม่สามารถ แนบไฟล์และเอกสารได้
คุณ ไม่สามารถ แก้ไขข้อความของคุณเองได้

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
ทางลัดสู่ห้อง


เวลาที่แสดงทั้งหมด เป็นเวลาที่ประเทศไทย (GMT +7) ขณะนี้เป็นเวลา 03:13


Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Modified by Jetsada Karnpracha