7-ші халықаралық Жәутіков олимпиадасы, 2011 жыл

Бүтін $n$ саны берілген, $n > 1$. Егер $ab-b$ саны $n^2$-қа бөлінетіндей $M = \{1, 2, \ldots, n^2-1\}$ жиынының $b$ элементі табылса, $M$ жиынының $a$ элементі жақсы деп аталады. Ал, егер $a^2-a$ саны $n^2$-қа бөлінсе, $a$ элементі өте жақсы деп аталады. $M$ жиынының жақсы элементтерінің санын $g$ деп, ал осы жиынның өте жақсы элементтерінің санын $v$ деп белгілейік. Дәлелдеңдер: $v^2+ v \le g \le n^2- n$.

Комментарий/решение

Докажем, что $g\le n^2-n.$ Любое число вида $a=i\cdot n,$ для любого $i=1,\ldots,n-1,$ нехорошее$.$ Иначе $$n^2\mid ab-b=b(a-1)\implies n^2\mid b, \quad\text{так как}\quad (a-1,n^2)=1.$$

Но тогда $n^2\le b\le n^2-1,$ противоречие. В следствии, хороших чисел не более $(n^2-1)-(n-1)=n^2-n,$ или же $g\le n^2-n.\quad\square$

Примечание: $a$ $-$ хорошее, тогда и только тогда, когда $gcd(a-1,n^2)>1.$