ปริศนาการนับคนของ Josephus

โจทย์

มีคนอยู่ 10 คนยืนเรียงกันเป็นวงกลม เล่นเกมนับเลขกัน โดยจะนับ 1, 2, 3 แล้ววนไป 1 ใหม่ โดยที่คนที่นับ 3 จะออกจากกลุ่มไป นับไปเรื่อยๆ พอถึงคนสุดท้ายก็วนกลับมาคนที่ 1 ใหม่ โดยคนที่ 1 จะเป็นคนที่เริ่มนับเป็นคนแรก

ถามว่าถ้านับจนคนออกจากกลุ่มจนเหลือคนเดียว คนนั้นคือคนที่เท่าไหร่?

วิเคราะห์โจทย์

คำถาม ถามแบบมี 10 คน กับนับถึงแค่ 3 แต่จะมาอธิบายวิธีแบบที่ใช้ได้กับทุกเลขเลยละกัน

ข้อนี้จะคิดรวดเดียวเลยมันก็ยาก แต่ถ้าสังเกตดีๆแล้ว วิธีการคิดข้อนี้ก็มีหลักการของ Dynamic Programming (DP) ปนๆอยู่ ดังนั้นเราค่อยๆเริ่มคิดจากตัวอย่างที่ง่ายๆก่อนแล้วหาความสัมพันธ์จะดีกว่า

เคสที่ง่ายที่สุด $n=1$

ถ้าเหลือคนเดียว เราก็ได้คำตอบเลยว่าคนเหลือนั่นแหละคือคนที่ชนะ และเราก็ตอบว่าเป็นคนที่ 0 ได้เลย ค่า $k$ ไม่มีผลอะไรทั้งนั้น (ย้ำอีกรอบว่าเรียกคนแรกว่าคนที่ 0)

สังเกตตอนคนออกจากเกม

ตอนที่มีคนนับเลข $k$ แล้วคนที่นับต้องออกจากเกม ทีนี้ถ้าเรามองว่าคนยืนเรียงกันเป็นเส้นตรง ตามภาพนี้

ตอนแรกเลย เนื่องจากเราจะเริ่มนับที่คนที่ $0$ ซึ่งเราก็รู้ได้เลยทันทีว่า คนที่ $k-1$ ต้องออกเป็นคนแรกแน่ๆ เพราะเขาจะนับเลข $k$

แต่ปัญหาใหม่ที่ตามมาทันทีคือ เราต้องนับต่อไปจากคนที่เพิ่งจะออกไป และจะคำนวณว่าคนไหนเป็นคนถัดไปในทางโปรแกรมนี่จะยากขึ้นเยอะ เพราะเราไม่ได้เริ่มนับจากคนที่ $0$ แล้ว และไหนจะต้องข้ามคนที่ออกจากเกมไปแล้วด้วยอีก

ซึ่งจะพยายามคำนวณหาต่อไปก็ได้แหละ แต่ถ้าเราคิดใหม่ว่า เอา $n-1$ คนที่เหลือมาจัดเรียงเป็นแถวแบบเดิมใหม่ล่ะ ถ้าทำได้ เราก็จะรู้ว่าคนที่ $k-1$ ต้องออกเหมือนเดิม แต่จะทำยังไงล่ะ?

ลองวาดรูปมาดูก่อนจะได้ว่า คนที่ $k$ (คนถัดไปจากคนที่เพิ่งออกจากเกม จากในรูปคือคนที่ 3) จะต้องกลายเป็นคนแรก (คนที่ $0$) ในแถวใหม่ และถัดไปเป็นคนที่ $k+1$ ไปเรื่อยๆ แล้ววนกลับมาที่คนที่อยู่หน้าแถว

หลังจากเรียงได้แล้วก็จะได้เป็นแถวใหม่ที่กลับมาหาคนที่ต้องออกจากเกมง่ายเหมือนเดิมแล้ว โดยตอนเรียงใหม่เราได้ว่า

• คนที่ $3,4,5, \dots,9$ กลายเป็นคนที่ $0,1, \dots, 6$ ในแถวใหม่แทน
• คนที่ $0,1$ ก็เปลี่ยนเป็นคนที่ $7$ กับ $8$
• คนที่ $2$ ออกจากเกมไป

แล้วถ้าเอาเขียนใหม่ด้วยตัวแปร $n$ กับ $k$ ก็จะได้ว่า

• คนที่ $k, k+1\dots, n-1$ จะกลายเป็นคนที่ $0, 1, \dots, n -k -1$
• คนที่ $0,1, \dots, k-2$ จะกลายเป็น $n-k, n-(k+1), \dots, n-2$
• คนที่ $k-1$ ออกจากเกมไปเพราะนับเลข $k$

พอเอามาเขียนเป็นสมการว่าคนที่เคยอยู่ในแถวเดิมจะไปอยู่ที่ไหนจะได้ว่า:

โดยให้ $I_{n}$ แทนเลขตำแหน่งในแถวเดิม ตอนที่มีคนอยู่ $n$ คน

คำนวณย้อนกลับมาจาก $n=1$

พอเราได้สมการจากขั้นตอนก่อนหน้าแล้ว เราก็จะนำมาจัดรูปเพื่อให้คิดจากคนน้อยๆ ไปหาคนมากๆ ได้

จัดรูปใหม่ได้เป็น

จากที่เรารู้ว่าถ้าเหลือคนเดียวแล้ว คนที่เหลือคือคำตอบเลย ประกอบกับสมการที่ใช้คำนวณหาตำแหน่งของคนใดๆ ในแถวก่อนหน้าแล้ว เราสามารถเอาข้อมูลสองอย่างนี้มาค่อยๆคำนวณย้อนกลับไปว่า คนๆนั้นอยู่คนที่เท่าไหร่ตอนที่แถวยังมีอยู่ $n$ คนอยู่ โดยที่เราเขียนสมการได้ว่า:

และ

โดยที่ $S_i$ แทนตำแหน่งของคนที่ชนะเมื่อแถวมีอยู่ $i$ คน

การหาคำตอบ

เราก็ใช้จากส่วนที่เราคิดได้ในตอนคำนวณย้อนมาแทนค่าตั้งแต่ $n=1$ แล้วค่อยๆ ใช้ค่าตรงนี้มาหา $n=2,3,4,\dots$ ได้

เช่นสมมติมีคน 10 คน เราจะเริ่มคิดจากมีคนเหลือ $1,2,3,\dots,10$ คนว่าคนรอดคือคนไหน

• เหลือ 1 คน คนที่รอดคือคนที่ $0$ (ในลำดับตอนนั้น)
• เหลือ 2 คน คนที่รอดคือคนที่ $(0+3) \bmod 2 \equiv 1$ (ในลำดับตอนนั้น)
• เหลือ 3 คน คนที่รอดคือคนที่ $(1+3) \bmod 3 \equiv 1$
• เหลือ 4 คน คนที่รอดคือคนที่ $(1+3) \bmod 4 \equiv 0$

ทีนี้ก็ทำไปเรื่อยๆ จนครบ 10 คน เลขที่ได้จะเป็นหมายเลขคนที่รอดจริงๆ (ถ้าเริ่มจากคนที่ 0) และเราก็จะได้ว่าคนที่ 3 คือคนที่จะชนะ แต่ถ้าให้คนแรกคือคนที่ 1 (ไม่ใช่คนที่ 0) ก็จะได้ว่าคนที่ 4 คือคนที่จะชนะ

เขียนเป็นโปรแกรม

1
int32_t josephus(int32_t n, int32_t k) {
2
  if (n == 1) return 0;
3
  return (josephus(n - 1, k) + k) % n;
4
}

Extra Challenge

• จริงๆแล้วสำหรับ $n$ ใดๆ ถ้า $k=2$ มันจะมีวิธีที่ทำให้คำนวณได้เร็วกว่านี้อีก ใครมีไอเดียมาคอมเมนต์ใต้โพสต์กันได้
• มีโจทย์เก่าๆข้อนึงที่ใช้หลักการทำแบบนี้แหละ เป็นโจทย์ระดับชาติปีแรกๆเลย ถ้าสนใจไปลองกันได้ โจทย์ทำเล่น
  https://programming.in.th/tasks/toi6_jail