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

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

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

Error

Too many requests (f061ab2)

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

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

Error

Too many requests (f061ab2)

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

ข้อย่อย 1

ให้

Error

Too many requests (f061ab2)

เป็นสตริง เรานิยามสตริงกลับ ของ ดังต่อไปนี้

เมื่อ เป็นสตริงและ

Error

Too many requests (f061ab2)

เป็นพยัญชนะ

ข้อย่อย 2

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

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

ข้อย่อย 3

ในปัญหาข้อนี้ ให้ แทนความยาวของสตริง

Error

Too many requests (f061ab2)

(ความยาวของสตริงคือจำนวนตัวอักษรในสตริงนั้น)

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

(Base Case)

Error

Too many requests (f061ab2)

เราจะได้ว่า ฉะนั้น

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

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

Error

Too many requests (f061ab2)

ใดๆ สมมติให้ โดย

เราได้ว่า

ดังนั้นเราสามารถสรุปได้ว่า

Error

Too many requests (f061ab2)

สำหรับสตริง และ ใดๆ

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