ได้ 22 คาดว่าถูกแล้วนะครับ.
ที่จริงปัญหาข้อนี้มีคนเคยถามมาแล้วในเว็บเราเมื่อสัก 5-6 ปีก่อน (ถ้าผมจำไม่ผิด แ่ต่เป็น 1000 หรือ 2000 ตู้) เมื่อครู่ผมลองหาดูแล้วไม่เจอ
แนวคิดก็คงคล้ายๆกับคุณ Dr.K กล่าวคือ
ตู้ที่สุดท้ายแล้ว 'ปิด' คือ ตู้ที่ถูกจับเป็นจำนวน คู่ ครั้ง
ตู้ที่สุดท้ายแล้ว 'เปิด' คือ ตู้ที่ถูกจับเป็นจำนวน คี่ ครั้ง
เราต้องการตู้ที่เปิด คือ ตู้ที่ถูกจับเป็นจำนวน คี่ ครั้ง เช่น ตู้หมายเลข 1 , 4 เป็นต้น
เช่น
ตู้หมายเลข 8 จะถูกจับโดยนักเรียน คนที่ 1, 2, 4, 8 (ซึ่งก็คือตัวประกอบทั้งหมดของ 8) (เปิด , ปิด , เปิด ,
ปิด)
ตู้หมายเลข 9 จะถูกจับโดยนักเรียน คนที่ 1, 3, 9 (เปิด , ปิด ,
เปิด)
ตู้หมายเลข 10 จะถูกจับโดยนักเรียน คนที่ 1, 2, 5, 10 (เปิด , ปิด , เปิด ,
ปิด)
ให้สังเกตว่าตัวประกอบทั้งหมด ของ 8 คือ 1, 2, 4, 8 เราจะมี
(1)(8) = 8
(2)(4) = 8
กล่าวคือ มีครบคู่ที่คูณกันแล้วได้ 8
ให้สังเกตว่าตัวประกอบทั้งหมด ของ 10 คือ 1, 2, 5, 10 เราจะมี
(1)(10) = 8
(2)(5) = 8
กล่าวคือ มีครบคู่ที่คูณกันแล้วได้ 10
แต่ตัวประกอบทั้งหมดของ 9 คือ 1, 3, 9
(1)(9) = 9
แต่ 3 ไม่มีคู่
หรือ ตัวประกอบของตู้หมายเลข 16 (ซึ่งสถานะสุดท้ายคือ เปิด) คือ 1, 2, 4, 8, 16
(1)(16) = 16
(2)(8) = 16
แต่ 4 ไม่มีคู่
ตรงนี้น่าจะตอบคำถามได้แล้วนะครับ.
สมมติว่ามีตู้หมายเลข 1, 2, ... , n
เราเขียน n ให้อยู่ในรูป n = a $\times$ b นั่นคือ จะได้ $b =\frac{n}{a}$ นั่นคือ a กับ $\frac{n}{a}$ จะเป็นตัวประกอบของ n ที่จับคู่คูณกันแล้วได้ n
ตู้ที่สถานะสุดท้าย เปิด คือ ตู้ที่มีจำนวนตัวประกอบเป็นจำนวนคี่ นั่นคือมีตัวตรงกลางอยู่หนึ่งตัวของตัวประกอบทั้งหมดของ n ที่ไม่มีคู่ ซึ่งจะเิิกิดเมื่อ $a = \frac{n}{a} \iff n = a^2$ แสดงว่า ตู้หมายเลข ที่เขียนในรูปกำลังสอง(สมบูรณ์) จะมีตัวประกอบเป็นจำนวนคี่ อันได้แก่ตู้หมายเลข $1^2, 2^2, 3^2, ... , 22^2 = 484 < 500$