[Thgx0312555]

ผมทำวิธีเดียวกันนิแหละ แต่ถ้าทำแบบนี้มันจะติดปัญหาตรงนี้

ข้อความเดิมเขียนโดยคุณ Pitchayut

วิธีผมเอง ไม่รู้มีใครทำแบบนี้ป่าว

ให้ $s_1,s_2,s_3,...,s_{ab+1}$

สมมติขัดแย้งว่า ทุกๆลำดับย่อยเพิ่มแท้ มีความยาวไม่เกิน $a$ และ ทุกๆลำดับย่อยลดแท้ มีความยาวไม่เกิน $b$

จะทาสีตัวเลขทุกตัว โดยให้ $f(n)$ แทนสีของ $s_n$ โดยทาสีตามขั้นตอนต่อไปนี้

1. ทาสี $s_1$ ด้วยสีที่ 1 จากนั้นหาตัวแรกที่น้อยกว่า $s_1$ ให้เป็นตัวที่ $t_{1,2}$)

2. ทำนองเดียวกัน หาตัวแรกที่น้อยกว่า $s_{t_{1,2}}$ ให้เป็นตัวที่ $t_{1,3}$ จากนั้นทำไปเรื่อยๆจนจบลำดับ

3. ทาสี $s_{t_{1,k}}$ ด้วยสีที่ 1 ทุกๆ $k$

4. ดำเนินการเช่นนี้ไปเรื่อยๆ โดยเริ่มจากตัวแรกที่ไม่ถูกทาสี และให้สีเป็น $2,3,4,...$ ไปเรื่อยๆ

สังเกตว่าจะมีช่องที่ทาสีที่ $i$ อยู่ไม่เกิน $b$ ช่อง (เพราะมิฉะนั้นจะเกิดลำดับลดความยาว $b+1$)

และมีสีไม่เกิน $a$ สี เพราะตัวแรกที่ทาสีที่ $i$ สำหรับ $i=1,2,3,...$ จะทำให้เกิดลำดับเพิ่ม

เพราะฉะนั้น จำนวนพจน์ต้องมีไม่เกิน $ab$ พจน์ ซึ่งเป็นข้อขัดแย้ง

จริงเหรอครับ

ปล. ข้อนี้มี alternate solution ที่สวยจริงๆ อยู่ในลิงค์ wiki ที่แปะลิงค์ไปแล้ว