418531 ภาคต้น 2552/โจทย์ปัญหาการพิสูจน์ II/เฉลยข้อ 8

ในการแก้ปัญหาข้อนี้เราจะให้ $\Sigma \,$ แทนเซตของพยัญชนะทั้งหมดที่เป็นไปได้ เช่น ถ้าสตริงที่เราสนใจเกิดจากการนำพยัญชนะของภาษาอังกฤษมาประกอบกัน เราอาจจะให้ $\Sigma =\{\mathrm {a,b,c,\ldots ,z} \}\,$ เป็นต้น

นอกจากนี้ เพื่อให้ไม่ให้เกิดความสับสน เราจะแทนสตริงด้วยตัวอักษรภาษาอังกฤษตัวเล็ก เช่น $x,y,z\,$ เป็นต้น และจะแทนตัวอักษรด้วยตัวอักษรกรีก เช่น $\alpha ,\beta ,\gamma \,$ เป็นต้น

ข้อย่อย 1

ให้ $x\,$ เป็นสตริง เรานิยามสตริงกลับ $x^{R}\,$ ของ $x\,$ ดังต่อไปนี้

$x^{R}={\begin{cases}\lambda ,&x=\lambda \\y^{R}\alpha ,&x=\alpha y\end{cases}}$

เมื่อ $y\,$ เป็นสตริงและ $\alpha \in \Sigma \,$ เป็นพยัญชนะ

ข้อย่อย 2

ให้ $P\,$ เป็นเซตของสตริงที่เป็นพาลินโดรม เราสามารถนิยาม $P\,$ ได้จากกฎต่อไปนี้

• $\lambda \in P$
• ถ้า $\alpha \in \Sigma$ แล้ว $\alpha \in P$
• ถ้า $\alpha \in \Sigma$ และ $x\in P$ แล้ว $\alpha x\alpha \in P$

ข้อย่อย 3

ในปัญหาข้อนี้ ให้ $n\,$ แทนความยาวของสตริง $x\,$ (ความยาวของสตริงคือจำนวนตัวอักษรในสตริงนั้น)

เราจะพิสูจน์ข้อความ $(xy)^{R}=y^{R}x^{R}$ โดยใช้ induction บนตัวแปร $n\,$

(Base Case)

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 1043105099
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Fri, 19 Jun 2026 16:17:58 GMT


Sensitive client information

IP address: 158.108.32.49

$n=0\,$ เราจะได้ว่า $x=\lambda \,$ ฉะนั้น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 1046774313
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Fri, 19 Jun 2026 16:17:59 GMT


Sensitive client information

IP address: 158.108.32.49

$(xy)^{R}=(\lambda y)^{R}=y^{R}=y^{R}\lambda ^{R}=y^{R}x^{R}\,$

(Induction Case) ให้ $n\,$ เป็นจำนวนเต็มที่ไม่เป็นลบ และสมมติว่าสำหรับสตริง

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 1015920948
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Fri, 19 Jun 2026 16:17:59 GMT


Sensitive client information

IP address: 158.108.32.49

$z\,$ ที่มีความยาว $n\,$ ใดๆ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 1039206778
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Fri, 19 Jun 2026 16:18:00 GMT


Sensitive client information

IP address: 158.108.32.49

$(zy)^{R}=y^{R}z^{R}\,$

ให้ $x\,$ เป็นสตริืงที่มีความ $n+1\,$ ใดๆ สมมติให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 1016743943
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Fri, 19 Jun 2026 16:18:01 GMT


Sensitive client information

IP address: 158.108.32.49

$x=\alpha z\,$ โดย $\alpha \in \Sigma \,$

เราได้ว่า $(xy)^{R}=(\alpha zy)^{R}=(zy)^{R}\alpha =y^{R}z^{R}\alpha =y^{R}x^{R}\,$

ดังนั้นเราสามารถสรุปได้ว่า $(xy)^{R}=y^{R}x^{R}\,$ สำหรับสตริง $x\,$ และ $y\,$ ใดๆ