مساله ۳۷. اعداد متمایز

امروز یک سوال از المپیاد ریاضی بالکان ۱۹۹۸ براتون داریم.

دنباله اعداد [k²/1998] به ازای k = 1, ..., 1997 رو در نظر بگیرین. تعداد اعداد متمایز در این دنباله چندتاست؟

(علامت [x] یعنی جزء صحیح x)

این سوال با برنامه‌نویسی کامپیوتری آسونه، ولی سعی کنید بدون استفاده از برنامه‌نویسی حلش کنید و یک روش ریاضی پیدا کنید.

لینک مساله در توویتر: https://twitter.com/Riazi_Cafe/status/1702560431720759369

پاسخ درست برابر با ۱۴۹۸ است.

اگر فاصله i² و ²(i-1) کمتر از ۱۹۹۸ باشد، آنگاه فاصله [i²/1998] و [1998/ ²(i-1)] صفر یا یک خواهد بود. پس به ازای k از ۱ تا i، هیچ جای خالی‌ای بین [k²/1998] های متوالی نخواهد بود و تمام صفر تا [i²/1998] جزو جواب خواهند بود.

فاصله‌ی i² و ²(i-1) برابر با 2i-1 است، پس این روند تا جایی ادامه دارد که 2i-1 < 1998. که نتیجه می‌دهد i ≤ 999. و این یعنی به ازای k از ۱ تا ۹۹۹، اعداد متمایز برابر خواهند بود با صفر تا [999²/1998] = 499 بدون فاصله، پس ۵۰۰ تا عدد متمایز اینجا بدست می‌آوریم.

از طرفی، وقتی i > 999 باشد، فاصله‌ی بین i² و ²(i-1) بزرگتر یا مساوی ۱۹۹۸ خواهد بود و به ازای هر [i²/1998] یک عدد متمایز جدید خواهیم داشت. پس 998=999-1997 تا عدد متمایز هم از اینجا خواهیم داشت.

پس در کل 998+500=1498 عدد متمایز خواهیم داشت.