دنبالهي $a_۱, a_۲...a_m$ از اعداد ۱ تا $n$ را خوب می نامیم اگر به ازای هر $i \lt j$ که $a_i = a_j$ هیچ یک از اعداد ظاهر شده در $a_{i+۱}, a_{i+۲}...a_{j-1}$ خارج از بازه $[a_i, a_{i+1}...a_j]$ ظاهر نشده باشند. در واقع در یک دنبالهي خوب ، اعداد ظاهر شده بین دو عدد مساوی نباید در خارج از بازه بینشان ظاهر شده باشند.
به عنوان مثال دنباله ۱,۲,۳,۱,۴,۱ یک دنباله ی خوب است ولی دنباله ی ۱,۲,۳,۱,۴,۲ خوب نیست، چون عدد ۲ هم بین دو تا ۱ ظاهر شده است و هم بیرون آنها. طول بزرگترین دنبالهی خوب با اعداد ۱ تا $n$ چند است؟
پاسخ
گزینهی ۲ درست است.
اگر در دنباله یک عدد چهار بار استفاده شود، همان چهار عدد ناقض شرط مسئله هستند (چرا؟).
پس طول دنباله حداکثر $3n$ خواهد بود. در صورتی که از هر عدد سه بار استفاده شود و تمام اعداد یکسان در کنار هم آمده باشند به راحتی دیده میشود که شرط مسئله در آن صدق میکند:
$$111222…nnn$$