====== سوال ۱۹======
دنباله‌ي $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$ چند است؟

  - $۴n$
  - $۳n$
  - $۲n-۱$
  - $۲n$
  - $۴n-۱$


<راهنمایی>
از یک عدد حداکثر چه تعداد می‌توان در یک دنباله‌ی مطلوب داشت؟
</راهنمایی>

<راهنمایی>
در راستای راهنمایی پیشین، اگر عدد $a$ چهار بار در دنباله ظاهر شده باشد، می‌توانید نشان دهید دنباله مطلوب نیست؟
</راهنمایی>

<راهنمایی>
حال سعی کنید مثالی ارائه دهید که هر عدد دقیقا سه بار ظاهر شده باشد.
</راهنمایی>


<راهنمایی>
اگر عدد $a$ در سه جایگاه متوالی دنباله ظاهر شود، دنباله‌ی نامطلوبی تشکیل خواهد شد؟
</راهنمایی>
<پاسخ>

گزینه‌ی ۲ درست است.


اگر در دنباله یک عدد چهار بار استفاده شود، همان چهار عدد ناقض شرط مسئله هستند (چرا؟).


پس طول دنباله حداکثر $3n$ خواهد بود. در صورتی که از هر عدد سه بار استفاده شود و تمام اعداد یکسان در کنار هم آمده باشند به راحتی دیده می‌شود که شرط مسئله در آن صدق می‌کند:


$$111222…nnn$$

</پاسخ>
  * [[سوال ۲۰|سوال بعد]]
  * [[سوال ۱۸|سوال قبل]]