418531 ภาคต้น 2552/โจทย์ปัญหาการวิเคราะห์เชิงการจัด/เฉลยข้อ 8

จาก Theory Wiki
รุ่นแก้ไขเมื่อ 10:54, 3 สิงหาคม 2552 โดย Aoy (คุย | มีส่วนร่วม) (→‎ข้อ 2)
(ต่าง) ←รุ่นแก้ไขก่อนหน้า | รุ่นแก้ไขล่าสุด (ต่าง) | รุ่นแก้ไขถัดไป→ (ต่าง)
ไปยังการนำทาง ไปยังการค้นหา

ข้อ 1

จำนวนวิธีมีค่าเท่ากับจำนวนคำตอบของสมการ โดยที่ แต่ละตัวเป็นจำนวนเต็มที่ไม่เป็นลบ

ดังนั้นจึงมีวิธีจัดหนังสือทั้งหมด วิธี

ข้อ 2

ให้แบ่งขั้นตอนการเลือกหนังสือออกเป็น 3 ขึ้นตอน

  1. นำหนังสือ n เล่มมาเรียงกันเป็นแถว ได้ว่ามีวิธีเรียงทั้งหมด วิธี
  2. ทำการตัดสินใจว่าจะให้ชั้นหนังสือแต่ละชั้นมีหนังสือกี่เล่ม เนื่องจากมีชั้นหน้งสือ k ชั้น เราได้ว่ามีวิธีตัดสินใจในขั้นนี้เท่ากับจำนวนคำตอบของสมการ โดยที่ แต่ละตัวเป็นจำนวนเต็มที่ไม่เป็นลบ ซึ่งมีจำนวนคำตอบทั้งหมด วิธี
  3. สมมติว่าในขั้นที่สองเราตัดสินใจว่าชั้นหนังสือที่ 1 จะมีหนังสือ เล่ม ชั้นที่ 2 จะมีหนังสือ เล่ม และชั้นหนังสือที่ จะีมีหนั้งสือ เล่ม
ให้เรานำหนังสือ เล่มแรกที่เรียงในขั้นที่ 1 ไปเรียงใส่ในชั้นหนังสือที่ 1 แล้วนำหนังสืออีก เล่มต่อไปไปเรียงขึ้นชั้นที่ 2 แล้วนำหนังสืออีก เล่มต่อไปไปเรียงใส่ชั้นที่ 3 แล้วนำหนังสืออีก เล่มต่อไปไปเรียงใส่ชั้นที่

ฉะนั้นจะมีวิธีการจัดหนังสือทั้งหมด