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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา

ในการแก้ปัญหาข้อนี้เราจะให้

Error

Too many requests (f061ab2)

แทนเซตของพยัญชนะทั้งหมดที่เป็นไปได้ เช่น ถ้าสตริงที่เราสนใจเกิดจากการนำพยัญชนะของภาษาอังกฤษมาประกอบกัน เราอาจจะให้ เป็นต้น

นอกจากนี้ เพื่อให้ไม่ให้เกิดความสับสน เราจะแทนสตริงด้วยตัวอักษรภาษาอังกฤษตัวเล็ก เช่น

Error

Too many requests (f061ab2)

เป็นต้น และจะแทนตัวอักษรด้วยตัวอักษรกรีก เช่น เป็นต้น

ข้อย่อย 1

ให้ เป็นสตริง เรานิยามสตริงกลับ

Error

Too many requests (f061ab2)

ของ ดังต่อไปนี้

เมื่อ เป็นสตริงและ เป็นพยัญชนะ

ข้อย่อย 2

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

  • ถ้า แล้ว
  • ถ้า และ แล้ว

ข้อย่อย 3

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

เราจะพิสูจน์ข้อความ โดยใช้ induction บนตัวแปร

(Base Case) เราจะได้ว่า ฉะนั้น

(Induction Case) ให้ เป็นจำนวนเต็มที่ไม่เป็นลบ และสมมติว่าสำหรับสตริง ที่มีความยาว ใดๆ

Error

Too many requests (f061ab2)

ให้ เป็นสตริืงที่มีความ ใดๆ สมมติให้

Error

Too many requests (f061ab2)

โดย

เราได้ว่า

ดังนั้นเราสามารถสรุปได้ว่า สำหรับสตริง และ ใดๆ

รายการเลือกการนำทาง