ให้ $f: \mathbb{N} \to \mathbb{N}$ เป็นฟังก์ชันเพิ่มโดยแท้ และมีสมบัติว่า $f(f(n)) = 3n$ จงหา $f(n)$

เคยทำโจทย์นี้ซักพักแล้ว แต่เพิ่งรู้ว่ามันมาจาก BMO รอบ 1 ปี 1992 ข้อที่ 5 (ต้นฉบับถามแค่ $f(1992)$ พอ) … อ้าว นี่เราโดน @sorawee_p หลอกให้แก้โจทย์คณิตศาสตร์โอลิมปิกโดยไม่รู้ตัวเหรอเนี่ย 😅

ตัวโจทย์นั้น แม้จะทำความเข้าใจกฎเกณฑ์ได้ไม่ยาก แต่หากลองคิดแก้ปัญหาดูแล้วคงมึนหัวไม่น้อย อาจถึงขั้นพาลคิดว่าโจทย์นี้ตั้งมามั่วๆ จนไม่มีคำตอบหรือเปล่า? เชื่อเถอะว่าคำตอบนั้นมีแน่ แค่ต้องจับจุดเริ่มต้นของมันให้เจอ แล้วที่เหลือจะง่ายเหมือนล้มโดมิโน่เอง

งั้นเราควรเริ่มตรงไหน?

อย่างน้อยๆ เราก็รู้ว่า $f$ เป็นฟังก์ชันบน $\mathbb{N}$ เราจึงไม่ต้องกังวลกับกรณีที่ค่าเป็นลบหรือศูนย์ ดังนั้นให้ $f(1)$ เป็นจุดเริ่มต้นที่เราจะแก้สมการนี้ เราอาจว่าทดคำตอบที่เป็นไปได้คือ $f(1) \in \lbrace1,2,3,\dots\rbrace$

แต่เนื่องจาก $f$ เป็นฟังก์ชันเพิ่ม และ $f(f(1))=3$ ดังนั้นเราจะได้ว่า $f(1)\lt3$ เท่านั้น เพราะถ้าสมมติให้ $f(1)=x$ โดย $x\ge3$ แล้ว จะเกิดข้อขัดแย้งว่า $f(1)=x\ge3=f(x)$ ซึ่งก็คือมันไม่ใช่ฟังก์ชันเพิ่มแล้ว

ตอนนี้จะเหลือความเป็นไปได้แค่ $\lbrace1,2\rbrace$ พิจารณากรณีที่ $f(1)=1$ (ฟังก์ชันเอกลักษณ์) จะได้ว่า $f(f(1))=1$ แต่จากกฎข้างต้นของโจทย์ที่บอกว่า $f(f(1))=3$ จึงทำให้เกิดเป็นข้อขัดแย้งอีกเช่นกัน

เมื่อเราตัดสิ่งที่เป็นไปไม่ได้ทั้งหมดทิ้งไป สิ่งที่เหลืออยู่ไม่ว่ามันจะดูน่าเหลือเชื่อแค่ไหน ก็จะต้องเป็นความจริงอย่างแน่แท้ ซึ่งก็คือ $f(1)=2$ เพียงเท่านั้น

และด้วยความรู้ข้างต้น จะทำให้เราได้ $f(2)=3$ ออกมาในทันที และเมื่อไล่ตามขบวนความคิดนี้ต่อไปอีกหนึ่งครั้ง ก็จะได้ $f(3)=f(f(2))=6$ เช่นกัน

อย่างไรก็ตาม เราจะพบทางตันเพราะไม่สามารถไล่ต่อเพื่อหา $f(4)$ กับ $f(5)$ ได้ เราจะหาทางแก้ขัดยังไงดี?

วิธีหนึ่งที่ทำได้ คือ เราจะกระโดดมาคำนวณ $f(6)=f(f(3))=9$ แทน ซึ่งเมื่อมองย้อนกลับไปจะเห็นว่า ช่องว่างของตัวเลขที่ยังไม่ได้หาค่าระหว่าง $f(3)=6$ และ $f(6)=9$ สามารถใส่ $7$ กับ $8$ ได้แค่สองตัวพอดี ซึ่งก็เท่ากับการที่เรามี $f(4)$ และ $f(5)$ เหลืออยู่เพียงสองตัวเท่ากันด้วย ดังนั้นเราจึงสามารถอนุมานได้ว่า $f(4)=7$ และ $f(5)=8$ เพียงเท่านั้น

พอได้ข้อมูลใหม่เพิ่มเข้ามา ลองทำต่อไปอีกหน่อยจะเห็นว่า

\[\begin{align} f(7) &= f(f(4)) = 12 \\ f(8) &= f(f(5)) = 15 \\ f(9) &= f(f(6)) = 18 \end{align}\]

แล้วเราก็มาถึงทางตันอีกรอบ คราวนี้เราจะกระโดดไปทำ $f(18)=f(f(9))=27$ ซึ่งเราก็จะเห็นอีกว่า $18-9=f(18)-f(9)$ พอดีเช่นกัน ทำให้เราสรุปได้ว่า

\[\begin{align} f(10) &= 19 \\ f(11) &= 20 \\ &\;\;\vdots \\ f(17) &= 26 \\ \end{align}\]

คือความเป็นไปได้เพียงหนึ่งเดียวเท่านั้น

---

บทตั้ง 1: $f(3^k) = 2\cdot3^k$ และ $f(2\cdot3^k) = 3\cdot3^k$ สำหรับ $k \in \mathbb{N}_0$

พิสูจน์: โดยอุปนัย ให้ $P(k): f(3^k) = 2\cdot3^k$ และ $Q(k): f(2\cdot3^k) = 3\cdot3^k$ เห็นได้ไม่ยากว่า $P(0)$ และ $Q(0)$ จริง ต่อมาสมมติให้ทั้ง $P(k)$ และ $Q(k)$ เป็นจริงพร้อมกัน ดังนั้นจะได้

• $f(f(3^k)) = f(2\cdot3^k) = 3^{k+1}$ ซึ่งก็คือ $P(k+1)$ จริงด้วย
• $f(f(2\cdot3^k)) = f(3^{k+1}) = 2\cdot3^{k+1}$ ซึ่งก็คือ $Q(k+1)$ จริงด้วยเช่นกัน $\quad\blacksquare$

บทตั้ง 2: $f(3^k+i) = 2\cdot3^k + i$ สำหรับ $0 \le i \le 3^k$

พิสูจน์: จากบทตั้ง 1 เรามี $f(3^k) = 2\cdot3^k$ และ $f(2\cdot3^k) = 3\cdot3^k$ ดังนั้น $f(2\cdot3^k) - f(3^k) = 3^k$ แต่ $2\cdot3^k - 3^k = 3^k$ เช่นกัน เพราะฉะนั้นจึงมีเพียงวิธีเดียวที่จะจับคู่ทุกค่า $0 \le i \le 3^k$ โดยยังคงสมบัติว่า $f$ เป็นฟังก์ชันเพิ่มโดยแท้ ซึ่งก็คือ $f(3^k+i) = 2\cdot3^k+i \quad\blacksquare$

บทตั้ง 3: $f(2\cdot3^k+i) = 3^{k+1}+3i$ สำหรับ $0 \le i \le 3^k$

พิสูจน์: จากบทตั้ง 2 เรารู้ว่า $f(2\cdot3^k+i) = f(f(3^k+i))$ ดังนั้น $f(2\cdot3^k+i) = 3^{k+1}+3i \quad\blacksquare$

จึงสรุปได้ว่าหน้าตาของ $f(n)$ เป็นดังนี้

\[f(n) = \begin{cases} 2M(n) + R(n) & \text{if leftmost trit of $n$ is 1} \\ \frac32M(n) + 3R(n) & \text{otherwise} \end{cases}\]

โดยที่ $M(n)$ จะเก็บเฉพาะหลักที่มีค่ามากที่สุดแล้วปัดหลักอื่นเป็นศูนย์เมื่อเขียน $n$ ในเลขฐานสาม ในขณะที่ $R(n)$ จะเปลี่ยนไปปัดหลักที่มีค่ามากที่สุดทิ้งไปแทน ตัวอย่างเช่น $n=42=1120_3$ จะได้ว่า $M(42)=1000_3=27$ และ $R(42)=120_3=15$ ตามลำดับ

หรือถ้ายังมีแรง จัดรูปต่อไปอีกหน่อยก็จะได้

\[f(n) = \max\left( n + 3^\left\lfloor\log_3n\right\rfloor, 3(n-3^\left\lfloor\log_3n\right\rfloor) \right)\]